1 #include<iostream>  2 #include<string>  3 #include <cstdlib>  4 #include<ctime>  5 #include <cmath>  6 using  std::string;  7   8 struct Position  9 { 10     string EID; 11     double x; 12     double y; 13     double z; 14  15 }; 16  17 double TSP(int n, struct Position* position,int T,int population_num,int top_num,int * sort) 18 { 19     //T;//迭代次数； 20     //population_num//种群个数 21     //top_num 选取前边多少个 22     int *population;//存放种群编码 23     int *p; 24     int getPerm(int *b, int n); 25     population=(int*)malloc(sizeof(int)*population_num*n);//一维数组存放 26     double *dis; 27     dis=(double*)malloc(sizeof(double)*n*n); 28     double *fitness; 29     fitness=(double*)malloc(sizeof(double)*population_num); 30  31     int *b; 32     b=(int*)malloc(sizeof(int)*population_num); 33  34  35     int *population1; 36     population1=(int*)malloc(sizeof(int)*population_num*n); 37  38     int* bb; 39     bb=(int*)malloc(sizeof(int)*n); 40  41     int* bbb; 42     bbb=(int*)malloc(sizeof(int)*n); 43  44     p=population; 45     //产生50个初始种群 46     srand(time(0)); 47     for(int i=0;i<population_num;i++) 48     { 49         getPerm(p,n); 50         p=p+n; 51     } 52     //以上生成了50个初始种群，放在population 53  54     //准备好距离矩阵 55  56     int getDis(struct Position* position,double *dis,int n); 57     getDis(position,dis,n); 58      59      60      61  62 for(int t=0;t<T;t++) 63 { 64     //a计算适应度 65     for(int i=0;i<population_num;i++) 66     { 67         fitness[i]=0; 68          69         for(int j=i*n;j<n+i*n-1;j++) 70         { 71             int ii=population[j]; 72             int jj=population[j+1]; 73  74             fitness[i]+=dis[ii*n+jj]; 75         } 76         int ii=population[i*n+n-1]; 77         int jj=population[i*n]; 78         fitness[i]+=dis[ii*n+jj]; 79     } 80  81      82     //b对适应度进行排序 83     int getIndex_double(double *a, int *b,int n); 84  85  86     getIndex_double(fitness, b,population_num); 87  88  89  90     //c选择比较好的个体，放入一个新的矩阵population1 91     for(int i=0;i<population_num;i++) 92     { 93         memcpy(&population1[b[i]*n],&population[i*n],4*n); 94     } 95  96  97  98  99 100     //选取比较好的top_num个体，进行交叉操作，放在从top_num+1开始的top_num/2个101     for(int i=top_num;i<population_num;i=i+2)102     {103         memcpy(&population1[i*n],&population1[(i-top_num)*n],n);104         memcpy(&population1[(i+1)*n],&population1[(i+1-top_num)*n],n);105 106         //选择交叉位置107         int pos=rand()%n;108         int tmp=population1[i*n+pos];109         population1[i*n+pos]=population1[(i+1)*n+pos];110         population1[(i+1)*n+pos]=tmp;111 112         //重新生成排列113         int getIndex(int *a, int *b,int n);114         getIndex(&population1[i*n],bb,n);115         memcpy(&population1[i*n],bb,4*n);116 117         getIndex(&population1[(i+1)*n],bb,n);118         memcpy(&population1[(i+1)*n],bb,4*n);119 120     }121 122 123     //变异操作124     //随机选取其中的以为进行变异125     int pos_population=rand()%population_num;126     int pos=rand()%n;127     int value=http://www.mamicode.com/rand()%n;128     population1[pos_population*n+pos]=value;129     int getIndex(int *a, int *b,int n);130 131     getIndex(&population1[pos_population*n],bbb,n);132     memcpy(&population1[pos_population*n],bbb,4*n);133 134 135 136     memcpy(population,population1,n*population_num*4);137 138 139 }140     //保存在population1中，适应度在fitness中，排序在b141     int i;142     for(i=0;i<population_num;i++)143     {144         if(b[i]==0)145             break;146     }147 148     memcpy(sort,&population[i*n],n*4);149     return fitness[i];150      151 }152 153 int getDis(struct Position* position,double *dis,int n)154 {155     for(int i=0;i<n;i++)156     {157         for(int j=0;j<n;j++)158         {159             dis[i*n+j]=sqrt((position[i].x-position[j].x)*(position[i].x-position[j].x)+160                 (position[i].y-position[j].y)*(position[i].y-position[j].y)+161                 (position[i].z-position[j].z)*(position[i].z-position[j].z));162             163         }164     }165     return 0;166 }167 168 int getPerm(int *b, int n)169 {170     //得到一个随机排列171     int getIndex(int *a, int *b,int n); 172     int* a;173     a=(int*)malloc(sizeof(int)*n);174     for(int i=0;i<n;i++)175         a[i]=rand()%n;176     getIndex(a, b,n);177 178     return 0;179 }180 181 //产生排列182 int getIndex(int *a, int *b,int n)183 {184     for(int i=0;i<n;i++)185     {186         b[i]=0;187     }188     for(int i=0;i<n-1;i++)189     {190         for(int j=i+1;j<n;j++)191         {192             if(a[i]>=a[j])193                 b[i]++;194             else195                 b[j]++;196         }197     }198     return 0;199 }200 201 int getIndex_double(double *a, int *b,int n)202 {203     for(int i=0;i<n;i++)204     {205         b[i]=0;206     }207     for(int i=0;i<n-1;i++)208     {209         for(int j=i+1;j<n;j++)210         {211             if((a[i]-a[j])>=0.0001)212                 b[i]++;213             else214                 b[j]++;215         }216     }217     return 0;218 }

 1 #include"tsp.h"; 2  3 int main() 4 { 5     int n=6,i; 6     struct Position* person; 7     struct Position* p; 8     int *sort; 9     sort=(int*)malloc(sizeof(int)*n);10     person=(struct Position*)malloc(sizeof(Position)*n);11     p=person;12 13     p->x=0;p->y=0;p->z=0;p=p+1;14     p->x=2;p->y=0;p->z=0;p=p+1;15     p->x=3;p->y=1;p->z=0;p=p+1;16     p->x=2;p->y=2;p->z=0;p=p+1;17     p->x=0;p->y=2;p->z=0;p=p+1;18     p->x=0;p->y=1;p->z=0;p=p+1;19 20     double dis=TSP(n, person,10,20,10,sort);21 22     printf("%.1f\n顺序为：",dis);23 24     for(int i=0;i<n;i++)25     {26         printf("%d ",sort[i]);27     }28     printf("\n");29 30     system("pause"); 31     return 0;32 }