求解直覺模糊多目標(biāo)規(guī)劃的改進(jìn)遺傳算法

楊進(jìn)帥，王 毅，李 進(jìn)，文 童，劉占強(qiáng)

(1.空軍工程大學(xué)防空反導(dǎo)學(xué)院，陜西 西安 710051；2.西北大學(xué)信息學(xué)院，陜西 西安 710069)

求解直覺模糊多目標(biāo)規(guī)劃的改進(jìn)遺傳算法

楊進(jìn)帥1，王 毅2，李 進(jìn)1，文 童1，劉占強(qiáng)1

(1.空軍工程大學(xué)防空反導(dǎo)學(xué)院，陜西西安710051；2.西北大學(xué)信息學(xué)院，陜西西安710069)

針對(duì)多目標(biāo)規(guī)劃獲取的參數(shù)模糊，求解算法容易早熟收斂和陷入局部最優(yōu)的問題，提出了求解直覺模糊多目標(biāo)規(guī)劃的改進(jìn)遺傳算法。該算法通過定義多目標(biāo)規(guī)劃的非隸屬度，調(diào)節(jié)λ參數(shù)控制方案選擇，執(zhí)行模擬退火拉馬克學(xué)習(xí)，增強(qiáng)局部搜索能力，指導(dǎo)個(gè)體尋找最優(yōu)值。仿真分析表明，該算法可以靈活地產(chǎn)生多種方案，有效克服早熟收斂和陷入局部最優(yōu)的問題。

直覺模糊；多目標(biāo)規(guī)劃；改進(jìn)遺傳算法；拉馬克學(xué)習(xí)

0 引言

多目標(biāo)規(guī)劃是對(duì)多個(gè)相互沖突的目標(biāo)的平衡和優(yōu)化。多目標(biāo)規(guī)劃決策環(huán)境的不確定，使得獲取的參數(shù)是不完全的和模糊的。Bellman和Zadeh從事物模糊性的本質(zhì)出發(fā)，提出了模糊規(guī)劃的概念；此后，Zimmemann提出了模糊多目標(biāo)規(guī)劃，S.Orbvsk提出了模糊多目標(biāo)非線性規(guī)劃；Atanassov提出的直覺模糊集合(Intuitionistic Fuzzy Sets，IFS)在模糊的基礎(chǔ)上增加了非隸屬度函數(shù)[1-2]，更加細(xì)膩地刻畫客觀世界的本質(zhì)。

傳統(tǒng)算法將多目標(biāo)轉(zhuǎn)為單目標(biāo)進(jìn)行求解，難以得到最優(yōu)解。目前，國(guó)內(nèi)外學(xué)者普遍采用遺傳算法、粒子群算法、模擬退火算法等智能算法。遺傳算法由于其全局搜索性能突出、隨機(jī)性和簡(jiǎn)單易實(shí)現(xiàn)等優(yōu)點(diǎn)，被國(guó)內(nèi)外學(xué)者廣泛應(yīng)用于輸電網(wǎng)絡(luò)[3]、交通網(wǎng)絡(luò)[4]和軍事裝備[5]等鄰域的多目標(biāo)規(guī)劃，先后提出了并列選擇法，非劣分層遺傳算法，基于目標(biāo)加權(quán)法的遺傳算法，微遺傳算法[6]等改進(jìn)算法。但是，遺傳算法不善于對(duì)局部區(qū)域精細(xì)調(diào)整，容易早熟收斂，陷入局部最優(yōu)，不能有效解決約束優(yōu)化問題。針對(duì)上述問題，本文提出了求解直覺模糊多目標(biāo)規(guī)劃的改進(jìn)遺傳算法。

1 直覺模糊多目標(biāo)規(guī)劃模型

多目標(biāo)優(yōu)化的一般形式為：

(1)

其中，x=(x1,…,xn)，并且xi∈[li,ui]。

Bellman將式(1)轉(zhuǎn)化為模糊約束形式：

(2)

(3)

直覺模糊集在模糊集的基礎(chǔ)上，通過非隸屬度更加清晰地刻畫目標(biāo)間的關(guān)系。設(shè)fi(x)={〈x,ufi(x),γfi(x)〉,x∈U}為fi(x)的直覺模糊集，ufi(x)和γfi(x)表示[7]為：

(4)

(5)

(6)

設(shè)gj(x)={〈x,ugj(x),γgj(x)〉,x∈U}為約束函數(shù)gj(x)的直覺模糊集[8]，ugj(x)和γgj(x)為：

(7)

(8)

