EDA-VNS混合算法在求解同序Flowshop問(wèn)題中的應(yīng)用＊-

張 強(qiáng) 王少參 李四超

（海軍駐鄭州地區(qū)軍事代表室1） 鄭州 450015）（鄭州機(jī)電工程研究所2） 鄭州 450015）

1 前言

自20世紀(jì)50年代Johnson發(fā)表了第一篇Flow-shop問(wèn)題論文之后，眾多學(xué)者開(kāi)展了關(guān)于Flow-shop問(wèn)題的研究［1］。隨著問(wèn)題規(guī)模的不斷增大，問(wèn)題的復(fù)雜性呈指數(shù)級(jí)別增長(zhǎng)，傳統(tǒng)的分支界定法、構(gòu)造式啟發(fā)式算法等精確算法已經(jīng)無(wú)法適應(yīng)問(wèn)題規(guī)模的增長(zhǎng)。與此同時(shí)，許多啟發(fā)式算法諸如遺傳算法、蟻群算法和粒子群算法等被應(yīng)用于Flow-shop問(wèn)題的求解。

估計(jì)分布算法（Estimation Distribution Algorithms，EDA）由 Mühlenbein和 Paaβ［2］提出的，該算法開(kāi)始于隨機(jī)產(chǎn)生的種群，通過(guò)初始種群的適應(yīng)度得到一個(gè)估計(jì)概率。然后，通過(guò)該估計(jì)分布產(chǎn)生新的個(gè)體，這個(gè)過(guò)程一直重復(fù)直至滿足結(jié)束條件。EDA算法已經(jīng)被應(yīng)用于0-1背包問(wèn)題（Knapsack Problem），旅行商問(wèn)題（Traveling Salesman Problem）和車間作業(yè)調(diào)度問(wèn)題（Job-shop Scheduling Problem）等組合優(yōu)化問(wèn)題［3］。

從生物進(jìn)化角度看，遺傳算法模擬了個(gè)體之間微觀的變化，而分布估計(jì)算法則是對(duì)生物群體整體分布的建模和模擬［4］。但是，有些較優(yōu)解群體性表現(xiàn)不強(qiáng)，分布估計(jì)算法對(duì)這些解搜索不太理想，為了改進(jìn)EDA的性能，Lozano建議在EDA過(guò)程中混合局部搜索算法［6］。本文用 VNS（Variable Neighborhood Search，變鄰域結(jié)構(gòu)搜索）算法與EDA結(jié)合，來(lái)提高EDA算法的性能。

2 用EDA算法求解FSSP

本文提出一種新的概率模型，基于該概率模型對(duì)EDA算法進(jìn)行了改進(jìn)。下面討論我們提出的EDA算法在求解FSSP中的應(yīng)用。

2.1 解的編碼和初始解

在諸多文獻(xiàn)中，直接用任務(wù)序列來(lái)表示一個(gè)解，本文也采用這樣的方式來(lái)表示解。為了保證種群中解的廣泛性，我們用根據(jù)均勻分布來(lái)隨機(jī)產(chǎn)生初始解。

2.2 選擇

本文采用的選擇策略具體描述如下：

（1）對(duì)種群中的每一個(gè)個(gè)體p，計(jì)算其適應(yīng)度f(wàn)（p）＝1／TFP（p）；

（2）將每個(gè)個(gè)體的適應(yīng)度按升序排列，即適應(yīng)度高的個(gè)體排在前面；

（3）父代的選擇基于prob（r）＝2r／p（p＋1），其中r表示個(gè)體在已經(jīng)排列好的適應(yīng)度集合中的位置。

2.3 概率模型和新個(gè)體的產(chǎn)生

概率模型的確定是EDA算法的重要內(nèi)容，它決定的EDA算法的效果。主要步驟是為父代種群的子集Q建立一個(gè)估計(jì)分布，在本文的算法中，進(jìn)行估計(jì)分布模型確定的時(shí)候既考慮了當(dāng)前Q中任務(wù)在整個(gè)任務(wù)序列排列又考慮了Q中任務(wù)序列的相似性。

假定：

ηjk：在Q被一個(gè)參數(shù)δ1擴(kuò)展后，工件j在位置k上或位置k之前出現(xiàn)的次數(shù)，ηjk表征了任務(wù)序列的重要性。

μj［k－1］：在Q被一個(gè)參數(shù)δ2擴(kuò)展后中，工件j在位置k－1之后出現(xiàn)的次數(shù)，μj［k－1］表征了任務(wù)序列的相似性。我們傾向于保留相似性很大的任務(wù)序列。

我們注意到δ1和δ2兩個(gè)參數(shù)是為了增強(qiáng)解的分散性，實(shí)際上，這兩個(gè)參數(shù)延緩了算法的收斂速度。

Ωk；到位置k尚未分配位置的工件集合。

我們定義πjk為工件j在k位置的概率，πjk＝ηjk×μj［k－1］／∑l∈Ωk（ηlk×μl［k－1］）。 根 據(jù) 這 個(gè) 概率，對(duì)每一個(gè)位置k，我們從尚未分配位置的工件集合Ωk中選擇一個(gè)工件，直至Ωk為空，產(chǎn)生一個(gè)新個(gè)體。

2.4 取代

取代是EDA算法中的最后一個(gè)步驟，取代的主要操作是更新種群。因此在每一代迭代中，都要根據(jù)Q產(chǎn)生子代個(gè)體幾個(gè)O，有許多種方法來(lái)確定O中的個(gè)體是否被留下。

