遗传算法程序设计探讨(2)
说明：文章内容仅供预览，部分内容可能不全，需要完整文档或者需要复制内容，请下载word后使用。下载word有问题请添加微信号:
或QQ：
处理（尽可能给您提供完整文档），感谢您的支持与谅解。
表2 20个城市的TSP问题求解结果数据
算法
交叉操作
次数
最优解
出现时间
平均
最优解
简单遗传算法
80244.4
79.4s
1641.8
含初始化启发信息的GA
79000.2
37.4s
1398.9
从表2中可以看出，当初始种群时引入启发信息将提高遗传算法的寻优能力。同时缩短了遗传算法的寻优时间和问题的求解精度。
2.3 交叉算子对TSP问题解的影响
1)循环贪心交叉算子的核心代码
for(i=1；i<m_Chrom；i++)
{
flag=0；
city=m_newpop[first].chrom[i-1]； //确定当前城市
j=0；
while(flag==0&&j<4)
{
sign=adjcity[city][j]； //adjcity数组的数据为当前城市按顺序排列的邻接城市
flag=judge(first，i，sign)； //判断此邻接城市是否已经存在待形成的个体中
j++；
}
if(flag= =0) //如果所有邻接城市皆在待扩展的个体中
{
while(flag= =0)
{
sign=(int)rand()/(RAND_MAX/(m_ Chrom-1))； //随机选择一城市
flag=judge(first，i，sign)；
}
}
if(flag==1)
m_newpop[first].chrom[i]=sign；
}
2)问题描述与结果比较
下面笔者用经典的测试遗传算法效率的Oliver TSP问题来测试循环贪心交叉算子的解的精度和解效率。Oliver TSP问题的30个城市位置坐标如表3所示
[2]。
表3 Oliver TSP问题的30个城市位置坐标
城市编号
坐标
城市编号
坐标
城市编号
坐标
1
(87，7)
11
(58，69)
21
(4，50)
2
(91，83)
12
(54，62)
22
(13，40)
3
(83，46)
13
(51，67)
23
(18，40)
4
(71，44)
14
(37，84)
24
(24，42)
5
(64，60)
15
(41，94)
25
(25，38)
6
(68，58)
16
(2，99)
26
(41，26)
7
(83，69)
17
(7，64)
27
(45，21)
8
(87，76)
18
(22，60)
28
(44，35)
9
(74，78)
19
(25，62)
29
(58，35)
10
(71，71)
20
(18，54)
30
(62，32)
表4 贪心交叉与部分匹配交叉的比较(Oliver TSP问题的30个城市)
交叉算子
交叉操作次数
平均时间
平均最优解
部分匹配交叉
59760
31.2s
517.0
贪心交叉
15774
28.6s
433.4
从表4、图1中可以看到，贪心交叉算子大大提高了遗传算法的寻优能力，同时也降低了交叉操作次数。在多次试验中，贪心交叉算子找到的最优解与目前记载的最佳数据的误差率为2.7%。而部分匹配交叉算子找到的最优解与目前记载的最佳数据的误差率高达7%。从而可以得到交叉算子对于遗传算法的计算效率和计算结果起主导性作用
[3]。
图1 遗传算法的收敛过程
2.4 并行遗传算法消息传递实现的核心代码
1)主程序代码
//接收各个从程序的最优个体
for(i=0；i<slave；i++)
{
MPI_Recv(Rchrom[i]，chrom，MPI_UNSIGNED，MPI_ANY_SOURCE，gen，MPI_COMM_WORLD，&status)；
}
//计算接收各个从程序的最优个体的回路距离
for(i=0；i<slave；i++)
{
fitness[i]=0.0；
for(int j=0；j<chrom-1；j++)
fitness[i]=fitness[i]+distance[Rchrom[i][j]][Rchrom [i][j+1]]；
fitness[i]=fitness[i]+distance[Rchrom[i][0]][Rchrom [i][chrom-1]]；
}
//找到最优的个体并把它记录到文件里
for(i=0；i<slave；i++)
{
if(1/fitness[i]>min)
{
sign=i；
min=1/fitness[i]；
}
}
fwrite(&gen，sizeof(int)，1，out)；
for(i=0；i<chrom；i++)
fwrite(&Rchrom[sign][i]，sizeof(unsigned)，1，out)；
fwrite(&fitness[sign]，sizeof(double)，1，out)；
//每九代向从程序发送一个最优个体
if(gen%9==0)
MPI_Bcast(Rchrom[sign]，chrom，MPI_ UNSIGNED，0，MPI_COMM_WORLD)；
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说计算机遗传算法程序设计探讨(2)在线全文阅读。
遗传算法程序设计探讨(2).doc
将本文的Word文档下载到电脑，方便复制、编辑、收藏和打印
下载失败或者文档不完整，请联系客服人员解决！
