一種基于翻轉(zhuǎn)角度的二進制粒子群優(yōu)化算法

豆增發(fā)

(中國電子科技集團 第二十研究所，陜西 西安710068)

0 引言

近年來，基于仿生學(xué)的粒子群優(yōu)化算法得到了飛速發(fā)展，各種粒子群優(yōu)化算法被開發(fā)出來，并將其應(yīng)用到了實踐當(dāng)中，取得了良好的效果。二進制粒子群算法是粒子群優(yōu)化算法的一種，該算法在特征選擇等方面得到了很好的應(yīng)用，但是，傳統(tǒng)的二進制粒子群算法存在收斂速度慢和收斂值不穩(wěn)定的問題，因此，為了提高二進制粒子群優(yōu)化收斂速度和收斂效果，本文提出了基于翻轉(zhuǎn)角度的二進制粒子群優(yōu)化算法。

1 傳統(tǒng)二進制粒子群優(yōu)化

二進制粒子群優(yōu)化的所有的粒子在一個二值搜索空間尋找最佳解。根據(jù)粒子群優(yōu)化的社會方法，一個粒子決定‘是’或者‘否’的概率可以建模如下：

概率P（Xid=1）完全依賴于Pid和Pg。Pid是迄今為止發(fā)現(xiàn)的個體最佳狀態(tài)，如果最佳個體發(fā)生在Xid為1時，Pid為1，否則，Pid為0。Pg是全局最佳，如果全局最佳發(fā)生在Xid為1時，Pg為1，否則，Pg為0。Vid決定了概率函數(shù)P（Xid=1）上的一個門限值，因而其取值范圍為[0.0,1.0],可以用反曲線函數(shù)表示：

在時刻t，第i個個體在字符串中第d個位置上的狀態(tài)Xid(t)表示為：

當(dāng)ρid＜S(Vid)時，Xid(t)=1;當(dāng)ρid＞=S(Vid)時，Xid(t)=0。

ρid是一個在[0.0,1.0]之間均勻分布的隨機數(shù)。Vid如下式所示：

rand1和rand2是在[0.0,1.0]范圍上均勻分布的隨機數(shù),φ1和φ2兩個參數(shù)的和為4.0。Vid的最大門限值Vmax被設(shè)為4.0。新的粒子位置由下式?jīng)Q定：

2 改進二進制粒子群優(yōu)化算法

在二進制粒子群優(yōu)化中，每個粒子有兩種狀態(tài)，即狀態(tài)1和狀態(tài)0，表示粒子處于狀態(tài)0的概率，表示粒子處于狀態(tài)1的概率，二進制粒子群并不是在一個連續(xù)的多維空間搜索，它實際上只是狀態(tài)的反轉(zhuǎn)而已，因此，通過對速率更新公式進行改進，移除隨機權(quán)重φ1和φ2，增加了一個狀態(tài)翻轉(zhuǎn)因子。第i個粒子的下式取0或1：位置向量根據(jù)概率進行更新，即，第i個粒子的第j個元素根據(jù)

其中，random()是取值在[0,1]區(qū)間同一分布的隨機函數(shù)，m是粒子群的最大個數(shù)，n是粒子群的維度。其中， β2可以用一個翻轉(zhuǎn)速率Δθ來代替：

上式中，XP表示局部最優(yōu)解，XG表示全局最優(yōu)解，θ是翻轉(zhuǎn)角度，γ1i和γ2i是局部翻轉(zhuǎn)因子和全局翻轉(zhuǎn)因子，它們可以通過分別與局部最佳解Pbesti和全局最佳解Gbest位置的適應(yīng)函數(shù)作比較獲得：

一般根據(jù)收斂情況動態(tài)的獲得翻轉(zhuǎn)角度：

上式中，θmax為最大翻轉(zhuǎn)角度，一般取0.05π，θmin為最小翻轉(zhuǎn)角度，一般取0.001π，t為當(dāng)前迭代次數(shù)，M為最大迭代次數(shù)。

3 實驗結(jié)果及分析

本文將改進二進制粒子群優(yōu)化和傳統(tǒng)二進制粒子群優(yōu)化、傳統(tǒng)粒子群優(yōu)化算法、GA算法做了比較。傳統(tǒng)粒子群優(yōu)化的維度取30,每個算法各運行50次，然后得出平均迭代次數(shù)和平均收斂值。為了公平起見，根據(jù)經(jīng)驗，二進制粒子群優(yōu)化、傳統(tǒng)二進制粒子群優(yōu)化以及傳統(tǒng)粒子群優(yōu)化中慣性因子和學(xué)習(xí)因子都去固定參數(shù)值，即慣性因子為0.9，局部學(xué)習(xí)因子和全局學(xué)習(xí)因子為2。

本文用平均收斂速度和平均收斂值來評價改進二進制粒子群優(yōu)化算法的收斂性能，結(jié)果如表1所示。總體來講，改進二進制粒子群優(yōu)化的收斂速度較傳統(tǒng)二進制粒子群優(yōu)化略快，平均收斂值要好很多。平均收斂速度v和平均收斂值t定義如下：

上式中m為迭代次數(shù)，n為測試次數(shù)，s為收斂值。平均收斂速度表示算法的平均在收斂之前的平均迭代次數(shù)，平均收斂值表示算法最后所取得的平均最優(yōu)解（表1）。

4 小結(jié)

本文提出了基于翻轉(zhuǎn)教的改進二進制粒子群優(yōu)化算法,該算法在二進制取值空間上，使粒子按翻轉(zhuǎn)角度進行隨機進化，最終得到使目標(biāo)函數(shù)最大的二進制參數(shù)向量。與實值連續(xù)空間的粒子群優(yōu)化不同，二進制粒子群在二進制空間取值，即每個粒子的取值為0或者為1，其進化速率根據(jù)一個翻轉(zhuǎn)角度隨機更新，這個翻轉(zhuǎn)角度參照全局最優(yōu)解和局部最優(yōu)解。

表1 改進二進制粒子群優(yōu)化算法與其他算法的性能比較

［1］吳斌，史忠植.一種基于蟻群算法的TSP問題分段求解算法[J].計算機學(xué)報，2001，24（12）：1328-1333.

［2］高海兵，周馳，高亮.廣義粒子群優(yōu)化模型[J].計算機學(xué)報，2005，28（12）：1980-1987.

［3］盧志剛，董玉香.基于改進二進制粒子群算法的配電網(wǎng)故障恢復(fù)[J].電力系統(tǒng)自動化，2006，30（24）：39-43.