肖 寧

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

1 引言

模 糊 相 關(guān) 機 會 規(guī) 劃［1］FDCP（Fyzzy Depen?dent-chance Programing），類似于隨機相關(guān)機會規(guī)劃，是決策者于模糊環(huán)境下以極大化模糊事件成立機會為基礎(chǔ)把最優(yōu)決策給出。FDCP問題的求解是工程應(yīng)用領(lǐng)域中的研究熱點。

在模糊環(huán)境下，F(xiàn)DCP模型可表示為

其中：ξ表示模糊向量，x表示決策變量，hk(x，ξ)≤0， k=1，2，…，q 表示模糊事件。不確定環(huán)境為 gj(x，ξ)≤0， j=1，2，…，p 。模糊事件的機會在模糊環(huán)境中和該事件相容的必要性（可能性或可信性）相等，即為不確定原理，其是求解模糊相關(guān)機會規(guī)劃的理論基礎(chǔ)。

部分管理目標與優(yōu)先結(jié)構(gòu)被決策者給定之后，目標函數(shù)此時能夠?qū)儆跇O小化偏差。根據(jù)決策者給定的優(yōu)先結(jié)構(gòu)和目標水平，建立FDCP目標規(guī)劃，其模型表示如下：

其中，系統(tǒng)約束個數(shù)為p；目標約束個數(shù)為m；目標i的目標值為bi；優(yōu)先級個數(shù)為1；不確定環(huán)境中實值函數(shù)為gj；pj表示優(yōu)先因子，表示了各個目標的相對重要性，且對于所有的j，有 pj?pj+1；目標i與目標值偏離的負偏差為；目標i與目標值偏離的正偏差為，hik是目標約束中的實值函數(shù)；第i個目標正、負偏差（和優(yōu)先級j對應(yīng)）權(quán)重因子分別是 uij、vij。

FDCP問題在工程應(yīng)用方面比較容易提取，但卻并不容易求解，所以，很有必要研究FDCP這種高效的求解算法。目前，智能計算技術(shù)依托計算機技術(shù)的高速發(fā)展能夠解決大量的復(fù)雜優(yōu)化問題。處理FDCP的主要方式是利用模擬退火算法（Simu?lated Annealing Algorithm）、遺傳算法（Genetic Algo?rithm，GA）、進化策略（evolution strategies）小生境技術(shù)搜索算法（Niche Technology Search Algorithms）等智能技術(shù)與模糊模擬相結(jié)合實現(xiàn)，而經(jīng)典的遺傳算法最為成功［2～8］，由于GA自身的缺點如遺傳操作復(fù)雜、收斂緩慢、精度低等。更有效的FDCP問題求解途徑依然是研究者們探索的重點。

受鳥群覓食過程中的群聚、遷徙行為的模擬、建模與仿真結(jié)果的研究啟迪，Kennedy、Eberhart博士提出了一種高效并行計算技術(shù)——PSO（Particle Swarm Optimization，微粒群算法），它以迭代方式獲取最優(yōu)解。作為進化算法，它兼有進化計算與群智能的特點。它采用并行全局搜索策略，依據(jù)微粒間的協(xié)作通過對微粒適應(yīng)值的評價，實現(xiàn)復(fù)雜空間的全局尋優(yōu)，這是它不同于GA的最顯著之處，該算法搜索速度快范圍大、易于編程實現(xiàn)，對目標函數(shù)無連續(xù)、可微等苛刻條件。它已在眾多的科學(xué)工程領(lǐng)域、學(xué)術(shù)研究方面尤其是在最優(yōu)化問題的求解時展現(xiàn)了它的優(yōu)勢［10～15］。為此，將PSO算法應(yīng)用于FD?CP問題是很有意義的研究方向，考慮到基本PSO有過早收斂的可能，為了對FDCP問題進行更精確地求解，通過SPSO（一種保證全局收斂的隨機微粒群算法［9］）代替以往的GA再結(jié)合模糊模擬技術(shù)，把一種FDCP模型求解的混合智能算法形成。算法實效性經(jīng)由仿真實驗得以證實。

2 基本微粒群算法

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

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

3 SPSO算法

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

這樣，式（4）在加強局部搜索能力的同時，弱化了全局搜索能力。如果Xj(t)=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在進化的某些代會把Xj(t)=Pk=Pg滿足，也就是說，搜索空間最少需重新隨機形成1個微粒，全局搜索能力會因此提高。

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

