遺傳算法簡(jiǎn)介及代碼詳解(優(yōu).選)

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

2、染色體組成，群體中個(gè)體的數(shù)量叫做群體大小。初始群體：若干染色體的集合，即解的規(guī)模，如30, 50等，認(rèn)為是隨機(jī)選取的數(shù)據(jù)集合。適應(yīng)度（fitness）:各個(gè)個(gè)體對(duì)環(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)備工作：1）數(shù)據(jù)轉(zhuǎn)換操作，包括表現(xiàn)型到基因型的轉(zhuǎn)換和基因型到表現(xiàn)型的轉(zhuǎn)換

3、。前者是把求解空間中的參數(shù)轉(zhuǎn)化成遺傳空間中的染色體或者個(gè)體（encoding），后者是它的逆操作（decodi ng）2）確定適應(yīng)度計(jì)算函數(shù)，可以將個(gè)體值經(jīng)過該函數(shù)轉(zhuǎn)換為該個(gè)體的適應(yīng)度，該適應(yīng)度 的高低要能充分反映該個(gè)體對(duì)于解得優(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í)例二）求 x 0,30 范圍內(nèi)的 y x 10 2 的最小值1）編碼算法選擇為”將X轉(zhuǎn)化為2進(jìn)制的串”，串的長(zhǎng)度為5位（串的長(zhǎng)度根據(jù)解的精

4、度設(shè)定，串長(zhǎng)度越長(zhǎng)解得精度越高） 。（等位基因的值為 0 or 1）。22）計(jì)算適應(yīng)度的方法是： 先將個(gè)體串進(jìn)行解碼， 轉(zhuǎn)化為 int 型的 x 值，然后使用 y x 102作為其適應(yīng)度計(jì)算合適 （由于是最小值，所以結(jié)果越小，適應(yīng)度也越好）。需要說明 ，將原目標(biāo)函數(shù)設(shè)置為適應(yīng)度函數(shù)是一種選擇，但未必是最貼切的方法。3）正式開始，先設(shè)置群體大小為 4，然后初始化群體 = （在0， 31 范圍內(nèi)隨機(jī)選取 4 個(gè)整數(shù)就可以編碼 ）4）計(jì)算適應(yīng)度Fi（由于是求解最小值，可以選取一個(gè)大的基準(zhǔn)線1000Fi 1000 x 10 2 ）5）計(jì)算每個(gè)個(gè)體的選擇概率，選擇概率要能夠反映個(gè)體的優(yōu)秀程度。這里用一個(gè)

5、很簡(jiǎn)單的方法來確定選擇概率p Fi / TOTAL （Fi ）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)就選取相對(duì)應(yīng)的個(gè)體。這個(gè)過程中，選取概率p 高的個(gè)體將可能被多次選擇，而概率低的就可能被淘汰。下面是一個(gè)簡(jiǎn)單的賭輪的例子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)入配對(duì)庫(kù) （mating pool ，配對(duì)群體 ）準(zhǔn)備開始繁殖。7）簡(jiǎn)

6、單交叉先對(duì)配對(duì)庫(kù)中的個(gè)體進(jìn)行隨機(jī)配對(duì)， 然后在配對(duì)的 2個(gè)個(gè)體中設(shè)置交叉點(diǎn)， 交換 2 個(gè)個(gè)體的 信息后產(chǎn)生下一代。比如 （ | 代表簡(jiǎn)單串的交叉位置 ）（ 0110|1， 1100|0 ） -交叉- （01100， 11001）（ 01|000， 11|011 ） -交叉- （01011 ， 11000）2 個(gè)父代的個(gè)體在交叉后繁殖出了下一代的同樣數(shù)量的個(gè)體 . 復(fù)雜的交叉在交叉的位置，交叉的方法，雙親的數(shù)量上都可以選擇.其目的都在于盡可能的培育出更優(yōu)秀的后代8）變異變異操作時(shí)按照基因座來的，比如說每計(jì)算 2 萬個(gè)基因座就發(fā)生一個(gè)變異（我們現(xiàn)在的每個(gè)個(gè)體有 5 個(gè)基因座。也就是說要進(jìn)化 10

