摘 要 本文通过对基本遗传算法添加初始化启发信息、改进交叉算子和利用本身所固有的并行性构架粗粒度并行遗传算法等方法提高了遗传算法的收敛性及其寻优能力。
关键词 遗传算法；TSP；交叉算子
1 引言
遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。总的说来，遗传算法是按不依赖于问题本身的方式去求解问题。它的目标是搜索这个多维、高度非线性空间以找到具有最优适应值(即最小费用的)的点
[1]。
基本遗传算法是一个迭代过程，它模仿生物在自然环境中的遗传和进化机理，反复将选择算子、交叉算子和变异算子作用于种群，最终可得到问题的最优解和近似最优解。
2 遗传算法程序设计改进比较
2.1 基本遗传算法对TSP问题解的影响
本文研究的遗传算法及改进算法的实现是以C
++语言为基础，在Windows2000的版本上运行，其实现程序是在Microsoft Visual Stadio 6.0上编写及运行调试的。
1) 遗传算法的执行代码
m_Tsp.Initpop()； //种群的初始化
for(int i=0；i<m_Tsp.ReturnPop()；i++)
m_Tsp.calculatefitness(i)； //计算各个个体的适应值
m_Tsp.statistics()； //统计最优个体
while(entropy>decen||variance>decvar)//m_Tsp.m_gen<100)
{
//将新种群更迭为旧种群，并进行遗传操作
m_Tsp.alternate()； //将新种群付给旧种群
m_Tsp.generation()； //对旧种群进行遗传操作，产生新种群
m_Tsp.m_gen++；
m_Tsp.statistics()； //对新产生的种群进行统计
}
2) 简单的遗传算法与分支定界法对TSP问题求解结果的对比
遗传算法在解决NPC问题的领域内具有寻找最优解的能力。但随着城市个数的增加，已没有精确解，无法确定遗传算法求解的精度有多高。一般情况下，当迭代代数增大时，解的精度可能高，但是时间开销也会增大。因此可以通过改进遗传算法来提高搜索能力，提高解的精度。
表1 10个城市的TSP问题求解结果数据
算法
试验结果
简单遗传算法
分支定界法
最佳解
时间
精确解
时间
试验1
2448.610037
5s
2448.610037
00：07：30
试验2
2448.610037
13s
试验3
2448.610037
9s
试验4
2459.543054
10s
试验5
2459.543054
7s
2.2 初始化时的启发信息对TSP问题解的影响
1) 初始化启发信息
在上述实验算法的基础上，对每一个初始化的个体的每五个相邻城市用分支界定法寻找最优子路径，然后执行遗传算法。
2) 遗传算法与含有启发信息的遗传算法求解结果的对比
当城市数增至20个时，用分支定界法已经不可能在可以接受的时间内得到精确的解了，只能通过近似算法获得其可接受的解。试验设计中算法的截止条件：固定迭代1000代。表2中的平均最优解为经过多次试验(10次以上)得到的最优解的平均值，最优解的出现时间为最优解出现的平均时间，交叉操作次数为最优解出现时交叉次数的平均值。
百度搜索“yundocx”或“云文档网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，云文档网，提供经典计算机遗传算法程序设计探讨在线全文阅读。
