牛佳惠 肖 寧 王煜東

（1.陜西職業(yè)技術(shù)學(xué)院人工智能學(xué)院 西安 710100）（2.國(guó)網(wǎng)咸陽(yáng)供電公司 咸陽(yáng) 712100）

1 引言

隨 機(jī) 相 關(guān) 機(jī) 會(huì) 規(guī) 劃［1～2］（Stochastic Dependent-Chance Programming，SDCP）是隨機(jī)規(guī)劃的一個(gè)子模型，是在隨機(jī)環(huán)境下，決策者以極大化隨機(jī)事件成立的機(jī)會(huì)（概率）為目標(biāo)而提供最佳策略的一個(gè)不確定模型。如何高效求解SDCP 模型問(wèn)題，一直是存在于經(jīng)濟(jì)、管理、最優(yōu)控制等領(lǐng)域中的熱點(diǎn)研究方向。

在實(shí)際的含有隨機(jī)不確定因素的水土資源的最優(yōu)配置、電力系統(tǒng)優(yōu)化、無(wú)線傳感網(wǎng)絡(luò)的路由選擇、作業(yè)車(chē)間調(diào)度、路徑優(yōu)化等應(yīng)用方向中，SDCP問(wèn)題不難提取，而SDCP 問(wèn)題所表現(xiàn)的隨機(jī)性及非線性導(dǎo)致了它難以求解，因而，研究者仍在繼續(xù)探究著SDCP 這類(lèi)問(wèn)題的更優(yōu)的求解途徑。現(xiàn)在，各類(lèi)智能計(jì)算技術(shù)在高速發(fā)展的算力平臺(tái)的助力下，可以計(jì)算常規(guī)的或傳統(tǒng)的方法很難實(shí)現(xiàn)的繁雜問(wèn)題。SDCP問(wèn)題的有代表性求解算法是基于遺傳算法（Genetic Algorithm，GA）［1～3］，但因該算法自身的一些缺點(diǎn)，如，遺傳操作過(guò)程復(fù)雜、程序需要控制的變量多、計(jì)算耗時(shí)、計(jì)算量大及容易早熟等等，探究更為有效的SDCP模型問(wèn)題的求解途徑仍舊為研究人員的關(guān)注點(diǎn)。

2005 年，Karaboga 提出人工蜂群（Artificial Bee Colony，ABC）［4］算法，為蟻群算法、微粒群算法之后的又一種仿生智能算法，如今已是智能計(jì)算的一個(gè)重要組成部分，同微粒群算法、遺傳算法等群體智能算法相比較，它具有參數(shù)少、結(jié)構(gòu)簡(jiǎn)單、易實(shí)現(xiàn)，并在整個(gè)尋優(yōu)階段，局部、全局搜索在每次迭代中都會(huì)進(jìn)行，這一特點(diǎn)提高了該算法獲得最優(yōu)解的概率，這在很大程度上阻擾了發(fā)生早熟等優(yōu)點(diǎn)，從算法的提出到如今的不足十五年，ABC算法在最優(yōu)控制等領(lǐng)域中的應(yīng)用得到大量的研究者的研究和關(guān)注［5～15］，然而，至今國(guó)內(nèi)外文獻(xiàn)資料只有本文作者發(fā)表的有關(guān)蜂群算法在隨機(jī)規(guī)劃問(wèn)題求解中的應(yīng)用研究的論文［16］，本文就是把隨機(jī)模擬技術(shù)和人工蜂群算法相融合求解隨機(jī)規(guī)劃中的SDCP 模型問(wèn)題，本論文算法的優(yōu)化效果通過(guò)代表性的算例加以檢驗(yàn)，同時(shí)它也為其它不確定環(huán)境下尋優(yōu)提供了思路。

2 SDCP模型

SDCP單目標(biāo)模型形式如下：

