1、.遺傳算法簡述及代碼詳解聲明：本文內(nèi)容整理自網(wǎng)絡(luò),認(rèn)為原作者同意轉(zhuǎn)載,如有冒犯請聯(lián)系我。遺傳算法基本內(nèi)容遺傳算法為群體優(yōu)化算法,也就是從多個(gè)初始解開始進(jìn)行優(yōu)化,每個(gè)解稱為一個(gè)染色體,各染色體之間通過競爭、合作、單獨(dú)變異,不斷進(jìn)化。遺傳學(xué)與遺傳算法中的基礎(chǔ)術(shù)語比較染色體 數(shù)據(jù),數(shù)組,序列基因單個(gè)元素,位等位基因數(shù)據(jù)值,屬性,值基因座 位置,iterator位置表現(xiàn)型 參數(shù)集,解碼結(jié)構(gòu),候選解染色體：又可以叫做基因型個(gè)體群體/種群：一定數(shù)量的個(gè)體組成,及一定數(shù)量的染色體組成,群體中個(gè)體的數(shù) 量叫做群體大小。初始群體：若干染色體的集合,即解的規(guī)模,如30,50等,認(rèn)為是隨機(jī)選取的數(shù)據(jù)集合。適應(yīng)度：各

2、個(gè)個(gè)體對環(huán)境的適應(yīng)程度優(yōu)化時(shí)先要將實(shí)際問題轉(zhuǎn)換到遺傳空間,就是把實(shí)際問題的解用染色體表示,稱為編碼,反過程為解碼/譯碼,因?yàn)閮?yōu)化后要進(jìn)行評(píng)價(jià)此時(shí)得到的解是否較之前解優(yōu)越,所以要返回問題空間,故要進(jìn)行解碼。SGA采用二進(jìn)制編碼,染色體就是二進(jìn)制位串,每一位可稱為一個(gè)基因；如果直接生成二進(jìn)制初始種群,則不必有編碼過程,但要求解碼時(shí)將染色體解碼到問題可行域內(nèi)。遺傳算法的準(zhǔn)備工作: 數(shù)據(jù)轉(zhuǎn)換操作,包括表現(xiàn)型到基因型的轉(zhuǎn)換和基因型到表現(xiàn)型的轉(zhuǎn)換。前者是把求解空間中的參數(shù)轉(zhuǎn)化成遺傳空間中的染色體或者個(gè)體,后者是它的逆操作2確定適應(yīng)度計(jì)算函數(shù),可以將個(gè)體值經(jīng)過該函數(shù)轉(zhuǎn)換為該個(gè)體的適應(yīng)度,該適應(yīng)度的高低要能充

3、分反映該個(gè)體對于解得優(yōu)秀程度。非常重要的過程。遺傳算法基本過程為:1 編碼,創(chuàng)建初始群體2 群體中個(gè)體適應(yīng)度計(jì)算3 評(píng)估適應(yīng)度4 根據(jù)適應(yīng)度選擇個(gè)體5 被選擇個(gè)體進(jìn)行交叉繁殖6 在繁殖的過程中引入變異機(jī)制7 繁殖出新的群體,回到第二步實(shí)例一：建議先看實(shí)例二求 范圍內(nèi)的的最小值1 編碼算法選擇為將轉(zhuǎn)化為2進(jìn)制的串,串的長度為5位串的長度根據(jù)解的精度設(shè)定,串長度越長解得精度越高。2 計(jì)算適應(yīng)度的方法是：先將個(gè)體串進(jìn)行解碼,轉(zhuǎn)化為int型的x值,然后使用作為其適應(yīng)度計(jì)算合適。需要說明,將原目標(biāo)函數(shù)設(shè)置為適應(yīng)度函數(shù)是一種選擇,但未必是最貼切的方法。3 正式開始,先設(shè)置群體大小為4,然后初始化群體 =

