錢崢遠，曾國蓀

1.同濟大學 計算機科學及技術系，上海 201804

2.國家高性能計算機工程技術中心 同濟分中心，上海 201804

差分進化（Differential Evolution，DE）算法通過模仿生物進化的過程在解空間內(nèi)迭代搜索最優(yōu)解，自從1997年由Storn和Price[1]提出以來，廣泛應用于解決現(xiàn)實世界中的各類優(yōu)化問題。差分進化算法作為一種競爭性的全局優(yōu)化算法，具有所需控制參數(shù)較少，實現(xiàn)簡單的優(yōu)勢。因此，差分進化算法及其改進算法常常被用于工業(yè)控制[2-3]、圖像處理[4]、電力系統(tǒng)[5-6]、多模態(tài)函數(shù)求解[7]等領域。但是差分進化算法實際應用時易出現(xiàn)早熟收斂和搜索停滯的問題，且優(yōu)化后期收斂速度慢。

針對上述問題，國內(nèi)外學者進行了大量研究，研究認為出現(xiàn)早熟收斂的主要原因是控制參數(shù)的設置與進化策略的選擇不當，使得種群過早地失去多樣性[8]。而對于搜索停滯的問題，文獻[9]認為它的發(fā)生原理還不明確，但是可以通過增加種群規(guī)模，降低其出現(xiàn)的概率。因此，差分進化算法的改進研究方向之一是對控制參數(shù)的改進，學者們提出人工設置多個控制參數(shù)數(shù)值，隨機取用以提高種群多樣性。例如Wang等[10]在CoDE算法中提出，對于每個個體從參數(shù)池中隨機選擇一組控制參數(shù)，而OXDE算法[11]則使用正交交叉概率代替?zhèn)鹘y(tǒng)概率參數(shù)。但是，這些控制參數(shù)的備選值是人工設置的，無法避免經(jīng)驗式的不穩(wěn)定性。因此，學者們提出了隨機參數(shù)設置方法和基于自適應的參數(shù)調(diào)節(jié)方式，例如Das等[12]提出讓變異概率在0.5～1.0的范圍內(nèi)隨機取值，或者在給定的時間間隔內(nèi)線性減小。Brest等[13]提出了jDE算法，通過給每個個體分配不同的變異、交叉概率，并根據(jù)兩個指定的閾值對其進行動態(tài)調(diào)整。此外，Wu等[14]提出的SACPMDE算法，Noman等[15]提出的aDE算法也是有效的參數(shù)自適應改進差分進化算法。研究方向之二是改進差分策略，例如Zhang等[16]在JADE算法中提出了一種基于外部的備份與歷史信息結(jié)合的DE/currentto-pbest/1的差分策略，在SaDE算法中則提出每次變異時，由算法從多種變異策略中自適應地選擇一種適合的策略執(zhí)行[17]。研究方向之三是針對DE算法的種群結(jié)構(gòu)進行改進，其中比較經(jīng)典的有主從模型[18]、島嶼模型[19]和元胞模型[20]等。

但是，單一地對控制參數(shù)、變異策略或者種群結(jié)構(gòu)進行改進，提升效果有限。因此，研究人員提出了綜合改進算法，例如Kushida等[19]在iDE算法中嘗試通過將種群分割成大小不等的島嶼，并給島嶼分配不同的控制參數(shù)，以便平衡全局搜索與局部搜索能力，同時通過個體遷移的方式進行島嶼間的基因交流，以便保持種群的多樣性。但是，該算法仍存在一些問題：（1）由于算法中各島嶼的控制參數(shù)都是人工確定的，對不同問題的適應能力不足，同時種群初始化的隨機性可能導致島嶼適應度情況與參數(shù)設置不匹配，影響算法穩(wěn)定性。（2）各島嶼間的移民過程中，iDE算法選取的是各島嶼上適應度最佳的個體，這樣做雖然有利于這些個體在各島嶼間擴散其基因，但在迭代后期，可能造成各島嶼上的基因趨同，種群多樣性不足導致收斂停滯的問題。（3）iDE算法的個體遷移機制，雖然能增強當前最佳島嶼的搜索能力，但是沒有考慮到增強局部搜索的位置，同時遷入適應度較差的個體也會干擾最佳島嶼的變異方向。

