采用混沌映射計算庫倫常數(shù)的改進人工電場算法

李曉瑜

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

0 引言

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

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

2 人工電場算法(AFEA)

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

(1)

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

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

(2)

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

(3)

(4)

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

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

(5)

(6)

其中，fitpi(t)表示在第t次迭代;第i個個體歷史最優(yōu)適應(yīng)度值;Qi(t)表示在第t次迭代時第i個個體的帶電量;best(t)和worst(t)分別表示在第t次迭代時所有粒子中最優(yōu)的適應(yīng)度值和最差的適應(yīng)度值。對于最大化問題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)

對于最小化問題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]之間服從均勻分布的一個隨機變量。

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

(12)

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

(13)

(14)

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

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

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

(15)

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

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

(16)

(17)

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

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

(18)

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

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

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

4 仿真實驗及結(jié)果分析

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

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

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

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

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

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

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

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

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

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

5 總結(jié)

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