【文章內(nèi)容簡(jiǎn)介】 的倒數(shù)，即fitness=l/T。其中， T= 1 111 ( , ) ( )n i i ni d C C d C C? ?? ??? 適應(yīng)度越小的 個(gè)體，該個(gè)體的路徑越短，該個(gè)體則越好。也有采用 fitness=l/T2 計(jì)算適應(yīng)度的算法。也有的算法采用 fitness=1/(T+aN)，其中 N 為未遍歷的城市的個(gè)數(shù)，a 為懲罰函數(shù)系數(shù)，常取城市間最長(zhǎng)距離的兩倍多，路徑 T 越大，適應(yīng)度函數(shù)越小。迭代停止條件一般是：若某代群體中的最差個(gè)體與最好的個(gè)體適應(yīng)度的差不大于某個(gè)數(shù)（根據(jù)問題規(guī)模變化），則終止算法。若最佳個(gè)體連續(xù)保持一定代數(shù)，則終止算法。若算法迭代次數(shù)達(dá)到一定代數(shù)，則終止算法。 貴州大學(xué) 第 10 頁(yè) 選擇算子 選擇是從一個(gè)舊種群 (old population)中選擇生命力強(qiáng)的個(gè)體位串產(chǎn)生新種群的過程。或者說(shuō)，選擇是個(gè)體根據(jù)其適值函數(shù) f 拷貝自己的過程。直觀地講，可以把適值（或目標(biāo)）函數(shù) f 看作是我們期望的最大效益或好處的某種量度。根據(jù)個(gè)體的適值拷貝位串意味著：具有高的適值的個(gè)體更大可能在下一代中產(chǎn)生一個(gè)或多個(gè)子孫。顯然這個(gè)操作是模仿自然選擇現(xiàn)象，將達(dá)爾文的適者生存理論運(yùn)用于個(gè)體的選擇。 對(duì)于求解 TSP 問題， 常用的選擇機(jī)制有輪盤賭選擇機(jī)制、隨機(jī)遍歷抽樣法、局部選擇法、截?cái)噙x擇法、錦標(biāo)賽選擇法等。遺傳算法中一個(gè)較難解決的問題是如何較快地找到最優(yōu)解并防止“早 熟”收斂問題。為了保證遺傳算法的全局收斂性，就要維持解群體的個(gè)體多樣性。這種做法會(huì)明顯改善遺傳算法的行為，因?yàn)槠湓黾恿梭w在種群中的分布區(qū)域，但增加了計(jì)算時(shí)間。 交叉算子 Goldberg 提出基于路徑表示的部分映射交叉 (partially— mapped, PMX)，首先隨機(jī)地在父?jìng)€(gè)體中選取兩雜交點(diǎn)，并交換相應(yīng)的段再根據(jù)該段內(nèi)的城市確定部分映射。在每代父?jìng)€(gè)體上先填入無(wú)沖突的城市。而對(duì)有沖突的城市分別執(zhí)行這些部分映射直到填人無(wú)沖突，剛可獲得交叉后的兩后代。由 Davis 提出順序交叉 (order, OX)，它與 PMX 操作非常類似。也是首先隨機(jī)地在父?jìng)€(gè)體中選擇兩雜交點(diǎn)，再交換雜交段，其它位置根據(jù)保持父代個(gè)體中城市的相對(duì)次序來(lái)確定。由 Oliver 等提出的循環(huán)交叉 (CX)，將另一個(gè)父?jìng)€(gè)體作為參照以對(duì)當(dāng)前父?jìng)€(gè)體中的城市進(jìn)行重組。先與另一父?jìng)€(gè)體實(shí)現(xiàn)一個(gè)循環(huán)鏈．并將對(duì)應(yīng)的城市填入相應(yīng)的位置，循環(huán)組成后．再將另一父體的城市填入相同的位置。 上述幾種 TSP 操作基本上考慮的是城市的位置和順序，未考慮城市間的連 Grefenstette 認(rèn)為遺傳算法應(yīng)用與 TSP，其遺傳操作不僅要考慮城市間的位置，而且有必要考慮 城市間的關(guān)系，城市間的關(guān)系定義為邊，讓子個(gè)體繼承父?jìng)€(gè)體中邊的信息設(shè)計(jì)邊的遺傳操作很有意義。 1989 年， Whitle 等提出了一種邊重組 (Edge Rebination． ER)交叉操作，使個(gè)體能夠從父?jìng)€(gè)體繼承 95％～ 99％的邊信息。 ER 操作是根據(jù)繼承兩個(gè)父?jìng)€(gè)體定義的旅程中城市間的相鄰關(guān)系生成子個(gè)體。 1991 年， Stark weather 等提出了一種改進(jìn)的方法，在 ER 操作中不再保留父?jìng)€(gè)體中共同部分的序列。實(shí)驗(yàn)結(jié)果表明這種處理方法比 貴州大學(xué) 第 11 頁(yè) 隨機(jī)選擇的處理的性能有相當(dāng)?shù)母纳啤? 變異算子 盡管復(fù)制 和交叉操作很重要 ,在遺傳算法中是第一位的 ,但不能保證不會(huì)遺漏一些重要的遺傳信息。在人工遺傳系統(tǒng)中 ,變異是用來(lái)防止這種不可彌補(bǔ)的遺漏，在簡(jiǎn)單遺傳算法中，變異就是某個(gè)字符串某一位的值偶然的（概率很小的）隨機(jī)的改變 ,即在某些特定位置上簡(jiǎn)單地把 1 變成 0，或反之。變異是沿著個(gè)體字符空間的隨機(jī)移動(dòng)，當(dāng)它有節(jié)制地和交叉一起使用時(shí)，它就是一種防止過度成熟而丟失重要概念的保險(xiǎn)策略。 變異本身是一種局部隨機(jī)搜索，與選擇 /重組算子結(jié)合在一起，保證了遺傳算法的有效性，使遺傳算法具有局部的隨機(jī)搜索能力；同時(shí)使得遺傳算法保持種群的多 樣性，以防止出現(xiàn)非成熟收斂。在變異操作中，變異率不能取得太大。變異算子的設(shè)計(jì)要比交叉算子的設(shè)計(jì)靈活得多。簡(jiǎn)單的倒位操作，即首先在父?jìng)€(gè)體中隨機(jī)地選擇兩截?cái)帱c(diǎn)，然后將該兩點(diǎn)所夾的子串中的城市進(jìn)行反序。也有一種貪婪倒位變異算子，它的主要思想是：首先隨機(jī)選擇一個(gè)城市 C，然后在除外的其他城市中選除 C、 cRight、 cLeft 以外的距離 C最近的城市 c? ，在對(duì) cRight 到 c? 之間的城市進(jìn)行倒位。 TSP 問題的總結(jié) 對(duì)于 TSP，目前還不存在能找到完美解的方法，這個(gè)問題是 NP 難的。為了進(jìn)一步提高算法的全局優(yōu)化能力，避免搜索過程陷入局部極小，現(xiàn)已提出的改進(jìn)策略主要有：并行多鄰域搜索、平滑優(yōu)化曲面形狀、熵抽樣等高級(jí)技術(shù)。對(duì)于復(fù)雜優(yōu)化問題，單一機(jī)制的優(yōu)化算法很難實(shí)現(xiàn)全局優(yōu)化，且效率較低。多種優(yōu)化機(jī)制和鄰域搜索結(jié)構(gòu)相混合，是能較大程度提高全局優(yōu)化度和魯棒性的有力途徑，并可一定程度上放松對(duì)單一算法參數(shù)選擇的苛刻性，所以混合優(yōu)化策略會(huì)是一種趨勢(shì)。 總之，對(duì)于 TSP 問題，可從問題的編碼及遺傳算子設(shè)計(jì)方面來(lái)改進(jìn)發(fā)展遺傳算 法。尤其包含啟發(fā)式信息，盡量讓子代繼承父代的優(yōu)良特性。通過保持邊的有用信息找到更好的算法，這是算法改進(jìn)的一個(gè)趨勢(shì)，同時(shí)為了防止局部收斂必須讓算法達(dá)到收斂性與群體多樣性的平衡。 貴州大學(xué) 第 12 頁(yè) 第四章 應(yīng)用舉例 4． 1 問題陳述 如下圖所示， 尋找圖 中 11 個(gè)端點(diǎn)的最短路徑，其中沒有連接的端點(diǎn)表示沒有路徑。要求設(shè)計(jì)遺傳算法對(duì)該問題求解。 abcdefghijk121683179467294211 4． 2 詳細(xì)解答過程 問題分析 1234567891 01 1121683179467294211 如圖如示，將節(jié)點(diǎn)編號(hào)，依次為 ，由圖論知識(shí)，則可寫出其帶權(quán)鄰接矩陣為： 0 2 8 1 500 500 500 500 500 500 500 2 0 6 500 1 500 500 500 500 500 500 貴州大學(xué) 第 13 頁(yè) 8 6 0 7 500 1 500 500 500 500 500 1 500 7 0 500 500 9 500 500 500 500 500 1 500 500 0 3 500 2 500 500 500 500 500 1 500 3 0 4 500 6 500 500 500 500 500 9 500 4 0 500 500 1 500 500 500 500 500 2 500 500 0 7 500 9 500 500 500 500 500 6 500 7 0 1 2 500 500 500 500 500 500 1 500 1 0 4 500 500 500 500 500 500 500 9 2 4 0 注：為避免計(jì)算時(shí)無(wú)窮大數(shù)吃掉小數(shù)，此處為令 inf=500。 問題要求求出任意兩點(diǎn)間的最短路徑， Floyd 算法采用的是在兩點(diǎn)間嘗試插入頂點(diǎn)，比較距離長(zhǎng)短的方法。我思考后認(rèn)為，用遺傳算法很難找到一個(gè)可以統(tǒng)一表示最短路徑的函數(shù)，但是可以對(duì)每一對(duì)點(diǎn)分別計(jì)算，然后加入 for 循環(huán)，可將相互之間的所有情況解出。觀察本題可發(fā)現(xiàn)，所有節(jié)點(diǎn)都是可雙向行走，則可只計(jì)算 i到 j的路徑與距離，然后將矩陣按主對(duì)角線翻折即可得到全部數(shù)據(jù)。 實(shí)驗(yàn)原理與數(shù)學(xué)模型 實(shí)現(xiàn)原理為遺傳算法原理 ， 按所選擇的適應(yīng)度函數(shù)并通過遺傳中的復(fù)制、交叉及變異對(duì)個(gè)體進(jìn)行篩選，使得適應(yīng)度高的個(gè)體被保留下來(lái)，組成新的群體，新的群體既繼承了上一代的信息，又優(yōu)于上一代。這樣周而復(fù)始，群體中個(gè)體適應(yīng)度不斷提高，直到滿足一定的條件。 數(shù)學(xué)模型如下： 設(shè)圖 G 由非空點(diǎn)集合 12{ , ... }nV V V V? 和邊集合 12{ , ... }mE e e e? 組成，其中1 2 1 2 2 1( , ) e , P , ) ( P , P ) ,i i i i i i i ie P P E P? ? ?且 若 （ 則 G 為 一 個(gè) 有 向 圖 ； 又設(shè) ie 的值為 ia ，12{ , ... },mA a a a? 故 G 可表示為一個(gè)三元組 { , , }G P E A? 則求最短路徑的數(shù)學(xué)模型可以描述為： 貴州大學(xué) 第 14 頁(yè) 1m in *..niiiiiAEs t A A E E????????? 實(shí)驗(yàn)具體 內(nèi)容 ： 第一 、 編碼與初始化