因此，為了提高差分進化算法的優(yōu)化精度與收斂速率，避免“早熟收斂”和“搜索停滯”等問題，本文基于傳統(tǒng)島嶼模型，研究一種精英化島嶼種群的差分進化算法（Elitist Island-based Differential Evolution，EIDE）。該算法在進化前期減緩最佳個體的基因擴散速度，保留種群的多樣性，有效避免算法出現(xiàn)“早熟收斂”問題，同時加速對解空間的全局搜索，使得個體盡快接近全局最優(yōu)解。算法在進化后期增強對適應度較高的個體周圍空間的搜索，提高算法收斂精度，控制島嶼基因流向，維護個體多樣性防止出現(xiàn)“搜索停滯”的問題。

1 傳統(tǒng)的島嶼模型差分進化算法

本文基于文獻[19]提出的島嶼模型差分進化算法（iDE）進行改進，其主要步驟包括：種群初始化及種群劃分，迭代執(zhí)行的變異、交叉、選擇、移民以及個體遷移操作，這些操作是改進算法的基礎。

1.1 種群初始化及種群劃分

iDE算法和DE算法同樣采用實數(shù)編碼方式，首先隨機生成NP個D維初始個體，對于種群中的第g代，第p個個體如公式（1）所示，其中均是一個實數(shù)，表示個體x p對應維度的數(shù)值，且取值范圍為；各維度初始化如公式（2）所示，其中和分別是被選擇個體x p的第q個維度值的上限和下限，表示一個取值范圍在[0，1]的隨機數(shù)。完成個體初始化后，iDE算法采用隨機種群劃分方式，將全種群P平均地劃分為多個子種群（島嶼）P s(s=1,2,…,K)，其中K表示島嶼數(shù)量，全種群中的NPtotal個個體則隨機地劃分到各島嶼，每個島嶼包含NPtotal/K個個體。

1.2 進化操作

1.2.1 變異操作

變異操作是由種群中多個單獨個體進行線性運算得到變異個體的過程，如公式（3）所示，其中X p(g)表示第g代的原始種群中的第p個個體，V p(g)表示第g代變異種群中的第p個個體，p1、p2、p3是原始種群里的三個個體，且p1≠p2≠p3。F是變異算子，可根據(jù)應用場景修改，F(xiàn)決定種群個體差分步長的大小。F的值較小會使得種群成員之間的差異性較小，使得算法容易出現(xiàn)局部最優(yōu)的問題；F增大可以增強算法的全局搜索能力，增大搜索到全局最優(yōu)解的概率，但會降低算法的收斂速度。

1.2.2 交叉操作

交叉操作將原始種群中個體的部分維度的值，與變異個體的對應維度的值按照某種規(guī)則進行交換，通過交換個體間某個分量以提高種群多樣性。交叉操作生成交叉?zhèn)€體，如公式（4）所示，其中，r是區(qū)間[0，1]的隨機數(shù)，t是區(qū)間[1,D]的隨機整數(shù)表示第g次迭代中，第p個交叉?zhèn)€體的第q個維度。表示第g次迭代中，第p個變異個體的第q個維度。表示第g次迭代中，原始種群中的第p個個體的第q個維度值。CR是交叉概率，且，CR越大，交叉?zhèn)€體從變異個體中獲取的值越多，更接近變異個體，全局搜索能力越強，但是收斂速度慢；反之，CR越小，其全局搜索能力就較弱，容易出現(xiàn)早熟的情況。iDE對于不同島嶼設置了不同的F算子及CR算子數(shù)值，以實現(xiàn)島嶼的分工，例如在島嶼個數(shù)為5時，文獻[19]建議F與CR設置如表1所示。

表1 iDE算法各島嶼控制參數(shù)設置Table 1 Control parameter settings of each island in iDE algorithm

1.2.3 選擇操作

iDE采用貪婪的方式來選擇進入下一代種群的個體，如公式（5）所示，其中f(x p)表示個體x p對應的目標函數(shù)值，x p(g)表示第g代種群中的第p個個體，z p(g)表示第g代的交叉種群中的第p個個體，x p(g+1)表示第g+1代種群中的第p個個體。

