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