基于改進粒子群優化算法的多目標銅卷加工生產調度研究

張建軍 彭亞麗 張 利 劉小平

合肥工業大學，合肥，230009

0 引言

銅卷加工制造兼有離散型制造和流程型制造的特點，屬于典型的混合型生產方式[1]，其生產過程的非線性、隨機性、不確定性，導致該類問題的生產約束條件更為多樣，其生產調度問題具有更大的復雜性，求解更加困難。而調度問題本身往往需要綜合考慮生產成本、資源能耗和產品周期等多個因素，而且各因素之間往往會存在沖突，屬于多目標優化問題（multi－objective optimization problem，MOP）[2]，混合型制造業也是典型的MOP。MOP往往不存在使各目標都為全局最優的解，而是存在一個在多個目標間折衷的均衡解的集合，即Pareto最優解集，求解多目標問題的關鍵就是找到數量足夠多且分布均勻的Pareto最優解[3]。

自從Kennedy等[4]在1995年提出粒子群優化（particle swarm optimization，PSO）算法以來，PSO算法就以其概念簡單、容易實現和需要調整的參數較少等優點吸引了大批學者進行研究，逐步滲透到各個應用領域[5－7]。而將PSO算法應用到MOP需要解決三個問題：如何產生非支配解并構成Pareto解集；采用何種策略更新全局極值和個體極值；如何保持Pareto前沿上優化解的多樣性。目前，在銅卷加工等混合型生產調度中應用PSO算法的研究相對較少，但由于混合型生產在現代制造生產中具有典型的代表意義，并且屬于多目標優化問題，以及PSO算法自身的優勢和容易與其他算法進行融合的特點，使得研究PSO算法在混合型多目標生產調度中的應用有著深刻的意義與廣闊的前景。

1 多目標銅卷加工生產調度模型

1.1 銅卷加工生產方式描述

相對于傳統的離散型或連續型生產方式而言，銅卷加工的生產方式有自己的特點：生產過程更為復雜、多種生產方式并存、多品種小批量生產等。以某銅卷生產企業的黃銅卷加工為例，產品的生產從投料到最終生產出成品需要經過若干個連續生產加工的過程（每個生產過程為一個單元）：熔煉爐→罩式爐退火1→粗扎機1→罩式爐退火2→粗扎機2→中間退火（罩式爐）→脫脂機→精扎機→氣墊爐→罩式爐退火3→脫脂機→拉彎機。企業的生產是按訂單驅動的，并且每件在制品在任一連續生產過程結束時都要進入緩沖區暫存。

1.2 銅卷加工生產調度問題模型

在生產計劃調度中，由于企業接到的訂單種類和產品類別都不唯一，各產品的交貨期也會有差別，因此在調度之初需對訂單進行分解，并將分解后的訂單進行合并來安排生產，以便將同種類型以及交貨期接近的產品作為一類產品進行加工。根據該銅卷加工企業的生產調度問題，建立企業生產調度問題模型如圖1所示。企業從X個客戶接收到一些訂單，將訂單基于交貨期和產品種類進行分解和合并，產生要加工的產品系列a、b、c、d、f，每個產品都要經歷 M 個生產單元，每個單元對應一臺生產設備，則生產調度問題就是將這些產品在M個生產設備上的加工時間和順序進行優化。

圖1 銅卷加工生產調度問題模型

對于問題模型必須有一定的約束條件才能使調度算法有合理的解空間。為方便建立模型，我們對該銅卷加工企業的生產進行如下的約定：①產品的加工工藝路線是確定的；②企業的一批訂單共涉及N種產品（序號為1，2，…，N），第j種產品的交貨期為Tj（天）；③產品經歷M個連續生產單元，第j種產品在第i個生產單元上所用的時間為tij，開始加工時間為tsij，結束的時間為teij，產品最后實際完成加工時間為TeMi，后一個加工單元必須在前一個加工單元完成后方可開始加工工件；④任一連續生產單元在任一時刻只能加工一種產品；⑤在零時刻，任何一種產品均有可能被加工。