1.3 移民操作與個體遷移操作

iDE的移民和個體遷移周期為I，每隔I次迭代，將所有島嶼隨機地連接成一個環(huán)，如圖1（a）左半部分所示，島嶼作為環(huán)的節(jié)點，將它們以隨機的順序連接起來。而后在每個島嶼上選擇適應度值最小的N P×R（R為移民比例）個個體，按照剛才隨機確定的連接順序，以順時針的方向，從上一個島嶼移入下一個島嶼，如圖1（a）中右半部分所示。iDE的個體遷移則是計算每個島嶼在這I次迭代中最佳個體適應度的平均值，以此平均值為標準，選出最佳島嶼（最佳個體適應度均值最?。┖妥畈顛u嶼（最佳個體適應度均值最大）。將最差島嶼上的任一個體，復制到最佳島嶼上，而后將其在最差島嶼上刪除，移民及個體遷移操作如圖1（b）所示，虛線圈為最差島嶼上刪除的個體，而綠色圓為其在最佳島嶼上的復制。

圖1 iDE算法移民與個體遷移操作圖Fig.1 iDE algorithm migration and individual transfer operation diagram

2 基于精英化島嶼種群的差分進化（EIDE）算法

針對iDE算法存在的問題，本文從島嶼分類、變異策略的選擇、控制參數(shù)的自適應化、“移民”方向的控制、“個體遷移”對象的選擇等多個角度，對iDE算法進行綜合改進，使得新算法能夠自主調(diào)整局部搜索能力與全局搜索能力。在此基礎上新算法明確島嶼分工，利用精英化的思想來實現(xiàn)快速收斂到最優(yōu)解的目的，同時利用島嶼間的基因隔離實現(xiàn)在迭代過程中保持種群多樣性的目的。

2.1 自適應的精英島嶼選擇

通常，精英個體被定義為種群中適應度值較好的個體，精英化則是通過精英個體對整個種群的進化起到引導作用。精英化思想常用在遺傳、協(xié)同進化等進化算法中，取得了不錯的效果。而在島嶼模型的差分進化算法中，精英個體分散在不同的島嶼上，雖然精英個體可以對該島嶼上的其他個體進化產(chǎn)生引導作用，但在迭代初期其他個體適應度較差的情況下進行變異操作，精英個體的子代適應度值減小的概率較小，將減慢收斂速度；在迭代后期，精英個體分散也易造成該島嶼上的其他個體與精英個體過度相似，導致種群失去基因多樣性；同時由于精英個體適應度值較小，在其周圍空間搜索得到全局最優(yōu)解的概率較大。

因此，本文設計一種新的島嶼分類方法，使得不同類型的島嶼實現(xiàn)不同的功能，普通島嶼維持種群多樣性，精英島嶼將精英個體集中在小范圍并增強局部搜索以提升優(yōu)化精度與收斂速率。此外，島嶼分類是實現(xiàn)有向移民策略的基礎。為了便于敘述，本文均假設要優(yōu)化一個極小值問題的解，假設算法初始化有K個島嶼，第k個島嶼初始化有N k個個體，則對于島嶼類型的判定方式如公式（6）、（7）所示，其中fitness()表示適應度計算函數(shù)，表示第k個島嶼第n個個體，bestFitness k表示第k個島嶼的最佳適應度值，表示所有島嶼最佳適應度值的均值，typek表示第k個島嶼類型函數(shù)，其值為1代表作為精英島嶼，其值為0代表作為普通島嶼。

2.2 精英島嶼的進化操作

2.2.1 精英島嶼的變異策略