在我們的算法中，我們用O中的個(gè)體與當(dāng)前種群中最差的個(gè)體比較，如果新個(gè)體優(yōu)于當(dāng)前最差個(gè)體，并且新個(gè)體的任務(wù)序列在種群中是唯一的，此時(shí)新個(gè)體取代當(dāng)前種群中的最差個(gè)體。

2.5 停止規(guī)則

停止條件表示搜索在該條件下終止，有多種停止規(guī)則可以使用。例如：最大迭代次數(shù)、計(jì)算時(shí)間限制、若干代沒(méi)有改進(jìn)結(jié)果等等，我們選用最大迭代次數(shù)和計(jì)算時(shí)間限制來(lái)作為停止條件。

3 混合EDA算法求解PFSP

為了提高EDA算法的性能并避免搜索過(guò)程陷入局部最優(yōu)，一個(gè)成功的方法就是在EDA算法中加入局部搜索的方法。我們將VNS算法作為一個(gè)改善策略與EDA結(jié)合用于解決PFSP。

我們?cè)诜N群的子集Q中應(yīng)用VNS算法，通過(guò)解的質(zhì)量得到一個(gè)改進(jìn)概率，如果這個(gè)改進(jìn)概率滿足條件，就用VNS算法生成一個(gè)新的個(gè)體。

我們選擇兩種鄰域結(jié)構(gòu)來(lái)實(shí)現(xiàn)，一種是交換局部搜索，一種是插入局部搜索。第一種鄰域結(jié)構(gòu)的構(gòu)建是通過(guò)交換兩個(gè)不同位置i，j的元素來(lái)實(shí)現(xiàn)的；第二種鄰域結(jié)構(gòu)的構(gòu)建是通過(guò)將i位置的元素插入到j(luò)位置之前實(shí)現(xiàn)的。（i≠j1≤i，j≤n）設(shè)定pc＝exp（－｜RD｜）為應(yīng)用VNS算法的概率。RD＝（f（xcurrent）－f（xbest））／f（xbest）。對(duì)每一個(gè)個(gè)體，如果pc大于或等于（0，1）之間產(chǎn)生的隨機(jī)數(shù)，我們就用VNS算法產(chǎn)生一個(gè)新個(gè)體。VNS算法的流程圖如圖1所示。

4 計(jì)算結(jié)果

圖1 VNS流程圖

算法用Visual-Studio2005的c＃進(jìn)行程序編寫，在處理器為2.4G，內(nèi)存為1G的PC上運(yùn)行。EDA—VNS混合算法的參數(shù)如下：P＝60，δ1＝δ2＝4／n，Q＝O＝3。用 Taillard提出的Flow-shop問(wèn)題基準(zhǔn)實(shí)例20×5，20×10和20×20作為算法的求解對(duì)象［7］，并將EDA-VNS混合算法和遺傳算法的計(jì)算結(jié)果進(jìn)行比較。

圖2 EDA-VNS混合算法和遺傳算法計(jì)算20×5實(shí)例的計(jì)算結(jié)果

圖3 EDA-VNS混合算法和遺傳算法計(jì)算20×10實(shí)例的計(jì)算結(jié)果

圖2，圖3和圖4是EDA-VNS混合算法和遺傳算法分別計(jì)算Flow-shop問(wèn)題基準(zhǔn)實(shí)例20×5，20×10和20×20的結(jié)果對(duì)比。從圖可以看出，EDA-VNS混合算法在求解Flow-shop問(wèn)題方面比遺傳算法更加有效，在第400代后，EDA-VNS混合算法就得到了質(zhì)量相當(dāng)不錯(cuò)的解，而遺傳算法在1300代的時(shí)候與最優(yōu)解還有一定的偏差。

圖4 EDA-VNS混合算法和遺傳算法計(jì)算20×20實(shí)例的計(jì)算結(jié)果

5 結(jié)語(yǔ)

本文針對(duì)EDA在求解Flow-shop問(wèn)題時(shí)微觀概念上的較優(yōu)解搜索能力不強(qiáng)的缺陷，將VNS算法與EDA集合，配合EDA搜索問(wèn)題的全局最優(yōu)。經(jīng)試驗(yàn)驗(yàn)證，EDA-VNS在求解Flow-shop問(wèn)題上有良好的性能。

［1］Misuo Gen，Runwei Cheng.Genetic Algorithms and Engineering Design［M］.John Wiley ＆Sons Inc，1997

［2］Mühlenbein H.PaaβG.From recombination of genes to the estimation of distribution.Binary parameters［J］.In：Lecture notes in computer science 1411：parallel problem solving from nature，PPSN，1996 Ⅳ：178～187

［3］Larraanaga，P.，Lozano，J.A.，（Eds）.Estimation of Distribution Algorithms：a new tool for evolutionary computation 2002［M］.Boston／Dordrecht／London：klower Academic publishers，2002

［4］周樹(shù)德，孫增圻.分布估計(jì)算法綜述［J］.自動(dòng)化學(xué)報(bào)，2007，33（2）：113～124

［5］盧申朋，馮好娣，劉宏.一種有到達(dá)時(shí)間的多處理器混合流水車間調(diào)度的遺傳算法（英文）［J］.計(jì)算機(jī)與數(shù)字工程，2008，36（10）

［6］Lozano JA，et al.Towards a New Evolutionary Computer Advances on Estimation of Distribution Algorithms［M］.Berlin：Springer，1996

［7］Taillard E.Benchmarks for basic scheduling problems［J］.European Journal of Operational Research，1993，64：278～285