一種自適應(yīng)變異策略的集體決策優(yōu)化算法

(長(zhǎng)江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023)

隨著計(jì)算機(jī)的不斷發(fā)展，人們提出了越來(lái)越多的元啟發(fā)式算法，并廣泛地運(yùn)用到復(fù)雜的函數(shù)優(yōu)化問(wèn)題上。這些元啟發(fā)式算法大致可以分為基于進(jìn)化的元啟發(fā)式算法、基于物理的元啟發(fā)式算法和基于群體的元啟發(fā)式算法3類。常見(jiàn)的基于進(jìn)化的元啟發(fā)式算法有遺傳算法(GA)[1]、差分進(jìn)化算法(DE)[2]、回溯搜索優(yōu)化算法(BSA)[3]，基于物理的元啟發(fā)式算法有模擬退火算法(SA)[4]、黑洞算法(BH)[5]、引力搜索算法(GSA)[6]，基于群體的元啟發(fā)式算法有蟻群優(yōu)化算法(ACO)[7]、粒子群優(yōu)化算法(PSO)[8]、人工蜂群優(yōu)化算法(ABC)[9]。隨著對(duì)算法的進(jìn)一步研究，人們提出了很多改進(jìn)的策略來(lái)增強(qiáng)算法的性能，包括改進(jìn)的自適應(yīng)差分進(jìn)化算法(ADE)[10]、自適應(yīng)變異尺度系數(shù)和混合選擇的回溯搜索算法(FS-BSA)[11]、基于多變異策略的自適應(yīng)差分進(jìn)化算法(ADE-MM)[12]。這些算法基本上都是在收斂速度和全局搜索能力之間做出改進(jìn)。

集體決策優(yōu)化算法(CDOA)是張清華博士于2016年受到集體決策行為啟發(fā)提出的一種基于種群的進(jìn)化算法[13]。每個(gè)決策者相當(dāng)于每次迭代的個(gè)體，決策者之間進(jìn)行交流最終產(chǎn)生的方案就相當(dāng)于最優(yōu)解。CDOA共有5步變異策略，分別是個(gè)體最優(yōu)、較好的其他個(gè)體、種群重心、全局最優(yōu)學(xué)習(xí)以及對(duì)局部最優(yōu)個(gè)體的變異，這些策略加快了算法的收斂速度，但種群多樣性不夠，并且算法在每一次迭代過(guò)程中需要5次函數(shù)評(píng)價(jià)，大大增加計(jì)算成本。

針對(duì)CDOA的不足，筆者提出了一種自適應(yīng)變異策略的集體決策優(yōu)化算法(ACDOA)，在變異策略中以一種自適應(yīng)的概率在增大種群多樣性和加快收斂速度的這2個(gè)變異算子中選擇1個(gè)作為變異算子對(duì)每一個(gè)個(gè)體進(jìn)行變異。在當(dāng)前種群中2種變異策略被選擇的概率與上一代種群中2種變異策略的成功率成正比，并隨2種變異策略搜索最優(yōu)解自適應(yīng)的改變。若前一種策略變異后個(gè)體適應(yīng)度大的個(gè)體越多，則下一次迭代選擇該策略的概率越大；反之，選擇后一種變異策略的概率越大。

1 集體決策優(yōu)化算法

集體決策優(yōu)化算法是基于種群的進(jìn)化算法，與其他進(jìn)化算法類似，算法分為變異、選擇2個(gè)部分。

隨機(jī)產(chǎn)生種群pop和第t次迭代的個(gè)體：

(1)

式中：i=1,2,…,N，N為種群大??；D為種群維數(shù)；lxk、uxk分別表示第k代個(gè)體的下界和上界；U表示均勻分布。

1.1 變異

1.1.1 經(jīng)驗(yàn)階段

該階段是依據(jù)會(huì)議中領(lǐng)導(dǎo)的經(jīng)驗(yàn)做出的決策。CDOA算法根據(jù)種群中每個(gè)個(gè)體適應(yīng)值選出相應(yīng)的最好的個(gè)體(Xb)來(lái)設(shè)計(jì)的算子，具體如下：

(2)

1.1.2 交流階段

接下來(lái)，所有的決策者隨意的相互交流意見(jiàn)。在算法中表現(xiàn)為隨機(jī)選取一個(gè)比當(dāng)前代個(gè)體Xi(t)適應(yīng)度大的個(gè)體Xj(t)指導(dǎo)個(gè)體學(xué)習(xí)，算子如下：

(3)

1.1.3 群體思考階段

群體思考會(huì)影響每個(gè)決策者進(jìn)行決策，相應(yīng)的選取所有個(gè)體的重心(XG)：

(4)

向群體學(xué)習(xí)的算子如下：

(5)

1.1.4 領(lǐng)導(dǎo)階段

領(lǐng)導(dǎo)的決策不僅影響其他的決策者，并且決定著會(huì)議的方向和最終的方案。相應(yīng)的選取種群中最好的個(gè)體XL，算子如下：

(6)

然而，領(lǐng)導(dǎo)的決策只能改變自己。因此，在算法中筆者運(yùn)用隨意擾動(dòng)策略來(lái)輕微地改變個(gè)體XL，也就是局部搜索：

(7)

XL=newXkk=min_ObjFun(newXq)

(8)

其中：min_ObjFun是最小目標(biāo)函數(shù)值的指標(biāo)。

1.1.5 創(chuàng)新階段

