求解直覺模糊多目標規劃的改進遺傳算法

楊進帥，王 毅，李 進，文 童，劉占強

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

求解直覺模糊多目標規劃的改進遺傳算法

楊進帥1，王 毅2，李 進1，文 童1，劉占強1

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

針對多目標規劃獲取的參數模糊，求解算法容易早熟收斂和陷入局部最優的問題，提出了求解直覺模糊多目標規劃的改進遺傳算法。該算法通過定義多目標規劃的非隸屬度，調節λ參數控制方案選擇，執行模擬退火拉馬克學習，增強局部搜索能力，指導個體尋找最優值。仿真分析表明，該算法可以靈活地產生多種方案，有效克服早熟收斂和陷入局部最優的問題。

直覺模糊；多目標規劃；改進遺傳算法；拉馬克學習

0 引言

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

傳統算法將多目標轉為單目標進行求解，難以得到最優解。目前，國內外學者普遍采用遺傳算法、粒子群算法、模擬退火算法等智能算法。遺傳算法由于其全局搜索性能突出、隨機性和簡單易實現等優點，被國內外學者廣泛應用于輸電網絡[3]、交通網絡[4]和軍事裝備[5]等鄰域的多目標規劃，先后提出了并列選擇法，非劣分層遺傳算法，基于目標加權法的遺傳算法，微遺傳算法[6]等改進算法。但是，遺傳算法不善于對局部區域精細調整，容易早熟收斂，陷入局部最優，不能有效解決約束優化問題。針對上述問題，本文提出了求解直覺模糊多目標規劃的改進遺傳算法。

1 直覺模糊多目標規劃模型

多目標優化的一般形式為：

(1)

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

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

(2)

(3)

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

(4)

(5)

(6)

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

(7)

(8)

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

(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)。

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

(11)

因此，構建直覺模糊多目標規劃模型的一般形式：

(12)

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

2 改進遺傳算法

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

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

2.1 拉馬克學習

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

學習與遺傳進化是生物體適應環境變化的兩種不同形式，作用于不同的時間和空間。個體進行學習的過程，即是個體局部搜索的過程。遺傳算法是一個全局搜索過程，感知環境緩慢的、整體的變化過程，而學習是全局搜索過程中的某一局部搜索，感知快速的、微小的變化過程。通過學習指導進化方向[14]，跳出局部極值點，引導個體朝向全局極值點進化。如圖2所示。

研究表明，模擬退火算法具有通用性和漸進收斂性，能避免陷入局部最優值[15]。本文利用模擬退火算法設計拉馬克學習策略，對種群中的個體進行局部搜索。

步驟1:采用n種不同的鄰域結構，對種群中個體x在初始溫度下進行n(n-1)步執行基于模擬退火的拉馬克學習；

步驟2:按下式計算每個鄰域的獎勵值：

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

式中，fb為進行局部學習前x的適應度值，fli為使用第i(i=1,2,…,n)種鄰域結構進行局部搜索后所獲得的最佳目標函數值；

步驟3:根據ηi，計算鄰域的選擇概率：

步驟4:采用輪盤賭選擇策略確定一個鄰域結構，然后對種群的最佳個體在當前溫度tk下再進行局部搜索，得到個體x′；

步驟5:基于模擬退火的選擇準則，計算學習得到的個體被保留的概率qtk：

步驟6:更新獎勵值ηi，若Step4中選擇第i個鄰域結構，則更新獎勵值ηi=ηi+Δηi進行更新，Δηi計算公式如上。

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

2.2 改進遺傳算法

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

遺傳算法作為全局搜索算法，產生更適應學習的基因，為學習提供更好的初始條件，減小學習的復雜程度。而學習結果能夠指導進化的方向，學習到的形狀被寫入基因。兩者的關系見圖3所示。

在遺傳算法的計算流程基礎上，將基于模擬退火的拉馬克學習作為一個附加模塊，從而改進遺傳算法，具體流程如圖4。

2.3 求解直覺模糊多目標規劃

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

非均勻變異增強算法的局部搜索能力，對原基因作隨機擾動，產生兩中基因：

具體求解算法步驟如下：

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

步驟2：產生初始種群，計算適應度值；

步驟3：對個體進行算術交叉、非均勻變異操作得到種群p1(k)；

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

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

停止條件為是否進化到最大迭代次數或者收斂到全局最優值。在求解過程中，隸屬度函數和非隸屬度函數可以通過設置不同的λ參數值進行優化，調節目標函數的適應度值，逐漸逼近到全局最優解。采用比例溫度下降法降低模擬退火溫度，可以平衡全局和局部搜索速度。

3 仿真及分析

為驗證本文算法的有效性，選擇在處理器為Intel(R)Core(TM)i7-4790，Windows7旗艦版系統的計算機上，運用Matlab語言編程實現典型的帶約束非線性多目標規劃，進行仿真比較。

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

實驗一：取λ分別為1，0.8，0.6，0.4，0.2，0.1和0，生成不同的約束函數的非隸屬度，采用改進遺傳算法進行5次重復運算，記錄目標函數的最優值，得到表1。相同設置下，求解模糊多目標規劃并進行比較，得到表2。

表1 改進遺傳算法求解直覺模糊多目標規劃

表2 改進遺傳算法求解模糊多目標規劃

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

實驗二：驗證算法的收斂性能，并與PSO算法、標準遺傳算法進行比較，得到圖5。

本文算法執行基于模擬退火的拉馬克學習，學習到的結果指導了遺傳的進化方向，使其朝著最優值方向迭代，在第35代收斂到最優值，其值大于標準遺傳算法，而粒子群算法沒有收斂到最優解。

實驗三：分析改進遺傳算法的種群多樣性。使用3倍于每代適應度的均值表征種群的多樣性，得到圖6。

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

4 結論

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

[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]張寧.配電網多目標經濟性優化模型和算法[J].電力自動化設備,2016,32(8):48-53.

[4]孫楊,孫小年,李葆青等.接運公交網絡設計的多目標優化模型及遺傳變鄰域搜索求解算法[J].北京工業大學學報,2014,40(4):535-541.

[5]葛優,劉景萍,趙惠昌,等.基于正交相位編碼信號的MIMO雷達測速測距算法[J].探測與控制學報,2016,38(6):80-83.

[6]馬小姝,李宇龍,嚴浪.傳統多目標優化方法和多目標遺傳算法的比較綜述[J].電氣傳動自動化,2010,32(3):48-50.

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

[8]徐小來,雷英杰,戴文義.基于改進PSO的加權直覺模糊多目標規劃[J].系統仿真學報,2009,21(11):3280-3282.

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

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

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

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

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

[14]張家奇,陳啟軍.學習對進化的影響研究及仿真實驗[J].系統仿真學報,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].自動化學報,2005,31(6):873-880.

[17]靳飛,單銳.基于局部搜索技術的混合遺傳算法[J].遼寧工程技術大學學報(自然科學版),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

國家自然科學基金項目資助(61402517)；中國博士后基金項目資助(2013M542331)；陜西自然科學基金項目資助(2013JQ8035)

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

TP18

A

1008-1194(2017)05-0096-06