遺傳算法解釋及代碼

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

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

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

4、題的解就屬于二進(jìn)制編碼。遺傳算法有3個最基本的操作：選擇，交叉，變異。選擇:選擇一些染色體來產(chǎn)生下一代。一種常用的選擇策略是“比例選擇” 也就是個體被選中的概率與其適應(yīng)度函數(shù)值成正比。假設(shè)群體的個體總數(shù)是M， 那么那么一個體Xi被選中的概率為f(Xi)/( f(X1) + f(X2) + + f(Xn)比例選擇實現(xiàn)算法就是所謂的輪盤賭算法(Roulette Wheel Selection )， 輪盤賭算法的一個簡單的實現(xiàn)如下：日輪盤賭算法 /*按設(shè)定的概率，隨機(jī)選中一個個體* Pi表示第i個個體被選中的概率*/int RWS()(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) return i;電交叉(Crossover)： 2條染色體交換部分基因，來構(gòu)造下一代的2條新的染色 體。例如：交叉前：00000|011100000000|1000011100|000001111110|00101交叉后：00000|000001111110|1000011100|11100000000|00101染色體交叉是以一定的概率發(fā)生的，這個概率記為Pc。變異(Mutation)：在繁殖過程，新產(chǎn)生的染色體中的基因會以一定的

6、概率出錯， 稱為變異。變異發(fā)生的概率記為Pm。例如：變異前：000001110000000010000變異后：000001110000100010000適應(yīng)度函數(shù)(Fitness Function ):用于評價某個染色體的適應(yīng)度，用f(x) 表示。有時需要區(qū)分染色體的適應(yīng)度函數(shù)與問題的目標(biāo)函數(shù)。例如：0-1背包問 題的目標(biāo)函數(shù)是所取得物品價值，但將物品價值作為染色體的適應(yīng)度函數(shù)可能并 不一定適合。適應(yīng)度函數(shù)與目標(biāo)函數(shù)是正相關(guān)的，可對目標(biāo)函數(shù)作一些變形來得 到適應(yīng)度函數(shù)?；具z傳算法的偽代碼日基本遺傳算法偽代碼/*Pc：交叉發(fā)生的概率Pm：變異發(fā)生的概率M：種群規(guī)模G：終止進(jìn)化的代數(shù)Tf：進(jìn)化產(chǎn)

7、生的任何一個個體的適應(yīng)度函數(shù)超過Tf,則可以終止進(jìn)化過程*/初始化Pm，Pc，M，G，Tf等參數(shù)。隨機(jī)產(chǎn)生第一代種群Popdo(計算種群Pop中每一個體的適應(yīng)度F(i)。初始化空種群newPopdo(根據(jù)適應(yīng)度以比例選擇算法從種群Pop中選出2個個體if ( random ( 0 , 1 ) Pc )(對2個個體按交叉概率Pc執(zhí)行交叉操作if ( random ( 0 , 1 ) Pm )(對2個個體按變異概率Pm執(zhí)行變異操作將2個新個體加入種群newPop中 until ( M個子代被創(chuàng)建)用newPop取代Popuntil (任何染色體得分超過Tf，或繁殖代數(shù)超過G )基本遺傳算法優(yōu)化下面

8、的方法可優(yōu)化遺傳算法的性能。精英主義(Elitist Strategy)選擇：是基本遺傳算法的一種優(yōu)化。為了防 止進(jìn)化過程中產(chǎn)生的最優(yōu)解被交叉和變異所破壞，可以將每一代中的最優(yōu)解原封 不動的復(fù)制到下一代中。插入操作：可在3個基本操作的基礎(chǔ)上增加一個插入操作。插入操作將染 色體中的某個隨機(jī)的片段移位到另一個隨機(jī)的位置。五-使用AForge.Genetic解決TSP問題AForge.NET是一個C#實現(xiàn)的面向人工智能、計算機(jī)視覺等領(lǐng)域的開源架 構(gòu)。AForge.NET中包含有一個遺傳算法的類庫。AForge.NET 主頁：/AForge.NET 代碼下載：http:/code.google.Com

9、/p/aforge/介紹一下AForge的遺傳算法用法吧。AForge.Genetic的類結(jié)構(gòu)如下：GEPChromosomoiniISe LectidnMQtlwdLttL；rfacIFitncssFunctioni nterfac(? IChroDiostsmeG PTr(? sC hrouiosorafrElitoScRankSelRoulettBinaryChromosomeShortArrayChromosomeSimplcGmterfaceIGPGcnc株 ExtendsTimeSeriesPredictionFitnessSy&ibDlicRcffre-ssionFitnessO

10、pt imi zat ionFu nc t i on2DOptioiizati on Function IDPe rmu t at i ontJhr omo s.otne圖 1. AForge.Genetic 的類圖下面用AForge.Genetic寫個解決TSP問題的最簡單實例。測試數(shù)據(jù)集采用 網(wǎng)上流傳的中國31個省會城市的坐標(biāo)：電13042312 36391315 41772244 37121399 34881535 33261556 32381229 41961004 4312790 4386570 30071970 25621756 27881491 23811676 1332695

11、37151678 39182179 40612370 37802212 36762578 40292838 42632931 34291908 35072367 33942643 34393201 29353240 31403550 25452357 27782826 23702975 亳操作過程:下載AForge.NET類庫，網(wǎng)址： HYPERLINK http:/code.google.eom/p/aforge/downloads/list http:/code.google.eom/p/aforge/downloads/list創(chuàng)建C#空項目GenticTSP。然后在AForge目錄下找

12、到AForge.dll 和AForge.Genetic.dll,將其拷貝到TestTSP項目的bin/Debug目錄下。再 通過“Add Reference.”將這兩個DLL添加到工程。將31個城市坐標(biāo)數(shù)據(jù)保存為bin/Debug/Data.txt。添加 TSPFitnessFunction.cs，加入如下代碼：日 TSPFitnessFunction 類using System;using AForge.Genetic;namespace GenticTSP(/ Fitness function for TSP task (TravalingSalasman Problem) /public

13、class TSPFitnessFunction : IFitnessFunction(/ mapprivateint , map =null;/ Constructorpublic TSPFitnessFunction(int, map)(this.map = map;/ Evaluate chromosome - calculates its fitness value/publicdouble Evaluate(IChromosome chromosome)(return1/ (PathLength(chromosome) +1);/ Translate genotype to phen

14、otype/publicobject Translate(IChromosome chromosome)(return chromosome.ToString();/ Calculate path length represented by the specified chromosome/publicdouble PathLength(IChromosome chromosome)(/ salesman pathushort path = (PermutationChromosome)chromosome).Value;/ check path sizeif (path.Length !=

15、map.GetLength(0)(thrownew ArgumentException(Invalid path specified - not all cities are visited);/ path lengthint prev = path0;int curr = pathpath.Length -1;/ calculate distance between the last and the first citydouble dx = mapcurr, 0 - mapprev, 0;double dy = mapcurr, 1 - mapprev, 1;double pathLeng

16、th = Math.Sqrt(dx * dx + dy * dy);/ calculate the path length from the first city to the lastfor (int i =1, n = path.Length; i n; 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

17、city as previous prev = curr; return pathLength;牛(5)添加GenticTSP.cs，加入如下代碼：日GenticTSP 類using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.IO;using AForge;using AForge.Genetic;namespace GenticTSP(class GenticTSP(staticvoid Main()(StreamReader reader =new Str

18、eamReader(Data.txt)；int citiesCount =31; /城市數(shù)int , map =newint citiesCount, 2;for (int i =0; i citiesCount; i+)(string value = reader.ReadLine();string temp = value.Split();mapi, 0 =int.Parse(temp0); /讀取城市坐標(biāo) mapi, 1 =int.Parse(temp1);/ create fitness functionTSPFitnessFunctionfitnessFunction =new TSPFitnessFunction(map);int populationSize = 1000; /種群最大規(guī)模/*0： EliteSelection 算法1： RankSelection 算法其他：RouletteWheelSelection 算法*/int selectionMethod =0;/ create populationPopulationpopulation =new Populati