求解FDCP模型問題的ABC算法

肖 寧,王 鑫

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

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

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

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

1 模型描述

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

(1)

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

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

(2)

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

2 人工蜂群算法

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

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

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

(3)

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

(4)

(5)

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

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

(6)

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

(7)

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

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

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

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

3.1 模糊模擬算法

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

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

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

第2步計算如下式子

第3步返回計算結果L。

3.2 算法流程

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

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

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

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

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

第6步結束條件判斷：檢查算法是否達到預先給定的停止準則(給定的計算精度或Nmaxcycle),若滿足，則轉向第7步，否則轉向第2步。

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

4 仿真測試和實驗結果分析

采用算例[1]開展仿真實驗以驗證本文ABC算法的效果。

例1計算以下的單目標模型問題

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

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

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

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

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

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

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

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

程序代碼參數(shù)的取值和文獻[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的計算機上運行。

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

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

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

5 結 語

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

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