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

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

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

Tabu部分原論文沒有很詳細(xì)的描述，因此很多內(nèi)容是小編收集各方資料，查閱其他相關(guān)文獻(xiàn)總結(jié)出的結(jié)論，小編自己編寫了三個(gè)tabu search，在這里分別分享介紹一下。如有專門研究這塊的同學(xué)，歡迎隨時(shí)指點(diǎn)交流！

代碼會(huì)在下一期統(tǒng)一給出，請(qǐng)關(guān)注我們！

Tabu1－基于編碼

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

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

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

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

swap很簡(jiǎn)單，再重復(fù)一下MS的變異：

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

鄰域部分代碼（開啟了一個(gè)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＿M(jìn)S．length； i＋＋）

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

int［］ MS ＝ chromosome．gene＿M(jìn)S．clone（）；

MSs．a(chǎn)dd（chromOps．machineSeqMutation（MS））；

｝

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

Tabu2－基于析取圖的k－insertion

析取圖

對(duì)JSP和FJSP來說，除了用甘特圖表示解意外，還有一個(gè)很重要的表示解的結(jié)構(gòu)：析取圖。

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