(長江大學信息與數(shù)學學院，湖北 荊州 434023)

隨著計算機的不斷發(fā)展，人們提出了越來越多的元啟發(fā)式算法，并廣泛地運用到復雜的函數(shù)優(yōu)化問題上。這些元啟發(fā)式算法大致可以分為基于進化的元啟發(fā)式算法、基于物理的元啟發(fā)式算法和基于群體的元啟發(fā)式算法3類。常見的基于進化的元啟發(fā)式算法有遺傳算法(GA)[1]、差分進化算法(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]。隨著對算法的進一步研究，人們提出了很多改進的策略來增強算法的性能，包括改進的自適應差分進化算法(ADE)[10]、自適應變異尺度系數(shù)和混合選擇的回溯搜索算法(FS-BSA)[11]、基于多變異策略的自適應差分進化算法(ADE-MM)[12]。這些算法基本上都是在收斂速度和全局搜索能力之間做出改進。

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

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

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

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

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

(1)

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

1.1 變異

1.1.1 經(jīng)驗階段

該階段是依據(jù)會議中領導的經(jīng)驗做出的決策。CDOA算法根據(jù)種群中每個個體適應值選出相應的最好的個體(Xb)來設計的算子，具體如下：

(2)

1.1.2 交流階段

接下來，所有的決策者隨意的相互交流意見。在算法中表現(xiàn)為隨機選取一個比當前代個體Xi(t)適應度大的個體Xj(t)指導個體學習，算子如下：

(3)

1.1.3 群體思考階段

群體思考會影響每個決策者進行決策，相應的選取所有個體的重心(XG)：

(4)

向群體學習的算子如下：

(5)

1.1.4 領導階段

領導的決策不僅影響其他的決策者，并且決定著會議的方向和最終的方案。相應的選取種群中最好的個體XL，算子如下：

(6)

然而，領導的決策只能改變自己。因此，在算法中筆者運用隨意擾動策略來輕微地改變個體XL，也就是局部搜索：

(7)

XL=newXkk=min_ObjFun(newXq)

(8)

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

1.1.5 創(chuàng)新階段

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

(9)

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

1.2 選擇

CDOA的選擇是將得到的5個子代個體newXi0、newXi1、newXi2、newXi3、newXi4和1個父代個體Xi進行比較，保留適應度高的個體進入下一代。

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

2 ACDOA

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

(10)

(11)

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

算法計算步驟如下:

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

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

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

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

5)t=t+1。

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

3 算法測試

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

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

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

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

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

4 結語

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