大数据人|大数据第一社区

 找回密码
 注册会员

扫一扫,访问微社区

查看: 1886|回复: 0

遗传算法解决10城市TSP问题程序源代码

[复制链接]
  • TA的每日心情
    奋斗
    2015-7-30 23:05
  • 签到天数: 12 天

    [LV.3]偶尔看看II

    852

    主题

    972

    帖子

    4804

    积分

    管理员

    Rank: 9Rank: 9Rank: 9

    积分
    4804
    QQ
    发表于 2015-9-29 15:01:41 | 显示全部楼层 |阅读模式
    1. #include "stdio.h"
    2. #include "stdlib.h"
    3. #include "conio.h"
    4. #include "math.h"
    5. #include "time.h"
    6. #define num_C  10   //城市个数
    7. #define N      100  //群体规模为100
    8. #define pc     0.9  //交叉概率为0.9
    9. #define pm     0.1  //变异概率为10%
    10. #define ps     0.6  //进行选择时保留的比例
    11. #define genmax 200  //最大代数200
    12. int RandomInteger(int low,int high);
    13. void Initial_gen(struct unit group[N]);
    14. void Sort(struct unit group[N]);
    15. void Copy_unit(struct unit *p1,struct unit *p2);
    16. int search_son(int son[num_C],int k);
    17. void Cross(struct unit *p1,struct unit *p2);
    18. void Varation(struct unit group[N],int i);
    19. void Evolution(struct unit group[N]);
    20. void Calculate_cost(struct unit *p);
    21. void Print_optimum(struct unit group[N]);
    22. /* 定义个体信息 */
    23. typedef struct unit
    24. {
    25.   int path[num_C]; //个体的路径信息
    26.   int cost;        //个体代价值
    27. };
    28. struct unit group[N]; //种群变量group
    29. int num_gen=0;        //记录当前达到第几代
    30. /***************************************************************************/
    31. /* 城市间的距离信息:                                                      */
    32. /*           北京  天津  武汉  深圳  长沙  成都  杭州  西安  拉萨  南昌    */
    33. /*           (0)   (1)   (2)   (3)   (4)   (5)   (6)   (7)   (8)   (9)     */
    34. /*  北京(0)   0    118   1272  2567  1653  2097  1425  1177  3947  1574    */
    35. /*  天津(1)  118    0    1253  2511  1633  2077  1369  1157  3961  1518    */
    36. /*  武汉(2)  1272  1253   0    1462  380   1490  821   856   3660  385     */
    37. /*  深圳(3)  2567  2511  1462   0    922   2335  1562  2165  3995  933     */
    38. /*  长沙(4)  1653  1633  380   922    0    1700  1041  1135  3870  456     */
    39. /*  成都(5)  2097  2077  1490  2335  1700   0    2311  920   2170  1920    */
    40. /*  杭州(6)  1425  1369  821   1562  1041  2311   0    1420  4290  626     */
    41. /*  西安(7)  1177  1157  856   2165  1135  920   1420   0    2870  1290    */
    42. /*  拉萨(8)  3947  3961  3660  3995  3870  2170  4290  2870   0    4090    */
    43. /*  南昌(9)  1574  1518  385   993   456   1920  626   1290  4090   0      */
    44. /***************************************************************************/
    45. int Cost_table[10][10]={{0,118,1272,2567,1653,2097,1425,1177,3947,1574},
    46.                                                 {118,0,1253,2511,1633,2077,1369,1157,3961,1518},
    47.                                                 {1272,1253,0,1462,380,1490,821,856,3660,385},
    48.                                                 {2567,2511,1462,0,922,2335,1562,2165,3995,933},
    49.                                                 {1653,1633,380,922,0,1700,1041,1135,3870,456},
    50.                                                 {2097,2077,1490,2335,1700,0,2311,920,2170,1920},
    51.                                                 {1425,1369,821,1562,1041,2311,0,1420,4290,626},
    52.                                                 {1177,1157,856,2165,1135,920,1420,0,2870,1290},
    53.                                                 {3947,3961,3660,3995,3870,2170,4290,2870,0,4090},
    54.                                                 {1574,1518,385,993,456,1920,626,1290,4090,0}};

    55. int main()
    56. {
    57.   srand((int)time(NULL)); //初始化随机数发生器
    58.   Initial_gen(group);     //初始化种群
    59.   Evolution(group);       //进化:选择、交叉、变异
    60.   getch();
    61.   return 0;
    62. }
    63. /* 初始化种群 */
    64. void Initial_gen(struct unit group[N])
    65. {
    66.   int i,j,k;
    67.   struct unit *p;
    68.   for(i=0;i<=N-1;i++) //初始化种群里的100个个体
    69.         {
    70.           p=&group[i]; //p指向种群的第i个个体
    71.           for(j=0;j<=num_C-1;j++) //生成10个城市间的一个随机路径
    72.                 {
    73.                   k=0;
    74.                   if(j==0)  p->path[j]=RandomInteger(0,num_C-1);
    75.                   else
    76.                         {
    77.                           p->path[j]=RandomInteger(0,num_C-1);
    78.                           while(k<j)
    79.                                 {
    80.                                   //与之前城市重复,重新生成一个城市
    81.                                   if(p->path[j]==p->path[k]){p->path[j]=RandomInteger(0,num_C-1); k=0; }
    82.                                   else k++;
    83.                                 }//end while
    84.                         }
    85.                 }//end 生成路径
    86.           Calculate_cost(p); //计算该路径的代价值
    87.         }//end 初始化种群
    88. }
    89. /* 种群进化,进化代数由genmax决定 */
    90. void Evolution(struct unit group[N])
    91. {
    92.   int i,j;
    93.   int temp1,temp2,temp3,temp4,temp5;
    94.   temp1=N*pc/2;
    95.   temp2=N*(1-pc);
    96.   temp3=N*(1-pc/2);
    97.   temp4=N*(1-ps);
    98.   temp5=N*ps;
    99.   for(i=1;i<=genmax;i++)
    100.         {
    101.           //选择
    102.       Sort(group);
    103.           Print_optimum(group,i-1); //输出当代(第i-1代)种群
    104.       for(j=0;j<=temp4-1;j++)
    105.                 { Copy_unit(&group[j],&group[j+temp5]); }
    106.           //交叉
    107.           for(j=0;j<=temp1-1;)
    108.                 {
    109.                   Cross(&group[temp2+j],&group[temp3+j]);
    110.                   j+=2;
    111.                 }
    112.           //变异
    113.           Varation(group,i);
    114.         }
    115.   Sort(group);
    116.   Print_optimum(group,i-1); //输出当代(第i-1代)种群
    117. }
    118. /* 交叉 */
    119. void Cross(struct unit *p1,struct unit *p2)
    120. {
    121.   int i,j,cross_point;
    122.   int son1[num_C],son2[num_C];
    123.   for(i=0;i<=num_C-1;i++) //初始化son1、son2
    124.         {
    125.           son1[i]=-1;
    126.           son2[i]=-1;
    127.         }
    128.   cross_point=RandomInteger(1,num_C-1); //交叉位随机生成
    129.   //交叉,生成子代
    130.   //子代1
    131.   //子代1前半部分直接从父代复制
    132.   for(i=0;i<=cross_point-1;i++)  son1[i]=p1->path[i];
    133.   for(i=cross_point;i<=num_C-1;i++)
    134.         {
    135.           for(j=0;j<=num_C-1;j++) //补全p1
    136.                 {
    137.                   if(search_son(son1,p2->path[j])==1)
    138.                         { son1[i]=p2->path[j]; break; }
    139.                   else ;
    140.                 }
    141.         }//end 子代1
    142.   //子代2
    143.   //子代1后半部分直接从父代复制
    144.   for(i=cross_point;i<=num_C-1;i++)  son2[i]=p2->path[i];
    145.   for(i=0;i<=cross_point-1;i++)
    146.         {
    147.           for(j=0;j<=num_C-1;j++) //补全p2
    148.                 {
    149.                   if(search_son(son2,p1->path[j])==1)
    150.                         { son2[i]=p1->path[j]; break; }
    151.                   else ;
    152.                 }
    153.         }//end 子代2
    154.   //end 交叉
    155.   for(i=0;i<=num_C-1;i++)
    156.         {
    157.           p1->path[i]=son1[i];
    158.           p2->path[i]=son2[i];
    159.         }
    160.   Calculate_cost(p1); //计算子代p1的代价
    161.   Calculate_cost(p2); //计算子代p2的代价
    162. }
    163. /* 变异 */
    164. void Varation(struct unit group[N],int flag_v)
    165. {
    166.   int flag,i,j,k,temp;
    167.   struct unit *p;
    168.   flag=RandomInteger(1,100);
    169.   //在进化后期,增大变异概率
    170.   if(flag<=(flag_v>100)?(5*100*pm):(100*pm))
    171.         {
    172.           i=RandomInteger(0,N-1);      //确定发生变异的个体
    173.           j=RandomInteger(0,num_C-1);  //确定发生变异的位
    174.           k=RandomInteger(0,num_C-1);
    175.           p=&group[i];                 //变异
    176.           temp=p->path[j];
    177.           p->path[j]=p->path[k];
    178.           p->path[k]=temp;
    179.           Calculate_cost(p);           //重新计算变异后路径的代价
    180.         }
    181. }
    182. /* 检查k是否在son[num_C]中已出现过 */
    183. int search_son(int son[num_C],int k)
    184. {
    185.   int i;
    186.   for(i=0;i<=num_C-1;i++)
    187.         {
    188.           if(son[i]==k) return -1;
    189.           else ;
    190.         }
    191.   return 1;
    192. }
    193. /* 将种群中个体按代价从小到大排序 */
    194. void Sort(struct unit group[N])
    195. {
    196.   int i,j;
    197.   struct unit temp,*p1,*p2;
    198.   for(j=1;j<=N-1;j++) //排序总共需进行N-1轮
    199.         {
    200.           for(i=1;i<=N-1;i++)
    201.                 {
    202.                   p1=&group[i-1];
    203.                   p2=&group[i];
    204.                    if(p1->cost>p2->cost) //代价值大的往后排
    205.                         {
    206.                           Copy_unit(p1,&temp);
    207.                           Copy_unit(p2,p1);
    208.                           Copy_unit(&temp,p2);
    209.                         }//end if
    210.                 }//end 一轮排序
    211.         }//end 排序  
    212. }
    213. /* 计算某个路径的代价值 */
    214. void Calculate_cost(struct unit *p)
    215. {
    216.   int j;
    217.   p->cost=0;
    218.   for(j=1;j<=num_C-1;j++)
    219.         { p->cost+=Cost_table[p->path[j-1]][p->path[j]]; }
    220.   p->cost+=Cost_table[p->path[num_C-1]][p->path[0]];
    221. }
    222. /* 复制种群中的p1到p2中 */
    223. void Copy_unit(struct unit *p1,struct unit *p2)
    224. {
    225.   int i;
    226.   for(i=0;i<=num_C-1;i++)  p2->path[i]=p1->path[i];
    227.   p2->cost=p1->cost;
    228. }
    229. /* 生成一个介于两整型数之间的随机整数 */
    230. int RandomInteger(int low,int high)
    231. {
    232.   int k;
    233.   double d;
    234.   k=rand();
    235.   k=(k!=RAND_MAX)?k:(k-1); //RAND_MAX是VC中可表示的最大整型数
    236.   d=(double)k/((double)(RAND_MAX));
    237.   k=(int)(d*(high-low+1));
    238.   return (low+k);
    239. }
    240. /* 输出当代种群中的每个个体 */
    241. void Print_optimum(struct unit group[N],int k)
    242. {
    243.   int i,j;
    244.   struct unit *p;
    245.   printf("当前第 %d 代:\n",k);
    246.   for(i=0;i<=N-1;i++)
    247.         {
    248.           printf("第 %d 代,个体 %d :",k,i);
    249.           p=&group[i];
    250.           for(j=0;j<=num_C-1;j++)  printf("%d  ",p->path[j]);
    251.           printf("  代价值为:%d \n",p->cost);
    252.         }
    253. }
    复制代码


    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 注册会员

    本版积分规则

    关闭

    站长推荐上一条 /2 下一条


    id="mn_portal" >首页Portalid="mn_P18" onmouseover="navShow('P18')">应用id="mn_P15" onmouseover="navShow('P15')">技术id="mn_P37" onmouseover="showMenu({'ctrlid':this.id,'ctrlclass':'hover','duration':2})">前沿id="mn_P36" onmouseover="navShow('P36')">宝箱id="mn_P61" onmouseover="showMenu({'ctrlid':this.id,'ctrlclass':'hover','duration':2})">专栏id="mn_P65" >企业id="mn_Nd633" >导航 折叠导航 关注微信 关注微博 关注我们

    QQ|广告服务|关于我们|Archiver|手机版|小黑屋|大数据人 ( 鄂ICP备14012176号-2  

    GMT+8, 2024-3-28 20:33 , Processed in 0.255829 second(s), 35 queries .

    Powered by 小雄! X3.2

    © 2014-2020 bigdataer Inc.

    快速回复 返回顶部 返回列表