李 偉,孫亞峰,黃 穎,顏雪松
(1.江西理工大學 信息工程學院,江西 贛州 341000;2.贛南師范大學 數(shù)學與計算機科學學院,江西 贛州 341000;3.中國地質(zhì)大學(武漢) 計算機學院,湖北 武漢 430740)
受生物群體性智能行為啟發(fā)的算法稱為群智能優(yōu)化算法。近年來,群智能優(yōu)化算法在理論研究和實際應用方面取得了長足的進展[1]。差分進化(Differential Evolution,DE)算法于1996年提出[2],屬于經(jīng)典的群智能優(yōu)化算法,具有結(jié)構(gòu)簡單、求解精度高、收斂速度快的特點。DE算法是解決復雜優(yōu)化問題的有效技術(shù)[3],目前已經(jīng)被廣泛應用于云計算[4]、并行機負荷平衡優(yōu)化[5]、物流配送[6]等多個領(lǐng)域。
雖然DE算法在實際應用中取得了不菲的成績,但隨著信息科學的高速發(fā)展,優(yōu)化問題的日益復雜,DE算法本身存在的過度依賴參數(shù)的選擇、局部搜索不充分的問題,給算法性能帶來了新的挑戰(zhàn)。為了應對這些挑戰(zhàn),很多學者從多個方面提出了DE算法的改進版本以提升性能。例如:ZHANG等[7]提出的基于外部存檔的自適應差分進化JADE算法為所有個體設(shè)置參數(shù),記錄優(yōu)秀個體集的參數(shù)值,利用優(yōu)秀個體的參數(shù)指導下一代個體的參數(shù)選擇,此外,JADE還設(shè)計了增強局部搜索的變異策略,以加強種群多樣性和收斂性能。LIN等[8]從當前進化種群和優(yōu)勢種群中選擇兩個父個體以提供正確的有希望的進化方向,根據(jù)個體的進化過程和后代成功率自適應改變交叉率和縮放因子。QIN等[9]提出的自適應差分進化算法(Self-adaptive DE,SaDE)通過經(jīng)驗學習對試驗向量的生成策略和控制參數(shù)值進行自適應,為搜索過程的不同階段確定更合適的參數(shù)組合。ORTIZ等[10]通過設(shè)計變異算子解決局部極小點的搜索停滯問題,并在此基礎(chǔ)上簡化了控制參數(shù)的選擇。MALLIPEDDI等[11]針對進化算法的性能依賴變異策略、交叉策略和相關(guān)控制參數(shù)選擇的問題,提出一種變異策略、交叉策略、控制參數(shù)協(xié)同的差分進化算法(Ensemble of mutation and crossover Strategies and Parameters in DE,EPSDE),在EPSDE中,不同的變異、交叉策略以及每個控制參數(shù)在整個進化過程中共存,并競爭產(chǎn)生后代。BREST等[12]針對DE算法控制參數(shù)設(shè)置不當?shù)膯栴},提出一種自適應控制參數(shù)設(shè)置方法。適應度景觀特征從多個角度反映了優(yōu)化問題的最優(yōu)解分布、數(shù)量和局部單峰拓撲,LI等[13]將適應度景觀與DE算法結(jié)合,對適應度距離相關(guān)信息進行定量分析,評價問題的難度,其提出的算法降低了陷入局部最優(yōu)的風險,提高了求解精度和收斂性能。
DE算法已經(jīng)被證明具有強大的全局尋優(yōu)能力[14],但其局部搜索能力仍需加強,因此一些學者致力于增強DE算法的局部搜索能力,拓撲結(jié)構(gòu)與DE算法結(jié)合是一種有效的方法。DORRONSORO等[15]分析了使用多種不同種群拓撲的變異策略,提出了13種與拓撲結(jié)合的DE算法,實驗結(jié)果表明13種改進的DE算法都具有高度的競爭力。LIAO等[16]采用環(huán)型拓撲構(gòu)建鄰域,將方向信息與鄰域信息引入到變異算子中,指導算法的搜索。NOMAN等[17]研究了種群分布的影響,將元胞拓撲結(jié)合到DE算法中,并采用鄰域的緊湊結(jié)構(gòu),從鄰域中選擇父代個體進行進化操作。CAI等[18]提出一種基于鄰域和方向信息的DE算法(Neighborhood and Direction information based DE,NDi-DE),該算法利用鄰近個體的信息挖掘最小的鄰域并加速收斂,使用方向信息防止個體進入不希望的區(qū)域,并移動到有希望的區(qū)域,可以在勘探和開發(fā)之間取得良好的平衡。李學強等[19]使用基于鄰域差分和協(xié)方差信息的進化算法來處理復雜的單目標優(yōu)化問題。DAS[20]提出兩種鄰域模型:局部鄰域模型和全局變異模型,局部鄰域模型的每個向量都在鄰域中尋找,全局變異模型則引入全局最優(yōu)個體參與變異。
此外,還有一些學者圍繞特定類型的問題改進DE算法。WANG等[21]開發(fā)了新的變異算子和交叉算子,并提出一種混合離散差分進化算法求解阻塞式流水車間調(diào)度問題。龔文引等[22]使用差分進化算法求解能量分配優(yōu)化問題,該問題是是無線傳感器網(wǎng)絡(luò)設(shè)計的核心問題之一。SHAN等[23]為了在雷達與通信系統(tǒng)共存的需求迅速增長的情況下緩解頻譜資源緊張的局面,提出一種基于差分進化算法的雷達—通信聯(lián)合系統(tǒng)時間調(diào)制陣列邊帶抑制方法,并推導了積分信號的形式。CHEN等[24]針對多峰優(yōu)化問題定位峰的位置數(shù)量和求解精度不足的問題,提出一種基于分布式個體多峰框架和分布式個體差分進化算法,多峰框架的每個個體使用自適應調(diào)整策略控制虛擬種群來充分探索搜索空間以定位峰值,顯著提高了解的精度。
雖然DE算法展現(xiàn)出了強大的全局尋優(yōu)能力,但其局部搜索能力不能與之匹配,而且目前許多改進版本只針對某一種特定類型的問題,不利于DE算法的通用性。針對這些問題,本文提出一種基于容忍度的網(wǎng)絡(luò)拓撲自適應DE算法(Tolerance-based Adaptive Differential Evolution algorithm with Network topology, TNADE)。與其他DE算法的改進版本相比,TNADE算法的主要工作體現(xiàn)在3個方面:
(1)邊界反向映射初始化策略使種群在搜索空間內(nèi)分布的均勻性最大化,有利于擴大算法搜索范圍;
(2)依據(jù)個體的適應度值構(gòu)建最近鄰耦合網(wǎng)絡(luò)拓撲和小世界網(wǎng)絡(luò)拓撲,從拓撲中選擇節(jié)點構(gòu)成個體的鄰域,從而進行變異;
(3)基于容忍度的拓撲選擇機制為個體選擇合適的拓撲,降低個體陷入局部最優(yōu)的風險。
在TNADE算法中,邊界反向映射初始化策略使初始種群在解空間內(nèi)的分布更加均勻,參與變異的個體從鄰域中選擇,而鄰域則依據(jù)基于容忍度的拓撲選擇機制從最近鄰耦合網(wǎng)絡(luò)拓撲或者小世界網(wǎng)絡(luò)拓撲中構(gòu)建。實驗結(jié)果表明,這些策略可以增強DE算法的局部搜索能力,收斂性能也有一定提升。
(1)
式中:rand為[0,1]內(nèi)的均勻分布隨機數(shù);Lj和Uj分別表示搜索空間的下界和上界。初始化種群之后,DE算法進行進化操作循環(huán)。
DE/rand/1:
vi=xr1,G+F·(xr2,G-xr3,G);
(2)
DE/best/1:
vi=xbest,G+F·(xr1,G-xr2,G)。
(3)
式中:xbest,G表示第G代種群中的最優(yōu)個體;r1,r2,r3,r4,r5∈[1,NP]且r1≠r2≠r3≠r4≠r5≠i;F是縮放因子,滿足0 (4) 選擇操作使用錦標賽選擇機制從xi和ui中選擇出較好的個體進入下一代,選擇機制如下: (5) 選擇操作之后,算法判斷是否達到終止條件,若達到,則終止算法,否則返回變異操作。 復雜網(wǎng)絡(luò)的提出為物理、生物、化學和計算機科學等領(lǐng)域的研究提供了新的方法[25]。最近鄰耦合網(wǎng)絡(luò)是一種常見的規(guī)則網(wǎng)絡(luò),度分布是以K為中心的δ函數(shù),一個總節(jié)點數(shù)為N,網(wǎng)絡(luò)中的每個節(jié)點之和它左右各K/2個鄰居節(jié)點相連(K為偶數(shù))構(gòu)成的最近鄰耦合網(wǎng)絡(luò)如圖1a所示。 WATTS等[26]在1998年首次從數(shù)學上定義了小世界的概念。小世界網(wǎng)絡(luò)的拓撲結(jié)構(gòu)如圖1b所示,與最近耦合網(wǎng)絡(luò)的不同在于當N個節(jié)點構(gòu)成最近鄰耦合網(wǎng)絡(luò)后,以概率p隨機地重新連接網(wǎng)絡(luò)中的每一條邊,而且任意兩個不同節(jié)點之間至多只有一條邊,且每個節(jié)點不能與自身重連[27]。當網(wǎng)絡(luò)節(jié)點數(shù)N遠大于K,保證了網(wǎng)絡(luò)具有稀疏性,且網(wǎng)絡(luò)具有較高的聚類系數(shù)。而隨機化重連過程減小了網(wǎng)絡(luò)的平均路徑長度,使網(wǎng)絡(luò)模型具有小世界特性。p的值越大,小世界網(wǎng)絡(luò)越趨向于隨機網(wǎng)絡(luò);而p的.值越小,則越趨向于最近鄰耦合網(wǎng)絡(luò)。理論上,對最近鄰耦合網(wǎng)絡(luò)的邊以一定概率隨機重連可以得到小世界網(wǎng)絡(luò),為了減少算法運行時間,本文同樣采用這種方式。 本章詳細介紹基于容忍度的網(wǎng)絡(luò)拓撲自適應差分進化算法,所提算法包括3個策略:①邊界反向映射初始化策略拓寬初始種群的分布范圍以使算法充分搜索;②基于容忍度的拓撲選擇機制為種群選擇有希望的網(wǎng)絡(luò)拓撲,以加速收斂;③基于網(wǎng)絡(luò)拓撲的鄰域變異限制參與變異的個體,以增強局部搜索能力。詳細闡述本文提出的3種策略與算法的流程。 一般而言,群智能優(yōu)化算法的種群通過服從均勻分布的隨機數(shù)初始化,但一些學者的研究表明改進初始化過程有助于提高算法的性能。關(guān)于初始化的改進可以分為三類:第一類是收縮搜索空間以提升收斂速度;第二類是劃分種群以并行初始化子種群;第三類是自適應地調(diào)整種群[14]?;诜聪?qū)W習的策略被廣泛使用于種群初始化[28],其目的是收縮搜索空間,而本文提出的邊界反向映射初始化策略的目的是使種群盡量分布均勻,使算法盡可能充分搜索。對于一個均勻隨機初始化的個體i,邊界反向映射初始化操作如下: (6) 其中:Uj和Lj分別表示第j維搜索空間的上界和下界,PUj和PLj分別代表種群第j維的最大值和最小值,rand為0~1之間的隨機數(shù)。式中第一個等式實際上是采用min-max數(shù)據(jù)標準化方法將個體的第j維的值映射到搜索空間中,而第二個等式是將映射后的值在搜索空間內(nèi)進行翻轉(zhuǎn)。整體上,邊界反向映射初始化策略依次執(zhí)行如下3步:①對原始個體進行min-max標準化,使其映射到[0,1]內(nèi);②將min-max標準化后的個體映射到搜索空間內(nèi);③將②得到的個體隨機在搜索空間內(nèi)進行反向映射。如圖2所示,初始種群可能會存在在某個維度上的分布及其不均勻的情況,在經(jīng)過邊界反向映射初始化策略之后,種群第j維的邊界被拉伸到搜索空間的邊界,從而充分搜索的目的。 此外,為了驗證使用邊界反向映射初始化策略得到的種群的分布是否均勻,本文以所有個體到最優(yōu)個體的歐氏距離之和SD表示種群的分散程度,SD表示為: (7) 式中:SD越大,則種群越分散,越有利于充分搜索。由式(7)得到的實驗結(jié)果在第4.1節(jié)展示。實驗表明該策略在保持種群多樣性方面具有較大優(yōu)勢。 TNADE算法構(gòu)建了兩種網(wǎng)絡(luò)拓撲,拓撲的選擇直接影響算法的性能。為了第i+1代種群較第i代種群的提升效果盡可能顯著,本文提出一種基于容忍度的拓撲選擇機制,其流程描述如下。 算法1基于容忍度的拓撲選擇機制。 輸入:局部計數(shù)器TL,全局計數(shù)器TG,最大局部容忍度MTL,最大全局容忍度MTG,當前代個體選擇的網(wǎng)絡(luò)拓撲標記NTG,當前代和子代種群的適應度valP,valO,個體計數(shù)器i,種群規(guī)模NP。 步驟1若i=NP,運行步驟6,否則運行步驟2~步驟5; 步驟2若valOi>valPi,則TLi和TGi自加1,否則TLi和TGi置為0; 步驟5i=i+1; 步驟6NTG+1=NTG; 輸出:NTG+1。 TNADE算法根據(jù)適應度值對個體排序,構(gòu)建最近鄰耦合網(wǎng)絡(luò)拓撲和小世界網(wǎng)絡(luò)拓撲。小世界網(wǎng)絡(luò)拓撲是在最近鄰耦合網(wǎng)絡(luò)的基礎(chǔ)上,以0.5的邊重連概率對邊隨機重連所得,如圖3所示,TNADE算法采用DE/best/1變異方式,但參與變異的個體均來自鄰域,因此小世界網(wǎng)絡(luò)中每個節(jié)點的度必須不小于3。由此,本文在構(gòu)建完成小世界網(wǎng)絡(luò)后,還需要對小世界網(wǎng)絡(luò)中的節(jié)點進行補度,具體操作是:若節(jié)點的度小于3,則以該節(jié)點為起點,增加一條不重復的邊,邊的終點隨機選擇。 算法首先使用邊界反向映射策略初始化種群,然后構(gòu)建最近鄰耦合網(wǎng)絡(luò),對最近鄰耦合網(wǎng)絡(luò)隨機重連、補度得到小世界網(wǎng)絡(luò),依據(jù)基于容忍度的拓撲選擇機制選擇出每個個體的鄰域,從鄰域中選擇出xbest、xr1和xr2進行變異,最后執(zhí)行交叉和選擇操作。TNADE算法的流程如算法2所示。 算法2基于容忍度的網(wǎng)絡(luò)拓撲自適應差分進化算法。 輸入:縮放因子F,交叉率CR,適應度函數(shù)f,種群規(guī)模NP,問題維度D,最大函數(shù)評估測試MFES。 步驟1邊界反向映射初始化策略初始化種群; 步驟2計算種群適應度; 步驟3如果不滿足算法終止條件,執(zhí)行步驟4~步驟11,如果滿足則終止算法; 步驟4個體按照適應度值排序; 步驟5構(gòu)造最近鄰耦合網(wǎng)絡(luò); 步驟6構(gòu)造小世界網(wǎng)絡(luò); 步驟7對小世界網(wǎng)絡(luò)進行補度; 步驟8選擇個體組建鄰域; 步驟9從鄰域中選擇個體進行變異; 步驟10執(zhí)行交叉操作; 步驟11執(zhí)行選擇操作; 輸出:最優(yōu)個體與最優(yōu)個體的適應度值。 所提算法的小世界網(wǎng)絡(luò)拓撲在最近鄰耦合網(wǎng)絡(luò)拓撲的基礎(chǔ)上構(gòu)造,所提策略僅在初始化階段和變異階段進行,使策略時間復雜度的影響最小化。 本節(jié)通過3組實驗詳細分析了算法參數(shù)的影響以及效果:①比較不同的全局容忍度值和局部容忍度值對算法的影響,確定合適的參數(shù);②比較不同的初始化策略,驗證邊界反向初始化策略的效果;③比較不同的算法,驗證所提算法的性能。 算法包含最大局部容忍度MTL和最大全局容忍度值MTG,其中MTL的確定影響個體鄰域變換的頻率,合適的MTL值對算法性能提升強度大,因此本文以最小值為10,間隔為10,最大值為100選擇10個不同的MTL值,比較不同MTL值的效果。表1列出了10種MTL值的實驗結(jié)果,實驗采取D=30,每個問題、每個MTL值均獨立運行30次。通過表1可以得出在MTL=90時,4種類型的函數(shù)均可得到最好的效果,因此本文選取的MTL的值為90。MTG確定個體何時不考慮經(jīng)驗,重新選擇網(wǎng)絡(luò)拓撲,其值的選取必須謹慎,本文選擇MTG為[100,1 000]之間間隔為100的10個值,比較不同MTG值對算法性能的影響,實驗結(jié)果如表2所示,實驗細節(jié)與MTL值的細節(jié)相同。由表2可得,TNADE在MTG取500時效果最優(yōu),在均值方面,在6個函數(shù)上的效果明顯優(yōu)于其他情況。綜上所述,本文選擇MTL=90,MTG=500。 表1 不同MTL值的TNADE算法結(jié)果 表2 不同MTG值的TNADE算法結(jié)果 為了驗證本文提出的邊界反向映射初始化策略是否提升了初始種群在搜索空間內(nèi)的分布范圍,本文將所提策略與隨機初始化方法和基于反向?qū)W習的初始化方法[28]在5個不同邊界范圍的基準測試函數(shù)上生成的初始種群進行比較,表3注明測試函數(shù)的表達式和搜索空間,其他信息可在網(wǎng)站http://www.sfu.ca/~ssurjano/optimization.html查詢。為避免初始化過程中的偶然因素對實驗的干擾,基于反向?qū)W習的初始化方法和邊界反向映射初始化策略直接對隨機初始化方法生成的種群進行操作,比較標準采用式(7)得出的分散程度SD。表4列出了3種初始化方式在維度分別為10、30、50的情況下的對比結(jié)果。 表3 基準測試函數(shù)信息 表4 初始化方法對比結(jié)果 表4的信息說明在3種維度情況下,邊界反向映射初始化得到的種群在搜索空間內(nèi)的分布范圍最廣,驗證了邊界反向映射初始化策略的有效性。同時相比于其他兩種初始化方法,維度越高,搜索空間越大,邊界反向映射初始化策略對種群分散程度的提升效果越好。 4.3.1 測試函數(shù)及參數(shù)設(shè)置 本文使用25個單目標優(yōu)化測試函數(shù),將所提算法與CoDE[29]、SaDE[9]、jDE[12]、ODE[28]進行比較,以驗證TNADE算法性能。25個測試函數(shù)分為4類:單峰函數(shù)(f1~f5)、基本多峰函數(shù)(f6~f12)、擴展函數(shù)(f13~f14)以及復合函數(shù)(f15~f25),有關(guān)測試集的詳細信息請參見網(wǎng)站https://github.com/P-N-Suganthan/CEC2005。表5列出了TNADE算法的控制參數(shù)的值,對比算法的參數(shù)設(shè)置均與原文獻相同。 表5 TNADE控制參數(shù) 4.3.2 實驗結(jié)果及分析 為避免實驗誤差,所有函數(shù)都在維度D分別為10、30和50的情況下進行測試,每個算法和每個測試函數(shù)進行30次獨立實驗,以D×10 000次函數(shù)評估(MFES)作為所有算法的終止標準。表6~表8分別展示了所有算法在3種維度上的實驗結(jié)果,表中最優(yōu)結(jié)果以粗體顯示。表9是所提算法相比于4種對比算法的Wilcoxon秩和檢驗結(jié)果,表中“+”代表所提算法優(yōu)于對比算法的函數(shù)數(shù)量,“-”代表所提算法差于對比算法的函數(shù)數(shù)量,“≈”代表效果持平的函數(shù)數(shù)量。 表6 TNADE與對比算法的最優(yōu)值、平均值及標準差比較(D=10) 表7 TNADE與對比算法的最優(yōu)值、平均值及標準差比較(D=30) 表8 TNADE與對比算法的最優(yōu)值、平均值及標準差比較(D=50) 表9 Wilcoxon秩和檢驗結(jié)果 從維度方面看,隨著維度的提高,所提算法比SaDE算法的優(yōu)勢更加明顯;相比于CoDE算法和ODE算法,TNADE算法在D=30時效果最好,D=50和D=10時效果略差,但仍然優(yōu)于對比算法;而相比于jDE算法,所提算法的優(yōu)勢逐漸下降,在D=10和D=30時處于領(lǐng)先地位,在D=50時的效果差于jDE。整體來看,TNADE算法在D=30時效果最好,D=10、D=30時排名第一,在D=50時排名第二。 從函數(shù)類型方面看,所提算法求解單峰問題的效果最好,3個指標都得到了令人滿意的效果;在基本多峰問題的效果略差;在擴展函數(shù)f13上的求解精度僅次于jDE算法,但在f14上的效果排名第一;求解復合函數(shù)的效果最差,但仍然有6個函數(shù)的最優(yōu)值指標排名第一。整體來看,所提算法求解單峰問題和基本多峰問題效果較好,雖然在復合函數(shù)上的精度略差,但從最優(yōu)值指標上看仍具有優(yōu)勢,說明所提算法具有進一步改進的潛力。 為驗證所提算法的收斂性能和穩(wěn)定性,本文給出了D=30時算法收斂性能對比和穩(wěn)定性對比結(jié)果,如圖4和圖5所示。圖5采用箱型圖的形式,使用算法獨立運行30次的結(jié)果體現(xiàn)算法穩(wěn)定性。箱型圖可以反映數(shù)據(jù)是否聚集,其矩形的上下邊分別為一組數(shù)據(jù)的上下邊緣,與矩形相連的兩條直線為數(shù)據(jù)的兩個四分位數(shù),中位數(shù)位于箱體中間,符號“+”表示數(shù)據(jù)中的異常值。在圖5中,算法對應的箱型圖的箱體越小,異常值越少,說明該算法越穩(wěn)定。 (1)收斂性能方面,圖4表明TNADE算法在大多數(shù)單峰函數(shù)和基本多峰函數(shù)上的收斂速度顯著優(yōu)于對比算法;在擴展函數(shù)上的前期收斂效果較快,后期的收斂速度介于jDE算法和SaDE算法之間;對于復合函數(shù),所提算法在大多數(shù)函數(shù)上都獲得了較快的收斂速度。 (2)從穩(wěn)定性方面來看,如圖5所示,TNADE算法依然在單峰問題上取得了最好的效果,除了在f10、f17和f25上表現(xiàn)不佳,所提算法在其他函數(shù)上的效果與對比算法差異較小。整體而言,CoDE算法與TNADE算法在穩(wěn)定性上都表現(xiàn)出了良好的性能。 綜上所述,TNADE算法在單峰函數(shù)和基本多峰函數(shù)上的效果最優(yōu),這說明算法的局部搜索能力得到了有效提升,求解擴展函數(shù)的效果處于中間位置,而對于復合函數(shù),所提算法雖然在求解精度上有所不足,但其收斂性能和穩(wěn)定性仍然優(yōu)于對比算法。 為了分析算法的總體復雜度與不同網(wǎng)絡(luò)拓撲下的復雜度,本文將所提算法分為4個版本:①TNADEv1不采用任何網(wǎng)絡(luò)拓撲,也不使用基于容忍度的拓撲選擇機制;②TNADEv2只采用最近鄰耦合網(wǎng)絡(luò)拓撲;③TNADEv3只采用小世界網(wǎng)絡(luò)拓撲;④TNADEv4采用兩種網(wǎng)絡(luò)拓撲。復雜度的計算采用IEEE國際進化計算大會的算法復雜度標準: (8) (9) AlgorithmComplexity=(T2-T1)/T1。 (10) 式中:t1i表示問題i計算10 000次所需時間;t2i表示算法在完整運行的情況下計算10 000次問題i所需時間,t2i的值越大,則算法的復雜度越高。算法的復雜度由式(10)計算得出,4個版本的TNADE算法在30維問題上的計算結(jié)果如表10所示。 表10 TNADE算法復雜度 由表10可知,隨著網(wǎng)絡(luò)拓撲的增加,算法的復雜度呈上升趨勢,由于規(guī)則網(wǎng)絡(luò)結(jié)果簡單,而小世界網(wǎng)絡(luò)結(jié)構(gòu)相對復雜,TNADEv2較TNADEv1的復雜度增幅小于TNADEv3較TNADEv2的復雜度增幅,而小世界網(wǎng)絡(luò)的構(gòu)造必須在最近鄰耦合網(wǎng)絡(luò)之后,因此TNADEv4較TNADEv3的復雜度增幅較小。總體而言,相比于基本差分進化算法,所提算法的復雜度較高。 本文提出一種基于容忍度的網(wǎng)絡(luò)拓撲自適應的差分進化算法,目的是提高DE算法的局部搜索能力和通用性。所提算法包括3個創(chuàng)新點:①提出一種邊界反向映射初始化策略,使初始種群在搜索空間內(nèi)的分布更加均勻;②構(gòu)建最近鄰耦合網(wǎng)絡(luò)和小世界網(wǎng)絡(luò)種群結(jié)構(gòu),充分利用復雜網(wǎng)絡(luò)的優(yōu)勢;③設(shè)計一種基于容忍度的拓撲選擇機制,有效提升種群迭代之間的改進率。 將所提算法與4種先進的DE改進版本在25個測試函數(shù)上進行了比較,實驗結(jié)果證明:①在初始化階段調(diào)控種群在解空間內(nèi)的分布有助于算法的搜索;②多種網(wǎng)絡(luò)拓撲與種群結(jié)構(gòu)的結(jié)合有利于調(diào)控算法的搜索方向。但TNADE算法仍然存在一些問題,如求解高維問題時求解精度不足、在復合問題上的開采性能和勘探性能不夠均衡、算法復雜度較高。下一步將繼續(xù)嘗試不同復雜網(wǎng)絡(luò)與進化算法的結(jié)合,并改進結(jié)合方式以降低算法復雜度。1.2 交叉
1.3 選擇
2 最近鄰耦合網(wǎng)絡(luò)與小世界網(wǎng)絡(luò)
3 基于容忍度的網(wǎng)絡(luò)拓撲自適應差分進化算法
3.1 邊界反向映射初始化策略
3.2 基于容忍度的拓撲選擇機制
3.3 基于網(wǎng)絡(luò)拓撲的鄰域變異
3.4 算法描述
4 實驗及分析
4.1 參數(shù)對算法性能的影響
4.2 邊界反向映射初始化性能實驗
4.3 TNADE算法性能實驗
4.4 收斂性與穩(wěn)定性分析
4.5 TNADE算法復雜度分析
5 結(jié)束語