離散粒子群優化算法求解多目標柔性作業車間調度問題??

喻明讓 陳 云 張志剛

(①中北大學機電工程學院，山西太原030051；②北方自動控制技術研究所，山西太原030051③北方通用動力集團有限公司，山西大同037036)

作業車間調度問題(JSP)作為典型的組合優化問 題,已經被證明是NP-hard問題[1-2].作為JSP的擴展,柔性作業車間調度問題(FJSP)包含兩個子問題:一個是機器選擇問題,即為每一道工序從其可選機器中選擇一臺機器；另一個是工序排序問題,即JSP.FJSP往往需要同時權衡多個優化目標,如最大完工時間、機器總負荷、任務拖期量以及瓶頸機器負荷等.由于FJSP以及多目標優化問題各自的復雜性,在以往的大多數研究中,研究者們往往將多目標FJSP優化問題通過一定的方式轉化為單目標FJSP,然后進行優化求解.Xia等[3]通過加權和的方式將最大完工時間、機器總負荷以及瓶頸機器負荷合并為一個加權目標函數,通過權重來反映各目標的重要程度,然后提出一種混合粒子群/模擬退火算法來求解多目標FJSP.類似地,Zhang等[4]提出的混合粒子群/禁忌搜索算法、Li等[5]提出的禁忌搜索和變鄰域搜索算法都是通過加權的方法將上述3個優化目標轉化為一個加權和目標來求解FJSP.

求解多目標優化問題的另一個方向就是基于Pareto的方法.基于Pareto的多目標優化方法試圖獲得所求問題的一組Pareto均衡解.Arroyo等[6]利用遺傳算法和局部搜索來求得流水車間調度問題的近似Pareto最優解集.Lei等針對多目標JSP分別提出了基于Pareto的多目標進化算法[7]和多目標粒子群算法[8].Behnamian等[9]針對混合流水車間調度問題提出了一種基于Pareto的啟發式算法.Li等[10]提出了一種基于Pareto的離散人工蜂群算法求解FJSP.

綜上所述,求解多目標FJSP的主要方法仍然是通過加權和將多目標優化問題簡化為單目標優化問題進行求解,當問題較為復雜時,合理分配各優化目標的權重是很困難甚至是不可能的.基于Pareto的方法在流水車間調度和作業車間調度優化問題上取得了一定的應用成果,但是較少應用于FJSP求解.進化算法如遺傳算法、粒子群優化(PSO)算法等能夠在一次迭代過程中產生多個Pareto近似最優解,在求解多目標優化問題上具有較強的優勢.尤其是粒子群算法的信息共享機制決定了其具有較強的搜索能力,然而粒子群算法中的速度和位置等變量都是連續的.如何將粒子群算法進行離散化使其能夠應用于調度問題的求解仍然具有一定的研究意義.為此,本文針對多目標FJSP提出了一種基于Pareto檔案的離散粒子群優化算法(PDPSO),通過交叉操作實現粒子位置的更新,從而在不改變編碼方式的前提下實現用PSO算法求解多目標FJSP優化問題.

1 問題描述

基于Pareto的多目標優化方法中需要用到以下概念(以最小化問題為例):

Pareto支配:對于決策空間中的兩個決策變量a和 b,當 fi(a)≤fi(b),?i∈{1,2,…,M},且 fi(a)＜fi(b),?i∈{1,2,…,M}時,稱 a支配 b(記作 a?b).也就是說,若a?b,則a對應的所有目標函數值都不大于b對應的目標函數值,且至少存在一個a對應的目標函數值小于b對應的目標函數值.當a不支配b且b不支配a時,則說a與b無關,記作a～b.

柔性作業車間調度問題一般定義為[11]:對于n個待加工工件,每個工件包含多道固定順序的加工工序,制造系統中有m臺機器.每一工序可以在多臺機器上進行加工,且相應的加工時間或成本也可能不同.要求確定最終各工序選擇的機器以及各工序在各機器上的加工順序及加工開始時間,同時優化一些性能指標.在對多目標柔性作業車間調度問題進行描述前,對其可能用到的符號作如下說明:

J＝{Ji,i＝1,2,…,n}表示n個待加工工件；

M＝{Mk,k＝1,2,…,m}表示系統中m臺機器；

Oij:第i個工件的第j道工序；

tijk:工序Oij在第k臺機器上的加工時間；

ci:第i個工件的完工時間；

Wk:第k臺機器的負荷；

為了便于后續和其他算法進行對比,本文選取的優化目標分別為最大完工時間、機器總負荷以及瓶頸機器負荷.各優化目標描述如下:

2 離散粒子群算法

2.1 標準粒子群算法

在大多數文獻中,一般將Shi等[12]提出的帶有慣性權值的粒子群算法作為標準粒子群算法.其速度與位置更新公式如下:

2.2 離散粒子群算法

