遗传算法解决10城市TSP问题程序源代码 - 大数据人|大数据第一社区

#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
#include "math.h"
#include "time.h"
#define num_C 10 //城市个数
#define N 100 //群体规模为100
#define pc 0.9 //交叉概率为0.9
#define pm 0.1 //变异概率为10%
#define ps 0.6 //进行选择时保留的比例
#define genmax 200 //最大代数200
int RandomInteger(int low,int high);
void Initial_gen(struct unit group[N]);
void Sort(struct unit group[N]);
void Copy_unit(struct unit *p1,struct unit *p2);
int search_son(int son[num_C],int k);
void Cross(struct unit *p1,struct unit *p2);
void Varation(struct unit group[N],int i);
void Evolution(struct unit group[N]);
void Calculate_cost(struct unit *p);
void Print_optimum(struct unit group[N]);
/* 定义个体信息 */
typedef struct unit
{
int path[num_C]; //个体的路径信息
int cost; //个体代价值
};
struct unit group[N]; //种群变量group
int num_gen=0; //记录当前达到第几代
/***************************************************************************/
/* 城市间的距离信息： */
/* 北京天津武汉深圳长沙成都杭州西安拉萨南昌 */
/* (0) (1) (2) (3) (4) (5) (6) (7) (8) (9) */
/* 北京(0) 0 118 1272 2567 1653 2097 1425 1177 3947 1574 */
/* 天津(1) 118 0 1253 2511 1633 2077 1369 1157 3961 1518 */
/* 武汉(2) 1272 1253 0 1462 380 1490 821 856 3660 385 */
/* 深圳(3) 2567 2511 1462 0 922 2335 1562 2165 3995 933 */
/* 长沙(4) 1653 1633 380 922 0 1700 1041 1135 3870 456 */
/* 成都(5) 2097 2077 1490 2335 1700 0 2311 920 2170 1920 */
/* 杭州(6) 1425 1369 821 1562 1041 2311 0 1420 4290 626 */
/* 西安(7) 1177 1157 856 2165 1135 920 1420 0 2870 1290 */
/* 拉萨(8) 3947 3961 3660 3995 3870 2170 4290 2870 0 4090 */
/* 南昌(9) 1574 1518 385 993 456 1920 626 1290 4090 0 */
/***************************************************************************/
int Cost_table[10][10]={{0,118,1272,2567,1653,2097,1425,1177,3947,1574},
{118,0,1253,2511,1633,2077,1369,1157,3961,1518},
{1272,1253,0,1462,380,1490,821,856,3660,385},
{2567,2511,1462,0,922,2335,1562,2165,3995,933},
{1653,1633,380,922,0,1700,1041,1135,3870,456},
{2097,2077,1490,2335,1700,0,2311,920,2170,1920},
{1425,1369,821,1562,1041,2311,0,1420,4290,626},
{1177,1157,856,2165,1135,920,1420,0,2870,1290},
{3947,3961,3660,3995,3870,2170,4290,2870,0,4090},
{1574,1518,385,993,456,1920,626,1290,4090,0}};
int main()
{
srand((int)time(NULL)); //初始化随机数发生器
Initial_gen(group); //初始化种群
Evolution(group); //进化：选择、交叉、变异
getch();
return 0;
}
/* 初始化种群 */
void Initial_gen(struct unit group[N])
{
int i,j,k;
struct unit *p;
for(i=0;i<=N-1;i++) //初始化种群里的100个个体
{
p=&group[i]; //p指向种群的第i个个体
for(j=0;j<=num_C-1;j++) //生成10个城市间的一个随机路径
{
k=0;
if(j==0) p->path[j]=RandomInteger(0,num_C-1);
else
{
p->path[j]=RandomInteger(0,num_C-1);
while(k<j)
{
//与之前城市重复，重新生成一个城市
if(p->path[j]==p->path[k]){p->path[j]=RandomInteger(0,num_C-1); k=0; }
else k++;
}//end while
}
}//end 生成路径
Calculate_cost(p); //计算该路径的代价值
}//end 初始化种群
}
/* 种群进化，进化代数由genmax决定 */
void Evolution(struct unit group[N])
{
int i,j;
int temp1,temp2,temp3,temp4,temp5;
temp1=N*pc/2;
temp2=N*(1-pc);
temp3=N*(1-pc/2);
temp4=N*(1-ps);
temp5=N*ps;
for(i=1;i<=genmax;i++)
{
//选择
Sort(group);
Print_optimum(group,i-1); //输出当代(第i-1代)种群
for(j=0;j<=temp4-1;j++)
{ Copy_unit(&group[j],&group[j+temp5]); }
//交叉
for(j=0;j<=temp1-1;)
{
Cross(&group[temp2+j],&group[temp3+j]);
j+=2;
}
//变异
Varation(group,i);
}
Sort(group);
Print_optimum(group,i-1); //输出当代(第i-1代)种群
}
/* 交叉 */
void Cross(struct unit *p1,struct unit *p2)
{
int i,j,cross_point;
int son1[num_C],son2[num_C];
for(i=0;i<=num_C-1;i++) //初始化son1、son2
{
son1[i]=-1;
son2[i]=-1;
}
cross_point=RandomInteger(1,num_C-1); //交叉位随机生成
//交叉，生成子代
//子代1
//子代1前半部分直接从父代复制
for(i=0;i<=cross_point-1;i++) son1[i]=p1->path[i];
for(i=cross_point;i<=num_C-1;i++)
{
for(j=0;j<=num_C-1;j++) //补全p1
{
if(search_son(son1,p2->path[j])==1)
{ son1[i]=p2->path[j]; break; }
else ;
}
}//end 子代1
//子代2
//子代1后半部分直接从父代复制
for(i=cross_point;i<=num_C-1;i++) son2[i]=p2->path[i];
for(i=0;i<=cross_point-1;i++)
{
for(j=0;j<=num_C-1;j++) //补全p2
{
if(search_son(son2,p1->path[j])==1)
{ son2[i]=p1->path[j]; break; }
else ;
}
}//end 子代2
//end 交叉
for(i=0;i<=num_C-1;i++)
{
p1->path[i]=son1[i];
p2->path[i]=son2[i];
}
Calculate_cost(p1); //计算子代p1的代价
Calculate_cost(p2); //计算子代p2的代价
}
/* 变异 */
void Varation(struct unit group[N],int flag_v)
{
int flag,i,j,k,temp;
struct unit *p;
flag=RandomInteger(1,100);
//在进化后期，增大变异概率
if(flag<=(flag_v>100)?(5*100*pm):(100*pm))
{
i=RandomInteger(0,N-1); //确定发生变异的个体
j=RandomInteger(0,num_C-1); //确定发生变异的位
k=RandomInteger(0,num_C-1);
p=&group[i]; //变异
temp=p->path[j];
p->path[j]=p->path[k];
p->path[k]=temp;
Calculate_cost(p); //重新计算变异后路径的代价
}
}
/* 检查k是否在son[num_C]中已出现过 */
int search_son(int son[num_C],int k)
{
int i;
for(i=0;i<=num_C-1;i++)
{
if(son[i]==k) return -1;
else ;
}
return 1;
}
/* 将种群中个体按代价从小到大排序 */
void Sort(struct unit group[N])
{
int i,j;
struct unit temp,*p1,*p2;
for(j=1;j<=N-1;j++) //排序总共需进行N-1轮
{
for(i=1;i<=N-1;i++)
{
p1=&group[i-1];
p2=&group[i];
if(p1->cost>p2->cost) //代价值大的往后排
{
Copy_unit(p1,&temp);
Copy_unit(p2,p1);
Copy_unit(&temp,p2);
}//end if
}//end 一轮排序
}//end 排序
}
/* 计算某个路径的代价值 */
void Calculate_cost(struct unit *p)
{
int j;
p->cost=0;
for(j=1;j<=num_C-1;j++)
{ p->cost+=Cost_table[p->path[j-1]][p->path[j]]; }
p->cost+=Cost_table[p->path[num_C-1]][p->path[0]];
}
/* 复制种群中的p1到p2中 */
void Copy_unit(struct unit *p1,struct unit *p2)
{
int i;
for(i=0;i<=num_C-1;i++) p2->path[i]=p1->path[i];
p2->cost=p1->cost;
}
/* 生成一个介于两整型数之间的随机整数 */
int RandomInteger(int low,int high)
{
int k;
double d;
k=rand();
k=(k!=RAND_MAX)?k:(k-1); //RAND_MAX是VC中可表示的最大整型数
d=(double)k/((double)(RAND_MAX));
k=(int)(d*(high-low+1));
return (low+k);
}
/* 输出当代种群中的每个个体 */
void Print_optimum(struct unit group[N],int k)
{
int i,j;
struct unit *p;
printf("当前第 %d 代：\n",k);
for(i=0;i<=N-1;i++)
{
printf("第 %d 代，个体 %d ：",k,i);
p=&group[i];
for(j=0;j<=num_C-1;j++) printf("%d ",p->path[j]);
printf(" 代价值为：%d \n",p->cost);
}
}

复制代码