---

theme: Chinese-red

一起養成寫作習慣！這是我參與「掘金日新計劃 · 4 月更文挑戰」的第15天，點選檢視活動詳情。

1. 禁忌搜尋演算法

本文主要介紹禁忌搜尋演算法中關鍵步驟的選取。

首先簡單回顧一下禁忌搜尋演算法的大體思路：一群兔子向要到達最高的山峰，他們從出發點（初始解）開始探索，每找一步，他們相互告知，在目前所到的最高處座上記號（禁忌），然後再商量下一步往哪裡找，短時間內他們不會重複再去探索已經做了記號的地方（記號就相當於被禁忌了），就這樣他們重複剛才的方式繼續探索，最終找到最高峰。

該演算法中”禁忌“是指：禁止重複前面的工作，相當於某個解被關進“小黑屋”了，需要等一段時間（禁忌長度）才能放出來，從而為了跳出區域性最優點。

禁忌搜尋演算法基本介紹及例項詳解請參考智慧演算法-禁忌搜尋演算法 - 掘金 (juejin.cn)

2. 關鍵步驟

2.1 禁忌物件的選取

禁忌物件是指禁忌表中被禁的那些變化元素，禁忌物件主要可以選擇一下幾種： - 解的簡單變化：同樣的解在一定禁忌長度內（期限）不能再出現。如$ABCDE$上一輪出現，在禁忌長度內就不能再出現$ABCDE$這個解。 - 解向量分量的變化：同樣的解的變化方式不能連續出現。如解$ABCDE$通過交換$BC$得到解$ACBDE$，即交換$BC$分量的操作不能連續出現。 - 目標值變化：相同的目標值在一定禁忌長度內不能出現。如將 $X1$ 代入目標函式得到100，將 $X2$ 代入目標函式也得到100，將 $X3$ 代入目標函式也得到100，因為得到的目標值都一樣，則$X1$，$X2$，$X3$在禁忌長度內需要被禁忌。

注意：解的簡單變化比解的分量變化和目標值變化的受禁範圍要小，可能造成計算時間的增加，但也給予了較大的搜尋範圍； 解分量的變化和目標值變化的禁忌範圍大，減少了計算時間，可能導致陷在區域性最優點（搜尋的不全）。

2.2 禁忌長度的選取

禁忌長度是指禁忌的步數，通俗來講就是關進小黑屋的期限，也就是在多少輪迭代中不能再用這個解。禁忌長度的選取主要有以下三種方式： 1. $t$可以為常數，易於實現；（t固定不變了） 2. $t$在$[tmin,tmax]$範圍內，t是可以變化的數，tmin和tmax是確定的。$tmin$和$tmax$需要根據問題的規模確定，t的大小主要依據實際問題、實驗和設計者的經驗。（t在上下限之間變化） 3. $tmin$和$tmax$的動態選擇。（上下限的大小動態調整） 禁忌長度對解的影響： - 禁忌長度過短，一旦陷入區域性最優點，出現迴圈無法跳出（想象一下禁忌長度為0，就反覆選擇同一個最優解） - 禁忌長度過長，造成計算時間較大，也可能造成計算無法繼續下去（相當於都被禁忌了，下一步迭代沒有解可以選了）。

2.3 候選集合的確定

每一輪迭代都要進行新的探索，那將要探索的地方是哪裡呢？將要探索的地方也就是候選解集。候選集主要有以下幾個方式來確定： 1. 從鄰域中選擇若干目標值最佳的鄰居入選； 2. 在鄰域中的一部分鄰居中選擇若干目標值最佳的狀態入選； 3. 隨機選取。

2.4 評價函式

每一輪迭代探索了很多新的地方，那這些地方的好壞怎麼判斷呢？需要用評價函式來計算這個解的好壞，起到了一個“評價”的作用。評價函式選擇方式從大的角度來說主要分為兩種： 1. 直接評價函式，通過目標函式的運算得到評價函式； 2. 間接評價函式，構造其他評價函式替代目標函式，應反映目標函式的特性，減少計算複雜性。