肖 寧

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

1 引言

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

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

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

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

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

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

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

2 基本微粒群算法

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

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

3 SPSO算法

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

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

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

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

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

該估計(jì)算法的基本程序如下：

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

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

第4步：返回L。

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

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

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

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

第4步：pg如果不等于 pj，同時(shí)沒(méi)有更新 pg，則以式（4）進(jìn)化所有粒子。

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

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

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

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

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

5 實(shí)例仿真

本文所論述方法采用文獻(xiàn)［4］內(nèi)的實(shí)例進(jìn)行驗(yàn)證。

例1 考慮如下的單目標(biāo)FDCP模型：

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

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

很顯然可用模糊模擬來(lái)計(jì)算。

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

在實(shí)例2中，

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

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

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

很顯然各個(gè)機(jī)會(huì)函數(shù)可用模糊模擬來(lái)計(jì)算。

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

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

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

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

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

表2 實(shí)例1運(yùn)行十次結(jié)果統(tǒng)計(jì)

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

圖1 實(shí)例1迭代過(guò)程抽樣圖

6 結(jié)語(yǔ)

FDCP模型問(wèn)題是在實(shí)際工程應(yīng)用和科學(xué)研究中都有重要意義的不確定規(guī)劃問(wèn)題，目前應(yīng)用普遍的方法是嘗試將智能算法用于該類問(wèn)題的求解，混合智能算法：模糊模擬與SPSO算法求解FDCP問(wèn)題是本文描述的主要內(nèi)容，對(duì)比混合智能算法（基于GA算法）與實(shí)例仿真的結(jié)果表明，它存在著極為突出的優(yōu)化性能；顯示了該算法在FDCP問(wèn)題的優(yōu)勢(shì)，該算法不僅對(duì)連續(xù)空間的FDCP問(wèn)題求解提供了新的方法，對(duì)其它不確定規(guī)劃問(wèn)題的求解也有重要的指導(dǎo)意義，同時(shí)也拓展了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］胡永強(qiáng)，劉晨亮，趙書(shū)強(qiáng)，等.基于模糊相關(guān)機(jī)會(huì)規(guī)劃的儲(chǔ)能優(yōu)化控制［J］.電力系統(tǒng)自動(dò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］龔樹(shù)鳳，龍偉軍，潘明海，等.基于模糊相關(guān)機(jī)會(huì)規(guī)劃的機(jī)會(huì)陣?yán)走_(dá)方向圖綜合［J］.電波科學(xué)學(xué)報(bào)，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é)報(bào)，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)濟(jì)環(huán)境系統(tǒng)模糊規(guī)劃研究［D］.青島：中國(guó)石油大學(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］.計(jì)算機(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］肖寧.求解隨機(jī)機(jī)會(huì)約束規(guī)劃的混合智能算法［J］.計(jì)算機(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.