EDA-VNS混合算法在求解同序Flowshop問題中的應用＊-

張 強 王少參 李四超

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

1 前言

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

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

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

2 用EDA算法求解FSSP

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

2.1 解的編碼和初始解

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

2.2 選擇

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

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

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

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

2.3 概率模型和新個體的產生

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

假定：

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

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

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

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

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

2.4 取代

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

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

2.5 停止規則

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

3 混合EDA算法求解PFSP

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

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

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

4 計算結果

圖1 VNS流程圖

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

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

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

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

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

5 結語

本文針對EDA在求解Flow-shop問題時微觀概念上的較優解搜索能力不強的缺陷，將VNS算法與EDA集合，配合EDA搜索問題的全局最優。經試驗驗證，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］.自動化學報，2007，33（2）：113～124

［5］盧申朋，馮好娣，劉宏.一種有到達時間的多處理器混合流水車間調度的遺傳算法（英文）［J］.計算機與數字工程，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