劉婷

(大連交通大學(xué) 軟件學(xué)院，遼寧 大連 116028)

0 引言

大多數(shù)車間調(diào)度問題屬于多目標(biāo)問題，一般來說，它各個(gè)優(yōu)化目標(biāo)之間通常相互沖突，即不可能同時(shí)在所有目標(biāo)上都達(dá)到最優(yōu)，只能在多個(gè)目標(biāo)之間進(jìn)行協(xié)調(diào)和權(quán)衡［1］.求解多目標(biāo)調(diào)度的傳統(tǒng)方法是將其轉(zhuǎn)化為單目標(biāo)優(yōu)化問題進(jìn)行處理，如多目標(biāo)加權(quán)法、層次優(yōu)化法等.多目標(biāo)遺傳算法具有處理大的問題空間的能力，在一次進(jìn)化過程中可以得到多個(gè)可行解曲面，對(duì)問題域的先驗(yàn)知識(shí)沒有要求，對(duì)函數(shù)定義域的凸性不敏感，這正是經(jīng)典算法所不具備的［2］.所以，應(yīng)用遺傳算法求解車間調(diào)度多目標(biāo)優(yōu)化問題，是這一領(lǐng)域的發(fā)展趨勢(shì).本文采用多點(diǎn)交叉的方式，提高收斂速度，預(yù)防早熟，同時(shí)采用交互權(quán)重方式使決策人的偏好盡可能得到滿足，將多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)問題.

1 新的交互式多目標(biāo)遺傳算法的基本思想

本文采用變點(diǎn)交叉的方式來提高多目標(biāo)遺傳算法的收斂速度，避免其局部收斂，引起早熟.同時(shí)針對(duì)傳統(tǒng)的多目標(biāo)遺傳算法忽略決策者偏好這一問題設(shè)計(jì)一種交互權(quán)重，改進(jìn)之處有以下兩點(diǎn):①采用變點(diǎn)交叉的方式彌補(bǔ)多目標(biāo)遺傳算法在解決作業(yè)車間調(diào)度問題時(shí)收斂速度慢和容易陷入局部最優(yōu)化的不足;②利用代理值置換法(SWT)［3］的思想對(duì)各目標(biāo)兩兩權(quán)衡分析，設(shè)計(jì)一種交互權(quán)重，從而簡(jiǎn)化多目標(biāo)問題，體現(xiàn)決策者偏好.

1.1 變點(diǎn)交叉的方式

對(duì)于多目標(biāo)遺傳算法在解決車間調(diào)度問題中存在的收斂速度慢和容易陷入局部最優(yōu)化的不足，提出一種采用變點(diǎn)交叉方式的多目標(biāo)遺傳算法.我們發(fā)現(xiàn)，傳統(tǒng)的遺傳算法都以固定交叉點(diǎn)數(shù)進(jìn)行交叉變異.但如果交叉點(diǎn)過少，起不到向最優(yōu)解收斂的目的，而交叉點(diǎn)過多，收斂速度又會(huì)降低.

為在以上兩者之間找到平衡，本文設(shè)計(jì)了變點(diǎn)交叉的方式.運(yùn)算初期采用多點(diǎn)交叉的方式，在于提高收斂速度.在運(yùn)算后期逐步減少交叉點(diǎn)，直至采用兩點(diǎn)交叉、單點(diǎn)交叉的方式，避免丟失最優(yōu)解導(dǎo)致早熟收斂.

交叉點(diǎn)數(shù):式中，Nmax是設(shè)定的最多交叉點(diǎn)數(shù);Nmin是設(shè)定的最少交叉點(diǎn)數(shù);t是本次運(yùn)算所設(shè)定的變化間隔.這樣，在每個(gè)運(yùn)算前期交叉點(diǎn)比較多，有很強(qiáng)的全局搜索能力.在中后期交叉點(diǎn)數(shù)比較少，可以防止局部?jī)?yōu)化，同時(shí)加快收斂速度.

圖1說明了4×4調(diào)度問題的變點(diǎn)交叉過程:第一代交叉點(diǎn)比較多，逐漸至最后一代為單點(diǎn)交叉.

圖1 變點(diǎn)交叉

1.2 多目標(biāo)權(quán)衡分析，誘導(dǎo)交互權(quán)重

