遺傳演算法問題

㈠ 請問遺傳演算法的主要缺陷是什麼

遺傳演算法在廣泛問題解決上顯示了強大的適應性，但這種通用性也是其主要缺陷。其核心問題在於，為了能夠應對各種問題，演算法不具備針對特定問題的結構化利用能力。

以連續優化問題為例，梯度下降法是更高效的選擇，因為它直接利用了問題的連續性和梯度信息。同理，求解最短路徑問題時，Dijkstra演算法是更優解，因為它能准確地利用問題的結構。

為彌補這種通用性缺陷，遺傳演算法提供了大量的參數，如保留精英策略、交叉和變異操作的設置等。然而，這反而引發了一個問題：在解決特定問題時，是否應該思考該問題的結構並利用結構，還是通過調整通用搜索演算法來提高效率？

值得注意的是，並非所有通用演算法都是低效的。例如，圖靈完備語言的編譯器在某種意義上是高度通用的，但它們並未犧牲對問題結構的利用。編譯器通過分析程序結構，優化重復計算，這正是遺傳演算法所缺乏的。

歸根結底，遺傳演算法試圖模擬自然演化的過程，這一想法看似美妙，但其背後的復雜性甚至可能不及一些簡單的演算法，如Tarjan的強連通分量演算法。對於通用問題求解器來說，至少它們嘗試思考問題的子結構。因此，盡管遺傳演算法在通用性上表現出色，但在特定問題解決上的效率和效果仍存在改進空間。

㈡ 遺傳演算法解決tsp問題怎麼編碼

研究對象的初始基因是固定的，因此選擇了一種特定的編碼方式。初始種群可以通過隨機生成或者使用某種演算法生成，關鍵在於保持種群的多樣性。在種群初始化階段，需考慮以下幾點：

1. 根據問題固有的知識，確定最優解所佔的空間范圍，然後在此范圍內設定初始群體。這樣可以更有效地找到潛在的最優解。

2. 隨機生成一定數量的個體，從中挑選出最佳個體加入群體。這一過程需要不斷迭代，直到初始種群中的個體數量達到預定規模。

親和度的設定為1/f，其中f代表總路徑長度。在確定親和度之後，接下來可以根據城市序號進行選擇、交叉和變異操作。

在選擇階段，可以根據親和度從種群中選擇個體，以確保選擇出的個體具有較高的適應性。交叉操作則通過交換兩個個體的某些基因片段，生成新的個體，從而增加種群的多樣性。

變異操作則通過對個體的某些基因進行隨機改變，以引入新的變異和多樣性。通過選擇、交叉和變異操作，可以不斷優化種群，逐步接近最優解。

在整個過程中，保持種群的多樣性是非常重要的，因為這有助於避免陷入局部最優解，提高演算法的全局搜索能力。

通過這種編碼方式，遺傳演算法能夠更有效地解決TSP問題，找到近似最優的路徑。

㈢ 遺傳演算法的收斂性問題

是運算元有問題，交叉的方法都是比較簡單的，但對於某些情況可能並不好用，也就是說演算法本身無法體現出優勝劣汰的規則，可能因此導致無法收斂。

收斂數列令為一個數列，且A為一個固定的實數，如果對於任意給出的b>0,存在一個正整數N，使得對於任意n>N,有|an-A|<b,則數列存在極限A，數列被稱為收斂。非收斂的數列被稱作「發散」（divergence)數列。

可見收斂不是指數值越來越小，而是指與極限值的距離（即差的絕對值）越來越小，只要你的目標函數是壓縮映射，那麼使用遺傳演算法就一定可以計算出全局收斂的近似值。

(3)遺傳演算法問題擴展閱讀：

由於遺傳演算法不能直接處理問題空間的參數,因此必須通過編碼將要求解的問題表示成遺傳空間的染色體或者個體。這一轉換操作就叫做編碼，也可以稱作（問題的）表示（representation）。

遺傳演算法在搜索進化過程中一般不需要其他外部信息，僅用評估函數來評估個體或解的優劣，並作為以後遺傳操作的依據。由於遺傳演算法中，適應度函數要比較排序並在此基礎上計算選擇概率，所以適應度函數的值要取正值。由此可見，在不少場合，將目標函數映射成求最大值形式且函數值非負的適應度函數是必要的。