一种基于病毒原理的遗传算法研究_局部最优解

一种基于病毒原理的遗传算法研究_局部最优解 一种基于病毒原理的遗传算法研究_局部最 优解 论文摘要:病毒进化遗传算法是一种基于病毒原理的协同进化算法，通过病毒种群和宿主种群的分工协作实现了继承信息在父代与子代群体间的纵向传递，同时也完成了进化基因在不同种群间的横向传播，有效解决了传统遗传算法在解空间快速搜索与易陷入局部最优解这对矛盾。该算法成功应用到旅行商问并取得了令人满意的效果。 论文关键词:病毒进化遗传算法,局部最优解,反转录,转导 遗传算法(GeneticAlgorithm,GA)是一种基于自然选择、遗传变异等进化机制的全局搜索算法。从形式上说，GA也是一种迭代计算，计算过程模拟了生物体的进化机制，从一组解出发，采用类似自然选择和有性繁殖的方式，在继承原有优良基因的基础上，生成具有更好性能指标的下一代群体。 为进一步解决GA在解空间快速搜索与易陷入局部最优解之间的矛盾，受人类社会分工和协作的启发，提出了病毒进化遗传算法(VirusCo-EvolutionGeneticAlgorithm，VEGA)。VEGA在进化计算过程中产生两类种群:宿主种群和 病毒种群。宿主种群对应问题的解空间,进行遗传操作,在上下代群体之间纵向传递遗传基因,实施解空间的全局搜索;同时病毒群体进行病毒感染操作,在同代个体之间横向传递,实施解空间的局部搜索。VEGA将宿主种群的全局进化和病毒种群的局部进化动态结合,从而病毒进化遗传算法有效解决了上述矛盾。 1VEGA的病毒、生物机制 1.1病毒机制 根据病毒进化理论,病毒是一种特有的生物,具有很强的感染能力,能够获得个体的染色体基因,并感染给另一个体,使得该个体的部分染色体基因发生相应的变化,从而改变遗传信息,又通过遗传传递给下一代,大大加速了生物体的进化换代。 病毒进化过程:首先病毒把基因反转录给邻近主种群中挑选出的个体，然后计算被感染个体的适应度，把病毒模式反转录给被选出的宿主个体，病毒不断感染直到满意为止，计算病毒i的生命力，如果生命力小于0，那么病毒个体从宿主个体中转导一个子链，否则从被传染的主个体中转导部分新子链。 1.2生物机制 生物进化过程:在自然界中生物的DNA结构是稳定的，很难被破坏，然而RNA的结构却不稳定，因此生物将 基本继承DNA遗传信息。在VEGA中这种遗传被复制实现，另一方面，病毒又通过自我复制来适应它的宿主(如图1)。 图1:VEGA生物机理 Fig1:VEGABiologyMechanism 2VEGA算法模型 2.1病毒种群的感染操作 病毒对宿主个体的感染算子具有两种搜索操作: (1)反转录:在宿主个体中随机选出与病毒等长的部分用病毒模式取代，形如病毒中某段为101，则宿主对应段被101取代(如图2)，反转录操作突变出新的宿主个体。 (2)转导:借助病毒因子从一种个体转移到另一个体，其目的是产生新的病毒个体(如图3)。 图2:病毒反转录图3:病毒转导 Fig2:Virus’sReverseTranscriptionFig3:Virus’sTransduction 2.2VEGA算法实现过程 宿主种群和病毒种群分别示待解决问题中的一组候选解和候选解个体上的一个子链，宿主遗传操作的纵向全局搜索和病毒感染操作的水平搜索协同进化共同构成了VEGA算法体系结构(如图4)。 图4:VEGA体系结构 Fig4:VEGASystemStruction VEGA算法实现步骤: Step1产生初始种群:生成宿主初始种群，再以一定概率产生病毒初始种群(取1/10~1/5); Step2实施遗传操作:以一定概率对宿主种群中的个体进行交叉操作，新个体取代父个体，再以较小的概率使群体中的少数个体发生变异，此时的遗传操作不受病毒影响; Step3实施病毒操作:取病毒群体中对应主群体的病毒个体，以一定的概率感染主群体，包括反转录和转导两种搜索算子; Step4计算宿主群体中每个个体感染前后的适应度，并计算病毒全体的感染力和生命力; Step5选择优良宿主个体，组成同规模的新一代种群，再根据感染力和生命力选择新的病毒个体; Step6判断终止条件，重复进行步骤2~步骤5，直至满足条件为止。 3TSP问题模拟仿真 3.1TSP问题描述 旅行商问题(TravelingSalesmanProblem,TSP)是著名的NP难题，在TSP问题中，已知N个城市两两间的距离， 现有一名旅行者要遍访这N个城市，且每个城市只去一次，最后返回到源出发点，希望安排一条访问路线使得旅行的总路程长度最短。 3.2仿真实验 在这里我们比较了27个城市的VEGA和SGA的性能，VEGA算法的参数设置(见表1)。 表1:VEGA参数 Table1:VEGA’sParameters VEGA和SGA的实验结果(如图5)，仿真实验证明了VEGA比SGA能获得更多的有效解，并且VEGA能更有效的搜索到解空间，从而解决了传统遗传算法在解空间快速搜索与易陷入局部最优解这对矛盾;同时证明病毒数越大，收敛越慢，其原因是因为转导算子在减少，仿真结果符合预期的效果。 图5:VEGA和SGA性能比较 Fig5:PerformanceComparisonofVEGAandSGA 4结束语 SGA是一种全局搜索算法，其局部搜索能力较差，算子的随机性容易导致局部收敛现象。 本文提出了一种基于病毒原理的遗传算法, 该算法采用协同进化思想，既实现了遗传算子在父、子代种 群间的全局搜索的功能，也实现了病毒感染操作在同一代种 群间的局部搜索功能，从而可以比SGA更快的获得问题的 满意解。 参考文献 1 丁永生,计算智能—理论、技术与应用[M]。北京:科学出 版社,2004.8; 2 Kubota N, Shimojima K .The role of virus infection in virus-evolutionary genetic algorithm [J]. EvolutionaryComputation, Proceedings of the IEEE International Conference on [C]. Nagoya, Japan: IEEE,1996; 3 胡仕成,徐晓飞,战德臣,大型产品结构优化问题的病毒进 化遗传算法[J]。计算机集成制造系统,2003,3(9); 4 黄明,梁旭,一种新型病毒进化遗传算法研究[J]。计算机集 成制造系统,2005,8(11); 5 刘晶,黄明,梁旭,改进的病毒进化遗传算法应用研究[J]。 大连交通大学学院,2009,2(30); 6 曹先彬,王本年,王煦法,一种病毒进化型遗传算法[J]。小 型微型计算机系统,2001,1(22); 7 杨锐,雍正正,引入病毒进化模型的新型模拟退火算法[J]。 深圳大学学报理工版,2006,2(23)。