混合智能算法在模糊規(guī)劃中的應用

裴振奎, 陳繼東, 趙艷麗, 劉 真

(中國石油大學(華東)計算機科學系 山東東營257061)

混合智能算法在模糊規(guī)劃中的應用

裴振奎, 陳繼東, 趙艷麗, 劉 真

(中國石油大學(華東)計算機科學系 山東東營257061)

簡要介紹了模糊規(guī)劃并綜述了模糊規(guī)劃的建模理論,提出在原有混合智能算法研究的基礎上將進化策略融合進混合智能算法中來解決原有算法易陷入局部最優(yōu)解的問題,提高了求解精度及收斂速度.

進化策略;模糊規(guī)劃;混合智能算法

0 引言

當今時代,信息作為人類交流的載體,越來越受到人們的關注,在人類發(fā)展和科技進步的進程中,信息更是為我們提供了知識的源泉.可以說,信息在當今社會中起到了至關重要的作用.然而人們接觸到的信息大多是不確定的,表現(xiàn)為隨機性、模糊性、粗糙性、隨機模糊性、隨機粗糙性等多重不確定性.對于數(shù)學中含有的不確定參數(shù)的規(guī)劃,傳統(tǒng)的經典優(yōu)化理論往往無法解決,需要考慮用一些智能算法如人工神經網絡、進化算法等構造成混合智能算法并通過計算機程序來進行不確定規(guī)劃的求解,本文討論的就是一類表現(xiàn)為模糊性的不確定規(guī)劃.

1 模糊規(guī)劃模型

目前,廣泛應用的模糊規(guī)劃模型有3種.

1.1 期望值模型

優(yōu)化問題中出現(xiàn)的不確定變量相應地都有該變量的數(shù)學期望的概念.基于此,第一種建模方法是在期望值約束成立下極大化這些不確定目標函數(shù)的數(shù)學期望,亦即期望值模型[1]

其中,x為決策向量,ξ為模糊變量,f(x,ξ)表示目標函數(shù),gj(x,ξ),j=1,2,…,p表示模糊約束函數(shù),E表示期望值算子.

1.2 機會約束規(guī)劃

借用隨機機會約束規(guī)劃的思想,Liu和Iwamura給出了模糊機會約束規(guī)劃的理論框架[2-3],其允許所作決策在一定程度上不滿足約束條件,但該決策使約束條件成立的概率或可能性不小于某一置信水平.典型的機會約束規(guī)劃可以表示成

其中,x是決策向量,ξ是模糊參數(shù),α和β分別是對約束和目標事先給定的置信水平,Cr{}表示{}中事件成立的概率或可能性.

1.3 相關機會規(guī)劃

一個復雜的決策系統(tǒng)通常要完成多項任務,稱之為事件,決策者往往希望這些事件實現(xiàn)的概率或可能性(機會函數(shù))盡可能的大.相關機會規(guī)劃是使事件的機會函數(shù)在不確定環(huán)境下達到最大的優(yōu)化理論[4].不確定環(huán)境下典型的相關機會規(guī)劃可以表示為

其中,x是一個n維決策向量,ξ是一個模糊向量,f(x)是一個事件的機會函數(shù),gj(x,ξ)≤0,j=1,2,…,p是不確定環(huán)境.

2 應用進化策略改進的混合智能算法

2.1 傳統(tǒng)的混合智能算法

對于不確定優(yōu)化,智能算法包括神經元網絡、模擬退火以及遺傳算法等,為了提高效率,可以將幾種方法有效地結合起來,從而形成混合智能算法.文[5]把神經元網絡和遺傳算法有機地結合起來,首先使用模擬產生訓練樣本,然后利用這些數(shù)據訓練神經網絡逼近不確定函數(shù),最后把神經元網絡嵌入到遺傳函數(shù),從而得到混合智能算法,其過程如下:

步驟1)用模擬產生一組數(shù)據,即訓練樣本.

步驟2)訓練神經元網絡以便逼近不確定函數(shù).

步驟3)初始產生pop_size個染色體,使用前面訓練的神經元網絡檢驗染色體的可行性.

步驟4)對染色體進行交叉操作以及變異操作,用神經元網絡檢驗后代的可行性.

步驟5)使用神經元網絡計算所有染色體的目標值.

步驟6)根據目標值計算每個染色體的適應度.

步驟7)旋轉賭輪,選擇染色體.

步驟8)重復步驟4～7,直到給定的次數(shù).

