pso-tsp.c

本程序是针对多序列比对问题

{
struct particle bestt;
float			coeff;
float			dmin, dmax;
float			dist[Nmax];
int				i,j;
int				rank_dmin[Nmax];
float			kx;
float			weight1;

kx=k;

        bestt=previous_best(p,0);

        for (i=1;i<kx/2;i++)
                {
                j=p.rank+i;
                if (j>sw1.size-1) {j=j-sw1.size;};

                if(sw1.p[j].best_f<bestt.f)
                        {
                        bestt=previous_best(sw1.p[j],0);
                        }
                }
        for (i=1;i<kx/2;i++)
                {
                j=p.rank-i;
                if (j<0) {j=sw1.size+j;};

                if(sw1.p[j].f<bestt.f)
                        {
                        bestt=previous_best(sw1.p[j],0);
                        }
                }
return bestt;

}

struct velocity	coeff_pos_minus_pos(struct particle p1,struct particle p2,float coeff)
{

int 			i,j,k,n1,nt;
int				GN;
struct particle pt;
struct velocity vt;
float			d0,d;

if (p1.rank>=0 && (p1.rank==p2.rank)) {vt.size=0; return vt;};
vt.size=0;
pt=p2;
GN=p2.x.size;

if (pt.x.s[0]!=0) pt.x=rotate(pt.x,0);
if (p1.x.s[0]!=0)
        {
        printf("\n 出错，路线不是从第 1 个城市开始",p1.rank);
        return vt;
        }

for (i=1;i<GN-1;i++)
        {
        nt=pt.x.s[i];
        n1=p1.x.s[i];
        for (j=i;j<GN;j++)
                        {
                        if (p1.x.s[j]==nt)
                                {
                                if (j!=i)
                                        {
                                        pt.x.s[i]=n1;
                                        vt.comp[vt.size][0]=n1;

                                        for (k=i+1;k<GN;k++)
                                                {
                                                if (pt.x.s[k]==n1)
                                                        {
                                                        pt.x.s[k]=nt;
                                                        vt.comp[vt.size][1]=nt;
                                                        vt.size=vt.size+1;

                                                        if (vt.size>Vmax)
                                                                goto stop;

                                                        goto next_node;

                                                        }
                                                }

                                        return vt;
                                        }
                                }
                        }
        next_node:;
        }

vt=coeff_times_vel(vt,coeff);
        return vt;
stop:

printf("\n 点数太多");
return vt;

}

struct velocity	coeff_times_vel(struct velocity v,float coeff)
{
float			coefft;
int				i;
struct velocity vt,vt0;


if (v.size==0) return v;


vt=v;
if (coeff==0) {vt.size=0;return vt;};

coefft=coeff;

if (coeff<0)
        {
         for (i=0;i<v.size;i++)
                {
                vt.comp[i][0]=v.comp[v.size-i-1][0];
                vt.comp[i][1]=v.comp[v.size-i-1][1];
                coefft=-coeff;
                }

        }

 if (coefft==1)
                return v;

if (coefft<1)
        {
         vt.size=coefft*v.size;
        return vt;
        }

vt0=vt;
for (i=0;i<coefft;i++)
        {
        vt=vel_plus_vel(vt,vt0);
        }

vt.size=MIN(coefft*v.size,Vmax);
return vt;
}

int	compare_particle(struct particle p1,struct particle p2)
{
int	i;
int GN;
GN=p1.x.size;

for (i=0;i<GN;i++)
        {
        if (p1.x.s[i]!=p2.x.s[i]) return 1;
        }

if (p1.v.size!=p2.v.size) return 1;

for (i=0;i<p1.v.size;i++)
        {
        if (p1.v.comp[i][0] != p2.v.comp[i][0]) return 1;
        if (p1.v.comp[i][1] != p2.v.comp[i][1]) return 1;
        }

return 0;

}

void	search(struct graph G, struct particle p1, struct particle p2)
{
float			f_l;
int				i,j;
float			min1;
struct particle pt;
struct velocity vt;

if (p2.f<p1.f) return ;

vt.size=1;
min1=p2.f;


for (i=0;i<G.N-1;i++)
        {
        for (j=i+1;j<G.N;j++)
                {
                vt.comp[0][0]=i;
                vt.comp[0][1]=j;
                pt=pos_plus_vel(p2,vt,0);
                if (pt.f<min1)
                        min1=pt.f;

                }
        }

return ;
}