如2.1節(jié)中所述，EIDE算法將精英個體集中在精英島嶼，以期實現(xiàn)在適應度值較小的個體周圍密集搜索，增大搜索到最優(yōu)解的概率，并設計以普通島嶼維護種群多樣性。對于普通島嶼采取DE/rand/1/bin的變異策略，并設置較大的變異概率及交叉概率值以增大普通島嶼的種群多樣性。對于精英島嶼，則需要增強局部搜索能力，故本文選用文獻[14]中的一種方向增強的變異策略。其主要思想為，選擇適應度值最小的個體作為變異的基礎個體，并向著適應度值次小的個體方向進化，如公式（8）所示，對于變異時的三個隨機選擇的個體，按照適應度函數(shù)值升序排序后存儲。假設適應度值最小那個個體是，次小的是，最大的是。為了加速收斂，基礎向量選擇，并且由生成差分向量。

在精英島嶼上應用該變異策略的優(yōu)勢在于，精英島嶼上的個體變異時將會探索最佳個體的周圍空間，且探索的方向都會在的上，即對于選定的變異個體，其變異過程不再是隨機的，而是一個確定的過程。但是由于變異時所選用的個體還是在該島嶼的所有個體中隨機選取的，所以整個變異操作還是一個隨機的過程，可以保持算法搜尋全局最優(yōu)解的能力。因此，應用該變異策略可實現(xiàn)增強精英島嶼的局部搜索能力的目的。

2.2.2 控制參數(shù)自適應方法

EIDE算法設計精英島嶼的主要目的是加速尋找最優(yōu)解，但是由于差分進化算法本身的隨機性，迭代時個體適應度的變化情況無法預測，參與變異過程的個體也無法確定，因此盲目地使用增強局部搜索的控制參數(shù)，極有可能使算法陷入局部最優(yōu)。針對這個問題，EIDE算法設計通過控制參數(shù)的自適應，實現(xiàn)根據(jù)個體適應度情況，平衡其局部搜索與全局搜索能力。

精英島嶼自適應調(diào)整變異概率的方法如公式（9）所示，自適應調(diào)整交叉概率的方法如公式（10）所示，其中fbest、fmid、fworst分別是、和三個個體的適應度函數(shù)值，F(xiàn)i表示第i個個體變異時的變異概率，F(xiàn)l表示變異概率的下限，F(xiàn)u表示變異概率的上限，CRl表示交叉概率的下限，CRu表示交叉概率的上限，f i表示第i個變異個體的適應度函數(shù)值表示該島嶼所有個體的平均適應度函數(shù)值，fmin和fmax分別表示當前島嶼種群中最好和最差個體的適應度函數(shù)值。

2.3 基于精英島嶼的有向“移民”操作

傳統(tǒng)的島嶼模型，在搜索得到一個適應度較小的個體后，該個體的基因首先會在自己的島嶼內(nèi)擴散，然后會隨著“移民”過程，依次進入下一個島嶼，并在島嶼內(nèi)擴散，然后再進入下一個島嶼，這就可能導致所有島嶼基因趨同，而陷入局部最優(yōu)的情況。為了保證普通島嶼內(nèi)的基因多樣性，防止陷入局部最優(yōu)解，EIDE算法設計所有島嶼都將自己的優(yōu)質(zhì)基因輸入到精英島嶼中的最佳島嶼（適應度值最小的個體所在的島嶼），而最佳島嶼則只會將優(yōu)質(zhì)基因擴散到精英島嶼中，如圖2（a）所示，將藍色箭頭終點的個體替換為箭頭起點個體。

在EIDE算法設計的“移民”策略中，除了最佳島嶼以外的所有島嶼，用本島嶼內(nèi)最佳個體（適應度值最小的個體），替換掉最佳島嶼上任一非最佳個體，而最佳島嶼將會為每一個精英島嶼，選擇一個本次移民過程中未被替換過的個體（可能是最佳個體），用來替換掉精英島嶼上任一個體，且這個被替換個體不能是該島嶼的最佳個體。對于適應度較差的島嶼，只存在基因輸出，而不存在基因輸入，使得算法在迭代后期仍能保證種群中的基因多樣性，防止陷入局部最優(yōu)解。

2.4 精英增強的“個體遷移”操作