步驟9)最好的染色體作為優(yōu)化問題的最優(yōu)解.

2.2 改進的混合智能算法

其中步驟3～9是利用遺傳算法來對函數(shù)進行解優(yōu)化,本文就是針對這一過程做出改進,將進化策略、模擬退火算法和遺傳算法有效地結合起來,達到尋優(yōu)操作,既能跳出局部最優(yōu)解,又能保證收斂速度的良好效果.

單純的遺傳算法存在這些局限性[6]:它不能保證所得到的是最佳答案;標準遺傳算法并不保證全局最優(yōu)收斂,只能在一定的約束條件下實現(xiàn)全局最優(yōu).單純的進化策略存在這些局限性[6]:每一維常數(shù)的標準偏差(平均步長)使收斂最優(yōu)值的速度變慢;點對點搜索的不穩(wěn)定性可能造成停止于局部最小值.因此考慮將兩者結合,構造一種新的混合智能算法并應用在模糊規(guī)劃中.

該算法以遺傳為基礎,將進化策略作為一個獨立算子,其中引入了進化策略的(μ,λ)選擇算子,提高算法跳出局部最優(yōu)的幾率,在算子的變異過程中采用模擬退火的思想,精英保留策略的應用能夠保證算法收斂到全局最優(yōu).兩種算法相互借鑒,起到互補的作用.

2.3 改進算法的基本思想

步驟1)產生初始群體 隨機生成初始群體,并利用神經元網絡對其進行可行性的檢驗.編碼方案采用實數(shù)編碼.

步驟2)交叉 隨機選取兩個配對個體進行交叉,然后隨機生成一個0或1標志數(shù),若標志數(shù)為“1”,則對兩個個體中相應位的基因進行負交叉運算;否則對兩個個體中相應位的基因進行正交叉運算.

步驟3)變異 對個體中的每個基因都隨機生成一個P,P屬于[0,1],若滿足P>Pm(Pm為變異概率),則對該位的基因進行變異操作;否則保持不變.下面應用模擬退火思想,對變異結果,按照Metropolis接受準則判斷接受與否,即:發(fā)生變異的個體與其變異后的個體適應度值進行比較,若變異后個體較優(yōu)則接受其作為新個體,并替代變異前個體;否則隨機產生一個隨機數(shù)r,若滿足exp(f1-f2/T)>r,則接受變異后個體作為新個體,其中f1為變異前個體的適應值;f2為變異后個體的適應值;T為退火溫度,退火函數(shù)為T=T0＊Sgen,T0為初始溫度,S為退火系數(shù),gen為進化代數(shù).若上面兩個條件都不滿足則不接受新個體.

步驟4)進化 在舊個體基礎上增加一個隨機量,從而形成新個體,這個隨機量由步長σ∈Rn(正態(tài)分布的標準差)構成,可以用來調整對個體進行變異操作時變異量的大小.根據進化策略的思想[7],假設群體的個體X={x,s}經過變異運算后得到一個新的個體X′={x′,s′},則新個體的組成元素是

其中,i=1,2,…,n,N(0,1)和Ni(0,1)是均值為0、方差為1的正態(tài)隨機變量,t和t′是算子集參數(shù),τ=和τ′=,τ＊N(0,1)和τi＊Ni(0,1)分別表示變異時的整體步長和個體步長.

步驟5)選擇 選擇不采用輪盤法那種隨機方式,而是采用進化策略中以確定方式進行的選擇算子(μ, λ)選擇,是優(yōu)良個體100%被保留,劣質個體100%被淘汰.在新產生的λ個個體中選取μ個最優(yōu)者,將它們保留到子代群體中,該選擇方式易于跳出局部最優(yōu)解,而且能夠擴大群體多樣性,從而有效避免未成熟收斂.

保留迄今為止存在的最優(yōu)個體,保證其不被交叉和變異等遺傳算子破壞.具體操作為:計算新群體的適應值,若新群體中的最優(yōu)個體優(yōu)于上代保存的最優(yōu)個體,則用該個體替換上代保留的最優(yōu)個體;否則用上代的最優(yōu)個體替換新群體中最差的個體.

3 數(shù)值試驗

分別對3種模型進行試驗:

①首先考慮模糊期望值模型

其中,ξ1,ξ2和ξ3分別是三角模糊變量(-4,-2,0),(-2,0,2)和(0,2,4).通過運行該算法1 000代,找到了最優(yōu)解:x＊1=-1.778 4,x＊2=-1.881 3,x＊3=-1.824 3,其目標值為3.81.只用遺傳算法進行解優(yōu)化所取得的最優(yōu)目標值是3.77.