式中：ξ，x分別代表隨機(jī)向量和決策向量，f（x）=pr｛hk(x,ξ)≤0,k=1,2,…,q｝，不等式組：hk(x,ξ)≤0,k=1,2,…,q是對(duì)隨機(jī)規(guī)劃的目標(biāo)事件的描述，gj(x,ξ)≤0,j=1,2,…,p代表了隨機(jī)不確定環(huán)境。該模型描述了在隨機(jī)環(huán)境gj(x,ξ)≤0,j=1,2,…,p約束下使得事件hk(x,ξ)≤0,k=1,2,…,q成立的機(jī)會(huì)達(dá)到最大。在隨機(jī)環(huán)境下，一個(gè)事件的機(jī)會(huì)等于與該隨機(jī)事件相容的概率，這就是不確定原理所描述的內(nèi)容，它是求解SDCP 的理論基礎(chǔ)。

在管理目標(biāo)與部分優(yōu)先結(jié)構(gòu)給定后，可通過(guò)極小化與本目標(biāo)的正或負(fù)偏差，獲得FDCP 目標(biāo)規(guī)劃描述如下：

這里，gj描述了隨機(jī)環(huán)境中的約束函數(shù)；pj描述了優(yōu)先系數(shù)，代表各個(gè)目標(biāo)的相對(duì)重要性，且對(duì)于?j，有pj?pj+1；第i個(gè)目標(biāo)小于、大于目標(biāo)值的偏差用代表；目標(biāo)約束的數(shù)量用m 代表；p 代表系統(tǒng)約束的數(shù)量；1 代表了優(yōu)先級(jí)的數(shù)量；目標(biāo)i 的函數(shù)值由bi代表；hik代表了實(shí)值函數(shù)；uij、vij分別描述了目標(biāo)i的第j個(gè)優(yōu)先級(jí)的正、負(fù)偏差權(quán)重系數(shù)。

3 人工蜂群算法

2005 年，Karaboga 提出人工蜂群算法，它也是基于仿生智能的一種啟發(fā)式算法，該算法受啟于蜂群的協(xié)作覓食，不斷探索蜜源的行為，以找到花蜜量最大的蜜源為目標(biāo)，完成優(yōu)化問(wèn)題的求解。

在該算法中，整個(gè)蜂群由三類(lèi)角色的蜜蜂組成：雇傭蜂、偵察蜂和觀察蜂，它們?cè)谝捠持蟹止ず献鳎粩嗟渲?，雇傭蜂的?shù)量是整個(gè)蜂群的二分之一，同具體的蜜源相對(duì)應(yīng)，雇傭蜂以跳搖擺舞的形式來(lái)與其他的個(gè)體分享蜜源信息，觀察蜂數(shù)量上也是占蜂群總數(shù)的二分之一，它們等候于舞蹈區(qū)，通過(guò)分享雇傭蜂的信息對(duì)蜜源完成挑選，雇傭蜂們總能根據(jù)自己記憶中的最優(yōu)位置并在其周?chē)M(jìn)行探測(cè)與偵查，丟棄食物源變?yōu)閭刹旆涞墓蛡蚍涞墓ぷ鲃t是開(kāi)始在蜂房周?chē)S機(jī)地探索新食物源。

在ABC 算法中，最優(yōu)化問(wèn)題的求解就是在問(wèn)題空間上不斷搜尋最優(yōu)的數(shù)據(jù)使得目標(biāo)函數(shù)達(dá)到最優(yōu)。在維數(shù)為D的問(wèn)題空間，食物源的位置對(duì)應(yīng)了優(yōu)化問(wèn)題的候選解，蜜源的濃度則代表了每個(gè)候選解的適應(yīng)度，食物源的數(shù)目等于雇傭蜂和觀察蜂數(shù)目的和，表示為CN，若第i 個(gè)食物源的第n 次迭代的位置表示為xi=[xi1,xi2,…xiD]，則該食物源i的初始位置利用式（1）在搜索空間隨機(jī)產(chǎn)生：

雇傭蜂根據(jù)式（2）在當(dāng)前位置周?chē)綔y(cè)與偵查潛在食物源：

