李曉瑜

(安康學(xué)院 電子與信息工程學(xué)院，陜西 安康 725000)

0 引言

在過去的幾十年中，由于基于種群的元啟發(fā)式算法在解決復(fù)雜問題和工程優(yōu)化方面有著突出的表現(xiàn)，所以各種不同的優(yōu)化算法相繼出現(xiàn)?；诜N群的元啟法式算法是通過模擬自然或生物的過程來進(jìn)行優(yōu)化的算法[1]。由于受到鳥群和魚群覓食行為的啟發(fā)Kennedy和Eberhart[2]在1995年提出了粒子群優(yōu)化算法(PSO)。由于受到達(dá)爾文進(jìn)化論的啟發(fā)Storn和Price[3]于1997年提出差分進(jìn)化算法(DE)。Karaboga,和Basturk[4]于2007年提出了人工蜂群算法(ABC)，模擬蜂群的覓食行為。Tang和Man等[5]于1996年提出了遺傳算法(GA)。Yang和 Deb[6]于2009年提出了布谷鳥算法(CCS)。受萬有引力定律啟發(fā)，Esmat Rashedi等[7]人在2009年提出萬有引力算法(GSA)。

還有一些最新提出的基于種群的元啟式搜索算法，受騎手運(yùn)動(dòng)行為的啟發(fā)的騎手算法(ROA)[8]和受自然中原子運(yùn)動(dòng)模型啟發(fā)的原子搜索算法(ASO)。人工電場(chǎng)算法是Anita 和 Anupam Yadav等于2019年提出來的一種基于庫侖定律和第二運(yùn)動(dòng)定律的元啟發(fā)式優(yōu)化算法[9]，根據(jù)帶電粒子間的引力或斥力，改變粒子的移動(dòng)位置來尋找最優(yōu)解的算法。在AEFA中粒子的位置更新的步長(zhǎng)是由粒子的速度決定的，而粒子的速度又是由加速度決定的，加速度的大小是由粒子間的電場(chǎng)力和帶電量決定的，粒子間的電場(chǎng)力又受到引力常數(shù)K的影響，K 越大粒子間的電場(chǎng)力越大，電場(chǎng)中粒子移動(dòng)的加速度就大，位置更新的步長(zhǎng)就大，算法的探索能力就越強(qiáng)。相反，K 越小粒子間的電場(chǎng)力越小，電場(chǎng)中粒子移動(dòng)的加速度就小，位置更新的步長(zhǎng)就小，算法的開采能力就越強(qiáng)。由于在人工電場(chǎng)算法中種群在庫侖力的作用下收斂到最優(yōu)位置，帶電量越大的粒子對(duì)其它粒子的吸引力就越大，所以被其他粒子吸引移動(dòng)的就慢，步長(zhǎng)就會(huì)變小，到算法后期具有較大電量的粒子會(huì)移動(dòng)的越來越慢。同時(shí)原始的引力常數(shù)計(jì)算方法，使得引力常數(shù)快速減小，進(jìn)一步降低了算法的收斂速度，易使算法陷入局部最優(yōu)和“早熟”。為了更好地平衡算法的勘探和開采能力，我們?cè)谒惴ǖ囊Τ?shù)計(jì)算中引入混沌映射，使得算法能夠平緩地在勘探和開采階段進(jìn)行過渡，避免算法陷入“早熟”。

2 人工電場(chǎng)算法(AFEA)

人工電場(chǎng)算法是一種基于庫倫定律和牛頓第二定律的基于種群的元啟法式優(yōu)化算法。算法把種群中的每一個(gè)個(gè)體看作是一個(gè)帶電的粒子，種群中個(gè)體的位置和問題的解相對(duì)應(yīng)，粒子靠它們之間的電場(chǎng)力在搜索空間中不斷移動(dòng)，粒子移動(dòng)到的最優(yōu)位置，便是要找的最優(yōu)解。在庫倫定律中，真空中兩個(gè)靜止的點(diǎn)電荷由于電場(chǎng)力的作用而相互吸引或排斥，同名電荷相排斥，異名電荷相吸引。兩個(gè)粒子間的電場(chǎng)力和它們電荷量的乘積成正比與它們之間距離的二次方成反比。如式(1)。

(1)

其中，F(xiàn)表示粒子間的電場(chǎng)力;K表示引力常數(shù);Q1和Q2分別表示兩個(gè)粒子的帶電量;D表示兩個(gè)粒子間的距離。

在AEFA算法中只考慮一個(gè)電量較大的粒子對(duì)其他電量較低的粒子的靜電引力，通過引力的作用，個(gè)體之間相互吸引并且朝著帶電量較大的個(gè)體方向移動(dòng)，在引力的不斷作用下，整個(gè)種群逐漸向電量較大的個(gè)體方向逼近，最終搜索到問題的最優(yōu)解。個(gè)體運(yùn)動(dòng)遵循牛頓第二定律。牛頓第二定律，物體的加速跟它所受的合力成正比，跟它的質(zhì)量成反比。如式(2)。

(2)

其中，a表示加速度;F表示粒子間的合力;m表示粒子的質(zhì)量。

(3)

(4)