7、00 代后才會(huì)在其中的某個(gè)基因座發(fā)生一次變異 ）變異 的結(jié)果是基因座上的等位基因發(fā)生了變化。我們這里的例子就是把0變成 1 或則 1 變成 0。至此， 我們已經(jīng)產(chǎn)生了一個(gè)新的 （下一代）群體， 然后回到第 4 步，周而復(fù)始， 生生不息下去。實(shí)例二：為了便于理解，手工計(jì)算來簡(jiǎn)單地模擬遺傳算法的各個(gè)主要執(zhí)行步驟:lUilX遍）f十時(shí)M 百e 九加汀x2 e（1 ）個(gè)體編碼遺傳算法的運(yùn)算對(duì)象是表示個(gè)體的符號(hào)串，所以必須把變量x1, x2 編碼為一種符號(hào)串。本題中，用無符號(hào)二進(jìn)制整數(shù)（編碼方式較多）來表示。因x1, x2 為0 7之間的整數(shù)，所以分別用3位無符號(hào)二進(jìn)制整數(shù)來表示，將它們連接在一起所組成

8、的6位無符號(hào)二進(jìn)制數(shù)就形成了個(gè)體的基因型，表示一個(gè)可行解。例如，基因型 X = 101110 所對(duì)應(yīng)的表現(xiàn)型是：x = 5 , 6 。個(gè)體的表現(xiàn)型x和基因型X之間可通過編碼和解碼程序相互轉(zhuǎn)換。（2）初始群體的產(chǎn)生遺傳算法是對(duì)群體進(jìn)行的進(jìn)化操作，需要給其淮備一些表示起始搜索點(diǎn)的初始群體數(shù) 據(jù)。本例中，群體規(guī)模的大小（隨機(jī)選?。┤?4，即群體由4個(gè)個(gè)體組成，每個(gè)個(gè)體可通 過隨機(jī)方法產(chǎn)生。女口： 011101, 101011, 011100, 111001（3）適應(yīng)度汁算遺傳算法中以個(gè)體適應(yīng)度的大小來評(píng)定各個(gè)個(gè)體的優(yōu)劣程度，從而決定其遺傳機(jī)會(huì)的大小。本例中，目標(biāo)函數(shù)總?cè)》秦?fù)值， 并且是以求函數(shù)最大

9、值為優(yōu)化目標(biāo)，故可直接利用目標(biāo)函數(shù)值作為個(gè)體的適應(yīng)度（適應(yīng)度函數(shù)可以有許多）（4）選擇運(yùn)算選擇運(yùn)算（或稱為復(fù)制運(yùn)算）把當(dāng)前群體中適應(yīng)度較高的個(gè)體按某種規(guī)則或模型遺傳到 下一代群體中。一般要求適應(yīng)度較高的個(gè)體將有更多的機(jī)會(huì)遺傳到下一代群體中。本例中，我們采用與適應(yīng)度成正比的概率來確定各個(gè)個(gè)體復(fù)制到下一代群體中的數(shù)量。其具體操作過程是:M?先計(jì)算出群體中所有個(gè)體的適應(yīng)度的總和Fl fi （i 1, ,M）；i 1?其次計(jì)算出每個(gè)個(gè)體的相對(duì)適應(yīng)度的大小fi/FI （i 1, ,M ），它即為每個(gè)個(gè)體被遺傳到下一代群體中的概率；?每個(gè)概率值組成一個(gè)區(qū)域，全部概率值之和為1 ；?最后再產(chǎn)生一個(gè)0到1之間

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

11、置在該基因座處；?然后依照某一概率將變異點(diǎn)的原有基因值取反。對(duì)群體P(t)進(jìn)行一輪選擇、交叉、變異運(yùn)算之后可得到新一代的群體p(t+1)從上表中可以看出，群體經(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é)果。選擇要能夠合理的反映 “適者生存”的自然法則，而交叉必須將有利的基因盡量遺傳給下一 代(這是算法的關(guān)鍵！) 算法過程當(dāng)中有幾個(gè)隨機(jī)過程：

