【正文】 … ， n ] [ 旅行商問題 (Traveling Salesman Problem，簡(jiǎn)稱 TSP)可描述為； 已知 n個(gè)城市之間的相互距離。如何安排他對(duì)這些城市的訪問次序，可 使其旅行路線的總長(zhǎng)度最短 ? ] (2) 符號(hào)編碼的主要優(yōu)點(diǎn)： ? 符合有意義積木塊編碼原則。 ? 便于遺傳算法與相關(guān)近似算法之間的混合使用。 多參數(shù)級(jí)聯(lián)編碼方法 多參數(shù)交叉編碼方法 適應(yīng)度函數(shù) ? 在研究自然界生物的遺傳和進(jìn)化現(xiàn)象時(shí)，生物學(xué)家使用適應(yīng)度這個(gè)術(shù)語來度量 某個(gè)物種對(duì)于其生存環(huán)境的適應(yīng)程度。 度量個(gè)體適應(yīng)度的函數(shù)稱為適應(yīng)度函數(shù)。 最優(yōu)化問題可分為兩大類，一類為求目標(biāo)函數(shù)的全局最大值，另一類為求目標(biāo)函 數(shù)的全局最小值。 ? 在遺傳算法運(yùn)行的初期階段 群體中可能會(huì)有少數(shù)幾個(gè)個(gè)體的適應(yīng)度相對(duì)其他個(gè)體來說非常高。這時(shí)產(chǎn)生新個(gè)體作用較大的交叉算子就 起不了什么作用，因?yàn)橄嗤膬蓚€(gè)個(gè)體不論在何處進(jìn)行交叉操作都永遠(yuǎn)不會(huì)產(chǎn) 生出新的個(gè)體，如下所示： A: 10101010 1010 10101010 1010 B: 10101010 1010 10101010 1010 單點(diǎn)交叉 這樣就會(huì)使群體的多樣性降低，容易導(dǎo)致遺傳算法發(fā)生早熟現(xiàn)象（或稱早期收 斂 )，使遺傳算法所求到的解停留在某一局部最優(yōu)點(diǎn)上。 ? 在遺傳算法運(yùn)行的后期階段 群體中所有個(gè)體的平均適應(yīng)度可能會(huì)接近于群體中最佳個(gè)體的適應(yīng)度。這將導(dǎo)致無法對(duì)某些重點(diǎn)區(qū)域進(jìn)行重點(diǎn)搜索， 從而影響遺傳算法的運(yùn)行效率。 (2) 適應(yīng)度尺度變換定義 在遺傳算法運(yùn)行的不同階段，有時(shí)需要對(duì)個(gè)體的適應(yīng)度進(jìn)行適當(dāng)?shù)臄U(kuò)大或縮小。 (3) 適應(yīng)度尺度變換方法 目前常用的個(gè)體適應(yīng)度尺度變換方法主要有三種：線性尺度變換、乘冪尺度變 換和指數(shù)尺度變換。 線性尺度變換的公式如下 : F’ = aF + b 式中 F——原適應(yīng)度； F’——變換后的新適應(yīng)度； a,b——系數(shù)。 條件 2： 尺度變換后群體中新的最大適應(yīng)度 F’max 要等于其原平均適應(yīng)度 Favg 的指定 倍數(shù)。 這條要求是為了保證群體中最好的個(gè)體能夠期望復(fù)制 C倍到新一代群體中。 最小適應(yīng)度為負(fù)時(shí)的處理： 在遺傳算法執(zhí)行的后期，個(gè)別劣質(zhì)個(gè)體的適應(yīng)度遠(yuǎn)遠(yuǎn)小于群體平均適應(yīng)度及最 大適應(yīng)度，并且后兩者比較接近。這將會(huì)給后面的處理過程帶來不便，必須避免這種情況的發(fā)生， 解決這個(gè)問題的方法是：把原最小適應(yīng)度 Fmin映射為 Fmin= 0，并且保持原平均適 應(yīng)度 Favg與新的平均適應(yīng)度 F’avg 相等。 Favg Fmax C 1 若不等式滿足，則執(zhí)行 (2)， 否則執(zhí)行 (3)。 Favg b = Fmax Favg Favg (3) 負(fù)適應(yīng)度時(shí)的縮放： a = Favg Favg Fmin b = Favg 冪指數(shù) k與所求解的問題有關(guān)， 并且在算法的執(zhí)行過程中需要不斷對(duì)其進(jìn)行修正才能使尺度變換滿足一定的伸 縮要求。式中系數(shù) ?決定了選擇的強(qiáng)制性， ?越小，原有適應(yīng)度較高的個(gè)體的新適應(yīng)度就越與其他個(gè)體的新適應(yīng)度相差較 大，亦即越增加了選擇該個(gè)體的強(qiáng)制性。 在遺傳算法的應(yīng)用中，必須對(duì)這些約束條件進(jìn)行處理，而目前還未找到一種能夠 處理各種約束條件的一般化方法。 在構(gòu)造遺傳算法時(shí)，處理約束條件的常用方法主要有如下三種： 搜索空間限定法 罰函數(shù)法 可行解變換法 (1) 搜索空間限定法 [基本思想 ] 對(duì)遺傳算法的搜索空間的大小加以限制，使得搜索空間中表示一個(gè)個(gè)體的點(diǎn)與解空間中表示一個(gè)可行解的點(diǎn)有一一對(duì)應(yīng)的關(guān)系。 [對(duì)一些比較簡(jiǎn)單的約束條件 (如 ax＜ b之類 )] 在個(gè)體染色體的編碼方法上著手，就能夠達(dá)到這種搜索空間與解空間之間的對(duì) 應(yīng)的要求。 ? 但需要注意的是：除了在編碼方法上想辦法之外，也必須保證經(jīng)過交叉、變異 等遺傳其子作用之后所產(chǎn)生出的新個(gè)體在解空間中也要有確 定的對(duì)應(yīng)解，而不會(huì)產(chǎn)生無效解。 這個(gè)實(shí)現(xiàn)方法要求我們?cè)O(shè)計(jì)出一種比較好的個(gè)體編碼方案。 方法二：用程序來保證直到產(chǎn)生出在解空間中有對(duì)應(yīng)可行解的染色體之前，一 直進(jìn)行交叉運(yùn)算和變異運(yùn)算。 (2) 罰函數(shù)法 [基本思想 ] 對(duì)在解空間中無對(duì)應(yīng)可行解的個(gè)體，計(jì)算其適應(yīng)度時(shí)，處以一個(gè)罰函數(shù)，從 而降低該個(gè)體適應(yīng)度，使該個(gè)體被遺傳到下一代群體中的機(jī)會(huì)減少。 F’(x)為考慮了罰函數(shù)之后的新適應(yīng)度 。 [懲罰函數(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ù)。在遺傳算法初期，懲罰輕一些；到了后期，則懲 罰重一些。 [難點(diǎn) ] 如何確定合理的罰函數(shù)是這種處理方法的難點(diǎn)之所在，因?yàn)檫@時(shí)既要考慮如 何度量解對(duì)約束條件不滿足的程度，又要考慮遺傳算法在計(jì)算效率上的要求。 (3) 可行解變換法 [基本思想 ] 在由個(gè)體基因型到個(gè)體表現(xiàn)型 的變換中，增加使其滿足約束條 件的處理過程。 下圖為該方法的示意圖。 選擇算子 在生物的遺傳和自然進(jìn)化過程中，對(duì)生存環(huán)境適應(yīng)程度較高的物種將有更多 的機(jī)會(huì)遺傳到下一代； 遺傳算法中的選擇操作用來確定如何從父代群體中按某種方法選取哪些個(gè)體 遺傳到下一代群體中的一種遺傳運(yùn)算。 最常用的選擇算子是基本遺傳算法中的比例選擇算子。下面介紹幾種常用選擇算子的操作方法。 設(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è)體被選中的概 率也越小。 分級(jí)選擇 ( ranking selecton ) （或稱排序選擇） (1) 產(chǎn)生原因 遺傳算法中個(gè)體適應(yīng)度數(shù)值上的差別有時(shí)會(huì)很大，尤其是在算法的早期這種差 別更是懸殊。因此，人們提出分級(jí)的概念，用連續(xù) 漸變的分級(jí)代替數(shù)值懸殊的適應(yīng)度。 ? 采用線性分級(jí)， 使各個(gè)個(gè)體被選中的可能性 有如下線性關(guān)系： p(i) = q ( i 1 )d 其中， q —— 最優(yōu)個(gè)體被選中的概率； d —— 相鄰個(gè)體被選中概率之差。 缺點(diǎn)：抹殺個(gè)體適應(yīng)度的實(shí)際差別，未能充分運(yùn)用遺傳信息。在每一代群體中，每次 都隨機(jī)選擇 k個(gè)個(gè)體構(gòu)成一個(gè)小群體，然后從這 k個(gè)個(gè)體中確定性地取適應(yīng)度最 大的個(gè)體復(fù)制，進(jìn)入下一代群體。這種隨機(jī)選擇重復(fù) M次，產(chǎn)生 M個(gè)下一代個(gè)體．