dj表示約束gj(x)允許最大的偏移；bj≥0用來調(diào)節(jié)猶豫度，當(dāng)bj=0，猶豫度為0，當(dāng)bj→，猶豫度→1-ugj(x)，bj一般取0～10；λ用來調(diào)節(jié)gj(x)允許最大的偏移。通過λ調(diào)節(jié)ugj(x)和γgj(x)的大小，控制對(duì)目標(biāo)函數(shù)的約束程度，產(chǎn)生不同的決策方案。取“最小”算子得：

(9)

取fi(x)和gj(x)的 “最小”算子得：

D=M∩S={〈x,uD(x),γD(x)〉,x∈U}

(10)

其中，uD(x)=uM(x)∧uS(x),γD(x)=γM(x)∨γS(x)。

對(duì)D在論域U上取“最大”算子，有：

(11)

因此，構(gòu)建直覺模糊多目標(biāo)規(guī)劃模型的一般形式：

(12)

式(12)中，x=[x1，…,xn]，且xi∈[li,ui]。顯然，若式(5)中的αi=1，式(8)中的bj=0，則β-α=1-2α，直覺模糊多目標(biāo)規(guī)劃退化為模糊規(guī)劃。因此，直覺模糊多目標(biāo)規(guī)劃拓寬了模糊多目標(biāo)規(guī)劃的表示范圍。

2 改進(jìn)遺傳算法

遺傳算法是Holland教授基于遺傳選擇和自然淘汰的生物進(jìn)化過程，提出的一種智能算法。其過程為隨機(jī)產(chǎn)生初始種群，計(jì)算適應(yīng)度值，通過交叉和變異操作進(jìn)化個(gè)體，淘汰適應(yīng)度值較小的個(gè)體，保留適應(yīng)度值較大的個(gè)體，組成子代種群。在迭代進(jìn)化過程中，遺傳算法貪心選擇適應(yīng)度大的個(gè)體，導(dǎo)致陷入局部最優(yōu)，種群容易早熟，無法收斂到全局最優(yōu)解。如圖1所示。

為此，國(guó)內(nèi)外學(xué)者通過精英選擇策略、自適應(yīng)交叉和變異等方法改進(jìn)遺傳操作；引入自適應(yīng)[9]、蟻群算法[10]、直接搜索[11]、模擬退火[12]等算法作為局部搜索策略，精細(xì)搜索遺傳算法的局部空間。本文基于模擬退火進(jìn)行局部搜索，采用拉馬克學(xué)習(xí)策略，將學(xué)習(xí)到的性狀直接在個(gè)體的基因中編碼。

2.1 拉馬克學(xué)習(xí)

拉馬克進(jìn)化理論的觀點(diǎn)是“用進(jìn)廢退，獲得性遺傳”，認(rèn)為生物體在生存期內(nèi)存在自身學(xué)習(xí)的過程，并能將后天學(xué)習(xí)獲得的性狀通過基因遺傳給后代[13]。這一理論在生物進(jìn)化中被證明是錯(cuò)誤的，卻可以將這一理論抽象為一種局部搜索機(jī)制，為改進(jìn)遺傳算法提供有益的啟發(fā)。

學(xué)習(xí)與遺傳進(jìn)化是生物體適應(yīng)環(huán)境變化的兩種不同形式，作用于不同的時(shí)間和空間。個(gè)體進(jìn)行學(xué)習(xí)的過程，即是個(gè)體局部搜索的過程。遺傳算法是一個(gè)全局搜索過程，感知環(huán)境緩慢的、整體的變化過程，而學(xué)習(xí)是全局搜索過程中的某一局部搜索，感知快速的、微小的變化過程。通過學(xué)習(xí)指導(dǎo)進(jìn)化方向[14]，跳出局部極值點(diǎn)，引導(dǎo)個(gè)體朝向全局極值點(diǎn)進(jìn)化。如圖2所示。

研究表明，模擬退火算法具有通用性和漸進(jìn)收斂性，能避免陷入局部最優(yōu)值[15]。本文利用模擬退火算法設(shè)計(jì)拉馬克學(xué)習(xí)策略，對(duì)種群中的個(gè)體進(jìn)行局部搜索。

步驟1:采用n種不同的鄰域結(jié)構(gòu)，對(duì)種群中個(gè)體x在初始溫度下進(jìn)行n(n-1)步執(zhí)行基于模擬退火的拉馬克學(xué)習(xí)；

步驟2:按下式計(jì)算每個(gè)鄰域的獎(jiǎng)勵(lì)值：

ηi=(fb-fli)/(n(n-1))