對于最佳個體的適應度值較大的島嶼，雖然也有可能在該島嶼上發(fā)現(xiàn)全局最優(yōu)解，但這個可能性較低，而對于最佳個體的適應度值較小的島嶼，其發(fā)現(xiàn)全局最優(yōu)解的可能性較高，因此EIDE算法增強在適應度值較小的個體周圍的搜索，并增大適應度值較大個體與其子代個體的距離，在迭代過程中加入了個體遷移的機制，即將最差島嶼（島嶼內(nèi)的最佳個體適應度值，在所有島嶼中是最大的）上的最差個體殺死，在最佳島嶼上復制一個最佳島嶼的最佳個體，如圖2（b）所示，其中黑色虛線圈表示最差島嶼上刪除的個體，黃色虛線圈表示最佳島嶼上最佳個體的復制個體，結(jié)合刪除與復制操作，即實現(xiàn)了個體由最差島嶼向最佳島嶼的遷移。

圖2 EIDE“移民”與“個體遷移”策略圖Fig.2“Migration”and“Individual Transfer”strategy diagrams of EIDE

EIDE算法每隔I次的迭代后，執(zhí)行一次“移民”和“個體遷移”的判斷，判斷內(nèi)容為最大島嶼接收的遷移個體總數(shù)，是否超過可接收的最大遷移個體數(shù)量?？山邮盏淖畲筮w移個體數(shù)量隨迭代次數(shù)遞增，如公式（11）和（12）所示，其中K表示島嶼數(shù)量，Ntotal表示個體總數(shù)，R表示個體遷移比例，Nbest表示當前最佳島嶼的個體數(shù)量，g表示當前迭代次數(shù)，G表示最大迭代上限，trans ferNum代表島嶼可接收的最大遷移個體數(shù)量，flag表示是否可遷移標志。

由于島嶼模型的并發(fā)性，各個島嶼可以并行進化。但如果“移民”和“個體遷移”發(fā)生得過于頻繁，會嚴重影響算法的可并發(fā)性，增大執(zhí)行時間，同時過于頻繁的基因交流也不利于對基因的有效搜索；如果基因交流和個體遷移發(fā)生的頻率過低，則會影響島嶼種群多樣性的擴散和搜索優(yōu)勢方向的能力，因此每隔I次迭代執(zhí)行一次判斷，可平衡島嶼模型執(zhí)行時間與優(yōu)化能力。通過可遷移數(shù)量隨著迭代次數(shù)遞增的方式，實現(xiàn)迭代初期加強全局搜索，迭代后期加強在候選最優(yōu)解周圍搜索的目的，這符合差分進化算法迭代初期最優(yōu)解方向并不明確的特點以及迭代后期加速收斂的需求。

2.5 EIDE算法描述

綜合2.1～2.4節(jié)所述，EIDE算法的步驟為，首先初始化各島嶼種群（默認初始時所有島嶼均為普通島嶼）；然后進行迭代過程，包括各個島嶼分別執(zhí)行變異操作、交叉操作、選擇操作，在分類島嶼，而后執(zhí)行“移民”“個體遷移”操作；重復迭代直至達到收斂條件或最大迭代次數(shù)，其偽代碼描述如下：

算法1一種精英化島嶼種群的差分進化算法（EIDE）

3 實驗分析

為了驗證EIDE算法的優(yōu)化與收斂能力，本文在PC機開展實驗，配置為Intel?CoreTMi7-8550U處理器和Window10操作系統(tǒng)，用Python3.6實現(xiàn)了EIDE算法和DADE、iDE、jDE、aDE算法[13，15，18，21]，并選取多個標準測試函數(shù)，分別利用上述5種差分進化算法求解每個測試函數(shù)的最小值，通過比較各個算法得到的解和實際值的誤差，判斷算法的準確度，并根據(jù)各個算法成功收斂所用的迭代次數(shù)，判斷算法的收斂速率。

3.1 EIDE算法參數(shù)設置

