1、一種基于病毒原理的遺傳算法研究論文摘要：病毒進(jìn)化遺傳算法是一種基于病毒原理的協(xié)同進(jìn)化算法，通過(guò)病毒種群和宿主種群的分工協(xié)作實(shí)現(xiàn)了繼承信息在父代與子代群體間的縱向傳遞，同時(shí)也完成了進(jìn)化基因在不同種群間的橫向傳播，有效解決了傳統(tǒng)遺傳算法在解空間快速搜索與易陷入局部最優(yōu)解這對(duì)矛盾。該算法成功應(yīng)用到旅行商問(wèn)題并取得了令人滿(mǎn)意的效果。論文關(guān)鍵詞：病毒進(jìn)化遺傳算法,局部最優(yōu)解,反轉(zhuǎn)錄,轉(zhuǎn)導(dǎo)遺傳算法(GeneticAlgorithm,GA)是一種基于自然選擇、遺傳變異等進(jìn)化機(jī)制的全局搜索算法。從形式上說(shuō)，GA也是一種迭代計(jì)算，計(jì)算過(guò)程模擬了生物體的進(jìn)化機(jī)制，從一組解出發(fā)，采用類(lèi)似自然選擇和有性繁殖的方式，在

2、繼承原有優(yōu)良基因的根底上，生成具有更好性能指標(biāo)的下一代群體。為進(jìn)一步解決GA在解空間快速搜索與易陷入局部最優(yōu)解之間的矛盾，受人類(lèi)社會(huì)分工和協(xié)作的啟發(fā)，提出了病毒進(jìn)化遺傳算法(VirusCo-EvolutionGeneticAlgorithm，VEGA)。VEGA在進(jìn)化計(jì)算過(guò)程中產(chǎn)生兩類(lèi)種群:宿主種群和病毒種群。宿主種群對(duì)應(yīng)問(wèn)題的解空間,進(jìn)行遺傳操作,在上下代群體之間縱向傳遞遺傳基因,實(shí)施解空間的全局搜索；同時(shí)病毒群體進(jìn)行病毒感染操作,在同代個(gè)體之間橫向傳遞,實(shí)施解空間的局部搜索。VEGA將宿主種群的全局進(jìn)化和病毒種群的局部進(jìn)化動(dòng)態(tài)結(jié)合,從而病毒進(jìn)化遺傳算法有效解決了上述矛盾。1VEGA的病毒、

3、生物機(jī)制1.1病毒機(jī)制根據(jù)病毒進(jìn)化理論,病毒是一種特有的生物,具有很強(qiáng)的感染能力,能夠獲得個(gè)體的染色體基因,并感染給另一個(gè)體,使得該個(gè)體的局部染色體基因發(fā)生相應(yīng)的變化,從而改變遺傳信息,又通過(guò)遺傳傳遞給下一代,大大加速了生物體的進(jìn)化換代。病毒進(jìn)化過(guò)程：首先病毒把基因反轉(zhuǎn)錄給鄰近主種群中挑選出的個(gè)體，然后計(jì)算被感染個(gè)體的適應(yīng)度，把病毒模式反轉(zhuǎn)錄給被選出的宿主個(gè)體，病毒不斷感染直到滿(mǎn)意為止，計(jì)算病毒i的生命力，如果生命力小于0，那么病毒個(gè)體從宿主個(gè)體中轉(zhuǎn)導(dǎo)一個(gè)子鏈，否那么從被傳染的主個(gè)體中轉(zhuǎn)導(dǎo)局部新子鏈。1.2生物機(jī)制生物進(jìn)化過(guò)程：在自然界中生物的DNA結(jié)構(gòu)是穩(wěn)定的，很難被破壞，然而RNA的結(jié)構(gòu)卻

4、不穩(wěn)定，因此生物將根本繼承DNA遺傳信息。在VEGA中這種遺傳被復(fù)制實(shí)現(xiàn)，另一方面，病毒又通過(guò)自我復(fù)制來(lái)適應(yīng)它的宿主(如圖1)。圖1：VEGA生物機(jī)理Fig1:VEGABiologyMechanism2VEGA算法模型2.1病毒種群的感染操作病毒對(duì)宿主個(gè)體的感染算子具有兩種搜索操作：1反轉(zhuǎn)錄：在宿主個(gè)體中隨機(jī)選出與病毒等長(zhǎng)的局部用病毒模式取代，形如病毒中某段為101，那么宿主對(duì)應(yīng)段被101取代如圖2，反轉(zhuǎn)錄操作突變出新的宿主個(gè)體。2轉(zhuǎn)導(dǎo)：借助病毒因子從一種個(gè)體轉(zhuǎn)移到另一個(gè)體，其目的是產(chǎn)生新的病毒個(gè)體如圖3。圖2：病毒反轉(zhuǎn)錄圖3：病毒轉(zhuǎn)導(dǎo)Fig2:VirussReverseTranscripti

