pso-tsp.c

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

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define	Nmax 110 //最大的节点数
#define Vmax 110  //最大的速度交换子个数
#define Max_size 130  // swarm的最大个数
#define MaxEdge 150000  //最大的可能的边的大小

struct seq		{int size;int s[Nmax+1];};
struct val		{float v[MaxEdge];float min;};
struct velocity	{int size;int comp[Vmax][2];};
struct particle	{int rank;struct seq x;struct velocity v;float f;
                      float fl;struct seq best_x;float best_f;};
struct swarm		{int size; struct particle p[Max_size+1];int rank_best;};
struct graph 		{int N;float v[Nmax][Nmax];float l_max;float l_min;int n_edge;};

struct particle 	best_best; //swarm全局最优
struct particle 	extra_best;   //真正的最优
struct graph 		G;
int			hood; //neighbour的大小
struct particle 	init;  //初始的
int			iter,iter_min,iter_max;
int			same_best; //最优的值出现第几次
int			same_best_thresh;
float			same_best_val;
int			seed=1; //随机值的种子
struct swarm		sw1;
struct val		val;

FILE *f_trace;
FILE *f_graph; //读TSPLIB文件

struct graph 			graph_min_max(struct graph G);
struct val				graph_min_tour(struct graph G);
struct graph			read_graph(FILE *file);
struct particle 		init_particle(struct graph G);
struct swarm			init_swarm(int size, struct graph G);
int			        move_slow(struct swarm sw,int swarm_size,float slow,int hood);
struct swarm 			reduce_swarm(struct swarm sw);
struct swarm			new_swarm(struct swarm sw,int swarm_size);

struct velocity			alea_velocity(int N);
struct particle			auto_move(struct particle p);
struct particle			best_neighbour(struct swarm sw1,struct particle p,int k);
struct velocity			coeff_pos_minus_pos(struct particle p1,struct particle p2,float coeff);
struct velocity			coeff_times_vel(struct velocity v,float coeff);
int						compare_particle(struct particle p1,struct particle p2);

float					f(struct particle p,int rank1, int rank2);
void					search(struct graph G, struct particle p1, struct particle p2);
struct particle			move_towards(struct particle p1,struct particle p3,int move_type);
struct particle			pos_plus_vel(struct particle p,struct velocity v,int type);
struct particle 		previous_best(struct particle p,int type);
float					tax_no_arc(int times,struct graph G);
struct velocity			vel_plus_vel(struct velocity v1,struct velocity v2);

int				alea(int min,int max);
int				alea_diff(int min, int max, int num);
float 			MAX(float a,float b);
float 			MIN(float a,float b);
struct seq 		rotate(struct seq s,int k);
struct seq		seq(int k,int N);
float   parameter1,  parameter2;

void display_position(struct particle p,int type);
void display_solution(struct particle p);

/* =============================================================================== */
void main()
{
FILE *f_graph;

struct particle	best_hood;
int				choice;
int				density;
float			kappa;
int				i;
int				iter,iter_min,iter_max;
char			graph[256];
int				max_iter;
float			min_tour;
float			slow;
int				parallel;
float			phi;
struct particle	solution;
int				swarm_size;
float			target;
int				vmax;
float			x;
int				xi;

slow=0.5;
same_best_thresh=2;

f_trace=fopen("trace.txt","w");
G.l_max=10;G.l_min=1;

printf("\n输入TSPLIB文件名:\n");
scanf("%s",&graph);

f_graph=fopen(graph,"r");
G=read_graph(f_graph);

G=graph_min_max(G);
val=graph_min_tour(G);
min_tour=val.min;

x=G.N; xi=x-1;
swarm_size=xi;
sw1.size=swarm_size;

printf("\n Neighbour 大小 ? (最大 = %i) ",sw1.size);
printf("\n : ");
scanf("%i",&hood);
hood=MAX(1,MIN(hood,sw1.size));

iter_min=0;
        sw1=init_swarm(swarm_size,G);
        if(sw1.size<swarm_size)
                {
                printf("\n 生成swarm时出错");
                goto error_end;
                }

iterations:

printf("\n 输入 迭代次数  ? (输入0结束)：  ");
scanf("%i",&max_iter);
if (max_iter==0) return;

printf("\n 输入 参数1 ? : ");
scanf("%f",&parameter1);

printf("\n 输入 参数2 ? :  ");
scanf("%f",&parameter2);

target=min_tour;

iter_max=iter_min+max_iter;

for (iter=iter_min;iter<iter_max;iter++)
        {

        printf("\n\n 第 %i 次迭代 , swarm 大小 %i, 可能的最小值 %f",iter,sw1.size,extra_best.f);
        if (best_best.f<=extra_best.f)
        display_solution(best_best);
        else
        display_solution(extra_best);

        if (extra_best.f<same_best_val)
                {
                same_best=0;
                same_best_val=extra_best.f;
                }
        else
                {
                same_best=same_best+1;
                }

        printf("\n 可能最小值 %f, 已出现 %i 次",same_best_val,same_best);

                 sw1=reduce_swarm(sw1);
                if (move_slow(sw1,swarm_size,slow,hood)==1)
                        {
                        sw1=new_swarm(sw1,swarm_size);
                        }

        for (i=0;i<sw1.size;i++)
                {
                best_hood=best_neighbour(sw1,sw1.p[i],hood);

                if (best_hood.f<best_best.f) best_best=best_hood;
                        sw1.p[i]=move_towards(sw1.p[i],best_hood,5);
                        if (sw1.p[i].f<best_best.f)
                                {
                                best_best=sw1.p[i];
                                }

                if (best_best.f<=G.l_min*G.N || extra_best.f<=G.l_min*G.N )
                        {
                        printf("\n\n Particle %i. 最小 ",i+1);
                        goto end;
                        }

                if (best_best.f<=target || extra_best.f<=target)
                        {
                        printf("\n 目标值: %f",target);
                        goto end;
                        }
                }
        if (best_best.f<=G.l_min*G.N || extra_best.f<=G.l_min*G.N )
                {
                printf("\n\n 找到最小 ");
                goto end;
                }
        }

end:

printf("\n 找到的最小值:");
if (best_best.f<=extra_best.f)
        {solution=best_best;}
else
        { solution=extra_best;}

display_solution(solution);

sw1.p[sw1.size]=extra_best;
sw1.size=sw1.size+1;

iter_min=iter_max;
goto iterations;

return;

error_end:
printf("\n 出错");

}