在決策過(guò)程中，創(chuàng)新對(duì)產(chǎn)生一個(gè)好想法起到了一定的作用。為了避免局部最優(yōu)，CDOA利用創(chuàng)新對(duì)變量進(jìn)行細(xì)微變異增大種群的多樣性，其類似于其他進(jìn)化算法里的交叉算子。相應(yīng)算子如下：

(9)

式中：r0是區(qū)間(0, 1)上的一個(gè)隨機(jī)數(shù)；p是區(qū)間[1,D]內(nèi)的隨機(jī)整數(shù)；MR是創(chuàng)新因子，是一個(gè)常數(shù)。

1.2 選擇

CDOA的選擇是將得到的5個(gè)子代個(gè)體newXi0、newXi1、newXi2、newXi3、newXi4和1個(gè)父代個(gè)體Xi進(jìn)行比較，保留適應(yīng)度高的個(gè)體進(jìn)入下一代。

最后將得到的新種群pop放入下一代循環(huán)，并重復(fù)上述過(guò)程，直到滿足循環(huán)終止條件為止。

2 ACDOA

CDOA的變異算子運(yùn)用了個(gè)體最優(yōu)、全局最優(yōu)、重心等個(gè)體指導(dǎo)變異。這種方式加快了算法的收斂速度，但是前期種群的多樣性不夠，容易使算法陷入局部最優(yōu)，且任意組合CDOA中的幾個(gè)變異算子可以形成一個(gè)新的算法。筆者提出了自適應(yīng)變異策略，在原算法中選出2組變異算子，前一種在迭代前期增強(qiáng)種群的多樣性，后一種變異算子在迭代后期加快收斂速度，算子如下：

(10)

(11)

式(11)表示通過(guò)向其他個(gè)體學(xué)習(xí)變異策略變異后和向領(lǐng)導(dǎo)者學(xué)習(xí)變異策略變異后能成功進(jìn)入下一代的子代個(gè)體占父代個(gè)體的比例。因此，在變異過(guò)程中使用這2種變異策略的概率是不斷進(jìn)行更新的，即種群自適應(yīng)的選擇變異策略進(jìn)行變異。一旦在前期種群陷入局部最優(yōu)，ns1、ns2、nf1、nf2參數(shù)會(huì)被重置。這種不斷自適應(yīng)的過(guò)程會(huì)讓算法在進(jìn)化過(guò)程中選擇最適合的學(xué)習(xí)策略。

算法計(jì)算步驟如下:

1)初始化操作：隨機(jī)產(chǎn)生N個(gè)個(gè)體的初始的種群，即pop(t)={X1(t) ,…,Xi(t),…,XN(t)}確定最大進(jìn)化代數(shù)Tmax，令T=0，初始概率p=0.5。

2)對(duì)第T代個(gè)體Xi(t)執(zhí)行式(2)～式(10)步驟生成第T+1代個(gè)體。

3)記錄ns1，ns2，nf1，nf2的大小，代入式(11)計(jì)算出p的值，然后將生成的T+1代個(gè)體根據(jù)前面計(jì)算p的值代入式(10)進(jìn)行計(jì)算。

4)選擇：將生成的 newXi0，newXi2子代個(gè)體與Xi(t)父代個(gè)體比較保留適應(yīng)度高的個(gè)體。

5)t=t+1。

6)重復(fù)步驟2)～ 步驟6)，直到求得最優(yōu)解或T>Tmax。

3 算法測(cè)試

利用3個(gè)標(biāo)準(zhǔn)的測(cè)試函數(shù)Spere、Ackley、Schwefel測(cè)試ACDOA的有效性，并將得到結(jié)果與CDOA的結(jié)果進(jìn)行比較。測(cè)試函數(shù)如表1所示，測(cè)試結(jié)果如表2所示，每一次的迭代結(jié)果收斂圖如圖1所示。算法參數(shù)如下：種群大小N=50，最大迭代次數(shù)T=6000。

表1 測(cè)試函數(shù)及參數(shù)設(shè)定

表2 算法尋優(yōu)結(jié)果

圖1 3個(gè)函數(shù)收斂圖

表1中，Sphere函數(shù)為單峰函數(shù)，不存在局部最優(yōu)解；其余函數(shù)均為多峰函數(shù)，存在較多局部最優(yōu)解；3個(gè)函數(shù)的最優(yōu)值均在零點(diǎn)處。表2中，通過(guò)3個(gè)函數(shù)尋優(yōu)的結(jié)果可以看出，ACDOA和CDOA都能找到最優(yōu)值，且ACDOA找到的最優(yōu)值更接近函數(shù)的最小值，說(shuō)明ACDOA在收斂精度上較CDOA有較大的提升，并且具有良好的競(jìng)爭(zhēng)力。從圖1還可以看出，ACDOA(紅色)的收斂速度在3個(gè)函數(shù)中都好于CDOA(藍(lán)色)。綜上所述，ACODA在尋優(yōu)準(zhǔn)確率和尋優(yōu)精度上較CODA都有進(jìn)一步的提高。

4 結(jié)語(yǔ)

為提高CDOA算法的搜索效率，提出了一種自適應(yīng)變異策略的集體決策優(yōu)化算法(ACDOA)。算法的設(shè)計(jì)思想是使算法在保持收斂速度快的基礎(chǔ)上增強(qiáng)全局搜索能力。3個(gè)測(cè)試函數(shù)的測(cè)試結(jié)果表明，ACDOA較CDOA具有更快的收斂速度、更高的收斂精度以及更好的全局收斂能力，說(shuō)明了ACDOA的可行性和有效性。