混合算法(GA+TS)求解作業(yè)車間調度問題—禁忌搜索部分

大家好，在上一篇文章中，我們介紹了FJSP問題以及HA算法的GA部分。這一篇文章主要介紹嵌套在其中的Tabu Search部分。

種群進化＋鄰域搜索的混合算法（GA＋TS）求解作業(yè)車間調度問題（JSP）－算法介紹

Tabu部分原論文沒有很詳細的描述，因此很多內容是小編收集各方資料，查閱其他相關文獻總結出的結論，小編自己編寫了三個tabu search，在這里分別分享介紹一下。如有專門研究這塊的同學，歡迎隨時指點交流！

代碼會在下一期統(tǒng)一給出，請關注我們！

Tabu1－基于編碼

在之前的文章中說過，算法對每一代子代的每一個個體，都需要decode成可行解，然后運用禁忌搜索優(yōu)化解，再編碼回GA編碼，進入下一代。可想而知，如果tabu寫的不好，算法的耗時肯定會很高。

論文中的tabu其實是以第二種為主體的?；诰幋a的tabu相對而言比較盲目，當初編寫時也是基于試一試的心態(tài)。

前文提到，對一串合法的OS序列，無論進行怎樣的交換、插入運算，都可以解碼成可行解；對MS序列，在同一工件范圍內任意交換順序，也可以保證得到可行解。

因此，小編在代碼中簡單設計了兩種鄰域：1． 對相鄰的OS編碼進行交換操作；2． 對MS編碼的每個位置分別采用GA中的變異操作。

swap很簡單，再重復一下MS的變異：

隨機選擇MS中一半的數(shù)字，隨機換為對應操作可以選擇的某個機器。例如圖中長度為6的MS String，隨機選擇三個位置，對O11而言，共有三個機器可選擇，則隨機選擇1，2，3中一個數(shù)字替換掉原先的2。

鄰域部分代碼（開啟了一個50％的采樣）：

for （int i ＝ 0； i ＜ chromosome．gene＿OS．length － 1； i ＋＝ 2）

for （int j ＝ i ＋ 1； j ＜ chromosome．gene＿OS．length； j ＋＝ 2）

if（r．nextDouble（） ＜ 0．5）

OSs．add（swap（chromosome．gene＿OS， i， j））；

for （int i ＝ 0； i ＜ chromosome．gene＿MS．length； i＋＋）

if（r．nextDouble（） ＜ 0．5）｛

int［］ MS ＝ chromosome．gene＿MS．clone（）；

MSs．add（chromOps．machineSeqMutation（MS））；

｝

結論：這個鄰域設計的比較隨意，但經過小編的測試后發(fā)現(xiàn)效果不佳，小編在這里建議大家不要使用基于編碼的鄰域搜索。

Tabu2－基于析取圖的k－insertion

析取圖

對JSP和FJSP來說，除了用甘特圖表示解意外，還有一個很重要的表示解的結構：析取圖。

析取圖是一張有向圖。圖中的點表示工序，邊代表工序加工的順序。