12、(1)初始種群的產(chǎn)生是隨機(jī)產(chǎn)生，但有時(shí)為了更好迭代，知道解在某一個(gè)值附近，可以認(rèn) 為設(shè)定初始種群(2 )確定個(gè)體被選中次數(shù)時(shí)，運(yùn)用到輪賭法，其產(chǎn)生的數(shù)據(jù)為隨機(jī)數(shù)據(jù)(3)交叉點(diǎn)(4)變異點(diǎn)偽代碼：/In it populati onforeach in dividual in populati onin dividual = En code(Ra ndom(0,31);while (App.IsR un)/計(jì)算個(gè)體適應(yīng)度int TotalF = 0;foreach in dividual in populati onin dividual.F = 1000 - (Decode(i ndividu

13、al)-10)A2;TotalF += in dividual.F;/-選擇過程,計(jì)算個(gè)體選擇概率-foreach in dividual in populati onin dividua l.P :=in dividual.F / TotalF;/選擇for(i nt i=0;i4;i+)/Selectl ndividual(float p)是根據(jù)隨機(jī)數(shù)落在段落計(jì)算選取哪個(gè)個(gè)體的函數(shù)Mati ngPooli = populatio nSelectI ndividual(Ra ndom(0,1);/ - 簡(jiǎn)單交叉 -/由于只有4個(gè)個(gè)體,配對(duì)2次for(i nt i=0;i2;i+)Mati n

14、gPool .Paren tsi.Mother = Mati ngPooI.Ra ndomPop();Mat in gPool .Paren tsi.Father = Mat in gPool.Ra ndomPop();/交叉后創(chuàng)建新的集團(tuán)populati on .Clea n();foreach Pare nt in Mat in gPool.Pare nts/注意在copy雙親的染色體時(shí)在某個(gè)基因座上發(fā)生的變異未表現(xiàn)child1 = Pare nt.Mother .DivHeader + Pare nt.Father.DivE nd;child2 = Pare nt.Father.DivH

15、eader + Pare nt.Mother.DivE nd;populati on .push(child1);populati on .push(child2);完整代碼如下：#include stdafx.h#include #in clude#in clude #define POPSIZE 500#define MAXIMIZATION1/求解函數(shù)為求最大值#define MINIMIZATION2/求解函數(shù)為求最小值#define Cmax 100/求解最大值時(shí)適應(yīng)度函數(shù)的基準(zhǔn)數(shù)#define Cmin 0求解最小值時(shí)適應(yīng)度函數(shù)的基準(zhǔn)數(shù)#define LENGTH110/每一個(gè)解用

16、位基因表示#define LENGTH210#define CHROMLENGTH LENGTH1 +LENGTH2int FunctionMode =MAXIMIZATION ; /函數(shù)值求解類型是最大值 int PopSize=80;/種群規(guī)模int MaxGeneration =100;/最大世代數(shù)，即最大迭代數(shù)double Pc = 0.6;/變異概率double Pm = 0.001;/交叉概率struct individual / 定義個(gè)體char chromCHROMLENGTH +1; /個(gè)體數(shù)double value;/ 個(gè)體對(duì)應(yīng)的變量值double fitness;/個(gè)體適

17、應(yīng)度 ;int generation;int best_index;int worst_index;struct individual bestindividual ; struct individual worstindividual ;struct individual currentbest;struct individual population POPSIZE;voidGenerateInitialPopulation (void ); / /初始種群生成voidGenerateNextPopulation( void ); /產(chǎn)生下一代種群voidvoidEvaluatePopul

18、ation(void);CalculateObjectValue(void );longDecodeChromosome(char *, int,int ); /譯碼void void void void void void void voidCalculateFitnessValue(void ); FindBestAndWorstIndividual (void ); PerformEvolution (void ); SelectionOperator(void );CrossoverOperator(void);MutationOperator (void ); OutputTextR

19、eport(void ); main(void )generation=0;GenerateInitialPopulation (); /初始種群生成EvaluatePopulation();/計(jì)算種群值，即計(jì)算種群適應(yīng)度while (generationMaxGeneration)generation+;GenerateNextPopulation(); /產(chǎn)生下一代種群EvaluatePopulation();/ 計(jì)算種群值，即計(jì)算種群適應(yīng)度PerformEvolution ();OutputTextReport();void GenerateInitialPopulation (void

20、 ) /隨機(jī)產(chǎn)生初始種群，且用 0,1表示int i,j;for (i =0;i PopSize; i+)for(j=0;jCHROMLENGTH ;j+)populatio ni.chromj=(ra nd()%105)?0:1; ra nd()% n 產(chǎn)生一個(gè)/ n-1 的數(shù)populationi.chromCHROMLENGTH =0;void GenerateNextPopulation(void)SelectionOperator();CrossoverOperator();MutationOperator();void EvaluatePopulation()CalculateOb

21、jectValue();CalculateFit nessValu&);FindBestAndWorstlndividual ();long DecodeChromosome(char *string,int point,int length) 譯碼，換算為十進(jìn)制數(shù)int i;long decimal=0L;char *po in ter;for(i=O,poi nter=stri ng+poi nt;ile ngth;i+,poi nter+)decimal+=(* pointer-0)(length-1-i); /移位操作，染色體實(shí)現(xiàn)十進(jìn)/制化return(decimal);void Ca

22、lculateObjectValue(void)計(jì)算函數(shù)值int i;long temp1,temp2;double x1,x2;for (i=0;iPopSize;i+)從染色體中讀取基因temp 仁 DecodeChromosome(populatio ni.chrom,0 ,L ENGTH1 );temp2=DecodeChromosome(populationi.chrom,LENGTH1 ,LENGTH2 );x1=4.0 *temp1/1023.0-2.0 ;x a, b；x2=4.0 *temp2/1023.0-2.0 ;/ x a (bpopulationi.value=100

23、*( x1*x2+x2)*(x1*x2-x2)*x2; 函數(shù)表達(dá)式void CalculateFitnessValue(void) 針對(duì)不同函數(shù)類型計(jì)算個(gè)體適應(yīng)度int i;double temp;for (i=0;i0.0) temp=Cmin +population i. value;elsetemp=0.0;else if (FunctionMode =MINIMIZATION ) /函數(shù)類型為求解最小值 if(populationi.valueCmax) temp=Cmax-populationi.value;elsetemp=0.0;populationi.fitness=temp;

24、void FindBestAndWorstIndividual (void )int i;double sum=0.0;bestindividual =population 0; worstindividual =population 0; for (i=1;ibestindividual.fitness) bestindividual=populationi; best_index=i ;else if (population i. fitness=currentbest.fitness) currentbest= bestindividual ;void PerformEvolution

25、(void ) /執(zhí)行進(jìn)化if (bestindividual .fitnesscurrentbest.fitness)currentbest=population best_index;elsepopulationworst_index = currentbest;void SelectionOperator(void ) /選取最優(yōu)進(jìn)化代int i ,index;double p,sum=0.0; double cfitness POPSIZE;struct individual newpopulation POPSIZE; for(i=0;iPopSize;i+)sum+=populat

26、ioni.fitness;for(i=0;iPopSize; i+)cfitness i= population i . fitness/sum;/ 個(gè)體的適應(yīng)度比例for(i=1;iPopSize; i+)cfitness i= cfitness i -1+ cfitness i;for (i=0;icfitnessindex) index+;newpopulation i= population index;for(i=0;iPopSize; i+)populationi=newpopulationi;void CrossoverOperator(void ) /染色體交叉int i,j;int indexPOPSIZE;int point,temp;double p;char ch;for (i=0;iPopSize;i+)indexi = i ;for(i=0;iPopSize;i+) /隨機(jī)化種群內(nèi)染色體point=rand()%(PopSize-i); temp=index i ; indexi=indexpoint+i; indexpoint +i = temp;for (i=0;iPopSize-1;i+=2)p=rand()%1000/1000.0; /隨機(jī)產(chǎn)生交叉概率 if (pPc)point=rand()%(CHROMLENG