式中，fb為進(jìn)行局部學(xué)習(xí)前x的適應(yīng)度值，fli為使用第i(i=1,2,…,n)種鄰域結(jié)構(gòu)進(jìn)行局部搜索后所獲得的最佳目標(biāo)函數(shù)值；

步驟3:根據(jù)ηi，計(jì)算鄰域的選擇概率：

步驟4:采用輪盤賭選擇策略確定一個(gè)鄰域結(jié)構(gòu)，然后對(duì)種群的最佳個(gè)體在當(dāng)前溫度tk下再進(jìn)行局部搜索，得到個(gè)體x′；

步驟5:基于模擬退火的選擇準(zhǔn)則，計(jì)算學(xué)習(xí)得到的個(gè)體被保留的概率qtk：

步驟6:更新獎(jiǎng)勵(lì)值ηi，若Step4中選擇第i個(gè)鄰域結(jié)構(gòu)，則更新獎(jiǎng)勵(lì)值ηi=ηi+Δηi進(jìn)行更新，Δηi計(jì)算公式如上。

在鄰域范圍較小的情況下，采用拉馬克學(xué)習(xí)機(jī)制跳出局部極值點(diǎn)的可能性更大[16]。本文采用較為簡(jiǎn)單的鄰域結(jié)構(gòu)s={x:|x-x0|<ε}，其中ε<1。

2.2 改進(jìn)遺傳算法

改進(jìn)遺傳算法通過選擇父代種群的個(gè)體，劃分為n個(gè)鄰域，執(zhí)行基于模擬退火的拉馬克學(xué)習(xí)，并將學(xué)習(xí)到的表現(xiàn)型直接在子代個(gè)體基因中進(jìn)行編碼，指導(dǎo)個(gè)體朝向更好的解移動(dòng)，并能以一定概率接受差解，保持種群的多樣性，避免陷入局部極值。

遺傳算法作為全局搜索算法，產(chǎn)生更適應(yīng)學(xué)習(xí)的基因，為學(xué)習(xí)提供更好的初始條件，減小學(xué)習(xí)的復(fù)雜程度。而學(xué)習(xí)結(jié)果能夠指導(dǎo)進(jìn)化的方向，學(xué)習(xí)到的形狀被寫入基因。兩者的關(guān)系見圖3所示。

在遺傳算法的計(jì)算流程基礎(chǔ)上，將基于模擬退火的拉馬克學(xué)習(xí)作為一個(gè)附加模塊，從而改進(jìn)遺傳算法，具體流程如圖4。

2.3 求解直覺模糊多目標(biāo)規(guī)劃

由于多目標(biāo)規(guī)劃的變量較多，二進(jìn)制編碼無法有效描述變量，故選擇浮點(diǎn)數(shù)編碼。采用式(12)作為適應(yīng)度函數(shù)，使用輪盤賭選擇、算術(shù)交叉和非均勻變異操作，通過優(yōu)化直覺模糊多目標(biāo)規(guī)劃的隸屬度和非隸屬度函數(shù)逼近全局最優(yōu)解。

非均勻變異增強(qiáng)算法的局部搜索能力，對(duì)原基因作隨機(jī)擾動(dòng)，產(chǎn)生兩中基因：

具體求解算法步驟如下：

步驟1：初始化。設(shè)定參數(shù)，群體規(guī)模np，迭代代數(shù)k；初始溫度tm=t0，降溫系數(shù)a，群體p(k)；

步驟2：產(chǎn)生初始種群，計(jì)算適應(yīng)度值；

步驟3：對(duì)個(gè)體進(jìn)行算術(shù)交叉、非均勻變異操作得到種群p1(k)；

步驟4：執(zhí)行基于模擬退火拉馬克學(xué)習(xí)，搜索局部空間，學(xué)習(xí)得到的個(gè)體直接進(jìn)入子代種群p2(k)；

步驟5：計(jì)算種群p2(k)中個(gè)體的適應(yīng)度值，判斷是否滿足終止條件。若滿足終止條件，則輸出最優(yōu)值的結(jié)果，算法結(jié)束；若不滿足條件，令tm+1=d(tm),m=m+1，降低退火溫度，轉(zhuǎn)到Step2。

停止條件為是否進(jìn)化到最大迭代次數(shù)或者收斂到全局最優(yōu)值。在求解過程中，隸屬度函數(shù)和非隸屬度函數(shù)可以通過設(shè)置不同的λ參數(shù)值進(jìn)行優(yōu)化，調(diào)節(jié)目標(biāo)函數(shù)的適應(yīng)度值，逐漸逼近到全局最優(yōu)解。采用比例溫度下降法降低模擬退火溫度，可以平衡全局和局部搜索速度。

