//该程序用来解决TSP问题
//其中城市从0开始标号
//TOTAL_POPULATION、TOTAL_CHILDREN、TOTAL_BEST、TOTAL_GENERATION都需要是偶数
#include<stdlib.h>
#include<time.h>
#include<stdio.h>
#include<float.h>
#include<algorithm>
#define N 10 //N是城市数
#define TOTAL_POPULATION 80 //遗传算法中总个体数
#define TOTAL_CHILDREN 70 //用轮盘赌算法得出的子代数
#define TOTAL_BEST 10 //用最优选择法得出的子代数
#define TOTAL_GENERATION 80 //总代数
#define VARIATION_RATE 0.6 //变异率
#define TOLERANCE 0.6 //容忍系数
#define V 50 //不可行路的距离
//如果构造出的个体中的可行路的比例小于TOLERANCE，则重新构造，不可行路的距离设为V，结点到自身的距离设为0
//V不一定是很大的数，V只是作为一种惩罚系数而存在，即不可行路的距离要比可行路的距离长很多
double dist[N][N]=
{
{0,1,2,3,4,5,6,7,8,9},
{1,0,3,1,1,1,1,1,1,1},
{2,3,0,1,1,7,1,1,1,5},
{3,1,1,0,1,V,1,1,1,6},
{4,1,1,1,0,1,1,1,1,1},
{5,1,7,V,1,0,1,1,1,1},
{6,1,1,1,1,1,0,1,1,1},
{7,1,1,1,1,1,1,0,V,1},
{8,1,1,1,1,1,1,V,0,1},
{9,1,5,6,1,1,1,1,1,0},
};
int population[TOTAL_POPULATION][N]; //存放个体的信息
int child_unselect[TOTAL_POPULATION][N]; //存放杂交后未经选择的个体的信息
int child_selected[TOTAL_CHILDREN][N]; //存放轮盘赌算法选择出的个体信息
int BEST[TOTAL_BEST][N]; //存放最优选择法选择出的个体信息
inline double array_sum(double *array,int begin,int end) //计算一个数组里所有元素的和
{
int i;
double result=0;
for(i=begin;i<=end;i++)
result+=array[i];
return result;
}
inline bool check_tolerance(int *array) //检查容忍系数是否在给定范围内
{
int i;
double tol=0;
for(i=0;i<N-1;i++)
{
if(dist[array[i]][array[i+1]]!=V)
tol+=1.0000/N;
}
if(dist[array[0]][array[N-1]]!=V)
tol+=1.0000/N;
if(tol>=TOLERANCE)
return 1;
return 0;
}
inline void create() //创造函数
{
int i,j;
for(i=0;i<TOTAL_POPULATION;i++)
{
for(j=0;j<N;j++)
population[i][j]=j;
do{random_shuffle(population[i],population[i]+N);}
while(!(check_tolerance(population[i])));
}
}
inline void variation(int method) //变异函数
{
int i;
int rand1,rand2;
int variation_select[TOTAL_POPULATION];
for(i=0;i<TOTAL_POPULATION;i++)
variation_select[i]=i;
random_shuffle(variation_select,variation_select+TOTAL_POPULATION);
if(method==1)
{
for(i=0;i<TOTAL_POPULATION*VARIATION_RATE;i++)
{
rand1=rand()%N;
rand2=rand()%N;
swap(population[variation_select[i]][rand1],population[variation_select[i]][rand2]);
}
}
else if(method==2)
{
for(i=0;i<TOTAL_POPULATION*VARIATION_RATE;i++)
{
rand1=rand()%N;
rand2=rand()%N;
reverse(population[variation_select[i]]+min(rand1,rand2),population[variation_select[i]]+max(rand1,rand2));
}
}
}
inline void crossover(int method) //杂交函数
{
int rand1,rand2;
int i,j,k;
int parent_select[TOTAL_POPULATION];
for(i=0;i<TOTAL_POPULATION;i++)
parent_select[i]=i;
random_shuffle(parent_select,parent_select+TOTAL_POPULATION);
if(method==1)
{
for(i=0;i<TOTAL_POPULATION;i+=2)
{
rand1=rand()%N;
rand2=rand()%N;
for(j=0;j<N;j++)
{
child_unselect[i][j]=population[parent_select[i]][j];
child_unselect[i+1][j]=population[parent_select[i+1]][j];
}
for(j=0;j<N;j++)
for(k=min(rand1,rand2);k<=max(rand1,rand2);k++)
{
if(child_unselect[i][j]==population[parent_select[i]][k])
child_unselect[i][j]=population[parent_select[i+1]][k];
else if(child_unselect[i][j]==population[parent_select[i+1]][k])
child_unselect[i][j]=population[parent_select[i]][k];
if(child_unselect[i+1][j]==population[parent_select[i]][k])
child_unselect[i+1][j]=population[parent_select[i+1]][k];
else if(child_unselect[i+1][j]==population[parent_select[i+1]][k])
child_unselect[i+1][j]=population[parent_select[i]][k];
}
if(!(check_tolerance(child_unselect[i])&&check_tolerance(child_unselect[i+1])))
i-=2;
}
}
}
inline double calculate_distance(int *array) //计算距离的函数
{
int i;
double result=0;
for(i=0;i<N;i++)
{
if(dist[array[i]][array[i+1]]!=V)
result+=dist[array[i]][array[i+1]];
else
result+=V;
}
if(dist[array[N-1]][array[0]]!=V)
result+=dist[array[N-1]][array[0]];
else
result+=V;
return result;
}
inline void select(int method,double sigma) //选择函数
{
int i,j,k;
double score[TOTAL_POPULATION];
double distance[TOTAL_POPULATION];
double min_distance=DBL_MAX,max_distance=0;
double score_rand,score_sum;
double score2[TOTAL_POPULATION];
if(method==1)
{
for(i=0;i<TOTAL_POPULATION;i++)
distance[i]=calculate_distance(population[i]);
min_distance=*(min_element(distance,distance+TOTAL_POPULATION));
max_distance=*(max_element(distance,distance+TOTAL_POPULATION));
for(i=0;i<TOTAL_POPULATION;i++)
score[i]=(max_distance-distance[i]+sigma)/(max_distance-min_distance+sigma);
score_sum=array_sum(score,0,TOTAL_POPULATION-1);
for(i=0;i<TOTAL_CHILDREN;i++) //轮盘赌选择法
{
score_rand=((double)rand()*score_sum)/(double)RAND_MAX;
for(j=0;j<TOTAL_POPULATION-1;j++)
if((array_sum(score,0,j)<=score_rand)&&(array_sum(score,0,j+1)>score_rand))
{
copy(child_unselect[j],child_unselect[j]+N,child_selected[i]);
break;
}
}
copy(score,score+TOTAL_POPULATION,score2);
sort(score2,score2+TOTAL_POPULATION);
k=0;
for(i=TOTAL_POPULATION-1;i>=TOTAL_POPULATION-TOTAL_BEST;i--) //最优选择法
for(j=0;j<TOTAL_POPULATION;j++)
if(score[j]==score2[i])
{
copy(child_unselect[j],child_unselect[j]+N,BEST[k]);
k++;
}
}
}
inline void from_children_to_parents() //当前的子代转化成父代
{
int i;
for(i=0;i<TOTAL_CHILDREN;i++)
copy(child_selected[i],child_selected[i]+N,population[i]);
for(i=TOTAL_CHILDREN;i<TOTAL_POPULATION;i++)
copy(BEST[i-TOTAL_CHILDREN],BEST[i-TOTAL_CHILDREN]+N,population[i]);
}
int main()
{
FILE *fp;
int i,j;
double result;
int result_index;
srand(unsigned(time(0)));
fp=fopen("temp.txt","w+");
create();
for(i=1;i<=TOTAL_GENERATION;i++)
{
variation(1);
crossover(1);
select(1,0.5);
from_children_to_parents();
}
for(i=0;i<TOTAL_POPULATION;i++)
{
fprintf(fp,"POPULATION %d:",i+1);
for(j=0;j<N;j++)
fprintf(fp,"%d ",population[i][j]);
fprintf(fp,"\n");
}
result=DBL_MAX;
result_index=0;
for(i=0;i<TOTAL_POPULATION;i++)
if(result>=calculate_distance(population[i]))
{
result=calculate_distance(population[i]);
result_index=i;
}
fprintf(fp,"\n\nSHORTEST PATH: %d\n\nSHORTEST DISTANCE: %lf\n",result_index+1,result);
fclose(fp);
return 0;
}
