肖 寧,王 鑫

(1.陜西職業(yè)技術(shù)學(xué)院 人工智能學(xué)院,西安 710100; 2.太原科技大學(xué) 系統(tǒng)仿真與計(jì)算機(jī)應(yīng)用研究所,太原 030024；3.山東省科學(xué)院 海洋儀器研究所,山東 青島 266001)

模糊相關(guān)機(jī)會規(guī)劃(fuzzy dependent-chance programming,FDCP )[1-2]，屬于不確定規(guī)劃中的模糊規(guī)劃的子類之一，針對的是決策者在模糊環(huán)境中為了極大化模糊事件成立的機(jī)會，從而提供最優(yōu)選擇的一類規(guī)劃。長久以來，如何能對這類模型問題進(jìn)行高效求解是普遍存在于管理、工程應(yīng)用、優(yōu)化算法研究等領(lǐng)域中的熱點(diǎn)問題。

在最優(yōu)控制、電力調(diào)度等實(shí)際應(yīng)用領(lǐng)域里，這類問題的提取很輕松，可因其具有模糊性和非線性等特點(diǎn)使得對它的求解或者計(jì)算并非易事，因此，進(jìn)一步研究這類問題的高效求解方法很有必要。目前，智能計(jì)算有了快速發(fā)展的計(jì)算機(jī)技術(shù)平臺的支持，已經(jīng)可以求解常規(guī)的、傳統(tǒng)的方法不易計(jì)算的復(fù)雜優(yōu)化問題，在各個應(yīng)用領(lǐng)域也發(fā)揮了突出效果。通過文獻(xiàn)可知，這類模型問題主要是利用進(jìn)化策略(evolution strategies)、遺傳算法(genetic algorithm,GA)以及差分進(jìn)化算法(differential evolution algorithm,DE)等智能計(jì)算技術(shù)和模糊模擬技術(shù)相結(jié)合求解的。大量的文獻(xiàn)表明遺傳算法[1-7]在智能算法中應(yīng)用得最成熟、效果最好且最廣泛，但因GA存在著遺傳操作過程復(fù)雜以及計(jì)算量大、控制變量較多、耗時長等固有不足，更高效地求解或計(jì)算這類模型問題依舊是學(xué)者們的努力方向。

在真實(shí)環(huán)境中蜜蜂的自組織覓食行為啟示下，人工蜂群算法(artificial bee colony,ABC)算法應(yīng)運(yùn)而生。它是人工魚群算法、粒子群算法及蟻群算法之后，又一個受啟于群體智能的啟發(fā)式智能搜索算法。2005年，ABC算法被學(xué)者D.Karaboga為了求解含有多變量的函數(shù)的優(yōu)化問題而最先提出[8]，如今已是智能計(jì)算技術(shù)的一個重要組成部分，該算法具有結(jié)構(gòu)簡單、需要控制的參數(shù)不多、易于編程實(shí)現(xiàn)、魯棒性強(qiáng)等特點(diǎn)。與粒子群、遺傳算法等智能求解算法相比，在整個尋優(yōu)期間中，每一次的迭代都進(jìn)行了全局、局部搜索，3種類型的蜂在不同情況下進(jìn)行轉(zhuǎn)換，這使ABC算法找到最優(yōu)解的概率大幅度提高，同時在較大程度上避免了陷入局部等顯著優(yōu)點(diǎn)。不到15年的時間，其理論在電力系統(tǒng)調(diào)度、圖像和信號處理、機(jī)器人行為調(diào)控、最優(yōu)路徑選擇等眾多應(yīng)用領(lǐng)域得到應(yīng)用[9-20]。從查閱的文獻(xiàn)可知，目前尚無ABC算法在模糊規(guī)劃問題求解中的報(bào)道。本文是把ABC算法與模糊模擬技術(shù)結(jié)合起來求解模糊規(guī)劃中的一個子類：模糊相關(guān)機(jī)會規(guī)劃模型問題，ABC算法的實(shí)效性通過經(jīng)典的算例得到檢驗(yàn)，實(shí)現(xiàn)了ABC算法對這一子類問題的高效求解；此外，它也為模糊機(jī)會約束規(guī)劃、模糊期望值規(guī)劃模型以及其他的不確定規(guī)劃問題的求解提供了思路。

1 模型描述

FDCP單目標(biāo)數(shù)學(xué)模型一般可以表示為以下形式

(1)

式中：C表示可信性測度;ξ和x分別表示模糊向量和決策向量；模糊不等式組{hk(x,ξ)≤0,(k=1,2,…,q)}刻畫的是模糊目標(biāo)事件；不確定環(huán)境用{gj(x,ξ)≤0,(j=1,2,…,p)}來表征。整個模型表達(dá)了在模糊不確定環(huán)境中使模糊目標(biāo)事件的可信性最大化。在模糊不確定環(huán)境下，模糊事件的機(jī)會等于與該事件相容的可能性、可信性或必要性，這是計(jì)算FDCP模型問題的不確定原理。

