肖 寧

（陜西職業(yè)技術(shù)學(xué)院計算機科學(xué)系 西安 710100）

1 引言

為適應(yīng)不確定規(guī)劃尤其是模糊規(guī)劃理論研究和應(yīng)用的發(fā)展，LIU 提出了模糊規(guī)劃理論并建立了相應(yīng)的模型及基于經(jīng)典GA 的求解算法［1～3］，許多模糊規(guī)劃問題因而也得到了有效求解［4～8］，鑒于PSO算法的求解優(yōu)勢［9～12］，本文作者在不確定規(guī)劃的求解算法方面也做了一些研究工作［14～16］，為了探究更優(yōu)的求解算法，本文采用隨機PSO（一種保證全局收斂的隨機微粒群算法［16］）并結(jié)合模糊模擬技術(shù)對模糊規(guī)劃中的期望值模型問題進行了研究，通過對典型算例的仿真實驗，從而為該類問題的有效求解提供了思路，也為另外兩類模糊規(guī)劃和其他不確定規(guī)劃問題的求解提供了思路。

2 模糊期望值模型

模糊期望值模型（Fuzzy Expected Value Model，F(xiàn)EVM）是Liu［1］所提出來的一類模糊規(guī)劃，它是使模糊目標(biāo)函數(shù)的期望值在模糊期望值的約束下達到最優(yōu)的一類規(guī)劃模型。一直以來對其進行高效求解是工程應(yīng)用領(lǐng)域中的熱點研究問題。

FEVM通常表示如下：

在以上模型中，X表示決策向量，ξ表示模糊向量，表示目標(biāo)函數(shù)表示約束函數(shù)。

為達到多個目標(biāo)的平衡，構(gòu)造出相應(yīng)的FEVM目標(biāo)規(guī)劃模型表示為

在此，bi是目標(biāo)i 的目標(biāo)值，m 代表目標(biāo)約束個數(shù)，p 代表系統(tǒng)約束，是優(yōu)先因子，它代表了各目標(biāo)的相對重要性，uij是對應(yīng)優(yōu)先級j的第i個目標(biāo)的正偏差的權(quán)重因子，vij是對應(yīng)優(yōu)先級j 的第i 個目標(biāo)的負偏差的權(quán)重因子，是目標(biāo)i 偏離目標(biāo)值的正偏差，是目標(biāo)i 偏離目標(biāo)值的負偏差，l 代表了優(yōu)先級個數(shù)，gj是系統(tǒng)約束中的函數(shù)，fi是目標(biāo)約束中的函數(shù)。

3 基本微粒群算法

在PSO 中，微粒群即是D 維空間中問題的潛在解的集合，微粒們依據(jù)本身及同伴的飛行經(jīng)驗不斷調(diào)整自己的位置、速度，用適應(yīng)值評價解的優(yōu)劣，不斷追隨當(dāng)前、歷史最優(yōu)微粒進行更新，通過不斷迭代朝著最好解飛行。微粒i 的第d 維的速度、位置通過下式更新：

在以上公式中：c1、c2表示飛行的加速常量；均勻分布于［0，1］上的隨機數(shù)為rand（）；個體第d 維分量（歷史最優(yōu)位置）為Pid；ω為慣性權(quán)重；全局第d維分量（歷史最優(yōu)位置）為Pgd。

4 SPSO算法

在以上的基本PSO 算法中，若ω=0，微粒的飛行速度取決于xi（dt）、pid、pgd，除全局最優(yōu)位置微粒此時會處于靜止?fàn)顟B(tài)之外，其余微粒均趨向自身及全局最優(yōu)位置的加權(quán)中心。即微粒群將收縮至當(dāng)前的全局最優(yōu)處，類似于一個局部算法；若ω≠0，讓微粒形成搜索范圍擴展的可能，也就是具備相應(yīng)的全局搜索能力。全局搜索能力與慣性權(quán)重成正比。這表明，慣性權(quán)重若是零，式（3）所描述的公式為

