国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

融合模擬退火和自適應的天牛須搜索算法*

2019-09-04 05:41周田江伏云發(fā)
通信技術(shù) 2019年7期
關(guān)鍵詞:模擬退火天牛極值

周田江,錢 謙,伏云發(fā)

(昆明理工大學 信息工程與自動化學院 云南省計算機技術(shù)應用重點實驗室,云南 昆明 650500)

0 引 言

在計算機研究領(lǐng)域,人們利用生物的自主行為或某些自然現(xiàn)象,模擬出一系列智能算法來解決最優(yōu)化問題,如遺傳算法[1]、模擬退火算法[2]等。遺傳算法是一種模擬生物進化規(guī)律的算法,模擬退火算法是來源于對固體高溫退火過程的模擬。這些算法一經(jīng)提出就被應用于許多工程領(lǐng)域[3-4]。

天牛須搜索算法[5](Beetle Antennae Search Algorithm,BAS)是于2017年由Jiang提出的一種新穎的生物啟發(fā)智能優(yōu)化算法,其思想源于對天牛覓食行為的模擬。BAS算法具有參數(shù)少、易于實現(xiàn)等優(yōu)點,并且算法計算過程簡單,通用且魯棒性強,較少的受到初始條件約束,可用于求解復雜的非線性優(yōu)化問題。該算法被提出后,就被應用于多個領(lǐng)域。文獻[6]將BAS算法與反向傳播(Back Propagation,BP)神經(jīng)網(wǎng)絡相結(jié)合應用于風暴潮災害損失預測。陳婷婷等[7]提出基于天牛須搜索的粒子群優(yōu)化算法,并將其應用于投資組合模型中。鄒東堯等[8]在基于接收信號的強度(Received Signal Strength Indicator,RSSI)測距的基礎(chǔ)上,將BAS算法應用到室內(nèi)定位中,有效的提高了定位的精度。Wang J等[9]對BAS算法進行了深入研究,提出了天牛群搜索算法(Beetle Swarm Antennae Search Algorithm,BSAS)。文獻[10]將混沌序列引入天牛群算法,提出了一種帶有群體學習與競技的群智能優(yōu)化算法。

本文作者在大量實驗研究中,發(fā)現(xiàn)在多維函數(shù)優(yōu)化問題中(例如維度大于4),BAS算法收斂速度慢、尋優(yōu)精度低,單獨利用單個天牛的搜索方法大大增加了算法陷入局部極值的可能。針對這一問題,本文提出了融合模擬退火和自適應的天牛須搜索算法(Simulated Annealing and Adaptive Beetle Antennae Search Algorithm,SABAS)。該算法將天牛須的感知與固體退火過程相結(jié)合,有效的避免了基本BAS易陷入局部最優(yōu)的問題。同時,引入自適應因子,加快了算法的收斂速度。多維函數(shù)優(yōu)化仿真結(jié)果表明,改進的天牛須搜索算法具有更好的尋優(yōu)能力。

1 BAS算法基本原理

天牛須搜索[11](BAS)算法是模擬天牛覓食行為的智能優(yōu)化算法。當天牛覓食時會利用左右觸須來感知食物的氣味強度,如果左邊觸須收到的氣味強度大,它下一步就往氣味強度大的左邊飛,否則往右邊飛。BAS算法中天牛的當前位置即為所求解問題的一個可行解,食物的氣味強度即為適應度函數(shù)。本文以多維函數(shù)優(yōu)化為例求解最優(yōu)值(最小值),建模步驟如下:

(1)假設天牛個體在k維解空間中的位置為X0=(x1,x2,…,xk);

(2)創(chuàng)建天牛左右須空間坐標:

式中,t是算法循環(huán)次數(shù);d是天牛質(zhì)心與觸須間的距離;b是隨機單位向量,表示天牛在空間中的朝向,取右須指向左須的方向為天牛的朝向。

(3)更新天牛的下一步位置:

式中,f(x)是x的適應度值;St表示在第t次迭代時的步長;sign()是符號函數(shù)。在實際研究中,Jiang[5]提出St=α·St-1,α為步長因子,一般設為0.95,該步長因子按比例減小搜索步長,可以有效提高算法的尋優(yōu)性能和收斂速度。

2 SABAS算法

2.1 基于模擬退火的尋優(yōu)

模擬退火[12](Simulated Annealing Algorithm,SA)算法是一種模擬物理中固體物質(zhì)的退火過程的智能算法,該算法具有能找到全局最優(yōu)解且收斂速度快的優(yōu)點,其在搜索過程中具有概率突跳的特征,這使得該算法可以有效地避免陷入局部極值。具體來說,SA算法在搜索過程中除了接受好的解,同時還可以以一定的概率接受差的解,而此概率受到溫度參數(shù)的影響,其值的大小隨溫度的下降而逐漸減小,這就使得算法在前期有較大概率跳出局部極值,而在后期又能具有較高的收斂速度。SA算法通常以Metropolis準則[13]作為是否接受新解的依據(jù),準則如下:

