国产成人a亚洲精品,久久激情国产,午夜三级黄色,中文字幕亚洲天堂,18紧激韩,在线观看亚洲福利,国产亚洲日韩欧美蝌蚪窝91视频,日韩A片一区二区三区在线播放

程序猿聲

代碼黑科技的分享區(qū)

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

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

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

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

Tabu1-基于編碼

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

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

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

因此，小編在代碼中簡單設(shè)計了兩種鄰域：

1. 對相鄰的OS編碼進(jìn)行交換操作；

2. 對MS編碼的每個位置分別采用GA中的變異操作。

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

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

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

for?(int?i?=?0;?i?1;?i?+=?2)?
?for?(int?j?=?i?+?1;?j?2)?
??if(r.nextDouble()?0.5)
???OSs.add(swap(chromosome.gene_OS,?i,?j));

for?(int?i?=?0;?i??if(r.nextDouble()?0.5){
??int[]?MS?=?chromosome.gene_MS.clone();
??MSs.add(chromOps.machineSeqMutation(MS));
?}

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

Tabu2-基于析取圖的k-insertion

析取圖

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

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

邊有兩種類型，一種是machine arc（也叫disjunctive arc），由同一機(jī)器上的前一道工序指向相鄰的后一道工序。圖中彩線部分表示machine arc。另一種是job arc（也叫conjunction arc），由同一工件上的前一道工序指向相鄰的后一道工序。圖中黑色實現(xiàn)部分代表job arc。兩種邊分別表示machine 和job的兩個約束，因此一個點最多引申出4條邊。

除此之外，圖中還有兩個超級源點，起始點和終止點（圖中的0號start和10號finish）。他們是虛擬的點，代表加工開始和結(jié)束。Start點只有job arc，分別連向每個工件的第一道工序；Finish 點也只有job arc，從每個工件的最后一道工序連接到此點。（要注意邊的順序?。?/span>

圖中的邊上沒有權(quán)值，權(quán)值存放在點上，代表加工時間。起始、終止點加工時間為0。

讀到這里大家應(yīng)該能感受到，一幅圖實際上已經(jīng)代表了一個解。點（即工序）的加工開始、結(jié)束時間都可以通過最長路算法得出。整個schedule的最大makespan（加工時間）就是起始點到終止點的最長路距離。如果這幅圖里沒有環(huán)，則解可行；否則為不可行解。

這里的最長路又稱為critical path（關(guān)鍵路徑），即圖中粉色框框起的部分。

最長路的算法小編沒有找到很好的資料，自以為可以用DFS寫，如果在鄰域算子后要進(jìn)行全部工件starting time的更新，那么可以使用bellman-ford算法，這些在小編的代碼里都有實現(xiàn)。

結(jié)論：很多JSP、FJSP論文的tabu search都是基于析取圖進(jìn)行的，因為可以使用圖的特性，畢竟容易操作。

k-insertion

相較于JSP，小編能查到的FJSP的鄰域較少，這一部分主要參考一篇2000年的論文 “Effective neighbourhood functions for the fexible job shop problem”，講解其中的k-insertion鄰域。

k-insertion其實就是一個insert操作，簡單來說就是將critical path中的每一個操作，分別插入到其他可加工機(jī)器的某個位置，形成新解。這里強(qiáng)調(diào)，無論什么鄰域搜索，一定要在critical path上做文章，才容易改變解的makespan。

實際上，并不是一個機(jī)器上的所有位置都需要插入的。如果一道工序由于job邊約束，加工時間在考前的位置，那么插入某臺機(jī)器靠后的位置顯然不會使加工時間縮短?？紤]到這一點，我們只需要挑出可能使結(jié)果更優(yōu)的位置，執(zhí)行插入操作。

論文中對每個機(jī)器上的工序根據(jù)starting time（開始加工的時間）進(jìn)行排序，然后根據(jù)公式計算出兩個邊界：L_k， R_k。再通過二分查找找到這兩個位置。經(jīng)過證明，只有兩者的并集（圖中中間的部分）插入后可能優(yōu)化結(jié)果。這里的計算公式需要定義一些新變量，難度不大但是不好講清，想要深入研究的同學(xué)可以下載代碼、論文進(jìn)一步研究，這里暫時不多說了。

前面我們反復(fù)強(qiáng)調(diào)，我們的tabu是要嵌入到每一個個體中的，因此計算速度一定要快。如果對TS的每一個解都精確運(yùn)算出makespan，速度會很慢（第一個tabu就是這樣的）。因此，我們需要特殊的估值方法。