其中的k（k≠i）代表在蜜源里隨機(jī)選擇一個(gè)蜜源k；若新的蜜源new_的適應(yīng)度好于，那么通過(guò)貪婪機(jī)制選擇保留該較好解。所有的雇傭蜂完成了式（2）的運(yùn)算之后，則將蜜源信息帶回蜂巢并通過(guò)舞蹈的方式進(jìn)行分享。觀察蜂依據(jù)雇傭蜂所分享的花蜜信息，依照式（3）選擇一個(gè)蜜源：

其中，fiti表示第i 個(gè)潛在解的適應(yīng)度值，pi則代表了食物源i被選中的概率。

以尋找最小化問(wèn)題為例，潛在解的適應(yīng)度值依據(jù)式（4）完成：

其中，fi代表了第i個(gè)潛在解所對(duì)應(yīng)的函數(shù)值。

所有的雇傭蜂和觀察蜂全部完成了搜索，然而食物源相對(duì)應(yīng)的適應(yīng)值在預(yù)定的number 次搜索，并在限定的食物源的改進(jìn)次數(shù)limit 次仍沒(méi)取得更好的食物源，則說(shuō)明該潛在解已經(jīng)淪為了局部最優(yōu)解，則該食物源被丟棄，而與該食物源所對(duì)應(yīng)的雇傭蜂轉(zhuǎn)變角色成為偵察蜂，它將依據(jù)式（5）繼續(xù)搜索新的食物源。

綜上，使用ABC 算法尋優(yōu)的要點(diǎn)是雇傭蜂的任務(wù)是負(fù)責(zé)搜索食物源；觀察蜂的任務(wù)是依據(jù)雇傭蜂所分享的花蜜信息，然后觀察蜂以指定的概率值完成對(duì)食物源的篩選；若某蜜源被丟棄，那么生成一個(gè)偵察蜂與隨機(jī)產(chǎn)生的新食物源相對(duì)應(yīng)。

4 嵌入隨機(jī)模擬的ABC 算法求解SDCP模型問(wèn)題

SDCP 模型問(wèn)題求解時(shí)，通過(guò)使用人工蜂群算法在解空間進(jìn)行尋優(yōu)，在不斷地迭代時(shí)需完成求解隨機(jī)適應(yīng)度值，適應(yīng)度值的計(jì)算離不開(kāi)隨機(jī)機(jī)會(huì)函數(shù)的計(jì)算，而利用隨機(jī)模擬技術(shù)可很容易地進(jìn)行計(jì)算，在利用ABC 算法進(jìn)行尋優(yōu)時(shí)，它主要為算法的初始化及所有迭代中均需要隨機(jī)模擬的概率估計(jì)算法來(lái)實(shí)現(xiàn)花蜜量的計(jì)算。

4.1 隨機(jī)模擬的概率估計(jì)算法

常規(guī)的解析法很難計(jì)算隨機(jī)事件的機(jī)會(huì)，現(xiàn)通過(guò)隨機(jī)模擬求解事件的機(jī)會(huì)。

已知量ξi（i=1，2…m）隨機(jī)變的概率分布函數(shù)用?i（i=1，2…m）表示，X 代表給定的決策向量，則計(jì)算隨機(jī)事件的機(jī)會(huì)如下：

下面給出隨機(jī)模擬的概率估計(jì)算法的基本流程：

步驟1：N′=0；

步驟2：利用概率分布函數(shù)?i，生成隨機(jī)變量ξi；

步驟3：若果hk（x，ξ）≤0 ，gj（x，ξ）≤0 ，則，N′++；

步驟4：步驟2～步驟3 共重復(fù)執(zhí)行N次；

步驟5：將N′/N的值返回。

4.2 算法步驟

嵌入隨機(jī)模擬的ABC 算法求解SDCP 算法的操作步驟。