由公式(1)可以發現,標準粒子群算法的速度與位置都是連續變量,無法直接應用于車間調度這類離散組合優化問題.文獻[8,13]通過對編碼方式進行改進從而將調度問題轉化為連續問題,進而采用PSO進行求解.但是這會使問題的編碼變得復雜,不能應用于FJSP的求解.為此,本文將遺傳算法中的交叉操作引入到PSO中,提出了一種離散粒子群優化算法(DPSO).此時,粒子位置更新公式如下:

(2)O2和種群全局最優位置作為兩個新的父代粒子經過交叉產生兩個新的子代粒子和選擇兩個新子代個體中較優的個體作為粒子更新后的位置.

值得注意的是,將上述DPSO應用于多目標優化問題時,每次交叉產生的兩個子代粒子可能彼此不受支配,此時可以采用和pbest選擇策略一樣的方法來選擇兩個體中的較優個體.pbest選擇策略將會在3.2節中進行介紹.

3 PDPSO求解多目標FSJP問題

PDPSO求解多目標FJSP問題流程如圖2所示,將外部檔案EA引入到前述DPSO中用于保存每一輪迭代產生的優秀個體.對于多目標優化問題,在Pareto概念下,粒子的pbest以及種群的gbest不再是唯一的,因此需要進行pbest以及gbest的選擇.同時還需要對EA進行維護,以保證最終得到的Pareto解集在具有一定多樣性的前提下盡可能接近真實Pareto前沿.最后,將變異操作引入到PDPSO中以增強算法的局部搜索能力.接下來對應用PDPSO求解多目標FJSP的關鍵操作進行介紹.

3.1 編碼與解碼

3.1.1 編碼

表1 一個3×3柔性作業車間調度問題

在PDPSO中,編碼就是將所求解問題用粒子來進行表示.如前所述,FJSP包含兩個子問題,即機器選擇和工序排序.因此,采用分段編碼的方式來進行描述.表1給出了一個3×3FJSP實例,其中999表示該機器不能用于相應工序的加工.針對該實例的一個可行編碼如圖3所示.其中工序段表示各工序的加工順序,工序段的長度等于各工件包含的總工序數,編碼值表示工序編號,編碼出現的次數表示其對應的工序編號.如工序段的第一個3表示J3的第一道工序,第二個2表示J2的第二道工序,以此類推.機器段表示對應工序所選擇的加工機器編號,如機器段的第一個3對應的工序段值為3,且為第一個3,表示J3的第一道工序選擇了機器M3,相應的加工時間由表1知為3 min.

3.1.2 解碼

在PDPSO中,解碼就是將粒子包含的信息轉化為相應問題的解.采用上述編碼方式時,當一個粒子位置確定時,其對應的各工序選擇的加工機器以及各工序的加工順序都已經確定.該問題轉化為一個標準的JSP問題,因此可以采用已有的解碼方法將該粒子解碼為活動調度.本文采用文獻[11]中的解碼方法,圖3所示粒子,其解碼結果如圖4所示.

3.2 pbest選擇方法

3.3 Pareto解集構造方法

粒子群算法在一次更新過程中,種群中可能存在多個不被其他粒子支配的粒子,這些粒子構成了該輪迭代的Pareto解集.Pareto解集是后續進行外部檔案維護以及pbest選擇的依據.簡單的說,Pareto解集構造就是要找到種群中所有不被其他粒子支配的粒子.這對應著NSGA-II[14](一種典型的多目標進化算法)中的第一級Pareto解.因此本文采用文獻[14]中的方法進行Pareto解集構造,選擇其第一級Pareto解作為本算法中的Pareto解集.

3.4 Pareto檔案維護與gbest選擇

在PDPSO中,通過Pareto檔案維護,使其中保存的解逐漸接近真實Pareto前沿并盡可能均勻分布.本算法中將Pareto檔案維護與gbest選擇同時進行,從而保證Pareto檔案中的個體至少為一個粒子的gbest,從而使算法盡可能搜索到全部Pareto前沿并避免局部收斂.

令EAt和EAt+1分別表示當前迭代和下一次迭代時的外部檔案.

令Xt＝{x1,x2,…,xk}為當前迭代產生的Pareto最優解集.

令Nmax和Nact分別表示外部檔案最大規模和外部檔案中當前個體數.

則外部檔案維護與gbest選擇流程如下:

(1)依據前述Pareto解集構造策略可知Xt中的每一個粒子必然支配種群中的一個或多個粒子.假設某粒子被xk支配,則首先選擇xk為其gbest.此時,一個粒子可能存在多個gbest,因為其可能同時被多個粒子支配,同時每一個粒子至少有一個gbest.

(2)將EAt中的個體復制到EAt+1中.

(3)對于Xt中的每一個個體xk,執行以下子步驟:

①如果xk支配了EAt+1中的部分個體,則刪除這些被支配的個體,并將xk加入到EAt+1中.

②如果xk被EAt+1中的個體Zt+1＝{z1,z2,…,zj}支配,則原來以xk為 gbest的粒子重新選擇Zt+1為其gbest,同時拒絕xk加入到EAt+1.

