【正文】 結(jié)束條件：當(dāng)前最優(yōu)解在 100代遺傳后仍未改變 ， 或已取到最優(yōu)解 TSP(旅行商)問題 GA在 TSP（ 旅行商 ） 問題求解中的應(yīng)用 ? 設(shè)存在 N個(gè)城市 ， Dij表示城 i與城 j之間的距離 ， Dij=Dji， 現(xiàn)在要求一條遍歷所有 N個(gè)城市 ， 且不走重復(fù)路的最短路徑 （ 最短哈密爾頓圈 ） 。在染色體以二進(jìn)制編碼的系統(tǒng)中，它隨機(jī)地將染色體的某一個(gè)基因由 1變成0，或由 0變成 1。 對(duì)許多用傳統(tǒng)數(shù)學(xué)難以解決或明顯失效的復(fù)雜問題，特別是優(yōu)化問題， GA提供了一個(gè)行之有效的新途徑。 ?? )(/)( icc xfxfP? )( ixf交 換 復(fù)制操作雖然能夠從舊種群中選擇出優(yōu)秀者，但不能創(chuàng)造新的染色體，因此，遺傳算法的開創(chuàng)者提出了交換操作。 ? 交換運(yùn)算與前述相同 ， 不過若進(jìn)行單點(diǎn)交換有可能使得兩個(gè)染色體在交換時(shí)產(chǎn)生的差異過大 ， 使得遺傳變得不穩(wěn)定 ， 優(yōu)秀的染色體不能遺傳到下一代 。 ? 算法的主要部分已經(jīng)討論完了 ， 但是還有一點(diǎn)值得提出的 ， 由于遺傳算法是一種不斷優(yōu)化的搜索算法 ， 因此 ， 我們可以用貪心算法構(gòu)造初始群 。例如 ， 兩父染色體串為： A： 2 8 4 10 * 5 1 7 3 * 6 9 B： 5 6 7 1 * 10 2 8 3 * 9 4 符號(hào) “ *” 表示交換點(diǎn) 。 9269367317511054108428 DDDDDDDDDDD ij ?????????????? ijDcxf m a x)(TSP(旅行商)問題 ? 關(guān)于選擇運(yùn)算 ， 可以考慮前面介紹的確定性選擇法 。 每一位 ，用 0、 1表示是否屬于子集 。上述 GA的工作過程可用 圖 1簡要描述。 GA就這樣反復(fù)迭代，直至滿足某種預(yù)定的優(yōu)化指標(biāo)。 子集和問題 ? 下面用遺傳算法來解決： ? 我們可以用 n位二進(jìn)制數(shù)來表示每個(gè)染色體 。 例如種群中的染色體： 2 8 4 10 5 1 7 3