這樣，式（4）在加強局部搜索能力的同時，弱化了全局搜索能力。如果X（jt）=Pj=Pg，因為處于歷史最好位置的微粒j不可以依據(jù)式（4）進化，所以經(jīng)由隨機產(chǎn)生于搜索空間內(nèi)的微粒把j 微粒替代，和經(jīng)過Pi、Pg更新之后的其余微粒一同依據(jù)式（4）進化；如果Pg與Pj不相等，同時也沒有更新Pg，那么依據(jù)式（4）進化全部微粒；如果Pg與Pj不相等，但已更新Pg，也就是在f≠j 時，Xf（t+1）=Pf=Pg，那么微粒f 進化終止，于搜索空間內(nèi)再次隨機形成，Pi、Pg更新之后，其它微粒依據(jù)式（4）進化。此時，最少存在1 個微粒j 在進化的某些代會把X（jt）=Pk=Pg滿足，也就是說，搜索空間最少需重新隨機形成1 個微粒，全局搜索能力會因此提高。

5 模糊模擬與SPSO 算法相結(jié)合的FEVM模型算法

該類問題求解過程中所采用的SPSO 算法，其核心主要在于模糊期望值函數(shù)如何計算，這可以通過模糊模擬來完成，在整個尋優(yōu)期間，它主要體現(xiàn)在：初始化時期要用到模糊模擬來實現(xiàn)所有微粒適應(yīng)值的計算；在每迭代中也要利用它計算個體的適應(yīng)值等。模糊模擬期望值估計算法過程如下：

如果實值函數(shù)，表示為f：Rn→ R，ξ=(ξ1，ξ2，…，ξn)是可能性空間(θ，P(θ)，Pos)中的n維模糊向量，則（fξ）也是一個模糊變量，其期望值定義為

以下的模糊模擬過程用來計算E[f(ξ)]。分別從θ中均勻產(chǎn)生θk，使Pos{θk}≥ε（ε代表了一個充分小的數(shù)）,并定義vk=Pos{θk}，k=1，2，…，N。對任意的r≥0 ，則可信性Cr{f(ξ)≥r}近似等于

對任意r＜0 ，可信性Cr{f(ξ)≥r}近似等于

模糊模擬算法的期望值估計算法：

第1步：令e=0；

第2步：分別從θ中均勻產(chǎn) 生θk，使 得Pos(θk)≥ε，令vk=Pos{θk}，k=1，2，…，N；

第3步 ：置a=f(ξ(θ1))? … ?f(ξ(θN))，b=f(ξ(θ1))? … ?f(ξ(θN))；

第4步：使得r從［a，b］中均勻產(chǎn)生；

第5步：若r≥0，令e←e+Cr{f(ξ)≥r}；

第6步：若r＜0，令e←e-Cr{f(ξ)≤r}；

第7步：重復(fù)第4至6步共N次；

第8步：E[f(ξ)]=a?0+b?0+e?(b-a)/N。

SPSO 算法與模糊模擬相結(jié)合的求解FEVM 的混合智能算法步驟：

第1步：微粒群初始化：若popsize是微粒數(shù)量，那么，把1個隨機數(shù)形成于決策向量x的可行域內(nèi)，且對它的可行性進行檢驗，把該過程進行popsize次重復(fù)之后，則獲得：xi=（xi1，xi2…xid）i=1，2…popsize 隨后再初始化群的最好位置、個體最好位置及所有微粒速度等。

第2步：所有微粒適應(yīng)值的計算，即計算目標(biāo)E［g（jx，ξ）］，均采用估計算法（模糊期望值模擬）展開。

第3步：若x（it）=pj=pg，則在搜索空間中隨機機產(chǎn)生粒子j的位置，并計算其適應(yīng)值，即計算目標(biāo)E［g（jx，ξ）］（模糊模擬的可信性估計算法）及個體最優(yōu)值，其他粒子按式（4）進化，并計算它們的適應(yīng)值，即計算目標(biāo)E［g（jx，ξ）］（模糊模擬的期望值估計算法）及個體最優(yōu)值。

第4步：pg如果不等于pj，同時沒有更新pg，則以式（4）進化所有粒子。

