TA的每日心情 | 奋斗 2015-7-30 23:05 |
---|
签到天数: 12 天 [LV.3]偶尔看看II
管理员
- 积分
- 4804
|
- #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);
- }
- }
复制代码
|
|