遺傳算法解釋及代碼(一看就懂)

1、.遺傳算法 ( GA , Genetic Algorithm ) ，也稱進(jìn)化算法 。 遺傳算法是受達(dá)爾文的進(jìn)化論的啟發(fā)，借鑒生物進(jìn)化過程而提出的一種啟發(fā)式搜索算法。因此在介紹遺傳算法前有必要簡單的介紹生物進(jìn)化知識。一.進(jìn)化論知識作為遺傳算法生物背景的介紹，下面內(nèi)容了解即可：種群(Population)：生物的進(jìn)化以群體的形式進(jìn)行，這樣的一個(gè)群體稱為種群。個(gè)體：組成種群的單個(gè)生物?；? Gene )：一個(gè)遺傳因子。染色體( Chromosome )：包含一組的基因。生存競爭，適者生存：對環(huán)境適應(yīng)度高的、牛B的個(gè)體參與繁殖的機(jī)會比較多，后代就會越來越多。適應(yīng)度低的個(gè)體參與繁殖的機(jī)會比較少，后代就

2、會越來越少。遺傳與變異：新個(gè)體會遺傳父母雙方各一部分的基因，同時(shí)有一定的概率發(fā)生基因變異。簡單說來就是：繁殖過程，會發(fā)生基因交叉( Crossover ) ，基因突變 ( Mutation ) ，適應(yīng)度( Fitness )低的個(gè)體會被逐步淘汰，而適應(yīng)度高的個(gè)體會越來越多。那么經(jīng)過N代的自然選擇后，保存下來的個(gè)體都是適應(yīng)度很高的，其中很可能包含史上產(chǎn)生的適應(yīng)度最高的那個(gè)個(gè)體。二.遺傳算法思想借鑒生物進(jìn)化論，遺傳算法將要解決的問題模擬成一個(gè)生物進(jìn)化的過程，通過復(fù)制、交叉、突變等操作產(chǎn)生下一代的解，并逐步淘汰掉適應(yīng)度函數(shù)值低的解，增加適應(yīng)度函數(shù)值高的解。這樣進(jìn)化N代后就很有可能會進(jìn)化出適應(yīng)度函數(shù)值

3、很高的個(gè)體。舉個(gè)例子，使用遺傳算法解決“0-1背包問題”的思路：0-1背包的解可以編碼為一串0-1字符串（0：不取，1：取） ；首先，隨機(jī)產(chǎn)生M個(gè)0-1字符串，然后評價(jià)這些0-1字符串作為0-1背包問題的解的優(yōu)劣；然后，隨機(jī)選擇一些字符串通過交叉、突變等操作產(chǎn)生下一代的M個(gè)字符串，而且較優(yōu)的解被選中的概率要比較高。這樣經(jīng)過G代的進(jìn)化后就可能會產(chǎn)生出0-1背包問題的一個(gè)“近似最優(yōu)解”。編碼：需要將問題的解編碼成字符串的形式才能使用遺傳算法。最簡單的一種編碼方式是二進(jìn)制編碼，即將問題的解編碼成二進(jìn)制位數(shù)組的形式。例如，問題的解是整數(shù)，那么可以將其編碼成二進(jìn)制位數(shù)組的形式。將0-1字符串作為0-1背

4、包問題的解就屬于二進(jìn)制編碼。遺傳算法有3個(gè)最基本的操作：選擇，交叉，變異。選擇：選擇一些染色體來產(chǎn)生下一代。一種常用的選擇策略是“比例選擇”，也就是個(gè)體被選中的概率與其適應(yīng)度函數(shù)值成正比。假設(shè)群體的個(gè)體總數(shù)是M，那么那么一個(gè)體Xi被選中的概率為f(Xi)/( f(X1) + f(X2) + . + f(Xn) ) 。比例選擇實(shí)現(xiàn)算法就是所謂的“輪盤賭算法”( Roulette Wheel Selection ) ，輪盤賭算法的一個(gè)簡單的實(shí)現(xiàn)如下：輪盤賭算法/* 按設(shè)定的概率，隨機(jī)選中一個(gè)個(gè)體* Pi表示第i個(gè)個(gè)體被選中的概率*/intRWS()m=0;r=Random(0,1);/r為0至1的