③如果xk與EAt+1中的個體無關,則執行以下子步驟:

ⅰ如果 Nact＜Nmax,將 xk加入到 EAt+1；

ⅱ如果Nact≥Nmax,將xk加入到EAt+1中,采用文獻[14]計算EAt+1中各成員的擁擠距離,并刪除擁擠距離最小的個體.若刪除的個體為新加入的xk,則隨機從外部檔案中選擇一個個體代替作為群體中被xk支配的粒子的gbest；

(4)由于步驟(1)和步驟②都可能使某一粒子存在多個gbest,檢查各粒子的gbest個數,若大于1,則隨機從這些gbest中選擇一個作為該粒子最終的gbest.

4 粒子更新方法

4.1 交叉操作

在PDPSO中,通過交叉操作實現粒子位置的更新.由圖3可知,粒子編碼包括兩個部分:工序段和機器段.接下來對各段的交叉操作分別進行介紹.

4.1.1 工序段交叉操作

工序段的編碼方式為調度編碼中常用的基于工序的編碼.基于工序的編碼具有半Lamarkian特性,交叉操作對算法性能有很大影響.本算法中采用基于工件編號的交叉方法.具體操作結合圖5介紹如下:

(1)隨機將工序依據工件編號劃分為兩個非空集合S1和 S2,如 S1＝{J1},S2＝{J2,J3}.

(2)生成兩個空子代O1和O2,將P1(P2)中屬于S1的工序編碼復制到O1和O2中對應的位置.

(3)將P1(P2)中屬于S2的工序編碼順序插入到O2(O1)中.

4.1.2 機器段交叉操作

機器段交叉操作結合圖6介紹如下:

(1)隨機選擇兩個不同的交叉點,將父代粒子分為三段,P1劃分為 A1、B1和 C1,P2劃分為 A2、B2和 C2.

(2)生成兩個空子代O1和O2,將B1(B2)中的編碼復制到O1(O2)中對應的位置.

(3)將A1(A2)和C1(C2)中的編碼順序插入到O2(O1)中.

4.2 變異操作

粒子群算法后期,粒子集中在某一最優(或局部最優)區域,運動緩慢.為此,在PDPSO中,將變異操作引入到粒子群優化算法中以增強算法局部搜索能力.變異操作結合圖7介紹如下:

(1)隨機選擇粒子中的一個位置,將該位置對應的工序段和機器段編碼插入到其之前的任意位置.

(2)隨機選擇機器段的一個基因位并隨機改變其編碼值.

5 實驗結果與分析

本節對本文所提方法進行測試,算法主要參數包括:粒子種群大小為10×n,其中n表示工件數量；最大迭代次數為10×n×m,其中m為機器數量；變異概率Pm＝0.1,交叉概率為1,即所有粒子都需要通過交叉操作來更新其位置.

表2 各種算法對5個實例的測試結果對比

為了覆蓋不同規模的調度問題,本文選擇了5個實例,實例規模分別為4×5(I1)、8×8(I2)、10×7(I3)、10×10(I4)和15×10(I5).該實例被廣泛應用于各種求解方法,從而方便后續的對比.各測試實例詳細信息可以參考文獻[15-16].

本文從已有文獻中選擇了4種具有代表性的算法來與本文算法進行對比.選擇的4種算法分別為PDABC[10]、MOGA[17]、HPSO[3]和 PSO/LS[18].各算法得到的Pareto解集對比如表2所示,其中?表示該組解被本文算法得到的一組或多組解支配.本算法得到的第一組解對應的甘特圖分別如圖8和圖9所示.

從表2中對比數據可以發現,已有算法得到的解總是存在一組或多組解被本文算法得到的解支配.依據Pareto最優的概念,被支配的解不是真正意義上的最優解.也就是說,本文算法能夠得到比已有算法更優的解,說明本文算法具有較強的搜索能力.另外由于所選測試實例規模覆蓋較為全面(從4×5到15×10),說明本文算法具有較強的適應性.

6 結語

針對多目標柔性作業車間調度優化問題,本文提出了一種基于Pareto的離散粒子群優化算法.利用遺傳算法的交叉操作實現粒子位置的更新.粒子通過與其歷史最優位置以及群體最優位置的交叉實現粒子飛行經驗的共享,保持了粒子群優化算法優良的信息共享機制.利用Pareto外部檔案保存算法運行過程中產生的優秀個體,并將Pareto外部檔案維護與gbest選擇結合進行,從而使得外部檔案中的個體至少是種群中一個粒子的gbest,從而使粒子種群盡可能搜索到全部Pareto前沿并避免局部收斂.并將變異操作引入到PDPSO中進一步提高算法的局部搜索能力.最后通過不同規模的測試實例以及與其他典型算法的對比證明了本文所提算法能夠很好地求解多目標柔性作業車間調度問題,并且具有較強的適應性.