遺傳算法實(shí)驗(yàn)報(bào)告

1、遺傳算法實(shí)驗(yàn)報(bào)告專業(yè)：自動(dòng)化_乂俊峰_13351067摘要：遺傳算法，是基于達(dá)爾文進(jìn)化理論發(fā)展起來(lái)的一種應(yīng)用廣泛、 高效的隨機(jī)搜索與優(yōu)化方法.本實(shí)驗(yàn)利用遺傳算法來(lái)實(shí)現(xiàn)求函數(shù)最大 值的優(yōu)化問(wèn)題，其中的步驟包括初始化群體、個(gè)體評(píng)價(jià)、選擇運(yùn)算、 交叉運(yùn)算、變異運(yùn)算、終止條件判斷.該算法具有覆蓋面大、減少進(jìn) 入局部最優(yōu)解的風(fēng)險(xiǎn)、自主性等特點(diǎn).此外，遺傳算法不是采用確定性 原則而是采用概率的變遷規(guī)則來(lái)指導(dǎo)搜索方向，具有動(dòng)態(tài)自適應(yīng)的優(yōu) 點(diǎn).關(guān)鍵詞：串集 最優(yōu)化評(píng)估 迭代 變異一：實(shí)驗(yàn)?zāi)康氖煜ず驼莆者z傳算法的運(yùn)行機(jī)制和求解的基本方法.遺傳算法是一種基于空間搜索的算法，它通過(guò)自然選擇、遺傳、變異等操作 以與達(dá)

2、爾文的適者生存的理論，模擬自然進(jìn)化過(guò)程來(lái)尋找所求問(wèn)題的答案.其求 解過(guò)程是個(gè)最優(yōu)化的過(guò)程.一般遺傳算法的主要步驟如下：(1)隨機(jī)產(chǎn)生一個(gè)確定長(zhǎng)度的特征字符串組成的初始種群.2對(duì)該字符春種群迭代地執(zhí)行下面的步驟a和步驟b，直到滿足停止準(zhǔn)則 為止：a計(jì)算種群中每個(gè)個(gè)體字符串的適應(yīng)值；b應(yīng)用復(fù)制、交叉和變異等遺傳算子產(chǎn)生下一代種群.3把在后代中表現(xiàn)的最好的個(gè)體字符串指定為遺傳算法的執(zhí)行結(jié)果，即為問(wèn)題 的一 個(gè)解.二：實(shí)驗(yàn)要求已知函數(shù) y=fx，x，x，x=1/，其中-5Wx，x，x，x W5, 123412341234用遺傳算法求y的最大值.三：實(shí)驗(yàn)環(huán)境操作系統(tǒng)：MicrosoftWindows7軟

3、件：MicrosoftVisualstudio 2010四：實(shí)驗(yàn)原理與步驟1、遺傳算法的思想生物的進(jìn)化是以集團(tuán)為主體的.與此相對(duì)應(yīng)，遺傳算法的運(yùn)算對(duì)象是由M個(gè)個(gè)體 所組成的集合，稱為群體.與生物一代一代的自然進(jìn)化過(guò)程相類似，遺傳算法的運(yùn) 算過(guò)程也是一個(gè)反復(fù)迭代過(guò)程，第t代群體極為Pt，進(jìn)過(guò)一代遺傳和進(jìn)化后， 得到第t+1代群體，他們也是由多個(gè)個(gè)體組成的集合，記做Pt+1.這個(gè)群體不 斷地經(jīng)過(guò)遺傳和進(jìn)化操作，并且每次都按照有優(yōu)勝劣汰的規(guī)則將適應(yīng)度較高的個(gè) 體更多地遺傳到下一代，這樣最終在群體中將會(huì)得到一個(gè)優(yōu)良的個(gè)體X,它所對(duì) 應(yīng)的表現(xiàn)性X將達(dá)到或接近于問(wèn)題的最優(yōu)解.2、算法實(shí)現(xiàn)步驟、產(chǎn)生初始種群

4、：產(chǎn)生初始種群的方法通常有兩種：一種是完全隨機(jī)的方法產(chǎn) 生的，適合于對(duì)問(wèn)題的解無(wú)任何先驗(yàn)知識(shí)的情況；另一種是將某些先驗(yàn)知識(shí)轉(zhuǎn)變 為必須滿足的一組要求，然后在滿足這些要求的解中再隨機(jī)地選擇樣本，t=0,隨 機(jī)產(chǎn)生n個(gè)個(gè)體形成一個(gè)初始群體Pt，該群體代表優(yōu)化問(wèn)題的一些可能解的 集合；適應(yīng)度評(píng)價(jià)函數(shù)：按編碼規(guī)則，將群體Pt中的每一個(gè)個(gè)體的基因碼所對(duì)應(yīng) 的自變量取值代入目標(biāo)函數(shù)，算出其函數(shù)值f,i=1,2,，n,f越大，表示該個(gè)體有 較高的適應(yīng)度，更適合于f所定義的生存環(huán)境，適應(yīng)度f(wàn)為群體進(jìn)化提供了依據(jù)；選擇：按一定概率從群體Pt中選出m個(gè)個(gè)體，作為雙親用于繁殖后代，產(chǎn) 生新的個(gè)體加入下一個(gè)群體Pt+