5、隨機(jī)數(shù)for(i=1;i=N; i+)/*產(chǎn)生的隨機(jī)數(shù)在mm+Pi間則認(rèn)為選中了i* 因此i被選中的概率是Pi*/m=m+Pi;if(r=m)returni;交叉(Crossover)：2條染色體交換部分基因，來構(gòu)造下一代的2條新的染色體。例如：交叉前：00000|0|1000011100|0|00101交叉后：00000|0|1000011100|0|00101染色體交叉是以一定的概率發(fā)生的，這個(gè)概率記為Pc 。變異(Mutation)：在繁殖過程，新產(chǎn)生的染色體中的基因會以一定的概率出錯(cuò)，稱為變異。變異發(fā)生的概率記為Pm 。例如：變異前：00變異后：01適應(yīng)度函數(shù)( Fitness Fun

6、ction )：用于評價(jià)某個(gè)染色體的適應(yīng)度，用f(x)表示。有時(shí)需要區(qū)分染色體的適應(yīng)度函數(shù)與問題的目標(biāo)函數(shù)。例如：0-1背包問題的目標(biāo)函數(shù)是所取得物品價(jià)值，但將物品價(jià)值作為染色體的適應(yīng)度函數(shù)可能并不一定適合。適應(yīng)度函數(shù)與目標(biāo)函數(shù)是正相關(guān)的，可對目標(biāo)函數(shù)作一些變形來得到適應(yīng)度函數(shù)。三.基本遺傳算法的偽代碼基本遺傳算法偽代碼/* Pc：交叉發(fā)生的概率* Pm：變異發(fā)生的概率* M：種群規(guī)模* G：終止進(jìn)化的代數(shù)* Tf：進(jìn)化產(chǎn)生的任何一個(gè)個(gè)體的適應(yīng)度函數(shù)超過Tf，則可以終止進(jìn)化過程*/初始化Pm，Pc，M，G，Tf等參數(shù)。隨機(jī)產(chǎn)生第一代種群Popdo計(jì)算種群Pop中每一個(gè)體的適應(yīng)度F(i)。初始化

7、空種群newPopdo根據(jù)適應(yīng)度以比例選擇算法從種群Pop中選出2個(gè)個(gè)體if( random (0,1)Pc )對2個(gè)個(gè)體按交叉概率Pc執(zhí)行交叉操作if( random (0,1)Pm )對2個(gè)個(gè)體按變異概率Pm執(zhí)行變異操作將2個(gè)新個(gè)體加入種群newPop中 until ( M個(gè)子代被創(chuàng)建 )用newPop取代Popuntil ( 任何染色體得分超過Tf， 或繁殖代數(shù)超過G )四.基本遺傳算法優(yōu)化下面的方法可優(yōu)化遺傳算法的性能。精英主義(Elitist Strategy)選擇：是基本遺傳算法的一種優(yōu)化。為了防止進(jìn)化過程中產(chǎn)生的最優(yōu)解被交叉和變異所破壞，可以將每一代中的最優(yōu)解原封不動的復(fù)制到下一

8、代中。插入操作：可在3個(gè)基本操作的基礎(chǔ)上增加一個(gè)插入操作。插入操作將染色體中的某個(gè)隨機(jī)的片段移位到另一個(gè)隨機(jī)的位置。五. 使用AForge.Genetic解決TSP問題AForge.NET是一個(gè)C#實(shí)現(xiàn)的面向人工智能、計(jì)算機(jī)視覺等領(lǐng)域的開源架構(gòu)。AForge.NET中包含有一個(gè)遺傳算法的類庫。AForge.NET主頁：AForge.NET代碼下載：介紹一下AForge的遺傳算法用法吧。AForge.Genetic的類結(jié)構(gòu)如下：圖1. AForge.Genetic的類圖 下面用AForge.Genetic寫個(gè)解決TSP問題的最簡單實(shí)例。測試數(shù)據(jù)集采用網(wǎng)上流傳的中國31個(gè)省會城市的坐標(biāo):操作過程：

