【文章內(nèi)容簡介】 可行解變換法 (1) 搜索空間限定法 [基本思想 ] 對遺傳算法的搜索空間的大小加以限制，使得搜索空間中表示一個個體的點與解空間中表示一個可行解的點有一一對應的關(guān)系。此時的搜索空間與解空間的對應關(guān)系如圖所示。 [對一些比較簡單的約束條件 (如 ax＜ b之類 )] 在個體染色體的編碼方法上著手，就能夠達到這種搜索空間與解空間之間的對 應的要求。 ? 用這種處理方法能夠在遺傳算法中設(shè)置最小的搜索空間，所以它能夠提高遺傳 算法的搜索效率。 ? 但需要注意的是：除了在編碼方法上想辦法之外，也必須保證經(jīng)過交叉、變異 等遺傳其子作用之后所產(chǎn)生出的新個體在解空間中也要有確 定的對應解，而不會產(chǎn)生無效解。 [處理方法 ] 方法一：用編碼方法來保證總是能夠產(chǎn)生出在解空間中有對應可行解的染色體。 這個實現(xiàn)方法要求我們設(shè)計出一種比較好的個體編碼方案。 如前面我們講到的二進制編碼方案即可實現(xiàn)上述要求。 方法二：用程序來保證直到產(chǎn)生出在解空間中有對應可行解的染色體之前，一 直進行交叉運算和變異運算。 雖然這個實現(xiàn)方法對編碼方法的要求不高，但它有可能需要反復地進 行交叉運算和變異運算才能產(chǎn)生出一個滿足約束條件的可行解，這樣 就有可能會降低遺傳算法的運行效率。 (2) 罰函數(shù)法 [基本思想 ] 對在解空間中無對應可行解的個體，計算其適應度時，處以一個罰函數(shù)，從 而降低該個體適應度，使該個體被遺傳到下一代群體中的機會減少。即用下式 來對個體的適應度進行調(diào)整： F(X) X滿足約束條件時 F(X) – P(X) X不滿足約束條件時 F’(X)= 式中， F(X)為原適應度 。 F’(x)為考慮了罰函數(shù)之后的新適應度 。 P(x)為罰函數(shù)。 [懲罰函數(shù) ] 設(shè)有優(yōu)化問題的目標函數(shù)： max F(x1,x2,…,x n) . Hi(x1,x2,…,x n) i=1,2,…,m )),...,((),...,( 21121 nmiiin xxxhxxxfF ??????max 式中 ?——懲罰函數(shù)； ?——懲罰系數(shù)。 Ⅰ . 最簡單的懲罰函數(shù)形式是平方法 ，即： 221121 )],...,(([),...,( nmiiin xxxhhxxxfF ????Ⅱ .也有人建議采用松緊法 。在遺傳算法初期，懲罰輕一些；到了后期，則懲 罰重一些。具體的新目標函數(shù) F為： 加入罰函數(shù)后，原來的問題變?yōu)橄率鲆粋€新的目標函數(shù)： ??? ????? miin dfTtKxxxfxF121 )(),... ,()( 其中： K——系數(shù)，可取 1/m； t——當前的迭代代次； T——終止迭代次數(shù)； ?——系數(shù)， 1左右； f——個體適應度的平均值； di——違背約束 i的程度，視問題的不同而定義。 [難點 ] 如何確定合理的罰函數(shù)是這種處理方法的難點之所在，因為這時既要考慮如 何度量解對約束條件不滿足的程度，又要考慮遺傳算法在計算效率上的要求。 ? 罰函數(shù)的強度太小的話，部分個體仍有可能破壞約束條件，所以保證不了遺 傳運算所得到的個體一定是滿足約束條件的一個可行解； ? 罰函數(shù)的強度太大的話，又有可能使個體的適應度差異不大，降低了個體之 間的競爭力，從而影響遺傳算法的運行效率。 (3) 可行解變換法 [基本思想 ] 在由個體基因型到個體表現(xiàn)型 的變換中，增加使其滿足約束條 件的處理過程。 即尋找出一種個 體基因型和個體表現(xiàn)型之間的多 對一的變換關(guān)系，使進化過程中 所產(chǎn)生的個體總能夠通過這個變 換而轉(zhuǎn)化成解空間中滿足約束條 件的一個可行解。 下圖為該方法的示意圖。 [優(yōu)劣 ] 這種處理方法雖然對個體的編 碼方法、交叉運算、變異運算 等沒有附加的要求，但它卻是以 擴大搜索空間為代價的，所以一 般會使得遺傳算法的運行效率有 所下降。 選擇算子 在生物的遺傳和自然進化過程中，對生存環(huán)境適應程度較高的物種將有更多 的機會遺傳到下一代； 遺傳算法中的選擇操作用來確定如何從父代群體中按某種方法選取哪些個體 遺傳到下一代群體中的一種遺傳運算。選擇操作建立在對個體的適應度進行評 價的基礎(chǔ)上。 最常用的選擇算子是基本遺傳算法中的比例選擇算子。 但對于各種不同的問題，比例選擇算子并不是最合適的一種選擇算子，所以 人們提出了其他一些選擇算于。下面介紹幾種常用選擇算子的操作方法。 比例選擇 ( Fitness proportional selection ) [基本思想 ] 各個個體被選中的概率與其適應度大小成正比。 設(shè)群體大小為 M，個體 i的適應度為 Fi，則個體 i被選中的概率 pis為： M pis= Fi / ? Fi i=1 i=1,2,…M [特點 ] 適應度越高的個體被選中的概率也越大，適應度越低的個體被選中的概 率也越小。 [缺點 ] 由于是隨機操作的原因，這種選擇方法的選擇誤差比較大，有時甚至連 適應度較高的個體也選擇不上。 分級選擇 ( ranking selecton ) （或稱排序選擇） (1) 產(chǎn)生原因 遺傳算法中個體適應度數(shù)值上的差別有時會很大，尤其是在算法的早期這種差 別更是懸殊。因此，個別特優(yōu)個體會多次被選中進行復制，經(jīng)過幾代后它們在群 體中數(shù)目愈來愈多，沖淡了群體的多樣性。因此，人們提出分級的概念，用連續(xù) 漸變的分級代替數(shù)值懸殊的適應度。 (2) 方法 ? 設(shè)群體中有 m個個體，將它們按降序方法依次排序，規(guī)定個體優(yōu)劣的等級依 次為： 1， 2， 3， … ， i， … ， M。 ? 采用線性分級， 使各個個體被選中的可能性 有如下線性關(guān)系： p(i) = q ( i 1 )d 其中， q —— 最優(yōu)個體被選中的概率； d —— 相鄰個體被選中概率之差。 上述線性關(guān)系使 p(i)構(gòu)成等差級數(shù)，即： q， q d， q – 2d， … ， q id， … ， q – (M1)d 由于概率定義要求 ，按級數(shù)求和，有： ???miip11)(12 )1( ???? dMMqMMdMq 12)1( ???即： ① 下面按兩種情況討論： Ⅰ . 所有個體按相同概率選取，即 d=0 ，得： q = 1/M Ⅱ . 令最壞（最后）個體的的選取概率為 0，即 q – (M1)d = 0，帶入 ① 式，得： q =