struct particle	move_towards(struct particle p,struct particle pg,int move_type)
{
struct particle pi;
struct particle pit,pgt;
struct particle	pt;

float			d1,d2;
float			alpha, beta, gamma, delta, eta;
float			phi;
int				tot_vel;
struct velocity	v1,v2,v3;

tot_vel=0;

pi=previous_best(p,0);

pt.rank=p.rank;
explicit_velocities:
v1=coeff_times_vel(p.v,parameter1);

if (pi.f<pg.f) pit=pi; else pit=pg;
v3=coeff_pos_minus_pos(pit,p,parameter2);
v2=vel_plus_vel(v1,v3);
        pt=pos_plus_vel(p,v2,1);
        pt.v=v2;
        tot_vel=tot_vel+v2.size;
        goto end;

end:
if (pt.x.s[0]!=0) pt.x=rotate(pt.x,0);

if (pt.f<p.best_f)
        {
        pt.best_x=pt.x;
        pt.best_f=pt.f;
        }
else
        {
        pt.best_x=p.best_x;
        pt.best_f=p.best_f;
        }

 pt.rank=p.rank;

return pt;
}

struct particle	pos_plus_vel (struct particle p,struct velocity v, int type)
{
float			ft[Vmax+1];
int				i,i1;
int				last_trans;
int				n1,n2;
struct particle	pt,ptemp;
int				rank1,rank2;

struct velocity	vtemp;

if (v.size==0) return p;

ptemp=p;
if (type>=0)
        {
        ft[0]=p.f;
        }

for (i=0;i<v.size;i++)
        {
        n1=v.comp[i][0];
        n2=v.comp[i][1];
        for (i1=0;i1<G.N+1;i1++)
                {
                if (ptemp.x.s[i1]==n1)
                        {
                        rank1=i1;
                        if (rank1==G.N) rank1=0;
                        ptemp.x.s[i1]=n2;
                        }
                else
                        {
                        if (ptemp.x.s[i1]==n2)
                                {
                                rank2=i1;
                                if (rank2==G.N) rank2=0;
                                ptemp.x.s[i1]=n1;
                                }
                        }
                }


                if (type>0)
                        {
                        ptemp.f=f(ptemp,rank1,rank2);

                        if (ptemp.f<ptemp.best_f)
                                {
                                ptemp.best_x=ptemp.x;
                                ptemp.best_f=ptemp.f;
                                }
                        if(ptemp.f<extra_best.f)
                                {
                                extra_best=ptemp;
                                }
                        }

        }

        if (type==0)
                {
                ptemp.f=f(ptemp,-1,-1);
               if ( ptemp.f<ptemp.best_f)
                        {
                        ptemp.best_x=ptemp.x;
                        ptemp.best_f=ptemp.f;
                        }
                if(ptemp.f<extra_best.f)
                        {
                        extra_best=ptemp;
                        }
                }
        pt=ptemp;
        goto end;
end:
if (pt.x.s[0]!=0) pt.x=rotate(pt.x,0);
if (extra_best.x.s[0]!=0) extra_best.x=rotate(extra_best.x,0);
return pt;


}


struct particle previous_best(struct particle p, int type)
{
struct particle pt;

if (type==0)
pt=p;
pt.x=p.best_x;
pt.f=p.best_f;
if (pt.x.s[0]!=0) pt.x=rotate(pt.x,0);
return pt;



pt=p;
pt.best_x=p.x;
pt.best_f=p.f;
return pt;

}

float tax_no_arc(int l,struct graph G)
        {
        float 	tax=1.1; /* >=1 */
        float 	x;
       x=tax*G.l_max+(G.N-1)*(G.l_max-G.l_min);
        return x;
        }

struct velocity	vel_plus_vel(struct velocity v1,struct velocity v2)
{
int				i;
struct velocity vt;

vt=v1;

vt.size=MIN(v1.size+v2.size,Vmax);

for (i=v1.size;i<vt.size;i++)
        {
        vt.comp[i][0]=v2.comp[i-v1.size][0];
        vt.comp[i][1]=v2.comp[i-v1.size][1];
        }

return vt;
}


int alea(int min,int max)
{
int ir;
float r;

srand(seed);

r=rand();
seed=r;

r=r/RAND_MAX; /* Normally, RAND_MAX = 32767 = 2^31-1 */
r=0.5+min+r*(max-min);
ir=r;
return ir;
}


