一種改進(jìn)的人工電場(chǎng)算法*

李曉瑜

（安康學(xué)院電子與信息工程學(xué)院 安康 725000）

1 引言

元啟法式算法是通過一些定義規(guī)則和隨機(jī)性來模擬自然現(xiàn)象或生物進(jìn)化的過程進(jìn)行優(yōu)化的算法［1］。由于元啟法式在解決復(fù)雜非線性，多模，雜交和組合等問題時(shí)具有較優(yōu)的性能，因此吸引了許多的研究者對(duì)其進(jìn)行研究，各種基于種群的元啟發(fā)式算法不斷被提出例如，遺傳算法（GA）［2］，差分算法（DE）［3］，人 工蜂 群 算 法（ABC）［4］，蟻 群 算法（ACO）［5］，粒子群算法（PSO）［6］，萬有引力算法（GSA）［7］和布谷鳥算法（CCS）［8］等。不同的算法有不同的優(yōu)勢(shì)，“天下沒有免費(fèi)的午餐”［9］，一些作者提出了一些雜交的算法［10～11］。

人工電場(chǎng)算法是受庫侖定律和運(yùn)動(dòng)定律啟發(fā)，由Anita 和Anupam Yadav 等在2019 年首次提出來的一種基于種群的元啟發(fā)式優(yōu)化算法［13］。人工電場(chǎng)算法將種群中的每個(gè)個(gè)體看作一個(gè)電的粒子，每個(gè)粒子所處的位置代表問題的一個(gè)候選解，這些粒子在電場(chǎng)力的作用下不斷改變其位置，來尋找個(gè)體的最優(yōu)位置也就是問題的最優(yōu)解。人工電場(chǎng)算法的性能主要受粒子間電場(chǎng)力的影響，粒子間的電場(chǎng)力決定粒子的速度和加速度，從而影響粒子移動(dòng)的速度和方向。

電場(chǎng)力越大，粒子位置改變的幅度越大，算法探索新的可行域的范圍越廣，算法的勘探能力就越強(qiáng)。電場(chǎng)力越小，粒子位置改變的幅度越小，算法可以開采鄰域區(qū)域，有利于算法的開采能力。在AEFA 算法中粒子間的電場(chǎng)力的大小除了受到粒子間距離和帶電量的影響外還受到引力常數(shù)的影響。引力常數(shù)的取值越大，粒子間的電場(chǎng)力越大，引力常數(shù)越小，粒子間的電場(chǎng)力也越小?；诜N群的元啟發(fā)式算法的健壯性和有效性是由在算法的探索和開采能力之間平衡的能力來決定的［14］。在算法的初始階段搜索空間中的解一般離最優(yōu)解的距離比較遠(yuǎn)所以個(gè)體需要較大的移動(dòng)步長(zhǎng)，也就是需要加強(qiáng)個(gè)體的探索能力；在算法后期最優(yōu)解一般位于當(dāng)前的個(gè)體的臨近區(qū)域，所以需要減小個(gè)體的移動(dòng)步長(zhǎng)，來增強(qiáng)個(gè)體的局部開采能力，避免錯(cuò)過最優(yōu)解［15］。在最初的AEFA 算法中采用一個(gè)遞減的指數(shù)函數(shù)來計(jì)算引力常數(shù)，這種計(jì)算方法會(huì)使引力常數(shù)的取值快速的減小，從而使得算法探索的時(shí)間不足，容易使算法陷入局部最優(yōu)，本文在通過對(duì)引力常數(shù)的計(jì)算方法進(jìn)行改進(jìn)，初始階段使得引力常數(shù)K 有一個(gè)較大的值，然后使其緩慢的減小，使得算法有充足的時(shí)間在搜索空間中進(jìn)行探索，在算法的后期引力常數(shù)取一個(gè)較小的值，使得算法能夠進(jìn)行局部開采功能，獲取最優(yōu)解。

2 人工電場(chǎng)算法（AEFA）

庫倫定律規(guī)定兩個(gè)帶電粒子間的電場(chǎng)力與粒子所帶的電量成正比，與粒子間的距離成反比。假如兩個(gè)粒子的帶電量分別為Q1和Q2，引力常數(shù)用K 來表示，粒子間的歐氏距離用D 來表示，則粒子間的電場(chǎng)力F可用公式表示為

在牛頓定律中，物體的加速度與它所受的合力成正比，與它的質(zhì)量成反比。如果加速度用a 表示，粒子的質(zhì)量用m 表示，粒子間的合力用F 表示，則加速度計(jì)算公式為