論文中的估值是一個上界。只需要根據(jù)前文定義的一些變量進(jìn)行簡單的加減乘除運(yùn)算即可得出，極大優(yōu)化了時間復(fù)雜度。這里同樣不多解釋。

然而，在實現(xiàn)析取圖的k-insertion后，小編發(fā)現(xiàn)自己實現(xiàn)的速度依舊很慢，嵌入個體后算法根本跑不動。因此小編嘗試了一下GA和TS的并行操作，用GA的初始解進(jìn)行TS操作，發(fā)現(xiàn)結(jié)果卻是有優(yōu)化，但是時間還是太久。小編目前也找不到代碼資料，只能自行編寫，因此陷入瓶頸。有了解這塊的同學(xué)可以和小編進(jìn)一步交流！

這里再提一句，JSP、FJSP的tabu禁忌表可以用插入或交換前后的的位置，制作一個二維表來表示，用單純的解作為禁忌對象會拖慢速度。

結(jié)論：Tabu2效果不錯，但是可能是因為析取圖部分沒有寫好，時間容易爆炸。

Tabu3-基于甘特圖的JSP N1鄰域

前面的tabu2是一種FJSP的鄰域結(jié)構(gòu)，搜索的是插入不同機(jī)器的解空間。如果不插入不同機(jī)器呢？

很顯然，問題轉(zhuǎn)化為JSP。

因此，小編在咨詢了一些專業(yè)人士后，打算嘗試加入JSP的tabu search。

JSP的tabu鄰域比FJSP多一些，比較知名的有N1，N4，N5，N6等鄰域（參考：A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem）。小編目前簡單實現(xiàn)了N1的鄰域，通過類似甘特圖的形式作為解的結(jié)構(gòu)。

在介紹N1之前還要提到一個critical block的概念。在critical path中，如果有若干個連續(xù)的工序是在同一機(jī)器上加工的，則稱其為一個critical block。很多tabu鄰域都是在critical block內(nèi)進(jìn)行操作，包括這里說的N1。

N1的鄰域為：在所有critical block內(nèi)，交換兩個相鄰工序在機(jī)器上的加工位置。

由于甘特圖的形式表示解沒有圖的性質(zhì)，因此計算makespan、更新starting time的方法和析取圖中又有所不同。簡單來說，需要像GA中查找空閑時間區(qū)間一樣不斷插入，然后更新時間。

簡單實現(xiàn)后說下小編實現(xiàn)+測試后的結(jié)論：時間上勉強(qiáng)可以接受，不至于跑不出來；但是解的質(zhì)量不夠理想。但至少說明嵌入個體是可行的。

這里提供一個進(jìn)一步改進(jìn)的思路：將第三部分的JSP的tabu鄰域和第二部分的k-insertion結(jié)合起來，因為我做第三部分的時候沒有寫成析取圖，所以這部分沒有做。結(jié)合之后還要將第二部分進(jìn)一步改進(jìn)，至少時間上要縮短，再嵌入到個體中。

Tabu部分大致就介紹到這里，剩下還會有一篇具體講解小編實現(xiàn)的代碼。講解有些地方不夠詳細(xì)，要具體研究的小伙伴還是推薦好好研讀論文。

參考

[1]Li, Xinyu , and L. Gao . "An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem." International Journal of Production Economics 174.Apr.(2016):93-110.

[2]Zhang, Chao Yong , P. G. Li , and Y. R. Zailin Guan . "A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem." Computers & Operations Research 34.11(2007):3229-3242.

[3]Mastrolilli, Monaldo , and L. M. Gambardella . "Effective Neighbourhood Functions for the Flexible Job Shop Problem." Journal of Scheduling 3.1(2015):3-20.

[4]Zhang, Guohui , L. Gao , and Y. Shi . "An effective genetic algorithm for the flexible job-shop scheduling problem." Expert Systems with Applications 38.4(2011):3563-3573.

推薦閱讀：

干貨 | 想學(xué)習(xí)優(yōu)化算法，不知從何學(xué)起？

干貨 | 運(yùn)籌學(xué)從何學(xué)起？如何快速入門運(yùn)籌學(xué)算法？

干貨 | 學(xué)習(xí)算法，你需要掌握這些編程基礎(chǔ)（包含JAVA和C++）

干貨 | 算法學(xué)習(xí)必備訣竅：算法可視化解密

干貨 | 模擬退火、禁忌搜索、迭代局部搜索求解TSP問題Python代碼分享

記得點個在看支持下哦～

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