1、遗传算法程序设计探讨穆艳玲(北京联合大学 电工电子技术实验实训基地，北京 100110)摘 要 本文通过对基本遗传算法添加初始化启发信息、改进交叉算子和利用本身所固有的并行性构架粗粒度并行遗传算法等方法提高了遗传算法的收敛性及其寻优能力。关键词 遗传算法；TSP；交叉算子1 引言遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。总的说来，遗传算法是按不依赖于问题本身的方式去求解问题。它的目标是搜索这个多维、高度非线性空间以找到具有最优适应值(即最小费用的)的点 1。基本遗传算法是一个迭代过程，它模仿生物在自然环境中的遗传和进化机理，反复将选择算子、交叉算子和
2、变异算子作用于种群，最终可得到问题的最优解和近似最优解。2 遗传算法程序设计改进比较2.1 基本遗传算法对 TSP 问题解的影响本文研究的遗传算法及改进算法的实现是以 C+语言为基础，在 Windows2000 的版本上运行，其实现程序是在 Microsoft Visual Stadio 6.0 上编写及运行调试的。1) 遗传算法的执行代码m_Tsp.Initpop()； /种群的初始化for(int i=0；idecen|variancedecvar)/m_Tsp.m_genmin)sign=i；min=1/fitnessi；fwrite(&gen，sizeof(int)，1，out)；fo
3、r(i=0；ichrom；i+)fwrite(&Rchromsigni，sizeof(unsigned)，1，out)；fwrite(&fitnesssign，sizeof(double)，1，out)；/每九代向从程序发送一个最优个体if(gen%9=0)MPI_Bcast(Rchromsign，chrom，MPI_ UNSIGNED，0，MPI_COMM_WORLD)；2)从程序代码/将上一代的最优个体传回主程序MPI_Send(Rchrom1，chrom，MPI_UNSIGNED，0，gen，MPI_COMM_WORLD)；/每九代接收一个最优个体并将其加入种群中替换掉最差个体if(ge
4、n%9=0)PI_Bcast(Rchrom2，chrom，MPI_UNSIGNED，0，MPI_COMM_WORLD)；Tsp.IndiAlternate(Rchrom2)；/进行下一代的计算Tsp.Aternate()；Tsp.Generation()； Tsp.Statistics()； 3)并行遗传算法的性能笔者在 MPI 并行环境下，用 C 语言实现了一个解决 TSP 问题的粗粒度模型的并行遗传算法。该程序采用的是主从式的 MPI 程序设计，通过从硬盘的文件中读取数据来设置染色体长度、种群的规模、交叉概率和变异概率等参数。试验环境为曙光 TC1700 机，测试的对象是 Oliver T
5、SP 问题的 30 个城市的 TSP 问题。正如在测试串行遗传算法所提到的数据结果，并行遗传算法也没有达到目前所记录的最好解，但是它提高了算法的收敛性，并行遗传算法的收敛趋势如图 2 所示 4。图 2 遗传算法的收敛过程3 结束语本文通过对基本遗传算法的不断改进，证明了添加启发信息、改进遗传算子和利用遗传算法固有的并行性都可以提高遗传算法的收敛性，其中对遗传算法交叉算子的改进可以大大提高遗传算法的寻优能力。参考文献1 刘勇、康立山，陈毓屏著 非数值并行算法遗传算法北京：科学出版社 1995.12 I M Oliver D J Smith and J R C Holland，A study of
6、 permutation crossover operators on the traveling salesmanC/ Problem of the second International Conference on Genetic Algorithms and Their Application，Erlbaum 1897： 224-2303 于海斌，王浩波，徐心和 两代竞争遗传算法及其应用研究 信息与控制，2000 Vol.29，No.4：309-3144穆艳玲，李学武，高润泉 遗传算法解 TSP 问题的并行实现北京联合大学学报(自然科学版)，2006 Vol.20 No.2： 40-43收稿日期：07 年 11 月 14 日 修改日期：07 年 11 月 18 日作者简介：穆艳玲(1975-)，女，山东省淄博市人，讲师，硕士，主要研究方向：遗传算法。