人工電場(chǎng)算法（AEFA）是一種基于種群的元啟法式優(yōu)化算法，通過模擬庫侖定律的特點(diǎn)來解決優(yōu)化問題。在AEFA 中每個(gè)個(gè)體是一個(gè)帶電的粒子，每個(gè)粒子的位置代表問題的一個(gè)解，這些帶電的粒子在它們之間的電場(chǎng)力的引導(dǎo)下，逐步的向種群中最優(yōu)的位置靠近，這個(gè)最優(yōu)的位置就是我們要找的最優(yōu)解。在AEFA 算法中電量較小的粒子在電量較大的粒子的引力下，向帶電量較大的粒子移動(dòng)。在引力的不斷作用下，整個(gè)種群逐漸向電量較大的個(gè)體方向逼近，最終搜索到問題的最優(yōu)解，并且個(gè)體的運(yùn)動(dòng)遵循牛頓第二定律。

其中，K0是庫倫常數(shù)的初始值，α是一個(gè)常數(shù)值，it表示當(dāng)前代數(shù)，maxit表示最大迭代次數(shù)。在AEFA 算法中粒子的帶電量越大，它所在的位置代表的解越優(yōu)。第i個(gè)個(gè)體所具有的電量的可使用如下公式計(jì)算：

粒子i在第d 維所受到的合力以及所具有的加速度可分別表示如式（11）和式（12）：

其中，rand 是一個(gè)取值范圍在0～1 之間的服從均勻分布的隨機(jī)數(shù)。

粒子在電場(chǎng)力的作用下不斷的更新位置，逐漸向最優(yōu)解靠近。

3 改進(jìn)的引力常數(shù)

為了平衡AEFA 算法的探索和開采能力，使得庫侖常數(shù)在算法初期有一個(gè)較大的數(shù)值，使得粒子在搜索空間的移動(dòng)步長(zhǎng)足夠大，這樣可以提升算法的探索能力，使得算法在較大的空間搜索最優(yōu)解，而且使得庫侖常數(shù)以相對(duì)緩慢的速度遞減，這樣可以使得算法充分的探索搜索空間。在迭代的后期庫侖常數(shù)取一個(gè)較小的值，粒子以較小的步長(zhǎng)在搜索空間進(jìn)行移動(dòng)，這樣可以使得算法增強(qiáng)算法的局部開采能力，避免錯(cuò)過最優(yōu)解。新的庫侖常數(shù)計(jì)算公式如下：

K′(t)和K(t)的對(duì)比圖如圖1 所示。其中黃色曲線代表的是K(t)，藍(lán)色曲線代表的是K′(t)。

圖1 庫侖常數(shù)對(duì)比圖

4 實(shí)驗(yàn)結(jié)果分析

為了證明改進(jìn)后算法的有效性，將IAEFA 與AEFA 在三個(gè)基準(zhǔn)測(cè)試函數(shù)，包括兩個(gè)單模函數(shù)（F1-F2）和一個(gè)多模函數(shù)（F3）上進(jìn)行對(duì)比，我們采用表示解的精度的平均值和表示解的穩(wěn)定性的方差來對(duì)算法結(jié)果進(jìn)行評(píng)估。實(shí)驗(yàn)設(shè)置如下：種群規(guī)模為50，問題的維度為30，最大迭代次數(shù)為1000，為了算法的公平性每個(gè)算法在每個(gè)函數(shù)上獨(dú)立運(yùn)行25次。F1，F(xiàn)2和F3的3D圖像如圖2～4所示。

圖2 F1 Schwefel's 函數(shù)

AEFA和IAEFA的實(shí)驗(yàn)結(jié)果如表2所示。

表2 解的對(duì)比結(jié)果

圖3 F2 Rosenbrock函數(shù)

圖4 Set Function 函數(shù)

由表1 中結(jié)果可以看出，IAEFA 在所有測(cè)試函數(shù)上的結(jié)果都優(yōu)于AEFA。為了進(jìn)一步驗(yàn)證改進(jìn)后算法的有效性，我們對(duì)IAEFA 和AEFA 兩種算法的收斂性進(jìn)行對(duì)比分析。其對(duì)比結(jié)果如圖5所示。

表1 基準(zhǔn)測(cè)試函數(shù)

通過對(duì)比發(fā)現(xiàn)改進(jìn)后的算法無論在求解精度和收斂速度上均有提高。

5 結(jié)語

本文通過分析AFEA 算法的工作原理，對(duì)影響其性能的引力常數(shù)進(jìn)行改進(jìn)，通過減緩引力常數(shù)變化的速度來延長(zhǎng)算法勘探的過程，延長(zhǎng)算法勘探新的可行區(qū)域的時(shí)間，提升算法的勘探能力，促進(jìn)算法尋找到更多的可行解。并將改進(jìn)后的算法和原始的AFEA 算法在三個(gè)經(jīng)典測(cè)試函數(shù)上進(jìn)行性能對(duì)比，對(duì)比結(jié)果顯示改進(jìn)后的算法在收斂速度和解的精度方面都有很大的提高，這表明本文提出的改進(jìn)算法是有效的。