其中，K0和α為初始參數(shù)值;iter為當(dāng)前迭代數(shù);maxiter為最大迭代次數(shù)。

在AEFA算法中粒子的電量是根據(jù)函數(shù)適應(yīng)度值計(jì)算出來的，粒子的電量越大，它所在位置代表的解越優(yōu)。一個(gè)個(gè)體i的電量可以定義為式(5)、式(6)。

(5)

(6)

其中，fitpi(t)表示在第t次迭代;第i個(gè)個(gè)體歷史最優(yōu)適應(yīng)度值;Qi(t)表示在第t次迭代時(shí)第i個(gè)個(gè)體的帶電量;best(t)和worst(t)分別表示在第t次迭代時(shí)所有粒子中最優(yōu)的適應(yīng)度值和最差的適應(yīng)度值。對(duì)于最大化問題best(t)和worst(t)定義如式(7)、式(8)。

best(t)=max(fitj(t)),j∈(1,2,…,N)

(7)

worst(t)=min(fitj(t)),j∈(1,2,…,N)

(8)

對(duì)于最小化問題best(t)和worst(t)定義如式(9)、式(10)。

best(t)=min(fitj(t)),j∈(1,2,…,N)

(9)

worst(t)=max(fitj(t)),j∈(1,2,…,N)

(10)

在第d維空間中，粒子i所受的合力為式(11)。

(11)

其中，rand()表示在[0,1]之間服從均勻分布的一個(gè)隨機(jī)變量。

粒子i在d維空間中所具有的加速度定義為式(12)。

(12)

粒子的位置和速度更新式為式(13)、式(14)。

(13)

(14)

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

3 通過混沌映射計(jì)算引力常數(shù)

為了平衡AEFA算法的探索和開采能力，在庫侖常數(shù)的生成過程中引入Singer[10]混沌映射來對(duì)引力常數(shù)進(jìn)行擾動(dòng)。使得粒子有充足的時(shí)間進(jìn)行勘探操作，擴(kuò)大搜索新解的范圍，減緩遞減的速度能夠較好地平衡算法的勘探和開采能力。Singer混沌映射表示為式(15)。

(15)

其中，映射范圍為(0,1)。

進(jìn)行歸一化處理,將x(t+1)從區(qū)間[0,1]映射到區(qū)間[0,N(t)],為式(16)、式(17)。

(16)

(17)

其中，max和min分別表示自適應(yīng)間隔的最大值和最小值，本實(shí)驗(yàn)中分別設(shè)為max=20,min=1E-10。iteration表示當(dāng)前迭代數(shù)，max iteration表示最大迭代數(shù)。

改進(jìn)后的庫侖常數(shù)表示為式(18)。

(18)

改進(jìn)前庫侖常數(shù)和改進(jìn)后的庫侖常數(shù)的遞減曲線分別如圖1、圖2所示。

圖1 改進(jìn)前庫侖常數(shù)遞減曲線

圖2 改進(jìn)前庫侖常數(shù)遞減曲線

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

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

為驗(yàn)證改進(jìn)后算法(IAEFA)的性能，將改進(jìn)后的算法與原始AEFA算法進(jìn)行對(duì)比，實(shí)驗(yàn)在6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)[11]上進(jìn)行，函數(shù)定義如表1所示。

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

表中函數(shù)F1-F4是單目標(biāo)簡(jiǎn)單函數(shù),函數(shù)F5也稱香蕉函數(shù)是比較復(fù)雜的函數(shù)，其全局最小值位于山谷中，而山谷又比較平緩，所以要找到最小值比較困難。

兩個(gè)算法采用相同的群體規(guī)模N=50，問題的維度D=30，最大迭代次數(shù) max iter=1 000,為了驗(yàn)證算法的有效性，每個(gè)函數(shù)獨(dú)立運(yùn)行20次取兩個(gè)算法最優(yōu)值的平均值和方差來進(jìn)行對(duì)比，其中最優(yōu)值的平均值表示解的精度，方差表示解的穩(wěn)定性，兩種算法在6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)上的最優(yōu)值的平均值和方差如表2所示。

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

通過表2，可以看出使用改進(jìn)后的引力常數(shù)，算法的精度和穩(wěn)定性都有較大的提高。

兩種算法的收斂曲線如圖3所示。

圖3 基準(zhǔn)函數(shù)收斂曲線

由圖3可以看出改進(jìn)后的算法算法的收斂速度明顯較快，并且改進(jìn)后的算法在函數(shù)6上，找到了最優(yōu)值。

5 總結(jié)

本文首先介紹了人工電場(chǎng)搜索算法的原理，在原始AEFA算法的基礎(chǔ)上通過對(duì)引力常數(shù)K進(jìn)行改進(jìn)，改進(jìn)后的人工電場(chǎng)算法，延長(zhǎng)了算法探索的過程，擴(kuò)大了搜索范圍，提高了算法尋優(yōu)的精度。通過6個(gè)基本的測(cè)試函數(shù)來對(duì)改進(jìn)后的算法進(jìn)行性能測(cè)試，通過與原始AEFA算法相對(duì)比無論是求解精度還是收斂速度都有提高，這表明了改進(jìn)后的算法具有較好的性能。