struct graph graph_min_max(struct graph G)
{
int 		i,j;
struct graph Gt;

Gt=G;
Gt.n_edge=0;
Gt.l_max=0;
Gt.l_min=1000000;

for (i=0;i<G.N;i++)
        {
        for (j=0;j<G.N;j++)
                {
                if (j!=i)
                        {
                        Gt.l_max=MAX(G.v[i][j],Gt.l_max);
                        if (G.v[i][j]>=0)
                                {
                                Gt.l_min=MIN(G.v[i][j],Gt.l_min);
                                Gt.n_edge=Gt.n_edge+1;
                                }
                        }
                }
        }
return Gt;
}

struct val graph_min_tour(struct graph G)
{
int 	i,j;
int		lmax;
int		n_diff_val;
int		nval;
int		rank;
float	x;
struct val val;

lmax=G.l_max;

if (G.l_max>MaxEdge)
        {
        printf("\n边值太大 ");
        }

for (i=0;i<MaxEdge;i++)
        val.v[i]=0;

for (i=0;i<G.N;i++)
        {
        for (j=0;j<G.N;j++)
                {
                if (i==j) continue;
                if(G.v[i][j]>=0)
                        rank=G.v[i][j]-G.l_min;
                else
                        rank=G.l_max+1-G.l_min;
                val.v[rank]=val.v[rank]+1;
                }
        }

val.min=0;
n_diff_val=0;
nval=0;

for (i=0;i<G.l_max-G.l_min+1;i++)
        if (val.v[i]>0)
                {
                n_diff_val=n_diff_val+1;
                }

for (i=0;i<G.l_max;i++)
        {
                for (j=0;j<val.v[i];j++)
                        {
                        val.min=val.min+(G.l_min+i);
                        nval=nval+1;
                        if (nval>=G.N) goto end;
                        }
        }

end:

x=G.N*(G.N-1);
for (i=0;i<G.l_max-G.l_min+2;i++)
        {
        if (val.v[i]>0)
                val.v[i]=val.v[i]/x;
        }

return val;
}

struct graph read_graph(FILE *file)
{
char			bidon[50];
char			comment[100];
char			edge_weight_format[30];
char			edge_weight_type[30];
struct graph	Gt;
int 			i,j;
char			name[20];
char			type[20];
int index=0,index1=0;
float  x[Nmax], y[Nmax];

fscanf(file," %s %s\n",bidon,name);
fscanf(file," %s %s\n",bidon,type);

  fscanf(file," %s %s\n",bidon,comment);
  fscanf(file,"%s %i\n",bidon,&Gt.N); // dimension
  fscanf(file,"%s %s\n",bidon,edge_weight_type);
  fscanf(file,"%s\n",bidon);


  printf("\n  %s,  %s, (%s)",name,type,comment);
  printf("\n 城市的个数: %i\n",Gt.N);


for (i=0;i<Gt.N;i++)
{
 fscanf(file,"%i %f %f\n",&index,&x[i],&y[i]);
 printf("%f %f\n",x[i],y[i]);
}