在相關(guān)機(jī)會規(guī)劃中，若預(yù)先給定了優(yōu)先結(jié)構(gòu)和管理目標(biāo)，則可極小化與該目標(biāo)的正或負(fù)偏差值，得到相應(yīng)的目標(biāo)規(guī)劃數(shù)學(xué)模型

(2)

式中：gj表示模糊環(huán)境中的約束函數(shù)；Pj代表優(yōu)先級權(quán)重，表示各管理目標(biāo)的相對重要程度，而且，對于?j,有Pj?Pj+1；第i個目標(biāo)高于、低于相對應(yīng)的目標(biāo)值的偏差分別用di+、di-表示；系統(tǒng)約束、目標(biāo)約束的數(shù)目分別用p和m表示；bi代表第i個目標(biāo)的函數(shù)值；l代表優(yōu)先級的數(shù)目；hik表示目標(biāo)約束中的實(shí)值函數(shù)；用uij與vij分別代表約束中的第i個目標(biāo)、優(yōu)先級為j的正與負(fù)偏差值的權(quán)重系數(shù)。

2 人工蜂群算法

人工蜂群算法是一種經(jīng)典的仿生群體智能尋優(yōu)計(jì)算方法，它源于自然界中蜜蜂的群體自組織覓食：蜜蜂可按照各自的角色或分工，通過氣味、舞蹈動作等多種信息交流方式，使得蜂群總能有效地找到花蜜量最大的蜜源。該算法就是通過模擬蜜蜂尋找最大量蜜源的這個過程實(shí)現(xiàn)尋優(yōu)。

在ABC算法模型中劃分了采蜜蜂、偵察蜂、觀察蜂這樣3種類型的蜜蜂。采蜜蜂同正在采集的蜜源一一對應(yīng)，其數(shù)量是蜂群總數(shù)的一半，而每個蜜源的所在位置代表了待優(yōu)化問題的潛在解；通過跳搖擺舞等方式，采蜜蜂與其他蜜蜂共享蜜源信息，采蜜蜂總能記得它們之前的最優(yōu)位置，并根據(jù)自己的記憶在鄰域中進(jìn)行搜索；觀察蜂在舞蹈區(qū)等待，它們通過分享來自采蜜蜂提供的信息對蜜源再進(jìn)行選擇，其數(shù)量等于采蜜蜂的數(shù)量，在算法中主要用于提高算法的收斂速度；而那些放棄了蜜源的采蜜蜂則變成了偵察蜂，其任務(wù)就是在蜂房附近開始隨機(jī)地搜索一個新的蜜源，起到了擺脫使算法陷入局部最優(yōu)的作用。

設(shè)蜜源的總數(shù)為Ns，蜜源位置代表了待求優(yōu)化問題的可能解向量，待求解問題的維數(shù)用D表示。在人工蜂群算法中，優(yōu)化問題的求解過程實(shí)質(zhì)上就是在給定的D維問題空間中搜尋最優(yōu)解的過程。設(shè)蜜源i在第n次迭代時的位置用Xi=[xi1,xi2,…,xiD]表示，依據(jù)(3)式，在問題空間隨機(jī)產(chǎn)生蜜源i的初始位置

(3)

依據(jù)(4)式，采蜜蜂在鄰域中進(jìn)行搜索新的蜜源

(4)

(5)

式中：pi代表第i個觀察蜂的跟隨概率;fi代表適應(yīng)度值;Ns代表蜜源數(shù)目。

以求解最小值問題為例，解的適應(yīng)度值fi按照(6)式進(jìn)行計(jì)算

(6)

式中：fi、vi分別表示第i個解的函數(shù)適應(yīng)度值、函數(shù)值。

(7)

在所有的采蜜蜂和觀察蜂結(jié)束整個搜索空間的搜索后，若蜜源的適應(yīng)值經(jīng)過Ntest次到達(dá)了給定的值Nlimit后(Nlimit表示放棄該蜜源的閾值)依舊沒有得到更好的蜜源時，表示該解已經(jīng)陷入了局部最優(yōu)。那么，fi所對應(yīng)的蜜源被放棄，而與該蜜源所對應(yīng)的采蜜蜂也就轉(zhuǎn)變成了偵察蜂。依據(jù)(7)式，該偵察蜂隨機(jī)地產(chǎn)生一個新的位置，一旦新的蜜源找到了，它又轉(zhuǎn)變?yōu)椴擅鄯洹?/p>

所以，ABC算法的核心點(diǎn)在于：采蜜蜂搜尋蜜源；依據(jù)采蜜蜂所提供的花蜜量信息，觀察蜂以一定的選擇概率再去選擇蜜源；若某個蜜源被采蜜蜂和觀察蜂所耗盡，則變成偵察蜂，重新隨機(jī)生成一個新的位置。