該類問題求解過程中所采用的SPSO算法，其核心主要在于機會函數(shù)（也就是模糊事件可信性）計算，其能通過模糊模擬來完成，在尋優(yōu)過程中，它主要體現(xiàn)在計算目標函數(shù)的適應(yīng)值上。模糊模擬可信性估計算法過程現(xiàn)闡述如下：

如果實值函數(shù)為 f:Rn→R，n維模糊向量［可能性空間 (θ，P(θ)，Pos)上］為 ξ，那么，能通過獲得可信性Cr{fL(ξ)≤0}。采用模糊模擬計算模糊事件的可信性：L=Cr{f(ξ)≤0}。

該估計算法的基本程序如下：

第1步：將θk于非空集合θ內(nèi)均勻形成，且讓它將 Pos(θk)≥ε(k=1，2，…，N)滿足，其中ε是個充分小的數(shù)。

第2步：使得 vk=Pos(θk)，k=1，2，…，N。

第4步：返回L。

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

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

第2步：所有微粒適應(yīng)值的計算均采用估計算法（模糊模擬可信性）展開。

第3步：若xi(t)=pj=pg，則在搜索空間中隨機機產(chǎn)生粒子j的位置，并計算其適應(yīng)值（模糊模擬的可信性估計算法）及個體最優(yōu)值，其它粒子按式（4）進化，并計算它們的適應(yīng)值模糊模擬的可信性估計算法）及個體最優(yōu)值。

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

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

第6步：檢驗更新后粒子的可行性：若可行，則接受并計算它們的適應(yīng)值（模糊模擬的可信性估計算法）及它們的個體最優(yōu)值，如果不可行，原位置保持原狀。

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

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

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

5 實例仿真

本文所論述方法采用文獻［4］內(nèi)的實例進行驗證。

例1 考慮如下的單目標FDCP模型：

例2 考慮如下的FDCP目標規(guī)劃：

其中：μaˉ(ξ)=1/[1+(ξ-2)2]為模糊變量的隸屬函數(shù)；aˉ為三角模糊變量（3，4，5），為三角模糊變量（2，3，4），為三角模糊變量（1，2，3）。

很顯然可用模糊模擬來計算。

在代碼中選擇和文獻［4］一樣的運行次數(shù)1；種群規(guī)模30；迭代次數(shù)400；模擬次數(shù)5000。

在實例2中，

第一優(yōu)先級中，只有一個事件x1+=3，記做ε1其支撐為：=｛x1，x3｝，相關(guān)支撐=｛x1，x2，x3，x4｝。由不確定原理，事件 ε1的機會函數(shù)f1(x)為：

第二優(yōu)先級中，也只有一個事件x2+=2，記做 ε2其支撐為：=｛x2，x5｝，相關(guān)支撐=｛x1，x2，x5｝。由不確定原理，事件ε2的機會函數(shù) f2(x)為

第三優(yōu)先級中，有一個事件x4+=1，記做ε3其支撐為：=｛x4，x6｝，相關(guān)支撐=｛x3，x4，x6｝。由不確定原理，事件ε3的機會函數(shù) f3(x)為

很顯然各個機會函數(shù)可用模糊模擬來計算。

在代碼中選擇和文獻［4］一樣的運行次數(shù)1；種群規(guī)模30；迭代次數(shù)400；模擬次數(shù)5000。

在PC機的CPU的主頻：2.5GHz，內(nèi)存：2GB，操作系統(tǒng)：winXP，VC++6.0環(huán)境下編寫代碼、運行程序。

在例1中：運行一次的結(jié)果如表1所示，對比文獻［4］中的數(shù)據(jù)，文獻［4］明顯不如它的結(jié)果。如圖一所示，基于迭代過程體現(xiàn)得更直觀，把它的迭代過程進行四十次抽樣。這種算法不但有極高的精度，同樣有極快的收斂速度，文獻［4］必需400代迭代才能獲得的最優(yōu)值，在這種算法中只要到第10代時便可實現(xiàn)?；诮Y(jié)果偶然因素（1次運行時）的規(guī)避，把程序進行10次運行，表2所示即為運行結(jié)果。很明顯，文獻［4］平均最優(yōu)值明顯不如采用此法所獲得的結(jié)果，無論哪次均如此［4］。