考慮到銅卷企業生產實際的需求，本文選擇交貨期滿意程度和完成時間兩項指標[8]建立多目標優化函數。交貨期滿意度指標用產品最大拖期Td度量，第j種產品的拖期表示為Tdj；完成時間用產品最大完成時間Tf度量。因此，銅卷加工多目標調度優化模型為

其中，式（1）表示調度問題的目標函數；式（2）表示最大完成時間為所有工件在最后一臺設備上完成時間的最大值；式（3）表示最大拖期取所有產品拖期的最大值，其中當所有產品均提前完成時，最大拖期為0；式（4）表示每個產品的拖期等于實際完工時間與交貨期之差；式（5）表示加工時間等于結束加工時間減去開始加工時間；式（6）表示某種產品在某個連續生產單元上的結束加工時間大于開始加工時間。

2 求解M OP的自適應改進PSO算法

2.1 多目標優化問題描述

一般地，一個多目標優化問題就是要求所有目標函數在滿足約束條件下越小越好，一個含有n個決策變量、m個目標變量的多目標優化問題可表述為[9]

其中，x為n維的決策矢量，x＝（x1，x2，…，xn）∈X?Rn；X為n維的決策空間；y為m維的目標矢量，y＝（y1，y2，…，yn）∈Y ?Rm；Y 為m 維的目標空間。

2.2 外部種群的更新

非支配排序遺傳算法（non－dominated sorting genetic algorithm，NSGA－Ⅱ）[10]是目前公認高效的多目標優化算法，NSGA－Ⅱ中非支配排序思想已成為目前M OPSO（PSO for multi－objective problem）構成Pareto最優解的主流方法[11]。利用外部種群保留種群進化過程中產生的非支配解是目前比較高效的精英策略。

本文借鑒文獻[12]中的基于擁擠距離排序的方法更新外部種群，其操作過程如圖2所示。設內部種群為Ps，進化到第t代時內部種群粒子數為St；外部種群為Pt，外部種群粒子數為Sp，設置外部種群最大粒子數為Sm（Sp≤Sm）。內部種群Ps進化后，將產生的非支配個體（Np為非支配個體的個數）復制到外部種群，形成種群P′t。

圖2 外部種群更新策略

（1）刪除P′t中的重復個體（目標值相同的個體即為重復個體，隨機刪除一個而保留另一個）；標記并刪除P′t中的非支配個體，此時記P′t中包含的非劣個體數為m2（m2≤Sm＋Np）；

（2）計算P′t中擁擠距離Di并降序排列，記為種群P″t；

（3）判斷m2與Sm的數值關系，若m2≤Sm，如圖2中情況①所示，則將P″t記為新外部種群Pt＋1，此時Pt＋1的后Sm－m2個個體為空；否則，如圖2中情況②所示，調用外部種群的縮減過程，僅保留P″t中的前Sm個個體，刪除后m2－Sm個最密集個體，形成縮減的外部種群Pt＋1，由此來保持外部種群的個體數在最大值Sm之內，避免了隨著進化運算的進行，非支配個體數無限增多而降低算法效率；同時，外部種群縮減時刪除最密集的多余個體而保留大量分散個體，保證了Pareto前沿的均勻分布。

其中對于非支配個體擁擠距離的計算，本文根據非支配個體與其周圍的兩個空間點的歐幾里得距離來計算：

式中，fi，j（x）表示第i個個體的第j個目標函數值；i－1、i＋1為外部種群基于各目標函數排序后個體i附近的兩個個體。

另外設置各目標函數排序后的第一個個體和最后一個個體的擁擠距離D1和DSp均為無窮大。

2.3 最優值更新策略

M OPSO希望獲得分布均勻的Pareto前沿，因此不同于求解單目標問題時只選取目標函數值最大或者最小的點，而是要選擇處于Pareto前沿中分散區域的點，從而引導原始粒子群向分散區域進化。圖2所示的外部種群Pt更新完成后，全局最優值Pg的更新策略分為如下兩種情況：

（1）若Pt中只包含極少數邊界個體，即所有個體的擁擠距離均為無窮大，則隨機選擇一個作為全局最優位置Pg；

