張 強 王少參 李四超

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

1 前言

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

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

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

2 用EDA算法求解FSSP

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

2.1 解的編碼和初始解

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

2.2 選擇

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

（1）對種群中的每一個個體p，計算其適應(yīng)度f（p）＝1／TFP（p）；

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

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

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

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

假定：

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

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

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

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

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

2.4 取代

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

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

2.5 停止規(guī)則

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

3 混合EDA算法求解PFSP

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

我們在種群的子集Q中應(yīng)用VNS算法，通過解的質(zhì)量得到一個改進概率，如果這個改進概率滿足條件，就用VNS算法生成一個新的個體。

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

4 計算結(jié)果

圖1 VNS流程圖

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

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

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

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

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

5 結(jié)語

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

［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］周樹德，孫增圻.分布估計算法綜述［J］.自動化學(xué)報，2007，33（2）：113～124

［5］盧申朋，馮好娣，劉宏.一種有到達時間的多處理器混合流水車間調(diào)度的遺傳算法（英文）［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