4、4 計(jì)算適應(yīng)度Fi 計(jì)算每個(gè)個(gè)體的選擇概率,選擇概率要能夠反映個(gè)體的優(yōu)秀程度。這里用一個(gè)很簡單的方法來確定選擇概率 6 選擇根據(jù)所有個(gè)體的選擇概率進(jìn)行淘汰選擇。這里使用的是一個(gè)賭輪的方式進(jìn)行淘汰選擇。先按照每個(gè)個(gè)體的選擇概率創(chuàng)建一個(gè)賭輪,然后選取4次,每次先產(chǎn)生一個(gè)0-1的隨機(jī)小數(shù),然后判斷該隨機(jī)數(shù)落在那個(gè)段內(nèi)就選取相對應(yīng)的個(gè)體。這個(gè)過程中,選取概率高的個(gè)體將可能被多次選擇,而概率低的就可能被淘汰。下面是一個(gè)簡單的賭輪的例子 13% 35% 15% 37% -|-|-|-|個(gè)體1 個(gè)體2 個(gè)體3 0.67 個(gè)體4隨機(jī)數(shù)為0.67落在了個(gè)體4的端內(nèi),本次選擇了個(gè)體4。被選中的個(gè)體將進(jìn)入配對庫準(zhǔn)備

5、開始繁殖。7 簡單交叉先對配對庫中的個(gè)體進(jìn)行隨機(jī)配對,然后在配對的2個(gè)個(gè)體中設(shè)置交叉點(diǎn),交換2個(gè)個(gè)體的信息后產(chǎn)生下一代。比如 -交叉- -交叉- 2個(gè)父代的個(gè)體在交叉后繁殖出了下一代的同樣數(shù)量的個(gè)體.復(fù)雜的交叉在交叉的位置,交叉的方法,雙親的數(shù)量上都可以選擇.其目的都在于盡可能的培育出更優(yōu)秀的后代8 變異變異操作時(shí)按照基因座來的,比如說每計(jì)算2萬個(gè)基因座就發(fā)生一個(gè)變異變異的結(jié)果是基因座上的等位基因發(fā)生了變化。我們這里的例子就是把0變成1或則1變成0。至此,我們已經(jīng)產(chǎn)生了一個(gè)新的群體,然后回到第4步,周而復(fù)始,生生不息下去。實(shí)例二：為了便于理解,手工計(jì)算來簡單地模擬遺傳算法的各個(gè)主要執(zhí)行步驟：個(gè)

6、體編碼遺傳算法的運(yùn)算對象是表示個(gè)體的符號(hào)串,所以必須把變量 x1, x2 編碼為一種符號(hào)串。本題中,用無符號(hào)二進(jìn)制整數(shù)編碼方式較多來表示。因 x1, x2 為 0 7之間的整數(shù),所以分別用3位無符號(hào)二進(jìn)制整數(shù)來表示,將它們連接在一起所組成的6位無符號(hào)二進(jìn)制數(shù)就形成了個(gè)體的基因型,表示一個(gè)可行解。例如,基因型 X101110 所對應(yīng)的表現(xiàn)型是：x 5,6 。個(gè)體的表現(xiàn)型x和基因型X之間可通過編碼和解碼程序相互轉(zhuǎn)換。初始群體的產(chǎn)生 遺傳算法是對群體進(jìn)行的進(jìn)化操作,需要給其淮備一些表示起始搜索點(diǎn)的初始群體數(shù)據(jù)。 本例中,群體規(guī)模的大小隨機(jī)選取取為4,即群體由4個(gè)個(gè)體組成,每個(gè)個(gè)體可通過隨機(jī)方法產(chǎn)生。

7、 如：011101,101011,011100,111001適應(yīng)度汁算 遺傳算法中以個(gè)體適應(yīng)度的大小來評(píng)定各個(gè)個(gè)體的優(yōu)劣程度,從而決定其遺傳機(jī)會(huì)的大小。 本例中,目標(biāo)函數(shù)總?cè)》秦?fù)值,并且是以求函數(shù)最大值為優(yōu)化目標(biāo),故可直接利用目標(biāo)函數(shù)值作為個(gè)體的適應(yīng)度適應(yīng)度函數(shù)可以有許多。選擇運(yùn)算 選擇運(yùn)算把當(dāng)前群體中適應(yīng)度較高的個(gè)體按某種規(guī)則或模型遺傳到下一代群體中。一般要求適應(yīng)度較高的個(gè)體將有更多的機(jī)會(huì)遺傳到下一代群體中。本例中,我們采用與適應(yīng)度成正比的概率來確定各個(gè)個(gè)體復(fù)制到下一代群體中的數(shù)量。其具體操作過程是： 先計(jì)算出群體中所有個(gè)體的適應(yīng)度的總和 ； 其次計(jì)算出每個(gè)個(gè)體的相對適應(yīng)度的大小,它即為每個(gè)