②考慮帶有模糊系數(shù)的單目標機會約束規(guī)劃

③考慮模糊相關規(guī)劃模型

用染色體V=(v1,v2)表示模型的一個解,它可按x1=v1,x2=v2,x3=方式進行解碼.

4 結論

采用混合智能算法來解決模糊規(guī)劃問題是目前廣泛使用且有效的計算方法,基于此,本文提出了將進化策略混合進遺傳算法中來構造混合智能算法并應用到模糊規(guī)劃中去.從數(shù)值試驗的結果可以看出,新算法改良了以往遺傳算法中易陷入局部最優(yōu)解問題.隨著技術的不斷發(fā)展,遺傳算法與進化策略兩種算法交叉滲透,差異也在不斷縮小,通過兩者的相互借鑒,必定會產生更多穩(wěn)定、高效的新算法.

[1] Liu B,Liu Y K.Expected value of fuzzy variable and fuzzy expected valuemodels[J].IEEE Transactionson Fuzzy System s,2002,10(4):445-450.

[2] Liu B,Iwamura K.Chance constrained p rogramming w ith fuzzy parameters[J].Fuzzy Sets and Systems,1998,94(2): 227-237.

[3] Liu B,Iwamura K.A note on chance constrained p rogramming w ith fuzzy coefficients[J].Fuzzy Sets and System s, 1998,100(1/2/3):229-233.

[4] Liu B.Dependent-chance p rogramming in fuzzy environments[J].Fuzzy Sets and System s,2002,109(1):97-106.

[5] Li X,Liu B.Foundation of credibilistic logic[J].Fuzzy Op timization and Decision Making,2009,8(1):91-102.

[6] Li P,Liu B.Entropy of credibility distributions for fuzzy variables[J].IEEE Transactions on Fuzzy Systems,2008,16 (1):123-129.

[7] Gao J,Liu B.Fuzzy multilevel p rogramming w ith a hybrid intelligent algo rithm[J].Computers and Mathematics w ith App lications,2005,49:1539-1548.

[8] Ke H,Liu B.Fuzzy p roject scheduling p roblem and its hybrid intelligent algorithm[J].Applied Mathematical Modelling,2010,34(2):301-308.

[9] 劉寶碇,趙瑞清,王綱.不確定規(guī)劃及應用[M].北京:清華大學出版社,2003.

[10] 黃華娟,周永權.改進型人工魚群算法及復雜函數(shù)全局優(yōu)化方法[J].廣西師范大學學報:自然科學版,2008,26(1): 194-197.

[11] 張美玉,黃翰,楊曉偉,等.求解線性運輸問題的新型進化算法[J].廣西師范大學學報:自然科學版,2006,24(4):74-78.

[12] 武志峰,楊蓓.一種改進的粒子群優(yōu)化算法[J].鄭州大學學報:理學版,2007,39(3):109-112.

[13] 李喜艷,張文寧,周清雷.混合編碼遺傳算法在測試數(shù)據生成中的應用[J].鄭州大學學報:理學版,2009,41(3):22-25.

Fuzzy Programm ing with a Hybrid Intelligent Algorithm

PEIZhen-kui, CHEN Ji-dong, ZHAO Yan-li, L IU Zhen
(Department of Com puter Science,China University of Petroleum,Dongying 257061,China)

Fuzzy p rogramm ing offers a powerful means of handling op tim ization p roblem s w ith fuzzy parameters.Fuzzy p rogramm ing has been used in different w ays in the past.Fuzzy p rogramming is p resented briefly,and the modeling p rincip le of fuzzy p rogramming is summarized. In o rder to increase the p robability of escaping from the local op tima,a new hybrid intelligent algorithm fused evolution strategies is given,w hich imp roves the p recision and convergence speed. Then the algorithm steps are introduced.Finally,the p rospects and directions for the development of hybrid intelligent algorithm are p roposed.Numerical results show that,the new hybrid intelligent algorithm is superior to the traditional algorithm on accuracy.

evolution strategies;fuzzy p rogramming;hybrid intelligent algorithm

TP 391

A

1671-6841(2010)03-0071-04

2010-01-26

國家自然科學基金資助項目,編號60673089.

裴振奎(1962-),男,副教授,主要從事計算智能、圖像處理和機器學習研究,E-mail:peizhk@upc.edu.cn.