3 仿真及分析

為驗(yàn)證本文算法的有效性，選擇在處理器為Intel(R)Core(TM)i7-4790，Windows7旗艦版系統(tǒng)的計(jì)算機(jī)上，運(yùn)用Matlab語言編程實(shí)現(xiàn)典型的帶約束非線性多目標(biāo)規(guī)劃，進(jìn)行仿真比較。

設(shè)置參數(shù)：種群規(guī)模為100，迭代次數(shù)為100，交叉概率為0.8，變異概率為0.01；降溫系數(shù)為0.97，初始溫度為90。

實(shí)驗(yàn)一：取λ分別為1，0.8，0.6，0.4，0.2，0.1和0，生成不同的約束函數(shù)的非隸屬度，采用改進(jìn)遺傳算法進(jìn)行5次重復(fù)運(yùn)算，記錄目標(biāo)函數(shù)的最優(yōu)值，得到表1。相同設(shè)置下，求解模糊多目標(biāo)規(guī)劃并進(jìn)行比較，得到表2。

表1 改進(jìn)遺傳算法求解直覺模糊多目標(biāo)規(guī)劃

表2 改進(jìn)遺傳算法求解模糊多目標(biāo)規(guī)劃

隨著λ的減小，目標(biāo)函數(shù)f1和f2的解逐漸增大，越來越逼近最優(yōu)解。當(dāng)λ=0時(shí)取得最優(yōu)解，直覺模糊多目標(biāo)規(guī)劃模型能清晰地描述各目標(biāo)之間的關(guān)系。與表2相比，f2的值基本相同，但表1中f1的值比表2小3～8，表明直覺模糊多目標(biāo)優(yōu)于模糊多目標(biāo)規(guī)劃。

實(shí)驗(yàn)二：驗(yàn)證算法的收斂性能，并與PSO算法、標(biāo)準(zhǔn)遺傳算法進(jìn)行比較，得到圖5。

本文算法執(zhí)行基于模擬退火的拉馬克學(xué)習(xí)，學(xué)習(xí)到的結(jié)果指導(dǎo)了遺傳的進(jìn)化方向，使其朝著最優(yōu)值方向迭代，在第35代收斂到最優(yōu)值，其值大于標(biāo)準(zhǔn)遺傳算法，而粒子群算法沒有收斂到最優(yōu)解。

實(shí)驗(yàn)三：分析改進(jìn)遺傳算法的種群多樣性。使用3倍于每代適應(yīng)度的均值表征種群的多樣性，得到圖6。

從圖6看出，本文算法的種群均值在10.1～10.7之間，均值變化程度較大。可以認(rèn)為，該算法求解下既能朝最優(yōu)值方向進(jìn)化，又能保持一定比例的較差解，種群的多樣性豐富，有效克服了早熟收斂。

4 結(jié)論

本文提出了求解直覺模糊多目標(biāo)規(guī)劃的改進(jìn)遺傳算法。該算法引入非隸屬度，構(gòu)建了直覺模糊多目標(biāo)規(guī)劃，全面地刻畫了多目標(biāo)模糊的本質(zhì)，更加清楚地區(qū)分了各個(gè)目標(biāo)間重要程度；通過λ參數(shù)調(diào)節(jié)約束函數(shù)，產(chǎn)生靈活的方案，在決策過程中，可以根據(jù)不同的環(huán)境和任務(wù)需求，選擇不同的λ，得到相應(yīng)的優(yōu)化方案；執(zhí)行模擬退火拉馬克學(xué)習(xí)，精細(xì)搜索局部空間，并將學(xué)習(xí)到的性狀在后代基因中編碼遺傳，指導(dǎo)個(gè)體朝最優(yōu)值方向進(jìn)化，同時(shí)以一定的概率接受差解，保持了種群的多樣性。仿真結(jié)果表明，本文算法求解直覺模糊多目標(biāo)規(guī)劃的效益值優(yōu)于PSO算法和標(biāo)準(zhǔn)遺傳算法，能避免陷入局部最優(yōu)，克服了早熟收斂的問題。

[1]Atanassov K T. Intuitionistic fuzzy sets[J].Fuzzy Sets and Systems,1986,20(1):87-96.

[2]Atanassov K T, Gargov G. Interal valued intuitionistic fuzzy sets[J].Fuzzy Sets and Systems, 1989,23(31): 343-349.

[3]張寧.配電網(wǎng)多目標(biāo)經(jīng)濟(jì)性優(yōu)化模型和算法[J].電力自動(dòng)化設(shè)備,2016,32(8):48-53.