8、個(gè)體被遺傳到下一代群體中的概率； 每個(gè)概率值組成一個(gè)區(qū)域,全部概率值之和為1； 最后再產(chǎn)生一個(gè)0到1之間的隨機(jī)數(shù),依據(jù)該隨機(jī)數(shù)出現(xiàn)在上述哪一個(gè)概率區(qū)域內(nèi)來確定各個(gè)個(gè)體被選中的次數(shù)。詳見下圖 交叉運(yùn)算 交叉運(yùn)算是遺傳算法中產(chǎn)生新個(gè)體的主要操作過程,它以某一概率相互交換某兩個(gè)個(gè)體之間的部分染色體。 本例采用單點(diǎn)交叉的方法,其具體操作過程是： 先對群體進(jìn)行隨機(jī)配對； 其次隨機(jī)設(shè)置交叉點(diǎn)位置； 最后再相互交換配對染色體之間的部分基因。 變異運(yùn)算 變異運(yùn)算是對個(gè)體的某一個(gè)或某一些基因座上的基因值按某一較小的概率進(jìn)行改變,它也是產(chǎn)生新個(gè)體的一種操作方法。 本例中,我們采用基本位變異的方法來進(jìn)行變異運(yùn)算,其

9、具體操作過程是： 首先確定出各個(gè)個(gè)體的基因變異位置,下表所示為隨機(jī)產(chǎn)生的變異點(diǎn)位置, 其中的數(shù)字表示變異點(diǎn)設(shè)置在該基因座處； 然后依照某一概率將變異點(diǎn)的原有基因值取反。對群體P進(jìn)行一輪選擇、交叉、變異運(yùn)算之后可得到新一代的群體p。從上表中可以看出,群體經(jīng)過一代進(jìn)化之后,其適應(yīng)度的最大值、平均值都得到了明顯的改進(jìn)。事實(shí)上,這里已經(jīng)找到了最佳個(gè)體111111。注意 需要說明的是,表中有些欄的數(shù)據(jù)是隨機(jī)產(chǎn)生的。這里為了更好地說明問題,我們特意選擇了一些較好的數(shù)值以便能夠得到較好的結(jié)果,而在實(shí)際運(yùn)算過程中,有可能需要一定的循環(huán)次數(shù)才能達(dá)到這個(gè)最優(yōu)結(jié)果。選擇要能夠合理的反映適者生存的自然法則,而交叉必須

10、將有利的基因盡量遺傳給下一代 算法過程當(dāng)中有幾個(gè)隨機(jī)過程：初始種群的產(chǎn)生是隨機(jī)產(chǎn)生,但有時(shí)為了更好迭代,知道解在某一個(gè)值附近,可以認(rèn) 為設(shè)定初始種群確定個(gè)體被選中次數(shù)時(shí),運(yùn)用到輪賭法,其產(chǎn)生的數(shù)據(jù)為隨機(jī)數(shù)據(jù)交叉點(diǎn)變異點(diǎn)偽代碼:/Init populationforeach individual in population individual = EncodeRandom;while /計(jì)算個(gè)體適應(yīng)度 int TotalF = 0; foreach individual in population individual.F = 1000 - Decode-102; TotalF += indi

11、vidual.F; /-選擇過程,計(jì)算個(gè)體選擇概率- foreach individual in population individual.P = individual.F / TotalF; /選擇 forint i=0;i /SelectIndividual是根據(jù)隨機(jī)數(shù)落在段落計(jì)算選取哪個(gè)個(gè)體的函數(shù) MatingPooli = populationSelectIndividualRandom; /-簡單交叉- /由于只有4個(gè)個(gè)體,配對2次 forint i=0;i MatingPool.Parentsi.Mother = MatingPool.RandomPop; MatingPool.

12、Parentsi.Father = MatingPool.RandomPop; /交叉后創(chuàng)建新的集團(tuán) population.Clean; foreach Parent in MatingPool.Parents /注意在copy 雙親的染色體時(shí)在某個(gè)基因座上發(fā)生的變異未表現(xiàn). child1 = Parent.Mother.DivHeader + Parent.Father.DivEnd; child2 = Parent.Father.DivHeader + Parent.Mother.DivEnd; population.push; population.push; 完整代碼如下：#inclu

13、destdafx.h#include#include#include#definePOPSIZE 500#defineMAXIMIZATION 1 /求解函數(shù)為求最大值#defineMINIMIZATION 2 /求解函數(shù)為求最小值#defineCmax 100 /求解最大值時(shí)適應(yīng)度函數(shù)的基準(zhǔn)數(shù)#defineCmin 0 /求解最小值時(shí)適應(yīng)度函數(shù)的基準(zhǔn)數(shù) #defineLENGTH1 10 /每一個(gè)解用位基因表示#defineLENGTH2 10 #defineCHROMLENGTHLENGTH1+LENGTH2intFunctionMode=MAXIMIZATION; /函數(shù)值求解類型是最大

