第3卷第5期 智能系统学报 Vol 3 Na 5 2008年10月 CAA I Transactions on Intelligent Systems 0ct2008 一种基于种群多样度的实数编码并行遗传算法 刘胜，李高云，孙天英 哈尔滨工程大学自动化学院，黑龙江哈尔滨150001) 摘要：为了改善遗传算法的收敛性能，提出了一种基于个体适应度的种群多样性度量函数，恰当地反映了遗传算 法的进化阶段，预报了早熟收敛的趋势.设计了基于种群多样度函数的迁移算子和交叉算子，并对交叉、变异概率等 进行了动态调整，构成了具有多层迁移特点的实数编码并行遗传算法.通过和其他优秀遗传算法对测试函数的验证 比较结果表明，该算法对于解决遗传算法中早熟、收敛速度慢等问题具有优越的性能」 关键词：遗传算法；种群多样性：迁移算子；实数编码 中图分类号：TP18文款标识码：A文章编号：1673-4785(2008)05-042306 A real coding parallel genetic algor ithm based on diversity of popula tion L U Sheng,LI Gao-yun,SUN Tian-ying (College of Autmation,Harbin Engineering University,Harbin,150001,China) Abstract:In order to mprove the convergence perfomance of genetic algorithms,a function measuring population diversity on the basis of the degree of ind ividual adap tability was needed This measuring function must reflect the evolutionary stage of the genetic algorithm and orecast premature trends appropriately.We designed am igration op- erator and crossover operaor based on diversity of population functions,and made dynam ic adjusments on cross- over and mutation probabilities This structured a parallel genetic algorithm with real coding and a multi-layer mi gration operator Comparative experments were made on benchmark functions The results showed that this algo- rithm is obviously superior to other genetic algorithms in overcom ing problems such as prematurity and slow conver gence Keywords:genetic algorithm;diversity of population;m igration operator,real coding 遗传算法是受生物进化理论启发的搜索算法， 能充分利用其他子群体的信息，同样不利于提高解 是由Holland在19世纪70年代提出来的)，其本身 的质量.管宇等分析了迁移算子在整个算法收敛过 具备良好的并行设计结构，不易陷入局部最优，并且 程中的重要作用，提出一种基于模式定理的迁移策 不依赖于梯度信息，因此特别适用于处理高度复杂 略MS,提高了算法的时间性能s).Marin等采用集 的非线性问题，并在函数优化、参数辨识、模式识别、 中式方案，从各进程在其子群体中执行G4,并周 自动控制等许多领域得到广泛地应用.然而，遗传算 期地将最好的部分结果发送给主进程，在网络上所 法作为一种随机搜索方法，存在局部领域搜索不敏 作的实验表明，运行速度以接近线性加速比增加.但 感，早熟收敛，寻优速度慢等诸多不足之处.为了改 迁移时机的把握还需作进一步的研究.Baun的方 善性能，人们进行了大量的研究，并提出了许多解决 案)是当GA在区域上产生早熟收敛时，才进行迁 的方案.J.Liening博士通过大量的实验发现2)：过 移.Knoger等则采用了另一种途径，每当一个区域中 多以及过频繁的迁移会破坏子群体的多样性，致使 发现一个改进的个体，就异步地执行迁移操作6 多个搜索进程集中到相同的区域，不利于提高解的 本文在以上基础上，提出了一种新的种群多样度度 质量：过少的迁移以及迁移频率过低，使各子群体不 量函数，并基于此设计引入迁移算子的实数并行遗 传算法，同时对实数交叉等方面也做了改进.算例结 收稿日期：20080301 基金项目：黑龙江省自然科学基金资助项目(A200419)」 果表明，该算法具有良好的防止早熟特性，并且增强 通信作者：李高云.Emai让ligaoyun@hrbeu edu cn 了全局最优解的搜索能力，能较快地搜索到全局最 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net第 3卷第 5期 智 能 系 统 学 报 Vol. 3 №. 5 2008年 10月 CAA I Transactions on Intelligent System s Oct. 2008 一种基于种群多样度的实数编码并行遗传算法 刘 胜 ,李高云 ,孙天英 (哈尔滨工程大学 自动化学院 ,黑龙江 哈尔滨 150001) 摘 要 :为了改善遗传算法的收敛性能 ,提出了一种基于个体适应度的种群多样性度量函数 ,恰当地反映了遗传算 法的进化阶段 ,预报了早熟收敛的趋势. 设计了基于种群多样度函数的迁移算子和交叉算子 ,并对交叉、变异概率等 进行了动态调整 ,构成了具有多层迁移特点的实数编码并行遗传算法. 通过和其他优秀遗传算法对测试函数的验证 比较 ,结果表明 ,该算法对于解决遗传算法中早熟、收敛速度慢等问题具有优越的性能. 关键词 :遗传算法 ;种群多样性 ;迁移算子 ;实数编码 中图分类号 : TP18 文献标识码 : A 文章编号 : 167324785 (2008) 0520423206 A real coding parallel genetic algorithm based on diversity of population L IU Sheng, L I Gao2yun, SUN Tian2ying (College of Automation, Harbin Engineering University, Harbin, 150001, China) Abstract: In order to imp rove the convergence performance of genetic algorithm s, a function measuring population diversity on the basis of the degree of individual adap tability was needed. This measuring function must reflect the evolutionary stage of the genetic algorithm and forecast p remature trends app rop riately. We designed a m igration op2 erator and crossover operator based on diversity of population functions, and made dynam ic adjustments on cross2 over and mutation p robabilities. This structured a parallel genetic algorithm with real coding and a multi2layer m i2 gration operator. Comparative experiments were made on benchmark functions. The results showed that this algo2 rithm is obviously superior to other genetic algorithm s in overcom ing p roblem s such as p rematurity and slow conver2 gence. Keywords: genetic algorithm; diversity of population; m igration operator; real coding 收稿日期 : 2008203201. 基金项目 :黑龙江省自然科学基金资助项目 (A200419). 通信作者 :李高云. E2mail: ligaoyun@hrbeu. edu. cn. 遗传算法是受生物进化理论启发的搜索算法 , 是由 Holland在 19世纪 70年代提出来的 [ 1 ] ,其本身 具备良好的并行设计结构 ,不易陷入局部最优 ,并且 不依赖于梯度信息 ,因此特别适用于处理高度复杂 的非线性问题 ,并在函数优化、参数辨识、模式识别、 自动控制等许多领域得到广泛地应用. 然而 ,遗传算 法作为一种随机搜索方法 ,存在局部领域搜索不敏 感 ,早熟收敛 ,寻优速度慢等诸多不足之处. 为了改 善性能 ,人们进行了大量的研究 ,并提出了许多解决 的方案. J. L iening博士通过大量的实验发现 [ 2 ] :过 多以及过频繁的迁移会破坏子群体的多样性 ,致使 多个搜索进程集中到相同的区域 ,不利于提高解的 质量 ;过少的迁移以及迁移频率过低 ,使各子群体不 能充分利用其他子群体的信息 ,同样不利于提高解 的质量. 管宇等分析了迁移算子在整个算法收敛过 程中的重要作用 ,提出一种基于模式定理的迁移策 略 SMS,提高了算法的时间性能 [ 3 ] . Marin等采用集 中式方案 [ 4 ] ,从各进程在其子群体中执行 GA,并周 期地将最好的部分结果发送给主进程 ,在网络上所 作的实验表明 ,运行速度以接近线性加速比增加. 但 迁移时机的把握还需作进一步的研究. Braun的方 案 [ 5 ]是当 GA在区域上产生早熟收敛时 ,才进行迁 移. Kroger等则采用了另一种途径 ,每当一个区域中 发现一个改进的个体 ,就异步地执行迁移操作 [ 6 ] . 本文在以上基础上 ,提出了一种新的种群多样度度 量函数 ,并基于此设计引入迁移算子的实数并行遗 传算法 ,同时对实数交叉等方面也做了改进. 算例结 果表明 ,该算法具有良好的防止早熟特性 ,并且增强 了全局最优解的搜索能力 ,能较快地搜索到全局最