（2）若Pt中包括擁擠距離不為無窮大的個體，則使用輪盤法選擇，即以較大概率選擇擁擠距離較大的個體為Pg，計算公式為

式中，PB（xi）為粒子xi被選中的概率；Di為xi的個體擁擠距離。

個體擁擠距離含有無窮大會造成輪盤法選擇失效，因此計算概率時定義邊界個體的擁擠距離為除去這些個體后其余個體擁擠距離的中位數。

通過比較個體歷史最優值與當前粒子的支配關系來確定是否更新個體最優值。若當前粒子支配該粒子的個體歷史最優值，則用當前粒子替換歷史最優值；若當前粒子與歷史最優值互不支配，則隨機選擇二者之一作為新的個體最優；否則，保持歷史最優值不變。

2.4 種群多樣性保持策略

2.4.1 粒子編碼與計算

借鑒遺傳算法的矩陣編碼方法對粒子進行編碼，編碼矩陣如下：

矩陣A是所有工件對應所有生產單元的完全編碼，其每一列對應一個生產單元，每一行對應一個工件。矩陣元素aij是區間（0，1）內的一個實數，其大小決定了每個工件在第j個生產單元上的加工順序。

解碼時，對矩陣A的第j（j＝1，2，…，M）列的元素a1j，a2j，…，aNj進行大小比較，按照數值從小到大的順序進行排列，排列結果即為這N個工件在第j個生產單元上的加工順序。顯然，從第二個生產單元開始，還得考慮工件在前面一個生產單元的結束時間，將結束時間和排序結果相結合來決定該工件在該生產單元上的加工順序。具體說來，若該工件在前一個生產單元的加工沒有結束，則考慮編碼矩陣排序結果中排在其后的工件是否已結束前一個生產單元的加工，若已結束，則安排該工件進行加工。

2.4.2 基于動態自適應慣性權重進行進化計算

根據上述編碼，計算時不再單獨考慮粒子在各維空間的信息，而是將編碼矩陣A整體作為搜索空間中的一個粒子，直接更新粒子的速度和位置的整體信息。

PSO算法的基本思想是隨機初始化一群沒有體積沒有質量的粒子，將每個粒子視為優化問題的一個可行解，粒子的好壞由一個事先設定的適應度函數來確定。每個粒子將在可行解空間運動，并由一個速度變量決定其運動方向和距離。假設一個由M個粒子組成的群體在D維搜索空間以一定的速度飛行，其中粒子i的位置的第d維分別為搜索空間的下限和上限；速度的第d維分量分別為最小和最大速度；個體最優位置為，全局最優位置為P（t）g。則粒子在t＋1時刻的位置和速度通過下式更新獲得[5]：

式中，ω 為慣性權重；r1、r2為均勻分布在（0，1）之間的隨機數；c1、c2為學習因子，通常取值為2；Pid為第i個粒子第d維的個體最優值；Pgd為所有粒子第d維的全局最優值。

慣性權重ω的大小決定了粒子對當前速度繼承的多少，較大的ω有利于全局尋優，較小的ω則有利于局部尋優，而根據進化代數進行慣性權重的自適應調整策略有利于加強保持種群多樣性的能力，因此本文采取了動態自適應慣性權重調整策略：

其中，r3為均勻分布在（0，1）之間的隨機數。本文根據前人經驗取ω0＝0.9，ω1＝0.35。

2.4.3 基于非支配解的內部種群規模自適應調整策略

如果進化多目標優化算法采用小規模種群，那么對于一些復雜的多目標優化問題將很難收斂到理想Parato前沿面，而且很難獲得均勻分布的Pareto最優解。因此，如何根據問題的復雜度自適應地調整種群的規模是需要進一步研究的問題[13]。根據非支配解在當前種群中所占的比例來自適應地調整種群規模是解決該問題的一個可行方向[9]。本文采取下式來更新內部種群大小：

式中，Ss、Se分別為最小、最大內部種群規模；Pp為非支配解在當前內部種群中所占比例。