實驗中由于EIDE算法主要通過普通島嶼保持種群多樣性，通過精英島嶼加強候選最優(yōu)解附近的搜索，故普通島嶼變異、交叉概率設置分別為F=0.5,CR=0.9；精英島嶼變異、交叉概率上下限設置為Fl=0.1,Fu=0.4,CRl=0.1,CRu=0.6。由于EIDE算法的總時間復雜度為O(N?(N P+M)?D?T)，文獻[22]的實驗結(jié)果可發(fā)現(xiàn)多種群的改進DE算法，在種群數(shù)量較少，且子種群個體數(shù)量與標準DE種群個體數(shù)量相等時，兩者執(zhí)行時間差距較小。故保證EIDE算法的島嶼個體數(shù)量最大值≤DE算法的種群個體數(shù)量時，基本可以保證兩者運算時間相近。因此，實驗時，EIDE算法的每個島嶼種群個體數(shù)量NP設置為80個，“移民”與“個體遷移”判斷的間隔代數(shù)I設置為5代，個體遷移比例R設置為20%，而其他4種算法的種群大小則為100，由于遷移個體數(shù)最大為NP×(1+R)故而可以保證在整個迭代過程中，EIDE的最大島嶼個體數(shù)均小于其他算法的種群個體數(shù)。EIDE的島嶼個數(shù)設置為5個，普通島嶼的變異概率和交叉概率參照文獻[1]分別設置為0.5和0.9。精英島嶼的變異概率和交叉概率上下界如2.2節(jié)中所述。作為對照，DE算法的變異概率和交叉概率也分別設置為0.5和0.9。iDE、jDE、aDE、DADE、NEA/NC 5種算法的參數(shù)設置如其來源文獻[13，15，19，21，23]中所述。所有算法的最大迭代次數(shù)為3 000次，均獨立執(zhí)行30次。

3.2 基準測試函數(shù)

為了測試算法性能，本文從文獻[24-25]選取了9個標準測試函數(shù)，具體如表2所示，目標是求解它們的最小值，其中f1～f4為單峰函數(shù)，f5是有一個極值但不連續(xù)的函數(shù)，f6～f9為多峰函數(shù)，其維數(shù)均為D=30。

表2 基準測試函數(shù)Table 2 Benchmark functions

3.3 實驗結(jié)果與分析

3.3.1 算法收斂精度分析

對于5種算法在9個標準測試函數(shù)下30次獨立執(zhí)行的優(yōu)化結(jié)果的平均值和標準差如表3所示，各算法在各標準測試函數(shù)下，成功收斂的比例(SR)和多次運行下每代最佳適應度值的均值成功收斂時的最小迭代次數(shù)(MG)如表4所示。本文中認為成功收斂的條件是這次迭代的最佳適應度值與測試函數(shù)最小值誤差小于等于一個閾值R，對于測試函數(shù)f2，閾值為10-2；對于測試函數(shù)f4，閾值為10-5；對于測試函數(shù)f7，閾值為10-1；對于測試函數(shù)f8、f9，閾值為1；對于其他5個測試函數(shù)閾值為10-8。而表格中的N/A表示此算法在此測試函數(shù)上多次重復運行的適應度均值未成功收斂。

表3 各算法在不同測試函數(shù)上優(yōu)化精度對比Table 3 Precision comparison of solutions optimized by each algorithm on different test functions

表4 各算法在不同測試函數(shù)上的收斂能力對比Table 4 Comparison of convergence ability of each algorithm on different test functions

SR的計算公式如公式（13）所示，MG的計算公式如（14）所示，其中T s表示多次重復運行中成功收斂的次數(shù)；T a表示重復運行的總次數(shù)；min(A)表示集合A中的最小元素；f b(i,k)表示第i次重復運行的第k次迭代的全種群（所有島嶼）的最佳適應度值；T表示該測試函數(shù)的目標解；R表示該測試函數(shù)的成功收斂閾值。

如表3所示，EIDE算法優(yōu)化精度高。EIDE在9個測試函數(shù)中的7個上平均誤差最小，特別是在單峰函數(shù)上，在f1和f3上EIDE的優(yōu)化精度較其他算法準確1030以上。這是因為精英島嶼自適應得到的較小的變異概率和交叉概率，在迭代后期保證了收斂精度，普通島嶼較大的變異概率和交叉概率，維持著種群多樣性，在收斂后期，通過“移民”策略保證精英島嶼繼續(xù)進化。在f2上表現(xiàn)不佳的原因在于F和CR的自適應算法對于各維度權重不同的情況難以適應，因此可以看到同樣采用參數(shù)自適應方法的jDE和aDE算法表現(xiàn)也是較差的。而DEA/NC算法放棄了交叉操作，并通過模擬退火的變異操作跳出局部最優(yōu)，但單峰函數(shù)只有一個優(yōu)化方向，因此在單峰函數(shù)上結(jié)果明顯較差。在多峰函數(shù)上，EIDE算法的優(yōu)勢沒有那么明顯，主要是因為多個島嶼可能會收斂至不同極值，對最佳島嶼的進化方向形成干擾，但仍可以看出EIDE算法在4個多峰函數(shù)的3個上優(yōu)化精度最高。

