【元啟發式算法】基于序列優化的遺傳算法常用變異算子

問題描述

很多問題的優化可以建模為基于序列的優化，如旅行商問題（TSP）,排產問題，各類資源分配問題等，不同的序列有不同的優度。尋找最優序列的問題是NP難問題（其解空間為N!）。

解決方法

常用兩種方法解決這類問題：一種是啟發式算法，基于問題本身的規則得到較好的可行解，本質是貪心算法，這種方法速度較快，但因與問題本身聯系緊密（problem-specific）,導致其通用性較差。

另一種方法是元啟發式算法，例如遺傳算法、禁忌搜索算法、蟻群算法、模擬退火算法等。這類方法從進化，物理等過程中受到啟發，得到一種解空間的搜索策略，因其搜索策略獨立于問題本身（problem-independent）,因此通用性強。這類方法有兩個最本質的操作：

選擇

改變

選擇

選擇的策略基本分為三類：

選擇最優解（遺傳算法常選擇前N個最優解，防止進入局部極小值；禁忌搜索選擇1個最優的解，通過禁忌策略跳出局部極小值）。

輪盤賭選擇（根據每個解的評價值S，通過某種映射F（線性、指數等），得到每個解的概率P，然后根據概率選擇解），公式：P = F(S)，從而避免選擇最優解，陷入局部極小值。

錦標賽選擇（從所有解中隨機抽取N個，再從N個中找最優解），有點神經網絡中dropout的思想，也是種避免陷入局部極小值的策略。

改變

常用的改變策略有交叉和變異，但本質都是從一個解改變為另一個解，如基于序列優化的問題，就是從一個序列，變為另一個序列（1,2,3?-> 2,1,3）,改變策略要兼顧保留原始解已有的良好結構，同時高效的探索新的結構。改變策略對于元啟發式算法的效果和效率起到決定性作用，因此本文主要重點介紹幾個變異算子。

Swap(交換算子)

基本操作：隨機交換序列中的一對（或多對）數字，形成新序列。

Cross(交叉算子)

基本操作：序列自交叉，將序列分組，隨機按組打亂重排。

Flip(翻轉算子)

基本操作：將序列分組，每組翻轉后重組。

Untie(結結算子)

基本操作：將序列分為三段，對中間一段翻轉，形成新序列。

Shift(轉移算子)

基本操作：將序列中的一個數字轉移到序列中的另一個位置。

Cross_and_untie(組合算子)

基本操作：交叉算子和解鎖算子的組合操作。

graft(嫁接算子)

基本操作：將序列中的某段截取后，隨機嫁接到剩余序列。

總結：

第一代：swap, 第二代：cross, flip, 第三代：untie, shift, graft

shift: 能找到接近最優值的算子, 但不穩定

untie: 能在最快時間找到接近最優解的算子， 穩定性很強

cross_and_untie: 種群數量足夠大時，效果優于untie算子

運籌優化

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。