          for (i=0;i<Gt.N;i++)
                  {
                  for (j=0;j<Gt.N;j++)
                          {
                         if (i==j)      Gt.v[i][j]=0;
                           else{
                          Gt.v[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
                           }
                          }
                  }
          return Gt;

}


struct particle init_particle(struct graph G)
{
int i;
struct particle init;

init.rank=-1;

init.x.size=G.N;
for (i=0;i<G.N;i++)
        init.x.s[i]=i;
init.x.s[G.N]=0;

init.v.size=0;
init.f=f(init,-1,-1);
init.best_x=init.x;
init.best_f=init.f;
return init;
}

struct swarm	init_swarm(int size,struct graph G)
{
int 				i;
struct swarm 		swt;
float				x,x1;

swt.size=size;

init=init_particle(G);
swt.rank_best=0;

for (i=0;i<size;i++)
        {

        swt.p[i]=init;
        swt.p[i].rank=i;
        swt.p[i].best_x=swt.p[i].x;
        swt.p[i].best_f=swt.p[i].f;
        swt.p[i].v=alea_velocity(i+1);

        swt.p[i]=pos_plus_vel(swt.p[i],swt.p[i].v,0);

        if (swt.p[i].f<swt.p[swt.rank_best].f)
                swt.rank_best=i;
        }

best_best=swt.p[swt.rank_best];
extra_best=best_best;
same_best_val=extra_best.f;
same_best=0;

return swt;
}

int	move_slow(struct swarm sw,int swarm_size, float slow,int hood)
{
int		i;
float	slow_thresh2;
float	sensibility=8;
int		v_size_tot,v_tot,v_tot_min;


if (same_best>=same_best_thresh)
        {
        printf("\n 更新群");
        return 1;
        }

v_tot=0;
v_size_tot=0;
for (i=0;i<sw.size;i++)
        if (sw.p[i].v.size>0) {v_tot=v_tot+1;v_size_tot=v_size_tot+sw.p[i].v.size;}


if (v_tot==0)
        {
        printf("\n更新群");
        return 1;
        }

       v_tot_min=swarm_size*slow+1;
      slow_thresh2=swarm_size*slow;

if (sw.size<=slow_thresh2 && slow>0)
        {
        printf("\n更新群");
        return 1;
        }

if (v_tot<v_tot_min)
        {
        printf("\n 更新群");
         return 1;
        }

return 0;
}

struct swarm reduce_swarm(struct swarm sw)
{
struct swarm	diff;
int				i,j;

diff.size=1;
diff.p[0]=sw.p[0];

for (i=1;i<sw.size;i++)
        {
        for (j=0;j<diff.size;j++)
                {
                if (sw.p[i].f==diff.p[j].f)
                        {
                        if (compare_particle(sw.p[i],diff.p[j])==0)
                                goto next_check;
                        }
                }

        diff.p[diff.size]=sw.p[i];
        diff.p[diff.size].rank=diff.size;
        diff.size=diff.size+1;
        next_check:;
        }

return diff;
}

struct swarm new_swarm(struct swarm sw,int swarm_size)
{
struct particle	current_best;
int				i;
int				rank_best;
int				type;
struct swarm 	swt;


for (i=0;i<swarm_size;i++)
        {
        if (i>=sw.size)
                {
                swt.p[i]=init;
                swt.p[i].rank=i;
                }
        else
                {
                 swt.p[i]=previous_best(sw.p[i],0);
                }

        swt.p[i]=auto_move(swt.p[i]);
        swt.p[i].v=alea_velocity(G.N-2);


        if (swt.p[i].f<swt.p[i].best_f)
                {
                swt.p[i].best_f=swt.p[i].f;
                swt.p[i].best_x=swt.p[i].x;
                }

        if (swt.p[i].x.s[0]!=0) swt.p[i].x=rotate(swt.p[i].x,0);

        }

best_best=swt.p[0];
for (i=0;i<swarm_size;i++)
        {
        if (swt.p[i].f<best_best.f)
                        best_best=swt.p[i];
        }

swt.size=swarm_size;

rank_best=best_best.rank;

if (rank_best<0) rank_best=0;

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

swt.rank_best=rank_best;
best_best.v.size=0;
swt.p[swt.rank_best].v.size=0;

return swt;

}

struct velocity	alea_velocity(int N)
{
int				i;
struct velocity vt;
vt.size=N;

for (i=0;i<vt.size;i++)
        {
        vt.comp[i][0]=alea(0,G.N-1);
        vt.comp[i][1]=alea_diff(0,G.N-1,vt.comp[i][0]);
        }

return vt;
}

struct particle auto_move(struct particle p)
{
int 			i,j,k;
struct particle	pt,pt1;
struct velocity v;
float t;

pt=p;


        v.size=1;
        next_step2:
        for (j=0;j<G.N-1;j++)
                {
                v.comp[0][0]=j;
                for (k=j+1;k<G.N;k++)
                        {
                        v.comp[0][1]=k;
                        pt1=pos_plus_vel(pt,v,1);

                  search(G,pt,pt1);
                        }
                }
        return pt;

}

struct particle	best_neighbour(struct swarm sw1,struct particle p,int k)