遺傳算法入門(mén)

優(yōu)化算法入門(mén)系列文章目錄(更新中)：模擬退火算法遺傳算法遺傳算法(GA,GeneticAlgorithm)，也稱(chēng)進(jìn)化算法。遺傳算法是受達(dá)爾文的進(jìn)化論的啟發(fā)，借鑒生物進(jìn)化過(guò)程而提出的一種啟發(fā)式搜索算法。因此在介紹遺傳算法前有必要簡(jiǎn)單的介紹生物進(jìn)化知識(shí)。進(jìn)化論知識(shí)作為遺傳算法生物背景的介紹，下面內(nèi)容了解即可：種群(Population)：生物的進(jìn)化以群體的形式進(jìn)行，這樣的一個(gè)群體稱(chēng)為種群。個(gè)體：組成種群的單個(gè)生物?；?Gene)：一個(gè)遺傳因子。染色體(Chromosome):包含一組的基因。生存競(jìng)爭(zhēng)，適者生存：對(duì)環(huán)境適應(yīng)度高的、牛B的個(gè)體參與繁殖的機(jī)會(huì)比較多，后代就會(huì)越來(lái)越多。適應(yīng)度低的個(gè)體參與繁殖的機(jī)會(huì)比較少，后代就會(huì)越來(lái)越少。遺傳與變異：新個(gè)體會(huì)遺傳父母雙方各一部分的基因，同時(shí)有一定的概率發(fā)生基因變異。簡(jiǎn)單說(shuō)來(lái)就是：繁殖過(guò)程，會(huì)發(fā)生基因交叉(Crossover)，基因突變(Mutation)，適應(yīng)度(Fitness)低的個(gè)體會(huì)被逐步淘汰，而適應(yīng)度高的個(gè)體會(huì)越來(lái)越多。那么經(jīng)過(guò)N代的自然選擇后，保存下來(lái)的個(gè)體都是適應(yīng)度很高的，其中很可能包含史上產(chǎn)生的適應(yīng)度最高的那個(gè)個(gè)體。遺傳算法思想借鑒生物進(jìn)化論，遺傳算法將要解決的問(wèn)題模擬成一個(gè)生物進(jìn)化的過(guò)程，通過(guò)復(fù)制、交叉、突變等操作產(chǎn)生下一代的解，并逐步淘汰掉適應(yīng)度函數(shù)值低的解，增加適應(yīng)度函數(shù)值高的解。這樣進(jìn)化N代后就很有可能會(huì)進(jìn)化出適應(yīng)度函數(shù)值很高的個(gè)體。舉個(gè)例子，使用遺傳算法解決“0-1背包問(wèn)題”的思路：0-1背包的解可以編碼為一串0-1字符串(0：不取，1：取)；首先，隨機(jī)產(chǎn)生M個(gè)0-1字符串，然后評(píng)價(jià)這些0-1字符串作為0-1背包問(wèn)題的解的優(yōu)劣；然后，隨機(jī)選擇一些字符串通過(guò)交叉、突變等操作產(chǎn)生下一代的M個(gè)字符串，而且較優(yōu)的解被選中的