在例2中：運行一次見表3，對比文獻［4］中的數(shù)據(jù)，顯然優(yōu)于文獻［4］；從程序多次運行的結(jié)果看，所有結(jié)果都優(yōu)于文獻［4］三個目標都滿足。

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

表2 實例1運行十次結(jié)果統(tǒng)計

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

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

6 結(jié)語

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

［1］Liu B.Dependent-chance programming in fuzzy environ?ments［J］.Fuzzy Sets and System，2000，109（1）：97-106.

［2］Baoding Liu.Theory and practice of uncertain program?ming.the third edition，http：//orsc.edu.cn/liu，2009.

［3］胡永強，劉晨亮，趙書強，等.基于模糊相關(guān)機會規(guī)劃的儲能優(yōu)化控制［J］.電力系統(tǒng)自動化。2014，38（6）：20-25.HU Yongqiang，LIU Chenliang，ZHAO Shuqiang，et al.Op?timalControlofEnergy Based On Fuzzy Correlat?ed-chance Programming［J］.Automation of Electic Power System，2014，38（6）：20-25.

［4］劉寶碇，趙瑞清，王綱.不確定規(guī)劃及應(yīng)用［M］.北京：清華大學(xué)出版社，2003.LIU Baoding，ZHAO Ruiqing，WANG Gang.Uncertain Programming and Application［M］.Beijing：Tsing Hua University Press，2003.

［5］龔樹鳳，龍偉軍，潘明海，等.基于模糊相關(guān)機會規(guī)劃的機會陣雷達方向圖綜合［J］.電波科學(xué)學(xué)報，2015，30（2）：201-207.GONG Shufeng，LONG Weijun，PAN Minghai，et al.Pat?tern Synthesis for Opportunistic Array Radar Based on Fuzzy Dependent-ohance Programming［J］.Chinese Jour?nal of Radio Science.2015，30（2）：201-207.

［6］裴振奎，陳繼東，趙艷麗，等.混合智能算法在模糊規(guī)劃中的應(yīng)用［J］.鄭州大學(xué)學(xué)報，2010，42（3）：71-74.PEI Zhenkui，CHEN Jidong，ZHAO Yanli，et al.Fuzzy Pro?gramming with a Hybrid Intelligent Algorithm［J］.Journal of Zhengzhou University.2010，42（3）：71-74.

［7］ Guangdong TIAN，Hua KE，Xiaowei CHEN.Fuzzy cost-profit tradeoff model for locating a vehicle inspection station considering regional constraints［J］.Journal of Zhe?jiang University-Science C（Computers&Electronics）2014，15（12）：1138-1146.

［8］陸悠悠.山東省能源經(jīng)濟環(huán)境系統(tǒng)模糊規(guī)劃研究［D］.青島：中國石油大學(xué)，2014.LU Youyou.Research on Fuzzy Programming of Ener?gey-economy-environment System of Shandong Province［D］.Qingdao：China University of Potroloum Master De?gee Thesis，2014.

［9］曾建潮，崔志華.一種保證全局收斂的PSO算法［J］.計算機研究與發(fā)展，2004，41（8）：1333-1338.ZENG Jianchao，CUI Zhihua.A Guaranteed Global Con?vergence Particle Swarm optimizer［J］.Journal of Comput?er Research and Development，2004，41（8）：1333-1338.

［10］崔志華，曾建潮.微粒群優(yōu)化算法［M］.北京：科學(xué)出版社，2011.CUI Zhihua，ZENG Jianchao.Particle swarm optimization［M］.BEIJing：Science Press，2011.

［11］Zhang Liyong，Xu Jian，Zheng Yidong，Huang Zhinan，Yu Jianglong.Study on Particle Swarm Optimization（PSO）for Aircraft Parameter Identification Based on BeiDou Satellite System and Strapdown AHRS Integrated Navigation［C］//Proceedings of 2014 IEEE Chinese Guid?ance，Navigation and Control Conference：2269-2274.

［12］Priya C，Lakshmi P.Particle swarm optimisation applied to real time control of spherical tank system.International Journal of Bio-inspired Computation，2012，4（4）：206-216.

［13］肖寧.求解隨機機會約束規(guī)劃的混合智能算法［J］.計算機工程與應(yīng)用，2010，46（22）：43-46.XIAO Ning.Solving Stochastic Chance-constrained Pro?gramming Problems with Hybrid Intelligent Algorithm［J］.Computer Engineering and Application，2010，46（22）：43-46.