[4]孫楊,孫小年,李葆青等.接運(yùn)公交網(wǎng)絡(luò)設(shè)計(jì)的多目標(biāo)優(yōu)化模型及遺傳變鄰域搜索求解算法[J].北京工業(yè)大學(xué)學(xué)報(bào),2014,40(4):535-541.

[5]葛優(yōu),劉景萍,趙惠昌,等.基于正交相位編碼信號(hào)的MIMO雷達(dá)測(cè)速測(cè)距算法[J].探測(cè)與控制學(xué)報(bào),2016,38(6):80-83.

[6]馬小姝,李宇龍,嚴(yán)浪.傳統(tǒng)多目標(biāo)優(yōu)化方法和多目標(biāo)遺傳算法的比較綜述[J].電氣傳動(dòng)自動(dòng)化,2010,32(3):48-50.

[7]徐小來,雷英杰,戴文義.基于遺傳算法的直覺模糊多目標(biāo)規(guī)劃[J].電光與控制,2009,16(1):31-33.

[8]徐小來,雷英杰,戴文義.基于改進(jìn)PSO的加權(quán)直覺模糊多目標(biāo)規(guī)劃[J].系統(tǒng)仿真學(xué)報(bào),2009,21(11):3280-3282.

[9]劉文遠(yuǎn),劉彬.基于協(xié)同進(jìn)化的自適應(yīng)遺傳算法研究[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(14):31-33,36.

[10]鄒攀,李蓓智,楊建國(guó)，等.基于分層蟻群遺傳算法的多目標(biāo)柔性作業(yè)車調(diào)度方法[J].中國(guó)機(jī)械工程,2015,26(21):2873-2879.

[11]王勇勝,梁昌勇,鞠彥忠.多項(xiàng)目環(huán)境下time-cost置換問題建模與求解[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(20):237-240.

[12]李金忠,夏浩武,曾小薈，等.多目標(biāo)模擬遺傳算法及其應(yīng)用研究進(jìn)展[J].計(jì)算機(jī)工程與科學(xué),2013,35(8):77-88.

[13]王叢佼,王錫淮,肖健梅.基于網(wǎng)格化拉馬克學(xué)習(xí)機(jī)制的差分進(jìn)化算法[J].控制與決策,2015,30(6):1085-1091.

[14]張家奇,陳啟軍.學(xué)習(xí)對(duì)進(jìn)化的影響研究及仿真實(shí)驗(yàn)[J].系統(tǒng)仿真學(xué)報(bào),2007,19(24):5849-5851.

[15]Li Junhui, Chen Xin, Zhu Jinfu. MULTI-OBJECTIVE PROGRAMMING FOR AIRPORT GATE REASSI- GNMENT[J]. Transactions of Nanjing University of Aeronautics & Astronautics,2013,30(2): 209-215.

[16]閻嶺,蔣靜坪.進(jìn)化學(xué)習(xí)策略收斂性和逃逸能力的研究[J].自動(dòng)化學(xué)報(bào),2005,31(6):873-880.

[17]靳飛,單銳.基于局部搜索技術(shù)的混合遺傳算法[J].遼寧工程技術(shù)大學(xué)學(xué)報(bào)(自然科學(xué)版),2013, 32(2):269-273.

SolvingIntuitionisticFuzzyMulti-objectionProgrammingbyImprovedGeneticAlgorithm

YANG Jinshuai1, WANG Yi2, LI Jin1, WEN Tong1, LIU Zhanqiang2

(1.Air and Missile Defense College, Air Force Engineering University, Xi’an China; 2.School of Information, Northwest University, Xi’an 710069, China)

An improved algorithm based on operating simulate anneal lamarckian learning was proposed to solve intuitionistic fuzzy multi-objection programming, which aiming at fuzzy obtainable parameter, premature convergence and local optimization. Defining non-membership function of multi-objection programming, adjusting to get more programs, operating simulate anneal Lamarckian learning to search the best individual and enhance the capacity of local search. Through simulation, this algorithm avoided premature convergence and local optimization.

intuitionistic fuzzy; multi-objection programming; improved genetic algorithm; Lamarckian learning

2017-03-21

國(guó)家自然科學(xué)基金項(xiàng)目資助(61402517)；中國(guó)博士后基金項(xiàng)目資助(2013M542331)；陜西自然科學(xué)基金項(xiàng)目資助(2013JQ8035)

楊進(jìn)帥(1993—)，男，陜西旬陽人，碩士研究生，研究方向：智能信息處理與智能決策。E-mail：youngjinshuai@163.com。

TP18

A

1008-1194(2017)05-0096-06