概率要比較高。這樣經(jīng)過(guò)G代的進(jìn)化后就可能會(huì)產(chǎn)生出0-1背包問(wèn)題的一個(gè)“近似最優(yōu)解”。編碼：需要將問(wèn)題的解編碼成字符串的形式才能使用遺傳算法。最簡(jiǎn)單的一種編碼方式是二進(jìn)制編碼，即將問(wèn)題的解編碼成二進(jìn)制位數(shù)組的形式。例如，問(wèn)題的解是整數(shù)，那么可以將其編碼成二進(jìn)制位數(shù)組的形式。將0-1字符串作為0-1背包問(wèn)題的解就屬于二進(jìn)制編碼。遺傳算法有3個(gè)最基本的操作：選擇，交叉，變異。選擇：選擇一些染色體來(lái)產(chǎn)生下一代。一種常用的選擇策略是“比例選擇”，也就是個(gè)體被選中的概率與其適應(yīng)度函數(shù)值成正比。假設(shè)群體的個(gè)體總數(shù)是M，那么那么一個(gè)體Xi被選中的概率為f(Xi)/(f(X1)+f(X2)++f(Xn))。比例選擇實(shí)現(xiàn)算法就是所謂的“輪盤(pán)賭算法”(RouletteWheelSelection)，輪盤(pán)賭算法的一個(gè)簡(jiǎn)單的實(shí)現(xiàn)如下：國(guó)日輪盤(pán)賭算法/**按設(shè)定的概率，隨機(jī)選中一個(gè)個(gè)體*P[i]表示第i個(gè)個(gè)體被選中的概率*/intRWS()(m=0;r=Random(0,1);//r為0至1的隨機(jī)數(shù)for(i=1;i<=N;i++)(/*產(chǎn)生的隨機(jī)數(shù)在m~m+P[i]間則認(rèn)為選中了土*因此i被選中的概率是P[i]*/m=m+P[i];if(r<=m)returni;}}交叉(Crossover)：2條染色體交換部分基因，來(lái)構(gòu)造下一代的2條新的染色體。例如：交叉前：00000|011100000000|1000011100|000001111110|00101交叉后：00000|000001111110|10000

11100|011100000000|00101染色體交叉是以一定的概率發(fā)生的，這個(gè)概率記為Pc。變異(Mutation)：在繁殖過(guò)程，新產(chǎn)生的染色體中的基因會(huì)以一定的概率出錯(cuò)，稱(chēng)為變異。變異發(fā)生的概率記為Pm。例如：變異前：000001110000000010000變異后：000001110000100010000適應(yīng)度函數(shù)(FitnessFunction):用于評(píng)價(jià)某個(gè)染色體的適應(yīng)度，用f(x)表示。有時(shí)需要區(qū)分染色體的適應(yīng)度函數(shù)與問(wèn)題的目標(biāo)函數(shù)。例如：0-1背包問(wèn)題的目標(biāo)函數(shù)是所取得物品價(jià)值，但將物品價(jià)值作為染色體的適應(yīng)度函數(shù)可能并不一定適合。適應(yīng)度函數(shù)與目標(biāo)函數(shù)是正相關(guān)的，可對(duì)目標(biāo)函數(shù)作一些變形來(lái)得到適應(yīng)度函數(shù)?；具z傳算法的偽代碼田日基本遺傳算法偽代碼/*Pc：交叉發(fā)生的概率Pm：變異發(fā)生的概率M：種群規(guī)模G：終止進(jìn)化的代數(shù)Tf：進(jìn)化產(chǎn)生的任何一個(gè)個(gè)體的適應(yīng)度函數(shù)超過(guò)Tf，則可以終止進(jìn)化過(guò)程*/初始化Pm，Pc，M，G，Tf等參數(shù)。隨機(jī)產(chǎn)生第一代種群Popdo(計(jì)算種群Pop中每一個(gè)體的適應(yīng)度F(i)。初始化空種群newPopdo(根據(jù)適應(yīng)度以比例選擇算法從種群Pop中選出2個(gè)個(gè)體if(random(0,1)<Pc)(對(duì)2個(gè)個(gè)體按交叉概率Pc執(zhí)行交叉操作

if(random(0,1)<Pm)(對(duì)2個(gè)個(gè)體按變異概率Pm執(zhí)行變異操作}將2個(gè)新個(gè)體加入種群newPop中}until(M個(gè)子代被創(chuàng)建)用newPop取代Pop}until(任何染色體得分超過(guò)Tf，或繁殖代數(shù)超過(guò)G)基本遺傳算法優(yōu)化下面的方法可優(yōu)化遺傳算法的性能。精英主義(ElitistStrategy)選擇：是基本遺傳算法的一種優(yōu)化。為了防止進(jìn)化過(guò)程中產(chǎn)生的最優(yōu)解被交叉和變異所破壞，可以將每一代中的最優(yōu)解原封不動(dòng)的復(fù)制到下一代中。插入操作：可在3個(gè)基本操作的基礎(chǔ)上增加一個(gè)插入操作。插入操作將染色體中的某個(gè)隨機(jī)的片段移位到另一個(gè)隨機(jī)的位置。五-使用AForge.Genetic解決TSP問(wèn)題AForge.NET是一個(gè)C#實(shí)現(xiàn)的面向人工智能、計(jì)算機(jī)視覺(jué)等領(lǐng)域的開(kāi)源架構(gòu)。AForge.NET中包含有一個(gè)遺傳算法的類(lèi)庫(kù)。AForge.NET主頁(yè)：/AForge.NET代碼下載：http://code.google.Com/p/aforge/介紹一下AForge的遺傳算法用法吧。AForge.Genetic的類(lèi)結(jié)構(gòu)如下:

圖1.AForge.Genetic的類(lèi)圖下面用AForge.Genetic寫(xiě)個(gè)解決TSP問(wèn)題的最簡(jiǎn)單實(shí)例。測(cè)試數(shù)據(jù)集采用網(wǎng)上流傳的中國(guó)31個(gè)省會(huì)城市的坐標(biāo)：13042312363913154177224437121399348815353326155632381229419610044312790438657030071970256217562788149123811676133269537151678391821794061237037802212367625784029283842632931342919083507236733942643343932012935324031403550254523572778282623702975操作過(guò)程：下載AForge.NET類(lèi)庫(kù)，網(wǎng)址：http://code.google.eom/p/aforge/downloads/list創(chuàng)建C#空項(xiàng)目GenticTSP。然后在AForge目錄下找到AForge.dll和AForge.Genetic.dll，將其拷貝到TestTSP項(xiàng)目的bin/Debug目錄下。再通過(guò)“AddReference..."將這兩個(gè)DLL添加到工程。將31個(gè)城市坐標(biāo)數(shù)據(jù)保存為bin/Debug/Data.txt。添加TSPFitnessFunction.cs，加入如下代碼：

TSPFitnessFunction類(lèi)usingSystem;usingAForge.Genetic;namespaceGenticTSP(///<summary>///FitnessfunctionforTSPtask(TravalingSalasmanProblem)///</summary>publicclassTSPFitnessFunction:IFitnessFunction(//mapprivateint[,]map=null;//ConstructorpublicTSPFitnessFunction(int[,]map)(this.map=map;}///<summary>///Evaluatechromosome-calculatesitsfitnessvalue///</summary>publicdoubleEvaluate(IChromosomechromosome)(return1/(PathLength(chromosome)+1);}///<summary>///Translategenotypetophenotype///</summary>publicobjectTranslate(IChromosomechromosome)(returnchromosome.ToString();}///<summary>///Calculatepathlengthrepresentedbythespecifiedchromosome///</summary>publicdoublePathLength(IChromosomechromosome)(//salesmanpathushort[]path=((PermutationChromosome)chromosome).Value;

//checkpathsizeif(path.Length!=map.GetLength(0))(thrownewArgumentException("Invalidpathspecified-notallcitiesarevisited");}//pathlengthintprev=path[0];intcurr=path[path.Length-1];//calculatedistancebetweenthelastandthefirstcitydoubledx=map[curr,0]-map[prev,0];doubledy=map[curr,1]-map[prev,1];doublepathLength=Math.Sqrt(dx*dx+dy*dy);//calculatethepathlengthfromthefirstcitytothelastfor(inti=1,n=path.Length;i<n;i++)(//getcurrentcitycurr=path[i];//calculatedistancedx=map[curr,0]-map[prev,0];dy=map[curr,1]-map[prev,1];pathLength+=Math.Sqrt(dx*dx+dy*dy);//putcurrentcityaspreviousprev=curr;}returnpathLength;}}}(5)添加GenticTSP.cs，加入如下代碼:GenticTSP類(lèi)usingSystem;usingSystem.Collections.Generic;

usingSystem.Linq;usingSystem.Text;usingSystem.IO;usingAForge;usingAForge.Genetic;namespaceGenticTSP(classGenticTSP(staticvoidMain()(StreamReaderreader=newStreamReader("Data.txt");intcitiesCount=31;//城市數(shù)int[,]map=newint[citiesCount,2];for(inti=0;i<citiesCount;i++)(stringvalue=reader.ReadLine();string[]temp=value.Split('');map[i,0]=int.Parse(temp[0]);//讀取城市坐標(biāo)map[i,1]=int.Parse(temp[1]);}//createfitnessfunctionTSPFitnessFunctionfitnessFunction=newTSPFitnessFunction(map);intpopulationSize=1000;//種群最大規(guī)模/*0：EliteSelection算法1：RankSelection算法其他：RouletteWheelSelection算法**/intselectionMethod=0;//createpopulationPopulationpopulation=newPopulation(populationSize,newPermutationChromosome(citiesCount),

fitnessFunction,(selectionMethod==0)?(ISelectionMethod)newEliteSelection():(selectionMethod==1)?(ISelectionMethod)newRankSelection():(ISelectionMethod)newRouletteWheelSelection());//iterationsintiter=1;intiterations=5000;//迭代最大周期//loopwhile(iter<iterations)(//runoneepochofgeneticalgorithmpopulation.RunEpoch();//increasecurrentiterationiter++;}System.Console.WriteLine"遍歷路徑是:{0}",((PermutationChromosome)population.BestChromosome).ToString());System.Console.WriteLine"總路程是:{0}",fitnessFunction.PathLength(population.BestChromosome));System.Console.Read();}}}網(wǎng)上據(jù)稱(chēng)這組TSP數(shù)據(jù)的最好的結(jié)果是15404，上面的程序我剛才試了幾次最好一次算出了15402.341，但是最差的時(shí)候也跑出了大于16000的結(jié)果。我這還有一個(gè)版本，設(shè)置種群規(guī)模為1000，迭代5000次可以算出15408.508這個(gè)結(jié)果。源代碼在文章最后可以下載?？偨Y(jié)一下使用AForge.Genetic解決問(wèn)題的一般步驟：定義適應(yīng)函數(shù)類(lèi)，需要實(shí)現(xiàn)IFitnessFunction接口選定種群規(guī)模、使用的選擇算法、染色體種類(lèi)等參數(shù)，創(chuàng)建種群population

(3)設(shè)定迭代的最大次數(shù)，使用RunEpoch開(kāi)始計(jì)算本文源代碼下載本文源代碼下載分類(lèi)：機(jī)器學(xué)習(xí)優(yōu)化算法入門(mén)系列文章目錄(更新中):模擬退火算法遺傳算法一.爬山算法(HillClimbing)介紹模擬退火前，先介紹爬山算法。爬山算法是一種簡(jiǎn)單的貪心搜索算法，該算法每次從當(dāng)前解的臨近解空間中選擇一個(gè)最優(yōu)解作為當(dāng)前解，直到達(dá)到一個(gè)局部最優(yōu)解。爬山算法實(shí)現(xiàn)很簡(jiǎn)單，其主要缺點(diǎn)是會(huì)陷入局部最優(yōu)解，而不一定能搜索到全局最優(yōu)解。如圖1所示：假設(shè)C點(diǎn)為當(dāng)前解，爬山算法搜索到A點(diǎn)這個(gè)局部最優(yōu)解就會(huì)停止搜索，因?yàn)樵贏點(diǎn)無(wú)論向那個(gè)方向小幅度移動(dòng)都不能得到更優(yōu)的解。二.模擬退火(SA,SimulatedAnnealing)思想爬山法是完完全全的貪心法，每次都鼠目寸光的選擇一個(gè)當(dāng)前最優(yōu)解，因此只能搜索到局部的最優(yōu)值。模擬退火其實(shí)也是一種貪心算法，但是它的搜索過(guò)程引入了隨機(jī)因素。模擬退火算法以一定的概率來(lái)接受一個(gè)比當(dāng)前解要差的解，因此有可能會(huì)跳出這個(gè)局部的最優(yōu)解，達(dá)到全局的最優(yōu)解。以圖1為例，模擬退火算法在搜索到局部最優(yōu)解A后，會(huì)以一定的概率接受到E的移動(dòng)。也許經(jīng)過(guò)幾次這樣的不是局部最優(yōu)的移動(dòng)后會(huì)到達(dá)D點(diǎn)，于是就跳出了局部最大值A(chǔ)。模擬退火算法描述：若J(Y(i+1))>=J(Y(i))(即移動(dòng)后得到更優(yōu)解)，則總是接受該移動(dòng)若J(Y(i+1))<J(Y(i))(即移動(dòng)后的解比當(dāng)前解要差)，則以一定的概率接受移動(dòng)，而且這個(gè)概率隨著時(shí)間推移逐漸降低(逐漸降低才能趨向穩(wěn)定)這里的“一定的概率”的計(jì)算參考了金屬冶煉的退火過(guò)程，這也是模擬退火算法名稱(chēng)的由來(lái)。

根據(jù)熱力學(xué)的原理，在溫度為T(mén)時(shí)，出現(xiàn)能量差為dE的降溫的概率為P(dE)，表示為：P(dE)=exp(dE/(kT))其中k是一個(gè)常數(shù)，exp表示自然指數(shù)，且dE<0。這條公式說(shuō)白了就是：溫度越高，出現(xiàn)一次能量差為dE的降溫的概率就越大；溫度越低，則出現(xiàn)降溫的概率就越小。又由于dE總是小于0(否則就不叫退火了)，因此dE/kT<0，所以P(dE)的函數(shù)取值范圍是(0,1)。隨著溫度T的降低，P(dE)會(huì)逐漸降低。我們將一次向較差解的移動(dòng)看做一次溫度跳變過(guò)程，我們以概率P(dE)來(lái)接受這樣的移動(dòng)。關(guān)于爬山算法與模擬退火，有一個(gè)有趣的比喻：爬山算法：兔子朝著比現(xiàn)在高的地方跳去。它找到了不遠(yuǎn)處的最高山峰。但是這座山不一定是珠穆朗瑪峰。這就是爬山算法，它不能保證局部最優(yōu)值就是全局最優(yōu)值。模擬退火：兔子喝醉了。它隨機(jī)地跳了很長(zhǎng)時(shí)間。這期間，它可能走向高處，也可能踏入平地。但是，它漸漸清醒了并朝最高方向跳去。這就是模擬退火。下面給出模擬退火的偽代碼表示。三.模擬退火算法偽代碼代碼/*J(y)：在狀態(tài)y時(shí)的評(píng)價(jià)函數(shù)值Y(i)：表示當(dāng)前狀態(tài)Y(i+1)：表示新的狀態(tài)r：用于控制降溫的快慢T：系統(tǒng)的溫度，系統(tǒng)初始應(yīng)該要處于一個(gè)高溫的狀態(tài)T_min:溫度的下限，若溫度T達(dá)到T_min，則停止搜索*/while(T>T_min)(dE=J