int alea_diff(int min,int max, int num)
{
int	temp1,temp2;

if (num==min)
        {
        temp1=alea(min+1,max);
        return temp1;
        }

if (num==max)
        {
        temp1=alea(min,max-1);
        return temp1;
        }

temp1=alea(min,num-1);
temp2=alea(num+1,max);

if (alea(0,100)<50)
        {
        return temp1;
        }
else
        {
        return temp2;
        }
}

float MAX(float a,float b)
{
if (a>b) return a; return b;
}


float MIN(float a,float b)
{
if (a<b) return a; return b;
}

struct seq rotate(struct seq s,int k)
{
int i,j;
struct seq st;

if (s.s[0]==k) return s;

for (i=0;i<s.size;i++)
        {
        if (s.s[i]!=k) continue;
                for (j=i;j<s.size;j++)
                        st.s[j-i]=s.s[j];

                for (j=0;j<i;j++)
                        st.s[j+s.size-i]=s.s[j];
        }
st.s[s.size]=st.s[0];
st.size=s.size;
return st;
}

void display_solution(struct particle p)
{

if (p.rank<0)
        {
        printf("\n Extra particle");
        }

display_position(p,1);

}

float f(struct particle p,int rank1,int rank2)
{
float				d;
float				delta_f;
float 				ft;
int 				i;
int					n,n0,n1,n2,ni;
int					no_arc;
float				val1,val2;

no_arc=0;

if (rank1>=0) goto modif;

ft=0;
for (i=0;i<G.N;i++)
        {
        n=p.x.s[i];
        n0=p.x.s[i+1];

if (n0>G.N || n>G.N)
        {
        printf("\nERROR arc %i=>%i",n+1,n0+1);
        printf(" value %f",G.v[n][n0]);
        }
        if (G.v[n][n0]<0)
                {
                delta_f=tax_no_arc(no_arc,G);
                no_arc=no_arc+1;
                }
        else
                {
                delta_f=G.v[n][n0];
                }
        ft=ft+delta_f;

        }
goto end;


modif:
n1=p.x.s[rank1];
n2=p.x.s[rank2];
ft=p.f;

if (rank1==0) i=G.N-1; else i=rank1-1;
ni=p.x.s[i];

if (G.v[ni][n1]<0) val1=tax_no_arc(no_arc,G); else val1=G.v[ni][n1];
if (G.v[ni][n2]<0) val2=tax_no_arc(no_arc,G); else val2=G.v[ni][n2];

ft=ft-val2+val1;


if (rank1==G.N-1) i=0; else i=rank1+1;
ni=p.x.s[i];

if (G.v[n1][ni]<0) val1=tax_no_arc(no_arc,G); else val1=G.v[n1][ni];
if (G.v[n2][ni]<0) val2=tax_no_arc(no_arc,G); else val2=G.v[n2][ni];

ft=ft-val2+val1;

if (rank2==0) i=G.N-1; else i=rank2-1;
ni=p.x.s[i];

        if (G.v[ni][n1]<0) val1=tax_no_arc(no_arc,G); else val1=G.v[ni][n1];
        if (G.v[ni][n2]<0) val2=tax_no_arc(no_arc,G); else val2=G.v[ni][n2];
        ft=ft-val1+val2;


if (rank2==G.N-1) i=0; else i=rank2+1;
ni=p.x.s[i];

        if (G.v[n1][ni]<0) val1=tax_no_arc(no_arc,G); else val1=G.v[n1][ni];
        if (G.v[n2][ni]<0) val2=tax_no_arc(no_arc,G); else val2=G.v[n2][ni];
        ft=ft-val1+val2;

if (abs(rank1-rank2)==1 || abs(rank1-rank2)==G.N-1) // Particular cases n1=>n2 or n2=>n1
        {
        if (G.v[n1][n2]<0) val1=tax_no_arc(no_arc,G); else val1=G.v[n1][n2];
        if (G.v[n2][n1]<0) val2=tax_no_arc(no_arc,G); else val2=G.v[n2][n1];
        ft=ft-val1-val2;
        }
end:

if (ft<extra_best.f)
        {
        extra_best=p;
        extra_best.f=ft;
        if (extra_best.x.s[0]!=0) extra_best.x=rotate(extra_best.x,0);
        }

return ft;

}


void display_position(struct particle p,int type)
{
int 	i;
float 	x;

printf("\n particle %i: ",p.rank+1);

for (i=0;i<p.x.size+1;i++)
        printf(" %i",p.x.s[i]+1);
}