第5步：pg如果不等于pj，但已更新pg，也就是說f 不等于j，導(dǎo)致x（ft+1）=pf=pg，那么粒子f的進化終止，把其位置重新隨機形成于搜索空間內(nèi)，并計算其適應(yīng)值，即計算目標(biāo)E［g（jx，ξ）］（模糊模擬的期望值估計算法）及個體最優(yōu)值，其余粒子按式（4）進化。

第6 步：檢驗更新后粒子的可行性：若可行，則接受并計算它們的適應(yīng)值，即計算目標(biāo)E［g（jx，ξ）］（模糊模擬的期望值估計算法）及它們的個體最優(yōu)值，否則則原位置保持原狀。

第7步：把全局最優(yōu)微粒pg找出。

第8步：第3步至第7步重復(fù)執(zhí)行，直到有1 個預(yù)設(shè)最大迭代次數(shù)或足夠好的適應(yīng)值。

第9步：結(jié)束迭代，把最優(yōu)解、對應(yīng)于最優(yōu)解的最優(yōu)值給出。

6 實例仿真

本文所論述方法采用以下典型實例進行驗證，運行環(huán)境：在PC 機的CPU 的主頻：2.5GHz，內(nèi)存：2GB，操作系統(tǒng)：WinXP，VC++6.0環(huán)境下編寫、運行代碼。

例1考慮如下的單目標(biāo)FEVM模型［2］：

其中ξ1為三角模糊變量（1，2，3），ξ2為三角模糊變量（2，3，4），ξ3為三角模糊變量（3，4，5）。

在本代碼中選擇和文獻［2］相同的參數(shù)值：種群規(guī)模：30，模擬次數(shù)：6000，迭代數(shù)目：1000，運行次數(shù)：1。

例2考慮如下的FEVM目標(biāo)規(guī)劃模型［3］：

其中模糊變量ξ1為三角模糊變量（0，1，2），ξ2為三角模糊變量（1，2，3），ξ3為三角模糊變量（2，3，4）。

在本代碼中選擇和文獻［3］相同的參數(shù)值：種群規(guī)模：30，模擬次數(shù)：5000，迭代次數(shù)：1000，運行次數(shù)：1。

在例1中：運行一次的結(jié)果如表1所示，對比文獻［2］中的數(shù)據(jù)，文獻［2］顯然不如本文算法的效果。如圖1 所示，為使得迭代過程體現(xiàn)得更直觀，把代碼運行1 次的整個1000 次的迭代過程每隔20代進行抽樣，文獻［2］必需1000 代迭代才能獲得的最優(yōu)值，在這種算法中只要到第20 代時便可實現(xiàn)。為規(guī)避一次運行所得到的結(jié)果的偶然性，把代碼進行了10 次運行，每次都是在20 代時就達到與文獻［2］相同的優(yōu)化效果，從60 代開始最優(yōu)值就開始穩(wěn)定，其平均值見表1 最后一行。顯然，文獻［2］最優(yōu)值不如采用此法所獲得的結(jié)果。

表1 實例1數(shù)據(jù)比較

在例2 中：運行結(jié)果如表2 所示，對比文獻［3］中的數(shù)據(jù)，顯然優(yōu)于文獻［3］；正如表3 所示，程序10次運行的每一次的結(jié)果均優(yōu)于文獻［3］。

表2 實例2結(jié)果比較

表3 結(jié)果統(tǒng)計

圖1 實例1迭代過程抽樣圖

7 結(jié)語

FEVM 模型問題是在實際工程應(yīng)用及科學(xué)研究中都有重要意義的不確定規(guī)劃問題，目前應(yīng)用普遍的方法是嘗試將智能算法用于該類問題的求解，混合智能算法：模糊模擬與SPSO 算法求解FEVM問題是本文描述的主要內(nèi)容，對比經(jīng)典的混合智能算法（基于GA 算法）與實例仿真的結(jié)果表明，它存在著很好的優(yōu)化性能；顯示了該算法在FEVM 問題中的優(yōu)勢，該算法不僅對連續(xù)空間的FEVM 問題求解提供了新的方法，對其他不確定規(guī)劃問題的求解也有重要的指導(dǎo)意義，同時也拓展了PSO算法研究的應(yīng)用領(lǐng)域。