由于人的認(rèn)知局限性和直覺模糊性，要直接確定決策者偏好關(guān)系是一件非常困難的事情［4］.因?yàn)闆Q策者在表達(dá)偏好時(shí)，往往只能對(duì)各目標(biāo)的偏好程度提供主觀判斷，采用諸如“若保持其他目標(biāo)不變，愿意用多少單位的目標(biāo)A的性能損失換取多少單位目標(biāo)B的性能改進(jìn)”、“目標(biāo)A比目標(biāo)B重要”［5］等語言定性地表達(dá)兩兩目標(biāo)的權(quán)衡關(guān)系，而不能給出精確的數(shù)學(xué)描述，因此多目標(biāo)權(quán)衡分析采用一種間接的方法.

假設(shè)初始可行解集為 S*={S1，S2，S3，…，Sn}，由代理值置換法［6］的思想，則其在目標(biāo)i處相對(duì)目標(biāo)j處的偏置換率可以近似為:

λij(sk)的含義為:在非劣可行解sk處，降低目標(biāo)fi的性能一個(gè)單位，同時(shí)必須提高目標(biāo)fj的性能λij(sk)個(gè)單位，從而使其他目標(biāo)性能保持不變.

(1)通過與決策人的交互誘導(dǎo)出其偏好信息

通過人機(jī)界面向用戶提問:“保持其他目標(biāo)不變的情況下，你愿意犧牲目標(biāo)fi的多少個(gè)性能單位(kij(sk))以改進(jìn)目標(biāo)fj的性能?”，同時(shí)給出參考和限制，即:“若保持其他目標(biāo)性能不變，降低目標(biāo)fi的性能一個(gè)單位必須提高目標(biāo)fj的性能λij(sk)個(gè)單位.”這說明了決策者能夠做出的讓步，表達(dá)出他在此方面的偏好.其中，0≤kij(sk)≤λij(sk).kij(sk)選擇參照表1.

表1 目標(biāo)間相對(duì)重要程度的量化值

(2)將決策者隱性偏好轉(zhuǎn)換為顯性目標(biāo)權(quán)重

由于目標(biāo)之間的性能單位并不相同，具有不可比性，本文以目標(biāo)的變化率即目標(biāo)的相對(duì)數(shù)值來代替沒有意義的絕對(duì)數(shù)值，作為目標(biāo)衡量的基準(zhǔn).

tij(sk)表示為在非劣解sk處，若保持目標(biāo)i不變，目標(biāo)j的變化率.

本文定義決策者的期望變化率為:

其中，Δf'ij(sk)=fij(sk)－kij(sk)

一般從人的思維習(xí)慣和心里狀態(tài)來講，決策者權(quán)衡目標(biāo)兩兩利害關(guān)系的期望更理智和實(shí)際，也往往體現(xiàn)了他對(duì)該目標(biāo)的關(guān)注程度［4］.同樣由于目標(biāo)單位的不可比性，以關(guān)注率(wij(sk))來表達(dá)決策者對(duì)目標(biāo)的偏好.

其中，Δtij(sk)=t'ij(sk)－tij(sk)

wij(sk)表示了在非劣解sk處，相對(duì)于目標(biāo)i來講決策者對(duì)目標(biāo)j的關(guān)注程度，即表達(dá)了決策者對(duì)于目標(biāo)之間兩兩比較后的的偏好.

定義wii(sk)=1，根據(jù)線性平均法不難計(jì)算決策者的權(quán)重偏好.

整理后可得體現(xiàn)決策者目標(biāo)偏好的權(quán)重wk，(k=1，2，…，i，…，j，…，n)，同時(shí)滿足 wk＞ 0，

2 新的多目標(biāo)遺傳算法流程

新算法流程如圖2所示，具體步驟如下:

Step1:針對(duì)車間調(diào)度的問題初始化參數(shù)，編碼采用文獻(xiàn)［7］Gen，Tsujimura和Kubota提出的基于工序的編碼方法;

Step2:給出至少一個(gè)用戶接受的可行解S(k);

Step3:通過人機(jī)交互，決策者對(duì)各目標(biāo)兩兩權(quán)衡;

Step4:由公式(3)～(6)，形成體現(xiàn)決策者主觀偏好的目標(biāo)權(quán)重wi;

Step5:將個(gè)體的目標(biāo)函數(shù)值作正規(guī)化處理;

Step6:計(jì)算個(gè)體適應(yīng)度;

