摘  要　本文通过对基本遗传算法添加初始化启发信息、改进交叉算子和利用本身所固有的并行性构架粗粒度并行遗传算法等方法提高了遗传算法的收敛性及其寻优能力。     关键词  遗传算法；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次以上)得到的最优解的平均值，最优解的出现时间为最优解出现的平均时间，交叉操作次数为最优解出现时交叉次数的平均值。