2022年遗传算法解决城市TSP问题程序源代码文 .pdf

《2022年遗传算法解决城市TSP问题程序源代码文 .pdf》由会员分享，可在线阅读，更多相关《2022年遗传算法解决城市TSP问题程序源代码文 .pdf（6页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、#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

2、groupN); void Sort(struct unit groupN); void Copy_unit(struct unit *p1,struct unit *p2); int search_son(int sonnum_C,int k); void Cross(struct unit *p1,struct unit *p2); void Varation(struct unit groupN,int i); void Evolution(struct unit groupN); void Calculate_cost(struct unit *p); void Print_optim

3、um(struct unit groupN); /* 定义个体信息*/ typedef struct unit int pathnum_C; / 个体的路径信息int cost; /个体代价值; struct unit groupN; / 种群变量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 157

4、4 */ /* 天津 (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 */ /* 杭州

5、(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 */ /*/ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - -

6、- - - - 第 1 页，共 6 页 - - - - - - - - - int Cost_table1010=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

7、,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(grou

8、p); /进化：选择、交叉、变异getch(); return 0; /* 初始化种群*/ void Initial_gen(struct unit groupN) int i,j,k; struct unit *p; for(i=0;i=N-1;i+) /初始化种群里的100 个个体 p=&groupi; /p指向种群的第i 个个体for(j=0;jpathj=RandomInteger(0,num_C-1); else p-pathj=RandomInteger(0,num_C-1); while(kpathj=p-pathk)p-pathj=RandomInteger(0,num_C-1

9、); k=0; else k+; /end while /end 生成路径Calculate_cost(p); / 计算该路径的代价值/end 初始化种群名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - /* 种群进化，进化代数由genmax 决定*/ void Evolution(struct unit groupN) int i,j; int temp1,temp2,temp3,temp4,temp5; temp1=N*pc/

10、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(&groupj,&groupj+temp5); /交叉for(j=0;j=temp1-1;) Cross(&grouptemp2+j,&grouptemp3+j); j+=2; /变异Varation(group,i); Sort(group)

11、; Print_optimum(group,i-1); /输出当代 (第 i-1 代)种群 /* 交叉*/ void Cross(struct unit *p1,struct unit *p2) int i,j,cross_point; int son1num_C,son2num_C; for(i=0;i=num_C-1;i+) /初始化 son1、son2 son1i=-1; son2i=-1; cross_point=RandomInteger(1,num_C-1); / 交叉位随机生成/交叉，生成子代/子代 1 /子代 1前半部分直接从父代复制名师资料总结 - - -精品资料欢迎下载 -

12、 - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 6 页 - - - - - - - - - for(i=0;ipathi; for(i=cross_point;i=num_C-1;i+) for(j=0;jpathj)=1) son1i=p2-pathj; break; else ; /end 子代 1 /子代 2 /子代 1后半部分直接从父代复制for(i=cross_point;ipathi; for(i=0;i=cross_point-1;i+) for(j=0;jpathj)=1) son2i=p1-pat

13、hj; break; else ; /end 子代 2 /end 交叉for(i=0;ipathi=son1i; p2-pathi=son2i; Calculate_cost(p1); / 计算子代p1 的代价Calculate_cost(p2); / 计算子代p2 的代价 /* 变异*/ void Varation(struct unit groupN,int flag_v) int flag,i,j,k,temp; struct unit *p; flag=RandomInteger(1,100); /在进化后期，增大变异概率if(flag100)?(5*100*pm):(100*pm)

14、i=RandomInteger(0,N-1); /确定发生变异的个体j=RandomInteger(0,num_C-1); /确定发生变异的位k=RandomInteger(0,num_C-1); p=&groupi; /变异名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - temp=p-pathj; p-pathj=p-pathk; p-pathk=temp; Calculate_cost(p); /重新计算变异后路径的代价 /

15、* 检查 k 是否在 sonnum_C 中已出现过*/ int search_son(int sonnum_C,int k) int i; for(i=0;i=num_C-1;i+) if(soni=k) return -1; else ; return 1; /* 将种群中个体按代价从小到大排序*/ void Sort(struct unit groupN) int i,j; struct unit temp,*p1,*p2; for(j=1;j=N-1;j+) /排序总共需进行N-1 轮 for(i=1;icostp2-cost) / 代价值大的往后排 Copy_unit(p1,&temp

16、); 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;jcost+=Cost_tablep-pathj-1p-pathj; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - p-cost+=Cost_

17、tablep-pathnum_C-1p-path0; /* 复制种群中的p1 到 p2 中 */ void Copy_unit(struct unit *p1,struct unit *p2) int i; for(i=0;ipathi=p1-pathi; 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

18、)(RAND_MAX); k=(int)(d*(high-low+1); return (low+k); /* 输出当代种群中的每个个体*/ void Print_optimum(struct unit groupN,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=&groupi; for(j=0;jpathj); printf( 代价值为： %d n,p-cost); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -