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