14、值intPopSize=80; /種群規(guī)模intMaxGeneration =100; /最大世代數(shù),即最大迭代數(shù)doublePc = 0.6; /變異概率doublePm = 0.001; /交叉概率structindividual/定義個(gè)體charchromCHROMLENGTH+1; /個(gè)體數(shù)doublevalue; /個(gè)體對應(yīng)的變量值doublefitness; /個(gè)體適應(yīng)度;intgeneration;intbest_index;intworst_index;structindividualbestindividual;structindividualworstindividual;

15、structindividualcurrentbest;structindividualpopulationPOPSIZE;voidGenerateInitialPopulation;/初始種群生成voidGenerateNextPopulation; /產(chǎn)生下一代種群voidEvaluatePopulation;voidCalculateObjectValue; longDecodeChromosome; /譯碼voidCalculateFitnessValue; voidFindBestAndWorstIndividual; voidPerformEvolution;voidSelecti

16、onOperator;voidCrossoverOperator; voidMutationOperator;voidOutputTextReport;voidmaingeneration=0; GenerateInitialPopulation; /初始種群生成EvaluatePopulation; /計(jì)算種群值,即計(jì)算種群適應(yīng)度whilegeneration generation+; GenerateNextPopulation; /產(chǎn)生下一代種群EvaluatePopulation; /計(jì)算種群值,即計(jì)算種群適應(yīng)度PerformEvolution; OutputTextReport; v

17、oidGenerateInitialPopulation /隨機(jī)產(chǎn)生初始種群,且用0,1表示inti,j; fori=0;i forj=0;jpopulationi.chromj=rand%10?0:1; /rand%n產(chǎn)生一個(gè) / n-1的數(shù)populationi.chromCHROMLENGTH=0; voidGenerateNextPopulation SelectionOperator;CrossoverOperator;MutationOperator;voidEvaluatePopulation CalculateObjectValue; CalculateFitnessValue

18、; FindBestAndWorstIndividual; longDecodeChromosome /譯碼,換算為十進(jìn) /制數(shù)inti;longdecimal=0L;char *pointer;fori=0,pointer=string+point;idecimal+=; /移位操作,染色體實(shí)現(xiàn)十進(jìn) /制化 return; voidCalculateObjectValue /計(jì)算函數(shù)值 inti;longtemp1,temp2;doublex1,x2;for i=0;i /從染色體中讀取基因temp1=DecodeChromosome; temp2=DecodeChromosome;x1=4

19、.0*temp1; /xa, b；x2=4.0*temp2; / populationi.value=100*x2;/ 函數(shù)表達(dá)式voidCalculateFitnessValue /針對不同函數(shù)類型計(jì)算個(gè)體適應(yīng)度inti;doubletemp;for i=0;iif /函數(shù)類型為求解最大值 if0.0temp=Cmin+populationi.value;elsetemp=0.0;elseif /函數(shù)類型為求解最小值ifpopulationi.valuetemp=Cmax-populationi.value;elsetemp=0.0;populationi.fitness=temp;void

20、FindBestAndWorstIndividual inti;doublesum=0.0;bestindividual=population0;worstindividual=population0;for i=1;iif bestindividual.fitness bestindividual=populationi;best_index=i;elseif populationi.fitness worstindividual=populationi;worst_index=i;sum+=populationi.fitness; if currentbest=bestindividual

21、; elseif=currentbest.fitness currentbest=bestindividual;voidPerformEvolution /執(zhí)行進(jìn)化if currentbest.fitnesscurrentbest=populationbest_index;elsepopulationworst_index=currentbest;voidSelectionOperator /選取最優(yōu)進(jìn)化代inti,index;doublep,sum=0.0; doublecfitnessPOPSIZE; structindividualnewpopulationPOPSIZE; fori=0;i sum+=populationi.fitness; fori=0;icfitnessi=populationi.fitness/sum; / 個(gè)體的適應(yīng)度比例 fori=1;icfitnessi=cfitnessi-1+cfitnessi; for i=0;i p=rand%1000/1000.0; index=0;while cfitnessindexindex+;newpopulationi=populationindex; fori=0;ipopulationi=newpopulationi; voidCrossoverOperator /染色體交叉i