3 求解FDCP模型問題的人工蜂群算法

求解FDCP問題時要通過人工蜂群算法完成尋找最優(yōu)解，在整個尋優(yōu)過程中，算法需要解決模糊適應(yīng)度值的計(jì)算問題。適應(yīng)度值的求解與模糊機(jī)會函數(shù)即模糊事件的可信性值(或者可能性、必要性)的求解緊密聯(lián)系。對于模糊機(jī)會函數(shù)值的計(jì)算，若用常規(guī)的解析方法很難實(shí)現(xiàn)。而模糊模擬技術(shù)是在模糊系統(tǒng)中進(jìn)行抽樣的一種技術(shù)，它在多維模糊變量問題中已經(jīng)廣泛使用，模糊機(jī)會函數(shù)值通過模糊模擬技術(shù)可以很方便地進(jìn)行求解。在利用人工蜂群算法進(jìn)行尋優(yōu)期間，它主要表現(xiàn)在：初始化階段，要用模糊 模擬 來實(shí)現(xiàn)所有蜜源的機(jī)會函數(shù)值的計(jì)算；在每一次迭代時，也需要通過模糊模擬求解蜜源的機(jī)會函數(shù)值等。

3.1 模糊模擬算法

常規(guī)的解析法很難計(jì)算可信性測度，通過模糊模擬技術(shù)求解模糊事件的可信性：L=C{f(ξ)≤0}。

下面給出模糊模擬可信性估計(jì)算法的流程：

第1步θk從非空集合θ中均勻生成后使得它能滿足條件Pos{θk}≥ε,其中的k=1,2,…,N;同時定義vk= Pos{θk},這里的k=1,2,…,N;ε代表一個充分小的數(shù)。

第2步計(jì)算如下式子

第3步返回計(jì)算結(jié)果L。

3.2 算法流程

求解FDCP問題的人工蜂群算法的具體流程如下：

第1步首先，對于NP個蜜源xi(i=1,2,…,NP)，在D維空間上先初始化：采蜜蜂的數(shù)目等于觀察蜂的數(shù)目等于蜜源總數(shù)據(jù)的一半，在蜜源停留的最大限制次數(shù)Nlimit,算法的最大迭代次數(shù)Nmaxcycle,各個維度的上界及下界值，隨機(jī)生成NP個初始蜜源，可通過(3)式計(jì)算每個蜜源的花蜜量即適應(yīng)度值，也就是通過模糊模擬可信性 估計(jì)算法來計(jì)算模糊機(jī)會函數(shù)值；對觀察蜂也要進(jìn)行初始位置等相應(yīng)的初始化工作以及對最優(yōu)蜜源的初始位置、花蜜量等進(jìn)行初始化等。

第3步通過(5)式，計(jì)算采蜜蜂找到蜜源被觀察蜂跟隨的概率，觀察蜂根據(jù)該概率的大小選擇蜜源。

第4步觀察蜂搜尋蜜源(與采蜜蜂相同的方式)，通過上面描述的模糊模擬算法計(jì)算機(jī)會函數(shù)值、適應(yīng)度值，即蜜源的花蜜量，依據(jù)貪婪選擇策略，保留當(dāng)前的最優(yōu)蜜源。

第5步為增加蜂群的多樣性，檢測各蜜源是否達(dá)到了被放棄的閾值，即檢測各蜜源的持續(xù)搜索次數(shù)記錄變量Ntest是否到達(dá)Nlimit，若超過，則通過(7)式隨機(jī)生成一個新的食物源來代替舊食物源，通過上面描述的模糊模擬算法計(jì)算模糊機(jī)會函數(shù)值、適應(yīng)度值，相應(yīng)的采蜜蜂變?yōu)閭刹旆?，依?jù)貪婪選擇策略，保留當(dāng)前的最優(yōu)蜜源。

第6步結(jié)束條件判斷：檢查算法是否達(dá)到預(yù)先給定的停止準(zhǔn)則(給定的計(jì)算精度或Nmaxcycle),若滿足，則轉(zhuǎn)向第7步，否則轉(zhuǎn)向第2步。

第7步停止計(jì)算，給出最優(yōu)值及相對應(yīng)的解。

4 仿真測試和實(shí)驗(yàn)結(jié)果分析

采用算例[1]開展仿真實(shí)驗(yàn)以驗(yàn)證本文ABC算法的效果。

例1計(jì)算以下的單目標(biāo)模型問題

例2求解以下的模糊相關(guān)機(jī)會規(guī)劃的目標(biāo)規(guī)劃問題

