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

?

?

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

局部最优解-论文网

?

?

论文摘要：病毒进化遗传算法是一种基于病毒原理的协同进化算法，通过病毒种群和宿主种群的分工协作实现了继承信息在父代与子代群体间的纵向传递，同时也完成了进化基因在不同种群间的横向传播，有效解决了传统遗传算法在解空间快速搜索与易陷入局部最优解这对矛盾。该算法成功应用到旅行商问题并取得了令人满意的效果。

论文关键词：病毒进化遗传算法,局部最优解,反转录,转导

遗传算法(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

交叉概率

变异概率

宿主规模A

病毒规模A

宿主规模B

病毒规模B

生命衰