計算增量ΔT=f(xt+1)-f(xt);

若ΔT<0,則接受xt+1為新解;

否則計算p=exp[-ΔT/T],以概率p接受xt+1為新解。式中,exp()是以自然常數(shù)e為底的指數(shù)函數(shù);T為當前溫度。由于T隨迭代次數(shù)遞增而減小,故p值也隨之減小。

在多維空間里,BAS算法中的天牛個體只在當前位置感知下一步位置的方向,則很大程度會陷入局部極值[10]。針對BAS算法的這一缺點,本文把模擬退火算法的退火過程融入到BAS算法中,使得BAS算法有一定概率接受較差解,有效地避免了BAS在多維度情況下易陷入局部最優(yōu)的問題。

在改進的算法中,存在兩層循環(huán)。外循環(huán)中利用當前溫度T控制基本BAS中的天牛初始步長S,在內(nèi)循環(huán)中使用Metropolis準則更新天牛下一步位置,溫度T隨迭代次數(shù)遞增而減小,故天牛的步長也隨之減小以達到收斂。

通過對改進后的算法進行實驗研究,發(fā)現(xiàn)在天牛搜索過程中,當天牛的下一步位置比當前位置好時,天牛移動到下一步位置;否則,如果下一步位置比當前位置差,天牛會以概率判斷是否進行移動,且通過溫度T來控制此概率。這樣天牛不會進行盲目的移動,而是通過判斷后再移動,使得天牛有概率跳出局部極值。并且天牛的步長S同樣被溫度T控制,在外循環(huán)過程中,天牛的步長隨退溫操作而逐漸減小,從而更快的搜索到最優(yōu)位置。

2.2 自適應因子

在BAS算法[9]中,參數(shù)步長因子α是控制算法收斂快慢的關(guān)鍵,步長大小與因子α息息相關(guān)。具體原因如下:

(1)如果步長衰減得足夠緩慢,全局搜索能力越強,但與此相對的是收斂速度太慢;

(2)如果步長衰減得過快,很可能得不到全局最優(yōu)解。

步長因子實現(xiàn)對算法收斂速度的控制,步長因子越大(趨于1),收斂速度越慢,但全局搜索能力強;反之因子越?。ㄚ呌?)收斂速度越快,但容易陷入局部極值。然而,基本BAS中的步長因子在尋優(yōu)過程中是固定不變的,為了讓算法獲得更好的尋優(yōu)能力,本文提出動態(tài)改變步長因子的改進方法。具體來說,在尋優(yōu)前期,為了擴大在解空間整體的搜索范圍,加快尋優(yōu)速度,應該采用較大的步長因子;在尋優(yōu)后期,搜索解趨于穩(wěn)定,為了使解的精度更高,應該減小步長因子。另外,初始步長因子越小,越容易陷入局部極值,所以應給與較高的初始值,如0.95。

基于上述考慮,設置如下調(diào)節(jié)機制:

式中,fi是當前適應度值,fmin是歷史最優(yōu)適應度值,i是當前迭代次數(shù),n是迭代總次數(shù),α是默認步長因子(一般為0.95),β是當前步長因子。式中表明,當當前適應度值小于歷史最優(yōu)適應度值時,表明目前尋優(yōu)性能良好,此時保持步長因子默認值,用以保證做到全局搜索;反之,則認為尋優(yōu)性能不佳,減小步長因子以加快收斂速度,與此同時隨著迭代次數(shù)的遞增,最小適應度值趨于穩(wěn)定,應使步長因子的減幅擴大。

2.3 SABAS算法步驟

步驟1:初始化天牛的位置X,溫度T,步長因子α,迭代次數(shù)N,退火循環(huán)次數(shù)L;

步驟2:設置天牛的步長S=T;

步驟3:根據(jù)式(1)和式(2)得到天牛下一步位置X′;

步驟4:根據(jù)Metropolis準則更新下一步位置X;

步驟5:更新步長S=α*S;

步驟6:判斷是否達到退火循環(huán)次數(shù)L,如果滿足執(zhí)行步驟7,否則返回步驟3;

步驟7:按式(3)更新自適應因子β;

步驟8:退溫操作T=β*T;

步驟9:判斷是否達到迭代次數(shù)N,如果滿足輸出當前天牛的位置作為最優(yōu)解,否則返回步驟2。

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

3.1 測試函數(shù)

為了驗證 SABAS 算法的性能,對6個具有代表性的基準測試函數(shù)[14-16]進行仿真實驗,并將測試結(jié)果與BAS、BSAS和SA算法進行比較,BSAS算法的具體實現(xiàn)詳見文獻[9]。表1給出了6個基準測試函數(shù)的名稱、函數(shù)表達式、解搜索空間范圍和最小值。其中,D是變量的維數(shù),F(xiàn)1和F2是單峰值函數(shù),F(xiàn)3-F6為多峰函數(shù)。

表1 測試函數(shù)

3.2 測試方案