對于例1,事件為：x12+x22+x32=1用ε表示，它的支撐ε*={x1,x2,x3}，它的相關(guān)支撐ε**={x1,x2,x3}，依據(jù)不確定原理可得到事件ε的模糊機(jī)會函數(shù)f(x)的值通過下式計(jì)算

機(jī)會函數(shù)的值可用模糊模擬技術(shù)計(jì)算得到。

算法代碼中參數(shù)的取值和文獻(xiàn)[1]相同。模糊模擬總次數(shù)：5 000；種群數(shù)量：30；迭代次數(shù)：400；運(yùn)行次數(shù)：1。此外，觀察蜂的數(shù)量等于采蜜蜂的數(shù)量(等于15)，閾值Nlimit=15。

對于例2，第一優(yōu)先級里的事件為x1+x32=3，用ε1表示， 它的支撐為ε1*={x1,x3}，它的相關(guān)支撐為ε1**={x1,x2,x3,x4}。依據(jù)不確定原理可得到該事件ε1的機(jī)會函數(shù)f1(x)為

類似地，第二優(yōu)先級里的事件為x2+x52=2，它的機(jī)會函數(shù)f2(x)為

第三優(yōu)先級里的事件為x4+x62=1，它的機(jī)會函數(shù)f3(x)為

顯然這3個機(jī)會函數(shù)的值可以通過模糊模擬技術(shù)計(jì)算得到。

程序代碼參數(shù)的取值和文獻(xiàn)[1]相同。模糊模擬總次數(shù)： 5 000；蜂群數(shù)量：30；觀察蜂數(shù)目：15；迭代次數(shù)：400；采蜜蜂數(shù)目：15；閾值Nlimit=15。

本文的ABC算法通過Visual C++6.0編程，在inter(R) coreTMi5-7400cpu@3.00 GHz、8 GB內(nèi)存、win10的計(jì)算機(jī)上運(yùn)行。

在例1中，ABC算法執(zhí)行一次后的最優(yōu)解和最優(yōu)值見表1，與文獻(xiàn)[1]中的求解結(jié)果相對比，文獻(xiàn)[1]的計(jì)算優(yōu)勢遠(yuǎn)遠(yuǎn)不如本文算法的優(yōu)化結(jié)果。如圖1的迭代過程抽樣分析，展現(xiàn)了本文所提出的人工蜂群算法的整個迭代過程，我們把代碼執(zhí)行的迭代流程進(jìn)行了80次的數(shù)據(jù)采樣。人工蜂群算法求解精度高、收斂速度快，文獻(xiàn)[1]中，GA算法進(jìn)行了400次的迭代后所求得的最優(yōu)結(jié)果，在本文的基于ABC的算法中15次迭代以內(nèi)就可以達(dá)到；而且，從該迭代過程抽樣分析圖中可以看到，隨著搜索的不斷進(jìn)行，待求問題的最大值也趨于穩(wěn)定，該求解算法的穩(wěn)定收斂性無需多言。另外，將該程序代碼執(zhí)行10次后進(jìn)行最終求解結(jié)果對比，每一次所得的運(yùn)行效果類似，而且全局最優(yōu)值平均從第9次迭代就超過了文獻(xiàn)[1]在400迭代時的全局最優(yōu)值，平均最優(yōu)解和最優(yōu)值見表1。

表1 實(shí)例1中不同算法的優(yōu)化結(jié)果對比Table 1 Comparison of optimization results of two algorithms in case 1

表2 實(shí)例2中不同算法的優(yōu)化結(jié)果對比Table 2 Comparison of optimization results of two algorithms in case 2

5 結(jié) 語

本文研究了ABC算法與模糊模擬技術(shù)相結(jié)合，即將模糊模擬技術(shù)嵌入到ABC算法中求解相關(guān)機(jī)會規(guī)劃的求解算法問題，通過與以GA智能算法為核心的求解算法的實(shí)例仿真的結(jié)果對比，驗(yàn)證了基于人工蜂群算法的方法在求解質(zhì)量和收斂速度及穩(wěn)定性方面效果明顯，能夠很好地解決這類優(yōu)化問題的計(jì)算，展現(xiàn)了其在該類問題上的算法的優(yōu)越性，在連續(xù)空間的相關(guān)機(jī)會規(guī)劃問題進(jìn)行高效計(jì)算。本文所提出的方法是一種全新的方法，具有潛在的應(yīng)用價(jià)值， 填補(bǔ)了ABC算法在模糊規(guī)劃問題中應(yīng)用研究的空白，而且也拓寬了ABC算法的應(yīng)用研究領(lǐng)域。

值得說明的是，本文作者將ABC算法也對其他2種模糊規(guī)劃和隨機(jī)規(guī)劃問題進(jìn)行了求解，得到了和本文類似的求解效果，它對其他的雙重不確定規(guī)劃模型問題的計(jì)算方法有借鑒意義，也是我們后繼要開展的研究工作。