3.3.2 算法收斂速度分析

如表4所示，EIDE算法穩(wěn)定，收斂成功率高。EIDE在9個測試函數(shù)中的7個上收斂成功率最高，因為普通島嶼的存在，保證了種群多樣性使得算法不易陷入局部最優(yōu)。同時，個體遷移和精英島嶼的變異策略以及參數(shù)自適應，加強了收斂結(jié)果的精度，因此收斂成功率高。在測試函數(shù)f4上，DADE、aDE、和EIDE均有較高的收斂成功率，但DADE和aDE的迭代均值均未能成功收斂，因為這兩個算法多次運行時均存在優(yōu)化結(jié)果適應度值很大的情況，影響了適應度均值。在測試函數(shù)f7上所有算法收斂成功率均小于等于30%，并非算法不收斂，而是因為本文收斂判定閾值需要對算法收斂能力做出區(qū)分，然而結(jié)合表3可以看出算法在f7上收斂精度的差異小于一個數(shù)量級，故設置的收斂判定閾值使得算法均不完全成功收斂，通過比較算法收斂成功的比例對比算法收斂能力，可見EIDE算法在測試函數(shù)f7上較其他算法收斂能力明顯更強。而對于測試函數(shù)f7、f8可以看出，各算法雖然都能到達收斂閾值，但EIDE算法所需的平均最小收斂代數(shù)較其他算法均少90代以上，說明其收斂速率較其他算法明顯更高。

圖3繪制了6種算法在4個標準測試函數(shù)下的收斂曲線，其中折線圖標題為該圖數(shù)據(jù)對應的測試函數(shù)，結(jié)合表4所示，可知EIDE算法收斂速度快。在所有算法均成功收斂的4個測試函數(shù)上，EIDE成功收斂所用的迭代次數(shù)都是最少的。且如收斂圖所示，在多個測試函數(shù)上收斂速度較其他算法明顯更快。因為精英島嶼的變異策略以及參數(shù)自適應方法加速了算法收斂，同時優(yōu)質(zhì)個體在精英島嶼上的集中，以及通過個體遷移方式增加最佳島嶼個體數(shù)量的方法，加強了當前最優(yōu)解周圍的搜索，加速了收斂。

圖3 各算法收斂過程曲線比較圖Fig.3 Comparison of convergence process curves of each algorithm

4 結(jié)束語

為了避免差分進化算法常見的早熟收斂和搜索停滯問題，同時提高精度并加速收斂，本文將精英化思想引入島嶼模型的差分進化算法中，設計了島嶼分類和“個體遷移”策略集中精英個體；通過使用方向增強的變異策略，并設計了自適應的控制參數(shù)方法，增加算法搜索精度與收斂速度；利用島嶼間有向的“移民”策略，保持種群基因多樣性，防止早熟收斂和搜索停滯問題。本文進而提出了一種基于精英化島嶼種群的差分進化算法（EIDE）。本文將該算法與5種經(jīng)典的改進差分進化算法在9個標準測試函數(shù)上進行優(yōu)化精度和收斂速度的比較實驗。實驗結(jié)果表明：EIDE算法相較于其他幾種對比算法在準確性、穩(wěn)定性、收斂速率方面具有明顯提升。但是，本文并沒有對算法的執(zhí)行時間進行詳細研究，而執(zhí)行時間一直是制約進化算法應用的一個重要問題，多種群的差分進化算法，具有高度的可并行性。因此，如何在分布式平臺上優(yōu)化EIDE算法的并行能力、加速算法執(zhí)行是下一步的研究工作。