由式（14）可知，種群規模是逐漸增大的，因此本文采取隨機單點交叉策略產生新的個體補充到原始種群以形成新的內部種群。具體操作如下：記錄內部種群進化結束時非支配解的個數Np，從原始種群中隨機選取Np個個體，從外部種群中隨機選取Np個個體，然后采用單點交叉方式產生新的個體復制到內部種群，同時將粒子的當前位置設置為個體最優值，由此形成新的內部種群進入下一代的進化，從而有效地保持了種群的多樣性。

2.5 基于自適應的改進PSO算法流程

基于以上分析，本文提出的求解M OP的改進PSO算法流程如圖3所示。

針對圖3，對該方法的操作步驟描述如下：①初始化內部種群Ps的粒子數為最小規模Ss，迭代次數t＝0（初始化時未開始迭代），隨機初始化粒子速度vi和位置xi，并將粒子當前位置作為該粒子的個體最優值。②判斷St中每個粒子是否是非支配解，若是，則將其放入外部種群，記錄外部種群粒子數Sp，轉 ③；否則，轉 ⑥。③ 刪除外部種群中的重復個體以及被支配個體，保留非劣個體。④計算外部種群Pt中各粒子的擁擠距離Di，并將所有粒子基于Di降序排列。⑤判斷Sp是否大于Sm，若是，則刪除Pt中后Sp－Sm個個體，轉 ⑥；否則，直接轉 ⑥。⑥ 更新全局極值Pg。判斷內部種群規模St是否超出規模上限Se，若是，直接轉 ⑦；否則，單點交叉產生新的粒子，并放入內部種群，并記錄個體極值，轉⑦。⑦t←t＋1。進化計算內部種群中個體速度和位置，根據進化計算結果更新個體極值。⑧判斷是否達到最大迭代次數tmax，若是，則輸出外部種群中的Pareto解集，結束；否則，轉②。

圖3 算法流程

3 性能驗證與實例仿真

3.1 測試函數和指標及性能分析

將本優化方法應用于經典的多目標優化函數ZDT1：

本文采用了如下2個評價非支配解集優劣的量化標準[14]進行算法的性能分析：

其中外部種群的粒子個數Sp是優化方法所得的非支配解的個數；DSi為第i個解到Pareto最優解在目標空間上的最短距離；di是第i個解到其他解在目標空間上的距離為di的平均值。

仿真環境：計算機處理器為英特爾Celeron（賽揚）2.66GHz，內存768MB，Windows XP操作系統，采用MATLAB7.0編寫算法程序。

參數設置如下：NSGA－Ⅱ、SPEA2（強度Pareto進化算法）[15]的交叉概率為0.8，變異概率為1／L（L為染色體編碼長度），SPEA2的外部集設為200；NSPSO（基于非支配解的PSO算法）[16]內部和外部種群大小均為200。本文算法的內部種群初始規模為200，最大規模為400，外部種群最大規模為200，迭代次數為1000，設置參數c1＝2，c2＝2，ω0＝0.9，ω1＝0.35。 表1所示為10次獨立運行的數據統計結果。

表1 各算法的收斂性和分布性比較

表1的實驗結果[17]表明，本文所提算法在收斂性和分布性方面與其他三種算法相比具有較大優勢，滿足了求解多目標優化的要求。

3.2 應用實例

將本文算法應用于某銅卷加工企業，通過仿真結果驗證算法的有效性。

選取該企業的5個加工單元對企業接到的一批訂單進行生產調度優化。各產品在各生產單元上的加工時間和交貨期如表2所示。

表2 產品在各生產單元上的加工時間表 h

鑒于最大完成時間的方差相對最大拖后時間要小，因此令目標f1為最大完成時間的5倍，目標f2為最大拖后時間的2倍[18]。

算法參數設置：內部種群初始規模Ss＝20，最大規模Se＝40，外部種群最大規模Sm＝20，迭代次數tmax＝100，設置參數c1＝2，c2＝2，ω0＝0.9，ω1＝0.35，外部種群粒子數初始化Sp＝0。