Step7:采用選擇、變點(diǎn)交叉、變異等遺傳算子產(chǎn)生一個(gè)子代種群;

Step8:世代更迭，若滿足結(jié)束條件則停止，否則轉(zhuǎn)向Step6;

Step9:輸出最優(yōu)解.

圖2 新的交互式多目標(biāo)遺傳算法流程圖

3 算例分析

3.1 問題描述和參數(shù)選擇

本文對(duì)一個(gè)一般車間作業(yè)排序問題進(jìn)行了研究，某車間有m臺(tái)機(jī)器，欲加工n種工件，每種工件的加工過程可由一系列工序組成，每道工序由相應(yīng)的機(jī)器完成，每個(gè)工件在每臺(tái)機(jī)器上加工一次，每臺(tái)機(jī)器同時(shí)只能加工一個(gè)工件.其中m=10，n=10，并且以工件的最大完工時(shí)間和n個(gè)工件的平均延誤時(shí)間最小化為目標(biāo)，其加工時(shí)間與調(diào)整時(shí)間均為區(qū)間［10，100］上生成的隨機(jī)數(shù)，交貨期為區(qū)間［500，1200］上生成的隨機(jī)數(shù).新算法的基本參數(shù)的合理取值在表2中給出.

表2 新算法參數(shù)設(shè)置

以無偏好多目標(biāo)優(yōu)化的小生境Pareto遺傳算法(NPGA)結(jié)果作為對(duì)比，NPGA算法參數(shù)列在表3中.

表3 NPGA算法參數(shù)設(shè)置

3.2 優(yōu)化結(jié)果分析

NPGA算法進(jìn)化完成時(shí)，最終解的3/4都是Pareto最優(yōu)解，而且分布極為廣泛，個(gè)體數(shù)目比較分散(圖3).讓決策者在眾多毫無側(cè)重點(diǎn)的可行解中進(jìn)行選擇具有一定難度.圖4顯示了改進(jìn)的多目標(biāo)遺傳算法以平均延誤時(shí)間最小為偏好信息進(jìn)化到相同代數(shù)后的個(gè)體分布情況.與NPGA算法相比，改進(jìn)的多目標(biāo)遺傳算法的個(gè)體向決策者偏好的方向集中，近60%的Pareto最優(yōu)解集中在平均延誤時(shí)間在100～200的區(qū)域上.圖5是兩種算法的收斂曲線對(duì)比，明顯新算法的效率更高.

圖3 NPGA算法解的分布情況

圖4 新算法解的分布情況

圖5 兩種算法收斂曲線對(duì)比

4 結(jié)論

(1)與NPGA相比，采用精英誘導(dǎo)目標(biāo)權(quán)重的方式更好地考慮了多目標(biāo)問題的決策者個(gè)人傾向，有效的簡(jiǎn)化了作業(yè)排序的選擇過程.

(2)采用變點(diǎn)交叉的方式可防止局部收斂，加快運(yùn)算速度;

綜上所述，改進(jìn)的多目標(biāo)遺傳算法適合于進(jìn)行最佳作業(yè)排序方案的選擇，幫助管理者做出科學(xué)合理的決策，可有效地運(yùn)用于作業(yè)車間調(diào)度問題.

［1］王凌.智能優(yōu)化算法及其應(yīng)用［M］.北京:清華大學(xué)出版社，2001:131-170.

［2］周泓，張惠民.求解多目標(biāo)作業(yè)排序問題的遺傳算法［J］.系統(tǒng)工程理論與實(shí)踐，2008，8(8):1-8.

［3］CHANGKONG V，HAIMES Y Y.Multi-objective Decision Making:Theory and Methodology［M］.New York:North-Holland，1983.

［4］申曉寧，郭毓，陳慶偉，等.一種引入偏好信息的多目標(biāo)優(yōu)化遺傳算法［J］.信息與控制，2007，36(6):746-753.

［5］周熠.傾向型心態(tài)的表示和推理［D］.合肥:中國(guó)科學(xué)技術(shù)大學(xué)，2006.

［6］古瑩奎，黃洪鐘，吳衛(wèi)東.基于Pareto解的交互式模糊優(yōu)化及其應(yīng)用［J］.清華大學(xué)學(xué)報(bào)(自然科學(xué)版)，2009，44(8):1111-1114.

［7］曹先彬，王本年，王煦法.一種病毒進(jìn)化型遺傳算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2009，22(1):59-62.