實驗采用Python 3.6.5進行仿真實驗。四種算法的實驗參數(shù)為:設置每個算法的最大迭代次數(shù)N=200,在SABAS中,退火循環(huán)次數(shù)L=100,初始溫度T=200,自適應因子α=0.95,算法中計算適應度函數(shù)的次數(shù)(即尋優(yōu)次數(shù))為200*100次;在BAS中,初始步長S=200,步長因子α=0.95,由于BAS中只有單個個體且無退火循環(huán)過程,為了客觀地與其它算法進行對比,測試中BAS并行運行100次然后取最佳結(jié)果,因此整個算法過程尋優(yōu)的總次數(shù)也為200*100次;在BSAS中,種群數(shù)P=100,初始步長S=200,步長因子α=0.95,由于包含了復數(shù)個天牛個體,算法的尋優(yōu)總次數(shù)同樣為200*100次;在SA中,退火循環(huán)次數(shù)L=100,初始溫度T=200,退火因子α=0.95,算法的尋優(yōu)總次數(shù)為200*100次。為了確保評價的公平性及客觀性,在測試中,四種算法獨立運行50次,取實驗結(jié)果的平均值進行比較。此外,本文采用平均最優(yōu)解(Average Optimal Solution,AOS)和平均收斂到最優(yōu)解代數(shù)(Average Optimal Iteration,AOI)這兩個指標來反應算法的性能。

表2 性能參數(shù)對比

從表2中的數(shù)據(jù)對比可以看出,SABAS算法相較于基本BAS和BSAS算法在尋優(yōu)結(jié)果上有顯著優(yōu)勢,在收斂速度上也有明顯提升,特別是對F4函數(shù)的優(yōu)化,其它三種算法都陷入了局部極值,只有SABAS算法跳出了局部極值。實驗結(jié)果表明,BAS算法雖然具有一定的全局尋優(yōu)能力,但該算法不容易跳出局部極值,而SABAS算法的模擬退火過程使算法可以以一定概率跳出局部極值,并且SABAS算法的自適應因子機制使算法具有更高的收斂性能。

為了更直觀地反應算法的性能,各函數(shù)4種算法收斂曲線如圖1所示。橫軸表示算法的迭代次數(shù),縱軸表示尋優(yōu)的目標函數(shù)值。其中BAS算法的目標函數(shù)值是100次并行運行中每次迭代的最優(yōu)值。由于測試函數(shù)F2初始值較大,不利于直觀反應算法的性能,因此設置了目標值的上限。SABAS算法在6種測試函數(shù)中都呈現(xiàn)平穩(wěn)快速下降的趨勢,體現(xiàn)了該算法的穩(wěn)定性,同時也表明了自適應因子在一定程度上加快了該算法的收斂速度。而BAS、BSAS和SA算法在函數(shù)F4、F6的優(yōu)化中很難達到SABAS在相同條件下所能達到的最優(yōu)解。在對F2、F3函數(shù)的優(yōu)化中4種算法都沒有尋找到最優(yōu)解,但SABAS相較于其它3個算法還是有著明顯的優(yōu)勢。因此,SABAS算法的收斂性能以及尋優(yōu)能力都優(yōu)于其它3個算法。

4 結(jié) 語

天牛須搜索算法是一種新型的生物啟發(fā)式智能算法,基本BAS算法在多維度條件下存在收斂速度慢、精度低和容易陷入局部最優(yōu)等缺陷。針對BAS的不足,本文提出了把模擬退火算法的退火過程和自適應因子融入到天牛須搜索算法中的混合算法(SABAS)。該算法利用天牛須的感知與固體退火過程相結(jié)合,有效的避免了基本BAS易陷入局部最優(yōu)的問題。同時,引入自適應因子,加快了算法的收斂速度。最后,通過仿真實驗表明,SABAS算法在多維度函數(shù)尋優(yōu)中有較好的尋優(yōu)能力。

猜你喜歡
模擬退火天牛極值
結(jié)合模擬退火和多分配策略的密度峰值聚類算法
極值(最值)中的分類討論
極值點帶你去“漂移”
天牛到底有多牛
極值點偏移攔路,三法可取
極值點偏移問題的解法
基于遺傳模擬退火法的大地電磁非線性反演研究
黑黃花天牛
巨型昆蟲——天牛
改進模擬退火算法在TSP中的應用
恩平市| 沾化县| 布尔津县| 金华市| 滨海县| 曲松县| 建瓯市| 阿合奇县| 安义县| 云安县| 营口市| 山西省| 威海市| 镇远县| 沙雅县| 元江| 昌邑市| 马鞍山市| 西平县| 武陟县| 京山县| 洛宁县| 安阳县| 原阳县| 鄂尔多斯市| 安福县| 文水县| 临夏县| 永新县| 喀什市| 会昌县| 泸定县| 大庆市| 水城县| 介休市| 岳西县| 灌阳县| 蓝山县| 北碚区| 沂南县| 闻喜县|