根據以上建立的數學模型與設計的算法，利用MATLAB7.0編程進行調度問題的求解，最終得到外部種群Pareto解集的分布如圖4所示。由圖4可以看出，算法得到了完整的Pareto解集，并且圖中Pareto最優解的目標向量比較均勻地分布在最優界面附近，說明基于擁擠距離排序的策略對外部種群保持的必要性。仿真結果表明，該改進的PSO算法用較小的迭代次數就可以得到較好的Pareto解，保持了算法的快速收斂性，體現了該調度方法的合理和有效性。

圖4 Pareto解集分布圖

4 結語

本文根據銅卷加工生產調度問題的特點，采用改進的粒子群優化算法求解該調度問題。首先采用外部種群保留進化過程中產生的Pareto最優解，同時在外部種群中基于擁擠距離概率更新全局極值，最后基于非支配解的概率使用單點交叉方式產生新的粒子來自適應調整內部種群的大小，同時采用動態自適應調整的慣性權重來更新粒子速度和位置。仿真實例驗證了該算法能較好地保持種群的多樣性，使算法能夠快速收斂到Pareto最優解集。如何將該算法進行調整用于更多約束和評價的混合型生產調度模型，需要進一步研究。

[1]張旭升，戴青云.一種基于改進蟻群算法的混合型調度算法[J].中國制造業信息化，2010，39（13）：8-17.

[2]Deb K.Multi－objective Optimization Using Evolutionary Algorithms[M].New York：John Wiley ＆Sons，2001.

[3]賈兆紅，陳華平，唐俊，等.面向多目標的自適應動態概率粒子群優化算法[J].系統仿真學報，2008，20（18）：4959-4963.

[4]Kennedy J，Eberhart R.Particle Swarm Optimization[C]／／IEEE Int.Conf.on Neural Networks.Piscataway，1995：1942-1948.

[5]李麗，牛奔.粒子群優化算法[M].北京：冶金工業出版社，2009.

[6]周輝仁，唐萬生，魏穎輝.基于微粒群算法的柔性流水車間調度優化[J].中國機械工程，2010，21（9）：1053-1057.

[7]魯建廈，蔣玲玲，李修琳.基于混合粒子群算法求解裝配線第二類平衡問題[J].中國機械工程，2010，21（4）：420-424.

[8]武廣州.混合型生產方式車間調度建模及應用[D].武漢：武漢理工大學，2007.

[9]公茂果，焦李成，楊咚咚，等.進化多目標優化算法研究[J].軟件學報，2009，20（2）：271-289.

[10]Laumanns M，Thiele L，Deb K，et al.Combining Convergence and Diversity in Evolutionary Multiobjective Optimization[J].Evolutionary Computation，2002，10（3）：263-282.

[11]陳民鈾，張聰譽，羅辭勇.自適應進化多目標粒子群優化算法[J].控制與決策，2009，24（12）：1851-1864.

[12]李中凱，譚建榮，馮毅雄，等.基于擁擠距離排序的多目標粒子群優化算法及其應用[J].計算機集成制造系統，2008，14（7）：1329-1336.

[13]Tan K C，Lee T H，Khor E F.Evolutionary Algorithms with Dynamic Population Size and Local Exploration for Multi－objective Optimization[J].IEEE Trans.on Evolutionary computation，2001，5（6）：565-588.

[14]蔣程濤，邵世煌.基于適配粒子群的多目標優化方法[J].計算機工程，2007，33（21）：175-178.

[15]Zitzler E，Thiele L.Multiobjective Evolutionary Algorithm：a Comparative Case Study and the Strength Pareto Approach[J].IEEE Transactions on Evolutionary Compution，1999，3（4）：252-271.

[16]Benabid R，Boudour M，Abido M.Optimal Location and Setting of SVC and TCSC Devices Using Non－dominated Sorting Particle Swarm Optimization[J].Electric Power Systems Research，2009，12（79）：1668-1677.

[17]陳紹新.多目標優化的粒子群算法及其應用研究[D].大連：大連理工大學，2007.

[18]王凌.車間調度及其遺傳算法[M].北京：清華大學出版社，2003.