5、1中.此處選用輪盤(pán)算法，也就是比例選擇算 法，個(gè)體被選擇的概率與其適應(yīng)度成正比.交叉重組：對(duì)于選中的用于繁殖的每一個(gè)個(gè)體，選擇一種交叉方法，產(chǎn)生新 的個(gè)體；此處采取生成隨機(jī)數(shù)決定交叉的個(gè)體與交叉的位置.變異：以一定的概率Pm從群體Pt+1中隨機(jī)選擇若干個(gè)個(gè)體，對(duì)于選中的 個(gè)體隨機(jī)選擇某個(gè)位置，進(jìn)行變異；對(duì)產(chǎn)生新一代的群體返回步驟再進(jìn)行評(píng)價(jià)，交叉、變異如此循環(huán)往復(fù)，使群體 中個(gè)體的適應(yīng)度和平均適應(yīng)度不斷提高，直至最優(yōu)個(gè)體的適應(yīng)度達(dá)到某一限值或 最優(yōu)個(gè)體的適應(yīng)度和群體的平均適應(yīng)度不再提高，則迭代過(guò)程收斂，算法結(jié)束.五：實(shí)驗(yàn)結(jié)果實(shí)驗(yàn)結(jié)果的顯示取決于判斷算法終止的條件，這里可以有兩種選擇：1、在程 序

6、中設(shè)定迭代的次數(shù)；2在程序中設(shè)定適應(yīng)值.本實(shí)驗(yàn)是在程序中實(shí)驗(yàn)者輸入需 要迭代的次數(shù)來(lái)判斷程序終結(jié)的.六：實(shí)驗(yàn)小結(jié)在實(shí)驗(yàn)過(guò)程中，我覺(jué)得發(fā)現(xiàn)算子的選擇對(duì)實(shí)驗(yàn)結(jié)果有一定程度的影響，所以除了 采用PPT上的算子選取外，也同樣嘗試了其他的算子選擇方法.1、選擇算子、排序選擇方法.基于個(gè)體按適應(yīng)度大小的排序來(lái)分配個(gè)體被選中的概率，這種 算法與輪盤(pán)算法的思路差不多.、保存最佳個(gè)體策略.由于選擇、交配、變異等操作的隨機(jī)性，當(dāng)代最優(yōu)秀的個(gè) 體可能會(huì)被破壞，所以可以采用保存當(dāng)代最優(yōu)秀的個(gè)體，參與到下一代的選擇過(guò) 程中.不過(guò)總的來(lái)說(shuō)，輪盤(pán)算法還是選取選擇算子最有效、最常用的算法.2、交叉算子、單點(diǎn)交叉.是指在個(gè)體編

7、碼串中隨機(jī)設(shè)置一個(gè)交叉點(diǎn)，在該店交換配對(duì)的兩條 染色體上的基因.、兩點(diǎn)交叉與多點(diǎn)交叉.在選擇交叉算子的過(guò)程中，單點(diǎn)交叉是最簡(jiǎn)單的方法, 又稱簡(jiǎn)單交叉，兩點(diǎn)甚至多點(diǎn)交叉，是交配兩點(diǎn)之間的染色體，比單點(diǎn)交叉的適應(yīng) 性更高，不過(guò)程序略復(fù)雜.本實(shí)驗(yàn)采用的是均勻交叉,在選定位置后每一位基因都以相同的概率進(jìn)行 交叉.附上實(shí)驗(yàn)代碼visual studio 2010環(huán)境下運(yùn)行#include#include#include#include using namespace std;int mainsrandtime;double arr54; /初始化cout初始化：endl;forint i=0;icout

8、Ci;forint j=0;jarrij=-5000+rand%100000*0.0001;coutsetiosflagssetwarrij;coutendl;double result5;double best_result; double result15;適應(yīng)值計(jì)算forvint i=0;idouble sum=0;forint j=0;jsum+=arrij*arrij;resulti=1/;forvint i=0;iresult1i=resulti;sort;best_result=result14;cout初始化后進(jìn)行適應(yīng)值計(jì)算，最大值 best_result : best_res

9、ultendl;int n;coutn;int test_num=1;double test_result;whiletest_numcout第test_num次迭代：vvendl;double sum_result=0;double pecentage5;選擇forint i=0;isum_result+=resulti;forint i=0;ipecentagei=resulti/sum_result;double a;double arr154;forint i=0;iforint j=0;jarr1ij=arrij;forvint i=0;ia=vrandv%100*0.01;ifaf

10、orint j=0;jarrij=arr10j;ifvapecentage0&av=vpecentage0+pecentage1forint j=0;jarrij=arr11j;ifvavpecentage0+pecentage1&av=vpecentage0+pecentage1+pecentage2forvint j=0;jarrij=arr12j;ifvavpecentage0+pecentage1+pecentage2&av=vpecentage0+pecentage1+pecentage2+pecentage3forvint j=0;jarrij=arr13j;ifvavpecent

11、age0+pecentage1+pecentage2+pecentage3&av=vpecentage0+pecentage1+pecentage2+pecentage3+pecentage4forvint j=0;jarrij=arr14j;double mating_pecentage=0.88;double mating5;int num;double tend4=0;交配forvint i=0;imatingi=vrand%100*0.01;forvint i=0;iifvmatingiforvint k=i+1;kifmatingknum=rand%3;forint l=num+1;

12、ltendl=arril;forint m=num+1;marrim=arrkm;arrkm=tendm;matingk=1;break;double variation54;變異forint i=0;iforint j=0;jvariationij=vrandv%100*0.01;forvint i=0;iforint j=0;jifvariationijarrij=-5000+rand%10000*0.0001;cout新群體：vvendl;forvint i=0;iforvint j=0;jcoutsetiosflagssetwarrij;coutendl;forvint i=0;i重新評(píng)價(jià)double sum=0;forvint j=0;jsum+=arrij*arrij;resulti=1/vsum+1;f