9、 (1) 下載AForge.NET類庫，網(wǎng)址： (2) 創(chuàng)建C#空項(xiàng)目GenticTSP。然后在AForge目錄下找到AForge.dll和AForge.Genetic.dll，將其拷貝到TestTSP項(xiàng)目的bin/Debug目錄下。再通過“Add Reference.”將這兩個(gè)DLL添加到工程。 (3) 將31個(gè)城市坐標(biāo)數(shù)據(jù)保存為bin/Debug/Data.txt 。 (4) 添加TSPFitnessFunction.cs，加入如下代碼：TSPFitnessFunction類usingSystem;usingAForge.Genetic;namespaceGenticTSP/Fitness

10、 function for TSP task (Travaling Salasman Problem)/publicclassTSPFitnessFunction : IFitnessFunction/mapprivateint, map=null;/ConstructorpublicTSPFitnessFunction(int, map)this.map=map;/Evaluate chromosome - calculates its fitness value/publicdoubleEvaluate(IChromosome chromosome)return1/(PathLength(

11、chromosome)+1);/Translate genotype to phenotype/publicobjectTranslate(IChromosome chromosome)returnchromosome.ToString();/Calculate path length represented by the specified chromosome/publicdoublePathLength(IChromosome chromosome)/salesman pathushort path=(PermutationChromosome)chromosome).Value;/ch

12、eck path sizeif(path.Length!=map.GetLength(0)thrownewArgumentException(Invalid path specified - not all cities are visited);/path lengthintprev=path0;intcurr=pathpath.Length-1;/calculate distance between the last and the first citydoubledx=mapcurr,0-mapprev,0;doubledy=mapcurr,1-mapprev,1;doublepathL

13、ength=Math.Sqrt(dx*dx+dy*dy);/calculate the path length from the first city to the lastfor(inti=1, n=path.Length; in; i+)/get current citycurr=pathi;/calculate distancedx=mapcurr,0-mapprev,0;dy=mapcurr,1-mapprev,1;pathLength+=Math.Sqrt(dx*dx+dy*dy);/put current city as previousprev=curr;returnpathLe

14、ngth; (5) 添加GenticTSP.cs，加入如下代碼：GenticTSP類usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;usingSystem.IO;usingAForge;usingAForge.Genetic;namespaceGenticTSPclassGenticTSPstaticvoidMain()StreamReader reader=newStreamReader(Data.txt);intcitiesCount=31;/城市數(shù)int, map=newintci

15、tiesCount,2;for(inti=0; icitiesCount; i+)stringvalue=reader.ReadLine();string temp=value.Split();mapi,0=int.Parse(temp0);/讀取城市坐標(biāo)mapi,1=int.Parse(temp1);/create fitness functionTSPFitnessFunction fitnessFunction=newTSPFitnessFunction(map);intpopulationSize=1000;/種群最大規(guī)模/* 0：EliteSelection算法* 1：RankSel

16、ection算法* 其他：RouletteWheelSelection 算法*/intselectionMethod=0;/create populationPopulation population=newPopulation(populationSize,newPermutationChromosome(citiesCount),fitnessFunction,(selectionMethod=0)?(ISelectionMethod)newEliteSelection() :(selectionMethod=1)?(ISelectionMethod)newRankSelection() :(ISelectionMethod)newRouletteWheelSelection();/iterationsintiter=1;intiterations=5000;/迭代最大周期/loopwhile(iteriterations)/run one epoch of genetic algorithmp