基本遺傳算法及的應(yīng)用舉例

基本遺傳算法及應(yīng)用舉例遺傳算法(GeneticAlgorithms)是一種借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)、高度并行、自適應(yīng)搜索算法。遺傳算法是多學(xué)科互相結(jié)合與滲入的產(chǎn)物?，F(xiàn)在它已發(fā)展成一種自組織、自適應(yīng)的多學(xué)科技術(shù)。針對(duì)多個(gè)不同類型的問題，借鑒自然界中生物遺傳與進(jìn)化的機(jī)理，學(xué)者們?cè)O(shè)計(jì)了不同的編碼辦法來表達(dá)問題的可行解，開發(fā)出了許多不同環(huán)境下的生物遺傳特性。這樣由不同的編碼辦法和不同的遺傳操作辦法就構(gòu)成了多個(gè)不同的遺傳算法。但這些遺傳算法有共同的特點(diǎn)，即通過對(duì)生物的遺傳和進(jìn)化過程中的選擇、交叉、變異機(jī)理的模仿來完畢對(duì)最優(yōu)解的自適應(yīng)搜索過程。基于此共同點(diǎn)，人們總結(jié)出了最基本的遺傳算法——基本遺傳算法?；具z傳算法只使用選擇、交叉、變異三種基本遺傳操作。遺傳操作的過程也比較簡(jiǎn)樸、容易理解。同時(shí)，基本遺傳算法也是其它某些遺傳算法的基礎(chǔ)與雛形。1．1．1編碼辦法用遺傳算法求解問題時(shí)，不是對(duì)所求解問題的實(shí)際決策變量直接進(jìn)行操作，而是對(duì)表達(dá)可行解的個(gè)體編碼的操作，不停搜索出適應(yīng)度較高的個(gè)體，并在群體中增加其數(shù)量，最后尋找到問題的最優(yōu)解或近似最優(yōu)解。因此，必須建立問題的可行解的實(shí)際表達(dá)和遺傳算法的染色體位串構(gòu)造之間的聯(lián)系。在遺傳算法中，把一種問題的可行解從其解空間轉(zhuǎn)換到遺傳算法所能解決的搜索空間的轉(zhuǎn)換辦法稱之為編碼。反之，個(gè)體從搜索空間的基因型變換到解空間的體現(xiàn)型的辦法稱之為解碼辦法。編碼是應(yīng)用遺傳算法是需要解決的首要問題，也是一種核心環(huán)節(jié)。迄今為止人們已經(jīng)設(shè)計(jì)出了許多個(gè)不同的編碼辦法?；具z傳算法使用的是二進(jìn)制符號(hào)0和1所構(gòu)成的二進(jìn)制符號(hào)集｛0，1｝，也就是說，把問題空間的參數(shù)表達(dá)為基于字符集｛0，1｝構(gòu)成的染色體位串。每個(gè)個(gè)體的染色體中所包含的數(shù)字的個(gè)數(shù)L稱為染色體的長度或稱為符號(hào)串的長度。普通染色體的長度L為一固定的數(shù)，如X=11010100表達(dá)一種個(gè)體，該個(gè)體的染色體長度L=20。二進(jìn)制編碼符號(hào)串的長度與問題所規(guī)定的求解精度有關(guān)。假設(shè)某一參數(shù)的取值范疇是[a，b]，我們用長度為L的二進(jìn)制編碼符號(hào)串來表達(dá)該參數(shù)，總共能產(chǎn)生種不同的編碼，若參數(shù)與編碼的對(duì)應(yīng)關(guān)系為……00000000=0→a……00000001=1→a+δ???……11111111=-1→b則二進(jìn)制編碼的編碼精度假設(shè)某一種個(gè)體的編碼是，則對(duì)應(yīng)的解碼公式為例如，對(duì)于[0,1023],若用長度為10的二進(jìn)制編碼來表達(dá)該參數(shù)的話，則下述符號(hào)串：=就表達(dá)一種個(gè)體，它對(duì)應(yīng)的參數(shù)值是=175.此時(shí)的編碼精度為1.二進(jìn)制編碼辦法相對(duì)于其它編碼辦法的優(yōu)點(diǎn)，首先是編碼、解碼操作簡(jiǎn)樸易行；另首先是交叉遺傳操作便于實(shí)現(xiàn)；另外便于對(duì)算法進(jìn)行理論分析。2.個(gè)體適應(yīng)度函數(shù)在遺傳算法中，根據(jù)個(gè)體適應(yīng)度的大小來擬定該個(gè)體在選擇操作中被選定的概率。個(gè)體的適應(yīng)度越大，該個(gè)體被遺傳到下一代的概率也越大；反之，個(gè)體的適應(yīng)度越小，該個(gè)體被遺傳到下一代的概率也越小?；具z傳算法使用比例選擇操作辦法來擬定群體中各個(gè)個(gè)體與否有可能遺傳到下一代群體中。為了對(duì)的計(jì)算不同狀況下各個(gè)個(gè)體的選擇概率，規(guī)定全部個(gè)體的適應(yīng)度必須為正數(shù)或?yàn)榱?，不能是?fù)數(shù)。這樣，根據(jù)不同種類的問題，必須預(yù)先擬定好由目的函數(shù)值到個(gè)體適應(yīng)度之間的轉(zhuǎn)換規(guī)則，特別是要預(yù)先擬定好目的函數(shù)值為負(fù)數(shù)時(shí)的解決辦法。設(shè)所求解的問題為：，.對(duì)于求目的函數(shù)最小值的優(yōu)化問題，理論上只需簡(jiǎn)樸地對(duì)其增加一種負(fù)號(hào)就可將其轉(zhuǎn)化為求目的函數(shù)最大值的問題，即當(dāng)優(yōu)化問題是求函數(shù)最大值，并且目的函數(shù)總?cè)≌禃r(shí)，能夠直接設(shè)定個(gè)體的適應(yīng)度函數(shù)值就等于對(duì)應(yīng)的目的函數(shù)值，即.但實(shí)際目的優(yōu)化問題中的目的函數(shù)有正也有負(fù)，優(yōu)化目的有求函數(shù)最大值，也有求函數(shù)最小值，顯然上面兩式確保不了全部狀況下個(gè)體的適應(yīng)度都是非負(fù)數(shù)這個(gè)規(guī)定，必須謀求出一種通用且有效的由目的函數(shù)值到適應(yīng)度之間的轉(zhuǎn)換關(guān)系，有它來確保個(gè)體適應(yīng)度總?cè)》秦?fù)值。為滿足適應(yīng)度取負(fù)值的規(guī)定,基本遺傳算法普通采用下面辦法將目的函數(shù)值變換為個(gè)體的適應(yīng)度對(duì)于求目的函數(shù)最大值的優(yōu)化辦法問題，變換辦法為0式中，為一種適宜的相對(duì)比較小的數(shù)，它能夠是預(yù)先指定的一種較小的數(shù)，或進(jìn)化到現(xiàn)在代為止的最小目的函數(shù)值，又或現(xiàn)在代或近來幾代群體中的最小目的函數(shù)值。3.基本遺傳操作辦法（1）比例選擇：選擇或稱復(fù)制，建立在對(duì)個(gè)體適應(yīng)度進(jìn)行評(píng)價(jià)的基礎(chǔ)之上。其作用是從現(xiàn)在群體中選擇出某些比較優(yōu)良的個(gè)體，并將其復(fù)制到下一代群體中?；具z傳算法采用比例選擇的辦法，所謂比例選擇，是指?jìng)€(gè)體在選擇操作中被選中的概率與該個(gè)體的適應(yīng)度大小成正比。（2）單點(diǎn)交叉。單點(diǎn)交叉又稱簡(jiǎn)樸交叉，是遺傳算法所使用的交叉操作辦法。（3）基本位變異?；疚蛔儺愂詈?jiǎn)樸和最基本的變異操作，也是基本遺傳算法中所使用的變異操作辦法。對(duì)于基本遺傳算法中用二進(jìn)制編碼符號(hào)串所示的個(gè)體，對(duì)需要進(jìn)行變異操作的某一基因，若原有基因值為0，則變異操作將該基因值變?yōu)?；反之，若原有基因值為1，則變異操作將其變?yōu)?.4.基本遺傳算法的運(yùn)行參數(shù)執(zhí)行基本遺傳算法時(shí)，有4個(gè)參數(shù)需要事先指定。它們是群體的大小M、交叉概率、變異概率及終止的代數(shù)T.群體大小M.群體的大小M表達(dá)群體中所含個(gè)體的數(shù)量。當(dāng)M取值較小時(shí)，可提高遺傳算法的運(yùn)算速度，但卻減少了群體的多樣性，有可能會(huì)引發(fā)遺傳算法的早熟現(xiàn)象；而當(dāng)M取值較大時(shí)，又會(huì)使得遺傳算法的運(yùn)行效率偏低。普通建議范疇是20~100.交叉概率。交叉操作室遺傳算法產(chǎn)生新個(gè)體的重要辦法，因此交叉概率普通應(yīng)取較大值。但若取值過大的話，它又會(huì)破壞群體活動(dòng)的優(yōu)良模式，對(duì)進(jìn)化運(yùn)算反而產(chǎn)生不利影響；若取值過小的話，產(chǎn)生新個(gè)體的速度有太慢。普通建議的取值范疇是0.4~1.00.變異概率。若變異概率取值較大的話，雖能夠產(chǎn)生出較多的新個(gè)體，但也有可能破壞掉諸多較好的模式，使得遺傳算法的性能近似于隨機(jī)搜索算法的性能；若變異概率取值太小的話，則變異操作產(chǎn)生新個(gè)體的能力和克制早熟現(xiàn)象的能力就會(huì)較差。普通建議的取值范疇是0.001~0.1.終止代數(shù)T.終止代數(shù)T式表達(dá)遺傳算法運(yùn)行結(jié)束條件的一種參數(shù)，它表達(dá)遺傳算法運(yùn)行到指定的進(jìn)化代數(shù)之后就停止運(yùn)行，并將現(xiàn)在群體中的最佳個(gè)體作為所求問題的最優(yōu)解輸出。普通建議的取值范疇是100~1000.至于遺傳算法的終止條件，還能夠運(yùn)用某種鑒定準(zhǔn)則，當(dāng)鑒定出群體已經(jīng)進(jìn)化成熟且不再有進(jìn)化趨勢(shì)時(shí)就可終止算法的運(yùn)行過程。如持續(xù)幾代個(gè)體平均適應(yīng)度的差別不大于某一種極小的值；或者群體中全部個(gè)體適應(yīng)度的方差不大于某一種極小的值。這4個(gè)參數(shù)對(duì)遺傳算法的搜索成果及搜索效率都有一定的影響，現(xiàn)在尚無合理選擇它們的理論根據(jù)在遺傳算法的實(shí)際應(yīng)用中，往往需要通過多次的試算后才干擬定出這些參數(shù)合理的取值范疇或取值大小?；具z傳算法是一種迭代過程，它模仿生物在自然環(huán)境中的遺傳和進(jìn)化機(jī)理，重復(fù)將選擇操作、交叉操作、變異操作作用與群體，最后可得到問題的最優(yōu)解或近似最優(yōu)解。即使算法的思想比較簡(jiǎn)樸，但它卻含有一定的實(shí)用價(jià)值，能夠解決某些復(fù)雜系統(tǒng)的優(yōu)化計(jì)算問題。遺傳算法的應(yīng)用環(huán)節(jié)以下；遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的領(lǐng)域和種類。對(duì)一種需要進(jìn)行優(yōu)化計(jì)算的實(shí)際應(yīng)用問題，普通可按下述環(huán)節(jié)來構(gòu)造求解該問題的遺傳算法。第一步：建立優(yōu)化模型，即擬定出目的函數(shù)、決策變量及多個(gè)約束條件以及數(shù)學(xué)描述形式或量化辦法。第二步：擬定表達(dá)可行解的染色體編碼辦法，也即擬定出個(gè)體的基因型x及遺傳算法的搜索空間。第三步：擬定解碼辦法，即擬定出個(gè)體基因型x到個(gè)體體現(xiàn)型x的對(duì)應(yīng)關(guān)系或轉(zhuǎn)換辦法。第四步：擬定個(gè)體適應(yīng)度的量化評(píng)價(jià)辦法，即擬定出由目的函數(shù)值到個(gè)體適應(yīng)度的轉(zhuǎn)換規(guī)則。第五步：設(shè)計(jì)遺傳操作辦法，即擬定出選擇運(yùn)算、交叉運(yùn)算、變異運(yùn)算等具體操作辦法。第六步：擬定遺傳算法的有關(guān)運(yùn)行參數(shù)，即擬定出遺傳算法的M、T、、等參數(shù)。由上述構(gòu)造環(huán)節(jié)能夠看出，可行解的編碼辦法、遺傳操作的設(shè)計(jì)是構(gòu)造遺傳算法時(shí)需要考慮的兩個(gè)重要問題，也是設(shè)計(jì)遺傳算法時(shí)的兩個(gè)核心環(huán)節(jié)。對(duì)不同的優(yōu)化問題需要使用不同的編碼辦法和不同的遺傳操作，它們與所求解的具體問題親密有關(guān)，因而對(duì)所求解問題的理解程度是遺傳算法應(yīng)用成功與否的核心。例1．1．1求解規(guī)劃問題s.t.解重要運(yùn)算過程如表7-3所示。（1）個(gè)體編碼.遺傳算法的運(yùn)算對(duì)象是表達(dá)個(gè)體的符號(hào)串，因此必須把變量1．1基本遺傳算法的構(gòu)成要素，編碼為一種符號(hào)串。該例題中，和取0～7之間的整數(shù)，可分別用3位無符號(hào)二進(jìn)制整數(shù)來表達(dá)，將它們連接在一起所構(gòu)成的6位無符號(hào)二進(jìn)制整數(shù)就形成了個(gè)體的基因型，表達(dá)一種可行解。例如，基因型=101110所對(duì)應(yīng)的體現(xiàn)型是=（5，6）T。個(gè)體的體現(xiàn)型和基因型之間能夠通過編碼和解碼互相轉(zhuǎn)換。（2）初始群體的產(chǎn)生。遺傳算法是對(duì)群體進(jìn)行遺傳操作，需要準(zhǔn)備某些表達(dá)起始搜索點(diǎn)的初始群體數(shù)據(jù)。本例中群體規(guī)模的大小M取為4，即群體由4個(gè)個(gè)體構(gòu)成，每個(gè)個(gè)體可通過隨機(jī)辦法產(chǎn)生。一種隨機(jī)產(chǎn)生的初始群體如表7-3中第2欄所示。（3）適應(yīng)度計(jì)算。本例中，目的函數(shù)總?cè)》秦?fù)值，并且是以求函數(shù)最大值為優(yōu)化目的，故可直接運(yùn)用目的函數(shù)值作為個(gè)體的適應(yīng)度，即。為計(jì)算函數(shù)的目的值，需先對(duì)個(gè)體基因型進(jìn)行解碼。表7-3中第3、第4欄所示為初始群體各個(gè)個(gè)體的解碼成果，第5欄所示為各個(gè)個(gè)體所對(duì)應(yīng)的目的函數(shù)值，它也是個(gè)體的適應(yīng)度，第5欄中還給出了群體中適應(yīng)度的最大值和平均值。表7-31個(gè)體編號(hào)2初始群體P(0)3456101110135343425500.242101011530.243011100340.174111001710.357選擇次數(shù)8選擇成果9配對(duì)狀況10交叉點(diǎn)位置11交叉成果12變異點(diǎn)13變異成果10111011-23-41-2：23-4：4011001501100111110011111011111110101011101001101001211100111101111101114子代群體P（1）1516170110013110982658111111771010015111101173(4)選擇操作.其具體操作過程是先計(jì)算出群體中全部個(gè)體的適應(yīng)度的總和及每個(gè)個(gè)體的相對(duì)適應(yīng)度的大小，如表7-3中5、6欄所示。表7-3中第7、8欄表達(dá)隨機(jī)產(chǎn)生的選擇成果。（5）交叉操作。本例中采用單點(diǎn)交叉的辦法，并取交叉概率=1.00。表7-3中第11欄所示為交叉運(yùn)算的成果。（6）變異操作。為了能顯示變異操作，取變異概率=0.25,并采用基本位變異的辦法進(jìn)行變異運(yùn)算。表7-3第13欄所示為變異運(yùn)算的成果。對(duì)群體P（t）進(jìn)行一輪選擇、交叉、變異