5、onFig3：VirussTransduction2.2VEGA算法實(shí)現(xiàn)過(guò)程宿主種群和病毒種群分別表示待解決問(wèn)題中的一組候選解和候選解個(gè)體上的一個(gè)子鏈，宿主遺傳操作的縱向全局搜索和病毒感染操作的水平搜索協(xié)同進(jìn)化共同構(gòu)成了VEGA算法體系結(jié)構(gòu)如圖4。圖4：VEGA體系結(jié)構(gòu)Fig4:VEGASystemStructionVEGA算法實(shí)現(xiàn)步驟：Step1產(chǎn)生初始種群：生成宿主初始種群，再以一定概率產(chǎn)生病毒初始種群取1/101/5；Step2實(shí)施遺傳操作：以一定概率對(duì)宿主種群中的個(gè)體進(jìn)行交叉操作，新個(gè)體取代父?jìng)€(gè)體，再以較小的概率使群體中的少數(shù)個(gè)體發(fā)生變異，此時(shí)的遺傳操作不受病毒影響；Step3實(shí)施病毒

6、操作：取病毒群體中對(duì)應(yīng)主群體的病毒個(gè)體，以一定的概率感染主群體，包括反轉(zhuǎn)錄和轉(zhuǎn)導(dǎo)兩種搜索算子；Step4計(jì)算宿主群體中每個(gè)個(gè)體感染前后的適應(yīng)度，并計(jì)算病毒全體的感染力和生命力；Step5選擇優(yōu)良宿主個(gè)體，組成同規(guī)模的新一代種群，再根據(jù)感染力和生命力選擇新的病毒個(gè)體；Step6判斷終止條件，重復(fù)進(jìn)行步驟2步驟5，直至滿(mǎn)足條件為止。3TSP問(wèn)題模擬仿真3.1TSP問(wèn)題描述旅行商問(wèn)題TravelingSalesmanProblem,TSP是著名的NP難題，在TSP問(wèn)題中，N個(gè)城市兩兩間的距離，現(xiàn)有一名旅行者要遍訪這N個(gè)城市，且每個(gè)城市只去一次，最后返回到源出發(fā)點(diǎn)，希望安排一條訪問(wèn)路線使得旅行的總路程

7、長(zhǎng)度最短。3.2仿真實(shí)驗(yàn)在這里我們比擬了27個(gè)城市的VEGA和SGA的性能，VEGA算法的參數(shù)設(shè)置見(jiàn)表1。表1：VEGA參數(shù)Table1:VEGAsParameters 交叉概率 變異 概率 宿主規(guī)模A 病毒規(guī)模A 宿主規(guī)模B 病毒規(guī)模B 生命衰減率 最大感染率 初始感染率 轉(zhuǎn)導(dǎo)率 病毒濃度上限 0.8 0.001 36 3 64 6 0.9 0.1 0.05 0.6 0.1 VEGA和SGA的實(shí)驗(yàn)結(jié)果如圖5，仿真實(shí)驗(yàn)證明了VEGA比SGA能獲得更多的有效解，并且VEGA能更有效的搜索到解空間，從而解決了傳統(tǒng)遺傳算法在解空間快速搜索與易陷入局部最優(yōu)解這對(duì)矛盾；同時(shí)證明病毒數(shù)越大，收斂越慢，其原

8、因是因?yàn)檗D(zhuǎn)導(dǎo)算子在減少，仿真結(jié)果符合預(yù)期的效果。圖5：VEGA和SGA性能比擬Fig5:PerformanceComparisonofVEGAandSGA4結(jié)束語(yǔ)SGA是一種全局搜索算法，其局部搜索能力較差，算子的隨機(jī)性容易導(dǎo)致局部收斂現(xiàn)象。本文提出了一種基于病毒原理的遺傳算法,該算法采用協(xié)同進(jìn)化思想，既實(shí)現(xiàn)了遺傳算子在父、子代種群間的全局搜索的功能，也實(shí)現(xiàn)了病毒感染操作在同一代種群間的局部搜索功能，從而可以比SGA更快的獲得問(wèn)題的滿(mǎn)意解。參考文獻(xiàn)1 丁永生,計(jì)算智能理論、技術(shù)與應(yīng)用。北京:科學(xué)出版社,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 胡仕成,徐曉飛,戰(zhàn)德臣,大型產(chǎn)品結(jié)構(gòu)優(yōu)化問(wèn)題的病毒進(jìn)化遺傳算法。計(jì)算機(jī)集成制造系統(tǒng),2003,3(9);4 黃明,梁旭,一種新型病毒進(jìn)化遺傳算法研究。計(jì)算機(jī)集成制造系統(tǒng),2005,8(11);5