步驟1：在D 維問(wèn)題空間中對(duì)蜜源總數(shù)為ColonyTotal 的蜜源xi（i=1，2…ColonyTotal）初始化：雇傭蜂、觀察蜂的數(shù)目均為蜜源數(shù)量的ColonyTotal/2，蜜源最大限制搜索的次數(shù)limit，最大迭代次數(shù)MaxLoopNumber，各個(gè)維度的上、下界，通過(guò)式（1）獲得ColonyTotal個(gè)隨機(jī)初始蜜源，并將雇傭蜂與其相對(duì)應(yīng)，利用隨機(jī)模擬概率估計(jì)算法計(jì)算適應(yīng)度值，并對(duì)雇傭蜂位置、觀察蜂位置、最好蜜源等初始化。

步驟2：雇傭蜂通過(guò)式（2）修改食物源信息，通過(guò)隨機(jī)模擬概率估計(jì)算法計(jì)算給定的隨機(jī)機(jī)會(huì)函數(shù)的值并計(jì)算適應(yīng)度值。然后對(duì)新食物源實(shí)施評(píng)價(jià)：若新食物源：new_的適應(yīng)度比的適應(yīng)度更好，那么通過(guò)貪婪機(jī)制把目前的較好解進(jìn)行保留，反之則保留。

步驟3：利用式（3）來(lái)獲得雇傭蜂找到食物源被觀察蜂追隨的概率，然后觀察蜂則依據(jù)該數(shù)值來(lái)挑選食物源。

步驟4：使用與雇傭蜂相同的搜索方式，觀察蜂進(jìn)行食物源的搜索，也就是通過(guò)隨機(jī)模擬可信性估計(jì)算法計(jì)算機(jī)會(huì)函數(shù)值、花蜜量，再通過(guò)貪婪機(jī)制保留當(dāng)前最好的食物源。

步驟5：檢驗(yàn)各食物源的連續(xù)搜索記錄即number 的值是否超過(guò)最大限制次數(shù)limit，如果超過(guò)，那么通過(guò)式（5）隨機(jī)產(chǎn)生一個(gè)新的食物源，利用隨機(jī)模擬概率估計(jì)算法計(jì)算隨機(jī)機(jī)會(huì)函數(shù)值、適應(yīng)度值，相應(yīng)的角色轉(zhuǎn)變：雇傭蜂轉(zhuǎn)變成偵察蜂，仍然通過(guò)貪婪機(jī)制保留當(dāng)前最好的食物源。

步驟6：判斷此時(shí)的算法是否達(dá)到了已經(jīng)給定的最高迭代次數(shù)MaxLoopNumber，若滿足，則尋優(yōu)結(jié)束，否則跳轉(zhuǎn)到步驟2。

5 性能測(cè)試與效果對(duì)比

筆者借助于經(jīng)典的文獻(xiàn)［1］里的實(shí)例完成仿真實(shí)驗(yàn)。

例5.1對(duì)單目標(biāo)的SDCP模型進(jìn)行求解：

式中，ξ1服從正態(tài)分布N（5，1），ξ2服從指數(shù)分布EXP（4）。

例5.2對(duì)目標(biāo)規(guī)劃SDCP進(jìn)行計(jì)算：

式中，ξ1服從從均勻分布U［3，5］，ξ2服從正態(tài)分布N（3.5，1），ξ3服從指數(shù)分布EXP（9）。

對(duì)于例5.1，事件為x1+2x2+3x3+4x4=6，該事件ε的支撐用ε*表示，ε*=｛x1,x2,x3,x4｝，對(duì)應(yīng)的相關(guān)支撐用ε**表示，ε**=｛x1,x2,x3,x4｝，根據(jù)隨機(jī)不確定原理，ε事件的機(jī)會(huì)函數(shù)：

機(jī)會(huì)函數(shù)的值可通過(guò)概率估計(jì)算法求得。

算法中相關(guān)參數(shù)的設(shè)置等同于文獻(xiàn)［1］：隨機(jī)模擬次數(shù)RandTime 設(shè)置為5000 次；蜂群規(guī)模ColonyTotal 設(shè)置為30 個(gè)；迭代次數(shù)MaxLoopNumber 設(shè)置為300 代；運(yùn)行次數(shù)設(shè)置為1。雇傭蜂和觀察蜂的數(shù)目都設(shè)置為15 個(gè)，最大限制搜索的次數(shù)limit設(shè)置為15次。

