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

《一种基于病毒原理的遗传算法研究_局部最优解.docx》由会员分享，可在线阅读，更多相关《一种基于病毒原理的遗传算法研究_局部最优解.docx（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

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

5、 Fig2:Virus’sReverseTranscriptionFig3：Virus’sTransduction 2.2VEGA算法实现过程 宿主种群和病毒种群分别表示待解决问题中的一组候选解和候选解个体上的一个子链，宿主遗传操作的纵向全局搜寻和病毒感染操作的水平搜寻协同进化共同构成了VEGA算法体系结构（如图4）。 图4：VEGA体系结构 Fig4:VEGASystemStruction VEGA算法实现步骤： Step1产生初始种群：生成宿主初始种群，再以肯定概率产生病毒初始种群（取1/101/5）； Step2实施遗传操作：以肯定概率对宿主种群中的个体进行交叉操

6、作，新个体取代父个体，再以较小的概率使群体中的少数个体发生变异，此时的遗传操作不受病毒影响； Step3实施病毒操作：取病毒群体中对应主群体的病毒个体，以肯定的概率感染主群体，包括反转录和转导两种搜寻算子； Step4计算宿主群体中每个个体感染前后的适应度，并计算病毒全体的感染力和生命力； Step5选择优良宿主个体，组成同规模的新一代种群，再依据感染力和生命力选择新的病毒个体； Step6推断终止条件，重复进行步骤2步骤5，直至满意条件为止。 3TSP问题模拟仿真 3.1TSP问题描述 旅行商问题（TravelingSalesmanProblem,TSP）是闻名的NP难题，在TSP问题中，已

7、知N个城市两两间的距离，现有一名旅行者要遍访这N个城市，且每个城市只去一次，最终返回到源动身点，希望支配一条访问路途使得旅行的总路程长度最短。 3.2仿真试验 在这里我们比较了27个城市的VEGA和SGA的性能，VEGA算法的参数设置（见表1）。 表1：VEGA参数 Table1:VEGA’sParameters 交叉概率 变异 概率 宿主规模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比

8、SGA能获得更多的有效解，并且VEGA能更有效的搜寻到解空间，从而解决了传统遗传算法在解空间快速搜寻与易陷入局部最优解这对冲突；同时证明病毒数越大，收敛越慢，其缘由是因为转导算子在削减，仿真结果符合预期的效果。 图5：VEGA和SGA性能比较 Fig5:PerformanceComparisonofVEGAandSGA 4结束语 SGA是一种全局搜寻算法，其局部搜寻实力较差，算子的随机性简单导致局部收敛现象。 第6页 共6页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页