一种基于病毒原理的遗传算法研究

1、一种基于病毒原理的遗传算法研究论文摘要：病毒进化遗传算法是一种基于病毒原理的协同进化算法，通过病毒种群和宿主种群的分工协作实现了继承信息在父代与子代群体间的纵向传递，同时也完成了进化基因在不同种群间的横向传播，有效解决了传统遗传算法在解空间快速搜索与易陷入局部最优解这对矛盾。该算法成功应用到旅行商问题并取得了令人满意的效果。论文关键词：病毒进化遗传算法,局部最优解,反转录,转导遗传算法(GeneticAlgorithm,GA)是一种基于自然选择、遗传变异等进化机制的全局搜索算法。从形式上说，GA也是一种迭代计算，计算过程模拟了生物体的进化机制，从一组解出发，采用类似自然选择和有性繁殖的方式，在

2、继承原有优良基因的根底上，生成具有更好性能指标的下一代群体。为进一步解决GA在解空间快速搜索与易陷入局部最优解之间的矛盾，受人类社会分工和协作的启发，提出了病毒进化遗传算法(VirusCo-EvolutionGeneticAlgorithm，VEGA)。VEGA在进化计算过程中产生两类种群:宿主种群和病毒种群。宿主种群对应问题的解空间,进行遗传操作,在上下代群体之间纵向传递遗传基因,实施解空间的全局搜索；同时病毒群体进行病毒感染操作,在同代个体之间横向传递,实施解空间的局部搜索。VEGA将宿主种群的全局进化和病毒种群的局部进化动态结合,从而病毒进化遗传算法有效解决了上述矛盾。1VEGA的病毒、

3、生物机制1.1病毒机制根据病毒进化理论,病毒是一种特有的生物,具有很强的感染能力,能够获得个体的染色体基因,并感染给另一个体,使得该个体的局部染色体基因发生相应的变化,从而改变遗传信息,又通过遗传传递给下一代,大大加速了生物体的进化换代。病毒进化过程：首先病毒把基因反转录给邻近主种群中挑选出的个体，然后计算被感染个体的适应度，把病毒模式反转录给被选出的宿主个体，病毒不断感染直到满意为止，计算病毒i的生命力，如果生命力小于0，那么病毒个体从宿主个体中转导一个子链，否那么从被传染的主个体中转导局部新子链。1.2生物机制生物进化过程：在自然界中生物的DNA结构是稳定的，很难被破坏，然而RNA的结构却

4、不稳定，因此生物将根本继承DNA遗传信息。在VEGA中这种遗传被复制实现，另一方面，病毒又通过自我复制来适应它的宿主(如图1)。图1：VEGA生物机理Fig1:VEGABiologyMechanism2VEGA算法模型2.1病毒种群的感染操作病毒对宿主个体的感染算子具有两种搜索操作：1反转录：在宿主个体中随机选出与病毒等长的局部用病毒模式取代，形如病毒中某段为101，那么宿主对应段被101取代如图2，反转录操作突变出新的宿主个体。2转导：借助病毒因子从一种个体转移到另一个体，其目的是产生新的病毒个体如图3。图2：病毒反转录图3：病毒转导Fig2:VirussReverseTranscripti

5、onFig3：VirussTransduction2.2VEGA算法实现过程宿主种群和病毒种群分别表示待解决问题中的一组候选解和候选解个体上的一个子链，宿主遗传操作的纵向全局搜索和病毒感染操作的水平搜索协同进化共同构成了VEGA算法体系结构如图4。图4：VEGA体系结构Fig4:VEGASystemStructionVEGA算法实现步骤：Step1产生初始种群：生成宿主初始种群，再以一定概率产生病毒初始种群取1/101/5；Step2实施遗传操作：以一定概率对宿主种群中的个体进行交叉操作，新个体取代父个体，再以较小的概率使群体中的少数个体发生变异，此时的遗传操作不受病毒影响；Step3实施病毒

6、操作：取病毒群体中对应主群体的病毒个体，以一定的概率感染主群体，包括反转录和转导两种搜索算子；Step4计算宿主群体中每个个体感染前后的适应度，并计算病毒全体的感染力和生命力；Step5选择优良宿主个体，组成同规模的新一代种群，再根据感染力和生命力选择新的病毒个体；Step6判断终止条件，重复进行步骤2步骤5，直至满足条件为止。3TSP问题模拟仿真3.1TSP问题描述旅行商问题TravelingSalesmanProblem,TSP是著名的NP难题，在TSP问题中，N个城市两两间的距离，现有一名旅行者要遍访这N个城市，且每个城市只去一次，最后返回到源出发点，希望安排一条访问路线使得旅行的总路程

7、长度最短。3.2仿真实验在这里我们比拟了27个城市的VEGA和SGA的性能，VEGA算法的参数设置见表1。表1：VEGA参数Table1:VEGAsParameters 交叉概率 变异 概率 宿主规模A 病毒规模A 宿主规模B 病毒规模B 生命衰减率 最大感染率 初始感染率 转导率 病毒浓度上限 0.8 0.001 36 3 64 6 0.9 0.1 0.05 0.6 0.1 VEGA和SGA的实验结果如图5，仿真实验证明了VEGA比SGA能获得更多的有效解，并且VEGA能更有效的搜索到解空间，从而解决了传统遗传算法在解空间快速搜索与易陷入局部最优解这对矛盾；同时证明病毒数越大，收敛越慢，其原

8、因是因为转导算子在减少，仿真结果符合预期的效果。图5：VEGA和SGA性能比拟Fig5:PerformanceComparisonofVEGAandSGA4结束语SGA是一种全局搜索算法，其局部搜索能力较差，算子的随机性容易导致局部收敛现象。本文提出了一种基于病毒原理的遗传算法,该算法采用协同进化思想，既实现了遗传算子在父、子代种群间的全局搜索的功能，也实现了病毒感染操作在同一代种群间的局部搜索功能，从而可以比SGA更快的获得问题的满意解。参考文献1 丁永生,计算智能理论、技术与应用。北京:科学出版社,2004.8;2 Kubota N, Shimojima K .The role of virus infection in virus-evolutionary genetic algorithm . EvolutionaryComputation, Proceedings of the IEEE International Conference on . Nagoya, Japan: IEEE,1996;3 胡仕成,徐晓飞,战德臣,大型产品结构优化问题的病毒进化遗传算法。计算机集成制造系统,2003,3(9);4 黄明,梁旭,一种新型病毒进化遗传算法研究。计算机集成制造系统,2005,8(11);5