顯然，它們的機(jī)會(huì)函數(shù)值可利用概率估計(jì)算法求得。

算法中相關(guān)參數(shù)的設(shè)置等同于文獻(xiàn)［1］：迭代次數(shù)MaxLoopNumber 設(shè)置為1000 代；隨機(jī)模擬次數(shù)RandTime 設(shè)置為6000 次；蜂群規(guī)模ColonyTotal設(shè)置為30 個(gè)；運(yùn)行次數(shù)設(shè)置為1 次，雇傭蜂的數(shù)目設(shè)置為15個(gè)，觀察蜂的數(shù)量設(shè)置為15個(gè)，最大限制搜索的次數(shù)limit設(shè)置為15次。

在內(nèi)存容量8GB、CPU 主頻3.0 GHz、操作系統(tǒng)Win10、Visual C++6.0為主要配置的臺(tái)式電腦上完成驗(yàn)證。

在例5.1 中：嵌入隨機(jī)模擬的ABC 算法運(yùn)行的結(jié)果見(jiàn)表1，相比于文獻(xiàn)［1］中的結(jié)果，本文的優(yōu)化效果和利用了GA 算法的文獻(xiàn)［1］的相當(dāng)，但從迭代過(guò)程可知，文獻(xiàn)［1］迭代到300 代取得了最優(yōu)值94.7%，本文的ABC算法只要迭代到98代時(shí)就可達(dá)到，本文算法所得的最優(yōu)值隨著迭代次數(shù)增加的變化流程，進(jìn)行每間隔10 代采樣一次，迭代曲線如圖1 所示，它直觀地地展示了整個(gè)迭代過(guò)程：當(dāng)?shù)螖?shù)增加時(shí)，問(wèn)題的全局最優(yōu)值開(kāi)始穩(wěn)定。

圖1 實(shí)例5.1迭代曲線圖

表1 實(shí)例5.1兩種算法的優(yōu)化結(jié)果

在例5.2 中：運(yùn)行嵌入隨機(jī)模擬的ABC 算法所得的最優(yōu)解、最優(yōu)值和結(jié)果如表2，同文獻(xiàn)［1］中的求解結(jié)果相對(duì)比，顯然優(yōu)于文獻(xiàn)［1］：文獻(xiàn)［1］中第一、第二目標(biāo)的負(fù)偏差、可以滿足，但第三目標(biāo)的負(fù)偏差的最終優(yōu)化結(jié)果為0.048，本文算法優(yōu)化的效果是所獲得的最優(yōu)解對(duì)應(yīng)的所有目標(biāo)負(fù)偏差均能滿足。

表2 實(shí)例5.2兩種算法的優(yōu)化結(jié)果對(duì)比

6 結(jié)語(yǔ)

人工蜂群算法的策略是局部、全局搜索同時(shí)進(jìn)行，這使得本算法具有了很強(qiáng)的全局尋優(yōu)、收斂能力，本文主要討論了嵌入了隨機(jī)模擬的人工蜂群算法求解SDCP 問(wèn)題，對(duì)照以GA 算法為核心的混合智能算法所得的求解結(jié)果，本算法求解質(zhì)量顯著，展示了它對(duì)于SDCP問(wèn)題的求解優(yōu)勢(shì)。補(bǔ)充了通過(guò)ABC算法對(duì)隨機(jī)規(guī)劃問(wèn)題求解研究的缺席，也拓展了該算法的應(yīng)用研究范圍。

值得一提的是，本文作者將ABC 算法對(duì)隨機(jī)規(guī)劃的另外兩個(gè)子模型以及模糊規(guī)劃模型進(jìn)行了仿真實(shí)驗(yàn)，取得了與本文類(lèi)似的結(jié)果，這為各類(lèi)混合不確定規(guī)劃問(wèn)題的求解提供了參考，這是后期我們將開(kāi)展的探究。