陳偉能 楊 強,2

1(華南理工大學計算機科學與工程學院 廣州 510006)2(中山大學數(shù)據(jù)科學與計算機學院 廣州 51006)

基于概率分布的多峰演化算法

陳偉能1楊 強1,2

1(華南理工大學計算機科學與工程學院 廣州 510006)2(中山大學數(shù)據(jù)科學與計算機學院 廣州 51006)

(eschenwn@scut.edu.cn)

2(SchoolofDataandComputerScience,SunYat-senUniversity,Guangzhou510006)

演化算法通過模擬自然界生物迭代演化的智能現(xiàn)象來求解優(yōu)化問題，因其不依賴于待解問題具體數(shù)學模型特性的優(yōu)勢，已成為求解復雜優(yōu)化問題的重要方法.分布估計算法是一類新興的演化算法，它通過估計種群中優(yōu)勢個體的分布狀況建立概率模型并采樣得到子代，具有良好的搜索多樣性，且能通用于連續(xù)和離散空間的優(yōu)化問題.為進一步推動基于概率分布思想的演化算法發(fā)展，概述了多峰優(yōu)化演化算法的研究現(xiàn)狀，并總結(jié)出2個基于概率分布的演化算法框架：面向多解優(yōu)化的概率分布演化算法框架和基于概率分布的集合型離散演化算法框架.前者針對現(xiàn)有的演化算法在求解多峰多解的優(yōu)化難題時缺乏足夠的搜索多樣性的缺點，將廣義上基于概率分布的演化策略與小生境技術(shù)相結(jié)合，突破多解優(yōu)化的搜索多樣性瓶頸；后者圍繞粒子群優(yōu)化等部分演化算法在傳統(tǒng)上局限于連續(xù)實數(shù)向量空間的不足，引入概率分布估計的思想，在離散的集合空間重定義了算法的演化操作，從而提高了算法的可用性.

概率分布；演化算法；進化計算；多峰優(yōu)化；計算智能

多峰優(yōu)化問題(multimodal optimization problems)是指問題的解空間含有多個局部最優(yōu)或全局最優(yōu)解的一類優(yōu)化問題.這類問題廣泛存在于人們的日常生活和工業(yè)生產(chǎn)之中，例如旅行商問題(traveling salesman problem, TSP)、多重背包問題(multiple knapsack problem, MKP)等經(jīng)典的組合優(yōu)化問題[1]，聚類、特征選擇和分類等機器學習問題[2]，功率電路設計[3]、網(wǎng)絡設計等工業(yè)生產(chǎn)問題[4-5]，車輛路由[6]、項目調(diào)度和金融管理優(yōu)化等運籌調(diào)度問題[7-8]，都屬于多峰優(yōu)化問題.隨著科技的發(fā)展以及大數(shù)據(jù)時代的到來，這些優(yōu)化問題日益復雜，如何有效地求解多峰優(yōu)化問題已經(jīng)成為工業(yè)生產(chǎn)和日常生活的迫切需求，也成為了計算機、運籌和控制等多個領(lǐng)域的研究熱點.

由于這些實際優(yōu)化問題往往不具備精確的數(shù)學解析模型，或其數(shù)學模型不具有連續(xù)、可導等數(shù)學特性，傳統(tǒng)的數(shù)學優(yōu)化方法難以求解.演化計算方法是通過模擬自然界生物迭代演化的智能現(xiàn)象來求解復雜優(yōu)化問題的一類計算智能方法，具有不依賴于待解問題的精確數(shù)學模型和數(shù)學特性、全局尋優(yōu)、在可接受的時間內(nèi)能獲得近似最優(yōu)解等優(yōu)勢，已逐漸成為了求解復雜優(yōu)化問題的重要方法[9-11].2015年《Nature》刊登的機器學習?？矊ρ莼惴ǖ陌l(fā)展進行了專題報道[12].傳統(tǒng)上，演化算法(evolutionary algorithm, EA)主要包括遺傳算法(genetic algorithm, GA)[13]、遺傳編程(genetic programming, GP)[14]、進化策略(evolutionary strategy, ES)[15]和進化編程(evolutionary programming, EP)[16]等模擬生物進化過程的算法.近15年來，演化算法的研究受到了廣泛關(guān)注，其范疇也得到了進一步的拓展，如差分進化算法(differential evolution, DE)[17]和分布估計算法(estimation of distribution algorithm, EDA)[18]等基于改進的進化和變異方式的演化算法相繼被提出；如粒子群優(yōu)化(particle swarm optimization, PSO)[19]和蟻群優(yōu)化(ant colony optimization, ACO)[20]等群體智能算法也作為演化算法的分支快速發(fā)展.

然而，復雜多峰問題的解空間中往往存在著非常多的局部最優(yōu)解，部分局部最優(yōu)解的峰區(qū)所涵蓋的范圍比較寬闊.隨著問題維度的增加，多峰優(yōu)化問題的局部最優(yōu)解個數(shù)將快速增長，這對演化算法的搜索多樣性提出了重大挑戰(zhàn).另外，部分多峰優(yōu)化問題還可能存在多個峰值近似、均可接受的(近似)全局最優(yōu)解，需要演化算法能同時發(fā)現(xiàn)盡可能多的這些可接受的全局最優(yōu)解，以提供更準確的決策支持.這類多峰問題稱為多峰優(yōu)化的多解問題，其對演化算法的多樣性提出了更高的要求.為有效求解多峰優(yōu)化問題，如何在保持算法高效率以用較少的適應值評價次數(shù)來迭代演化的同時，提高算法的搜索多樣性以避免算法落入局部最優(yōu)，儼然是演化算法的關(guān)鍵，這也一直是演化算法研究的重點和熱點.

為了有效解決多峰優(yōu)化問題，學者們從不同角度、基于不同的演化算法，提出了各種各樣的多峰演化算法，提高了演化算法求解多峰優(yōu)化問題的效率和精度.特別地，如粒子群優(yōu)化、差分進化等基于解之間的差值運算作為交叉或變異算子的演化算法，憑借其簡單且有效的優(yōu)勢，吸引了廣大學者的關(guān)注[17,21-23].然而，隨著問題維度的擴大，峰值個數(shù)的增加，或者是在多樣性要求更高的多峰優(yōu)化多解問題上，基于差值運算作為進化算子的演化算法仍存在著容易落入局部最優(yōu)、早熟收斂的瓶頸[19,24].同時，這類算法傳統(tǒng)上一般定義于連續(xù)實數(shù)向量空間，難以直接應用于離散空間的組合優(yōu)化問題[1].

近年來，一類新型的演化算法——分布估計算法(EDA)逐漸受到了關(guān)注[18].與傳統(tǒng)的交叉、變異或者基于差值運算的進化操作不同，分布估計算法根據(jù)當前種群中的個體信息，評估種群演化的概率分布信息，并依據(jù)該概率分布采樣產(chǎn)生子代個體.該算法評估種群演化的分布信息，能更宏觀地把握整個空間的搜索情況，因此在算法的搜索多樣性維護上具有很大優(yōu)勢.同時，概率分布估計策略能通用于連續(xù)型和離散型的決策變量，不受解空間連續(xù)、離散特性的限制.若能進一步突破這類算法的搜索效率瓶頸，將能為復雜的多峰優(yōu)化問題提供高搜索多樣性的有效解決途徑.

狹義上，基于概率分布的演化算法一般指分布估計算法.廣義上，概率分布的思想實際上也在其他多種演化算法中體現(xiàn).例如蟻群優(yōu)化算法(ACO)的基本思想是通過信息素記錄種群搜索的歷史信息，并基于信息素指導依概率為子代個體構(gòu)建解，因此信息素的分布可以理解為一種特殊的概率分布[20].為了進一步探索基于概率分布的演化算法在復雜多峰優(yōu)化問題上的應用，本文將闡述2類廣義上基于概率分布的演化算法框架：面向多解優(yōu)化的概率分布演化算法框架和基于概率分布的集合型離散演化算法框架.其中，前者圍繞多峰問題多解優(yōu)化等搜索多樣性要求高的復雜多峰優(yōu)化問題，通過將概率分布演化算法和小生境(Niching)[25]技術(shù)相結(jié)合，充分發(fā)揮概率分布演化算法具備良好搜索多樣性的優(yōu)勢，克服演化算法在多解優(yōu)化中容易早熟收斂的缺陷.基于這一框架，本文將介紹2類新型多解優(yōu)化算法：多解優(yōu)化的分布估計算法(multimodal EDA, MEDA)[26]和自適應的多解優(yōu)化蟻群算法(adaptive multimodal ACO, AM-ACO)[27].另一方面，基于概率分布的集合型離散演化算法框架，能將傳統(tǒng)定義于連續(xù)實數(shù)向量空間的粒子群優(yōu)化等算法在集合空間中重定義，從而能夠突破算法的解空間受限瓶頸，將算法拓展成通用于連續(xù)和離散空間的通解算法.

1 面向多峰優(yōu)化的演化算法

1.1 多峰問題的單解演化算法

演化算法的思想是通過種群的迭代演化來不斷逼近問題的最優(yōu)解，其框架如算法1所示.

算法1. 演化算法基本框架.

輸入: 種群大小NP、最大迭代次數(shù)GEN；

輸出: 全局最優(yōu)解.

① 初始化種群并評估每個個體的適應值；

②generation=0；

③ While (generation

④ 根據(jù)父代個體通過操作算子等操作得到子代個體；

⑤ 評估子代個體適應值；

⑥ 用子代個體淘汰差的父代個體并更新全局最優(yōu)解gbest；

⑦generation++；

⑧ End While

不同的演化算法采用了不同的演化機制和演化算子.例如，GA通過模擬生物進化過程中染色體的交叉和變異操作來完成種群的演化；PSO通過個體向自我認知(即每個個體曾經(jīng)搜索到達的最優(yōu)位置pbest)和社會影響(即種群曾到達的最優(yōu)位置gbest)學習的演化操作來迭代進化，其迭代公式為

vi=wvi+r1c1(pbesti-xi)+r2c2(gbest-xi)，

(1)

xi=xi+vi，

(2)

其中，實數(shù)向量xi，vi分別表示第i個粒子的位置和速度；pbesti是第i個粒子的歷史最優(yōu)解，gbest是整個種群所找到的歷史最優(yōu)解；w是慣性權(quán)重，r1和r2是在[0,1]內(nèi)的隨機數(shù)，c1和c2是加速因子.

傳統(tǒng)上，多峰優(yōu)化問題一般是指單解問題.盡管這類問題的目的在于只尋找優(yōu)化問題解空間中的一個全局最優(yōu)解，但由于問題的局部最優(yōu)解眾多，算法很容易落入局部最優(yōu)，出現(xiàn)早熟收斂現(xiàn)象.為克服以上弊端，演化算法必須維持高搜索多樣性，以協(xié)助種群逃離局部最優(yōu)區(qū)域，同時又要節(jié)省適應值評價的使用次數(shù)，以提高算法搜索效率.為使演化算法既高效又具備足夠的搜索多樣性，學者們主要從3個角度開展研究并提出了眾多演化算法的改進版本：

1) 演化算法的參數(shù)調(diào)節(jié).演化算法的性能往往與算法的控制參數(shù)息息相關(guān).例如，GA的性能受到了交叉和變異概率的影響，PSO的性能則受到了慣性權(quán)重w和加速因子c1，c2的影響.對不同類型的優(yōu)化問題，在不同的演化階段，這些控制參數(shù)的選擇也各不相同.因此，如何動態(tài)自適應地為算法選擇合適的控制參數(shù)，成為了研究焦點.目前，主要的參數(shù)自適應方法包括2類：①基于進化狀態(tài)感知的自適應控制參數(shù)方法[21,28]，即通過分析種群的適應值和分布特性，感知算法在進化過程中所處的進化狀態(tài)，并最終根據(jù)算法所處的進化狀態(tài)特征設定不同的參數(shù)調(diào)整策略；②參數(shù)自我調(diào)節(jié)(self-adaptive)策略[29-30]，即根據(jù)種群適應值的變動情況，評價參數(shù)對算法性能的貢獻程度，并動態(tài)自適應地調(diào)整某組參數(shù)被選擇的概率，從而篩選出更有效的參數(shù)設置.

2) 演化算法的操作算子.盡管自適應調(diào)整控制參數(shù)能提高算法的搜索效率，但演化算子對算法的性能起到了更決定性的影響.圖1描述了基于式(1)和式(2)的原始PSO算法的搜索特征.

Fig. 1 The search behavior of the classical PSO on 1-D multimodal problem圖1 原始PSO算法在一維多峰優(yōu)化問題上的搜索特性

從圖1中可以看到，所有個體都向種群搜索到的歷史最優(yōu)解gbest學習，因此，如果gbest落入局部最優(yōu)，則其他個體很容易被吸引到局部最優(yōu).為了克服這一缺陷，學者們提出了多種更新算子的改進方案.例如Kennedy等人[31]提出了向個體的某個鄰域的歷史最優(yōu)解lbest而非gbest學習，得到了基于個體鄰域拓撲結(jié)構(gòu)的局部PSO版本；Liang等人[32]和Zhan等人[22]分別提出了分維全面學習和正交學習的PSO算法；Cheng等人[33]針對大規(guī)模優(yōu)化問題，提出了競爭學習的粒子群算法.我們也借鑒自然界中生物的壽命和衰老現(xiàn)象，依托生物學的進化衰老理論，提出了基于壽命的PSO算法[19]；同時借鑒競爭策略，我們提出了基于分塊的支配學習機制，并引進PSO算法，形成了基于分塊支配學習機制的PSO算法[24].類似地，其他基于改進操作算子的新型演化算法如JADE[29]，DEEP[17]，CMA-ES[34]等也相繼被提出.

3) 混合演化算法.由于不同類型的演化算法各具特征，所適合的優(yōu)化問題也各不相同，部分研究者希望通過結(jié)合多種演化算法來提高算法的性能.目前，主要的混合模式包括多策略混合和多算法混合.多策略混合指同一演化算法的多種操作算子相混合，例如多策略混合的DE算法[35-36]；多算法混合是指多種演化算法的操作算子相結(jié)合，例如基于遺傳進化操作的粒子群算法[37].

1.2 多峰問題的多解演化算法

實際應用中部分優(yōu)化問題可能具有多個可接受的近似全局最優(yōu)解，因此優(yōu)化算法需要發(fā)現(xiàn)盡可能多的這些最優(yōu)解以提供更好的決策支持.與單解優(yōu)化相比，多解優(yōu)化要求算法必須具備極高的多樣性維持能力，否則算法將很容易落入局部最優(yōu)或某個全局最優(yōu)解，而忽略了其他可接受的全局最優(yōu)解.因此，目前多解優(yōu)化往往只能采用演化算法進行求解，同時為了進一步提高搜索多樣性，在多解優(yōu)化時必須向演化算法引入特殊的策略.目前主流的2個策略是小生境策略(Niching)和多目標策略(Multi-objective).

1) 小生境策略.小生境策略的核心思想是通過某種技術(shù)限制種群中的個體全部向一個方向靠攏.目前主流的小生境策略有：適應值分享策略(fitness sharing)[38]、聚集策略(crowding)[39]以及物種劃分策略(speciation)[40]等.為了克服小生境策略對參數(shù)的敏感性，基于山谷/山峰檢測的小生境策略[41-42]以及基于近鄰聚類的小生境策略[43,25]也相繼被提出.小生境策略讓每個個體在自己附近區(qū)域進行搜索，有效地增加了種群的多樣性，成為處理多解優(yōu)化問題的關(guān)鍵技術(shù).

2) 多目標策略.由于多峰問題的多解優(yōu)化和多目標優(yōu)化[44]具有一定的近似性，部分學者提出將多峰問題多解優(yōu)化轉(zhuǎn)化為多目標優(yōu)化問題進行求解[45-47].一般而言，多峰問題多解優(yōu)化問題會被轉(zhuǎn)化為雙目標優(yōu)化問題.其中一個目標是多峰優(yōu)化的目標函數(shù)本身，另一個是評價個體位置對搜索空間覆蓋度的自定義優(yōu)化目標.最近，文獻[48]結(jié)合目標函數(shù)和空間分布信息定義出若干個相互沖突的雙優(yōu)化目標，并取得了良好的多解優(yōu)化效果.

值得一提的是，由于以PSO，DE為代表的基于差值演化操作的演化算法簡單而有效，目前大量多峰優(yōu)化研究都圍繞著這類算法展開.對于更復雜的多解問題，現(xiàn)有的工作也幾乎圍繞將小生境策略或多目標策略與PSO，DE或GA算法相結(jié)合而開展.根據(jù)湯森路透《2015研究前沿》，PSO，DE等演化算法已經(jīng)被列為了熱點研究前沿.然而，隨著峰值個數(shù)的增加，特別是在局部最優(yōu)解眾多的多解優(yōu)化問題上，基于差值演化操作的演化算法仍面臨著性能瓶頸，例如在CEC’2013多解優(yōu)化標準測試函數(shù)中，現(xiàn)有的基于DE，PSO等算法的多峰演化算法在部分問題上(特別是包含眾多局部最優(yōu)區(qū)域的多峰問題)的全局最優(yōu)解檢出率仍不足20%，甚至為0.此外，由于PSO，DE等算法傳統(tǒng)上定義于連續(xù)實數(shù)向量空間，一般不能直接應用于離散空間的組合優(yōu)化問題.如何進一步克服算法的搜索多樣性問題，突破算法在不同解空間中的可用性瓶頸，仍有待研究.

1.3 分布估計算法

EDA是近年來逐漸受到關(guān)注的一類演化算法[18].與DE，PSO等傳統(tǒng)演化算法不同的是，該算法沒有任何交叉或者變異等操作，而是采用了一種特殊的基于概率分布的種群演化策略.該算法根據(jù)當前種群的個體信息，評估種群演化的概率分布信息，并基于該概率分布信息采樣產(chǎn)生子代個體.其算法的基本框架如算法2所示.

算法2. EDA算法偽代碼.

輸入: 種群大小NP、用于分布評估的個體數(shù)M、最大迭代次數(shù)GEN；

輸出: 全局最優(yōu)解.

① 初始化種群，并評價每個個體的適應值；

②generation=0；

③ While(generation

④ 從種群中選擇M個個體，并用這些個體評估種群分布；

⑤ 依據(jù)評估的分布模型，采樣生成新的個體，并評估新個體的適應值；

⑥ 通過選擇產(chǎn)生新的種群，更新全局最優(yōu)解；

⑦generation++；

⑧ End While

由算法2可以看出，EDA算法的核心在于概率分布的估計,不同的概率分布估計模型衍生出不同的EDA算法.目前，主流的概率分布評估模型有：視所有變量相互獨立的單變量模型[49]、將2個變量視為相關(guān)變量的雙變量模型[50]、將多個變量視為相關(guān)變量的多變量模型[51]以及評估每個變量區(qū)間個體分布的直方圖模型[52].

EDA采用概率分布的思想，具有2個方面的重要優(yōu)勢：1)具有良好的搜索多樣性和全局搜索能力.圖2給出了EDA算法的搜索特征，即選擇種群中部分適應值更高的個體(圖2中框內(nèi)的空心圓點)，粗略估計這些優(yōu)勢個體在解空間中的分布概率.與圖1所示的PSO等算法的搜索特征相比，EDA能從更宏觀的角度評估種群的演化信息，因此往往具有更好的全局性和多樣性，不易被個別落入局部最優(yōu)的個體吸引從而造成早熟收斂現(xiàn)象.2)概率分布統(tǒng)計的方法在連續(xù)、離散的解空間中均適用，因此該方法并不受解空間特征的約束.正是這2個方面的優(yōu)勢，基于概率分布的演化算法將為求解多解優(yōu)化問題提供新的思路，也有助于突破傳統(tǒng)上部分演化算法的定義局限于連續(xù)實數(shù)向量空間的瓶頸.

Fig. 2 The search behavior of EDA on 1-D multimodal problem圖2 EDA算法在一維多峰優(yōu)化問題上的搜索特性

2 多解優(yōu)化的概率分布演化算法框架

如1.3節(jié)所述，基于概率的演化算法在保持搜索多樣性方面具有優(yōu)勢，然而基于概率分布的演化算法仍沒有在搜索多樣性要求極高的多解優(yōu)化等問題中得到研究和應用.針對此，我們在文獻[26]中采用傳統(tǒng)的概率分布估計算法，提出了多解優(yōu)化的EDA算法；在文獻[27]中進一步利用蟻群優(yōu)化算法通過信息素釋放隱式地建立概率分布的特點，提出了自適應的多解優(yōu)化ACO算法.本節(jié)將從廣義的概率分布演化算法的角度，總結(jié)出一套多解優(yōu)化的概率分布演化算法框架，通過將小生境策略與基于概率分布的演化算法相結(jié)合，為求解復雜的多峰多解優(yōu)化問題提供行之有效的新途徑，并基于這一框架介紹多解優(yōu)化的EDA和ACO算法.

2.1 算法框架

基于概率分布的多解優(yōu)化演化算法的基本思想是將概率分布演化與小生境策略相結(jié)合，建立對整個搜索空間中高適應值區(qū)域的概率分布估計，從而進一步提高算法的搜索多樣性，并結(jié)合局部搜索策略保證解的精度.算法框架如圖3所示.從圖3可以看出，基于概率分布的多解演化算法的整體框架由6個步驟構(gòu)成：

Fig. 3 The framework of the probability distribution-based multimodal algorithms圖3 多解優(yōu)化的概率分布演化算法框架

步驟1. 種群初始化.和其他演化算法一樣，該操作隨機產(chǎn)生一個分布均勻的初始種群并評價每個個體的適應值.

步驟2. 小生境劃分.該操作利用小生境策略將種群劃分為若干小生境.

步驟3. 概率分布估計.每個小生境相互獨立，因此每個小生境內(nèi)部的概率分布也相互獨立估計.基于每個小生境對應的子種群，評估每個小生境內(nèi)的演化分布情況.因此，整個種群內(nèi)包含了多個概率分布模型，對應于解空間中的不同區(qū)域.

步驟4. 子代采樣.每個小生境根據(jù)其評估的概率分布，獨立采樣得到其新一代的個體，從而使得新一代個體可以分布于解空間的不同區(qū)域.

步驟5. 個體選擇.每個小生境將子父代個體合并，采用基于近鄰的精英選擇策略得到新一代種群.

步驟6. 局部搜索.為提高解的精度，對每個小生境內(nèi)的最好個體，自適應地通過高斯分布進行鄰域局部搜索，從而提高解的質(zhì)量.

上述的步驟2～6反復迭代，直至算法達到終止條件.

在這一框架下，步驟2可以引入不同的小生境策略；步驟3可以選擇不同的概率分布估計方法，包括顯式的概率分布估計(如EDA顯式采用了高斯或柯西分布)或隱式的概率分布估計(如ACO通過信息素隱含地給出了概率分布)；步驟5和步驟6中可以引入不同的選擇和局部搜索操作.通過這些操作，可以得到不同的基于概率分布的多解演化算法.特別地，該框架將小生境策略和概率分布估計相結(jié)合，既保證了搜索個體能覆蓋解空間中的不同區(qū)域，又對每個小生境內(nèi)的種群演化信息做出了更全面的概率分布估計，從而從搜索空間整體到小生境內(nèi)部2個層次提高了算法的搜索多樣性；同時，該框架還引入了局部搜索策略，并允許根據(jù)實際應用中優(yōu)化精度的需求調(diào)整局部搜索的范圍和深度，從而更有利于算法在優(yōu)化精度和搜索多樣性之間取得平衡.

2.2 基于EDA的多解優(yōu)化算法(MEDA)

在圖3的框架下，我們在文獻[26]中首次提出了將分布估計算法(EDA)拓展到多峰優(yōu)化的多解問題，算法的詳細偽代碼如算法3所示.

算法3. MEDA算法偽代碼.

輸入: 種群大小NP、分組個數(shù)N、局部搜索點數(shù)K、最大迭代次數(shù)GEN；

輸出: 整個種群.

① 初始化種群；

②generation=0；

③ While (generation

④ 將種群劃分為N個組，每個組包含M=NPN個個體；

⑤ Fori=1:N

⑦ If(rand(0,1)<0.5)*rand(0,1)產(chǎn)生一個在(0,1)之間的均勻隨機數(shù)*

⑧ 用柯西分布Cauchy(μ,δ)生成M個新個體；

⑨ Else

⑩ 用高斯分布Gaussian(μ,δ)生成M個新個體；

該算法在每次迭代中首先利用聚類小生境策略將種群劃分為若干個小生境(行④)，而后對每個小生境獨立地進行概率分布估計(行⑥)，并根據(jù)分布信息采樣生成子代個體(行⑦～).子代生成后，不同小生境的子代只和自己對應的小生境父代進行比較，淘汰差的個體(行～)，最后通過局部搜索策略提高解的精度(行～).與其他基于小生境策略的多解優(yōu)化算法及傳統(tǒng)EDA算法相比，MEDA算法具有3點新特征：

1) 高斯/柯西相混合的顯式概率分布.MEDA采用了顯式的概率分布估計方法對每個小生境對應的子種群的演化分布情況進行評估.與以往EDA算法不同的是，MEDA針對多解優(yōu)化問題的特點，利用小生境策略達到對不同區(qū)域的演化信息進行評估，從而使得算法內(nèi)保持了多個分布信息；并且該算法采用了將柯西分布與高斯分布相結(jié)合的方式，通過2種分布二選一的方式來采樣生成子代個體，從而利用了高斯分布的強開發(fā)能力(exploitation)以及柯西分布的強探索能力(exploration)來平衡算法的多樣性和收斂速度.

2) 最近鄰替換原則.在將父子兩代個體合并篩選出新一代種群的過程中，該算法采用最近鄰原則(行)進行個體替換，即適應值更優(yōu)的個體只替換與其歐幾里得距離最近且適應值相對較差的個體，而非如傳統(tǒng)EDA算法那樣替換掉個體索引號一致或適應值最差的個體.最近鄰替換原則能防止個體向同一區(qū)域靠攏，使得不同的小生境涵蓋了解空間中不同區(qū)域的分布信息，從而使得不同小生境內(nèi)的個體沿著不同的方向搜索解空間，有利于提高搜索多樣性，使算法發(fā)現(xiàn)解空間中盡可能多的全局最優(yōu)解.

3) 基于高斯分布的自適應局部搜索.為了克服傳統(tǒng)EDA算法局部尋優(yōu)能力較差、解精度較低的不足，該算法引入了基于高斯分布的局部搜索方法，對每個小生境內(nèi)的種子個體(即該小生境內(nèi)最好的個體)根據(jù)其適應值自適應進行局部搜索，從而使算法能用較少的適應值評價次數(shù)獲取精度更高的最優(yōu)解.

文獻[26]的實驗結(jié)果也表明，該算法能夠比以往多峰算法，特別是基于PSO，DE等基于差值操作的多峰演化算法能夠發(fā)現(xiàn)更多的全局最優(yōu)解.例如在共有20個多解優(yōu)化問題的CEC’2013測試集上，MEDA算法能夠在12個測試函數(shù)上發(fā)現(xiàn)更多的全局最優(yōu)解.特別地，在包含眾多局部最優(yōu)點的多峰問題如f20上，MEDA算法將全局最優(yōu)解的檢出率從0%提高到24.8%.這些實驗結(jié)果證明MEDA算法具有更強的多樣性，而且能夠更好地平衡算法多樣性和收斂速度.

2.3 基于自適應ACO的多解優(yōu)化算法(AM-ACO)

除了顯式采用概率分布的EDA算法之外，部分演化算法的進化過程也蘊含了概率分布的思想.例如，蟻群優(yōu)化算法(ACO)是一類重要的群體智能算法，其核心思想是模擬螞蟻群體在尋找食物過程中在路徑上釋放信息素，并通過感知路徑的信息素積累來發(fā)現(xiàn)最短路徑.ACO已在眾多組合優(yōu)化問題中展現(xiàn)出了良好的性能[53].由于ACO的信息素歷史積累，本質(zhì)上可以理解成一種特殊的概率分布，拓展至連續(xù)空間的ACO算法版本，即ACOR算法[54]更具有明顯的概率分布特征，因此我們將ACO理解成一類廣義的基于概率分布的演化算法.與EDA不同，ACO的信息素是以每個個體的位置為中心，根據(jù)個體適應值的好壞而正相關(guān)地釋放并向外擴散，因此如果種群能覆蓋多個峰值所在的區(qū)域，其構(gòu)建的信息素分布可以同時刻畫出多個峰值所對應的解空間分布特征，從而有助于進一步提高算法的搜索多樣性.受此啟發(fā)，我們在文獻[27]首次將ACO拓展至多峰問題多解優(yōu)化，提出了自適應的多峰蟻群算法(AM-ACO)，其偽代碼如算法4所示.

算法4. AM-ACO算法偽代碼.

輸入: 種群大小NP、文檔集大小NP、分組個數(shù)N、局部搜索點數(shù)K、最大迭代次數(shù)GEN；

輸出: 整個種群.

① 初始化文檔集；

②generation=0；

③ While(generation

④ 將文檔集劃分為N個組，每個組包含M=NPN個個體；

⑤ 獲得文檔集的最大和最小適應值：FSmax，F(xiàn)Smin；

⑥ Fori=1:N

在如圖3所示的基于概率分布的多解演化算法框架下，AM-ACO仍采用聚類小生境策略將種群進行劃分為小生境(行④)，隨后基于ACO的進化模式對每個小生境分別構(gòu)建子代解(行～).在種群更新方面，該算法仍采取最近鄰替換策略進行種群更新(行)，并利用基于高斯分布的自適應局部搜索算法(行～)提高解的精確度.特別地，AM-ACO算法有如下的新特點：

Fig. 4 The framework of the probability-based discrete evolutionary algorithms based on set operations圖4 基于概率的集合型離散演化算法框架

1) 基于蟻群優(yōu)化模式的解構(gòu)建.與EDA的概率分布估計方法不同，AM-ACO算法根據(jù)小生境內(nèi)每個個體的適應值，計算每個個體釋放的信息素，對應于該個體的鄰域被選擇用于構(gòu)建子代解的概率分布(行⑨⑩).根據(jù)這一概率，選擇個體并在其鄰域或鄰域的變異區(qū)域內(nèi)基于高斯分布采樣生成新的子代解(行～).

2) 自適應控制參數(shù).對構(gòu)造概率分布中的關(guān)鍵控制參數(shù)σ，該算法提出了一種自適應調(diào)整策略(行⑧).該策略將小生境間個體的差異以及小生境內(nèi)個體的差異同時考慮在內(nèi)，使得不同的小生境有不同的σ，從而使得ACO算法擺脫了對參數(shù)σ的敏感性和依賴性.

通過將小生境策略、基于ACO的解構(gòu)建策略和σ的自適應調(diào)整策略相結(jié)合，AM-ACO算法能夠既在各個小生境層面上均勻地演化，又能使每個小生境內(nèi)的解分布于不同的區(qū)域，沿著不同方向進化；基于高斯分布的子代解生成和局部搜索策略還能進一步提高搜索的速度和解的精度，因此AM-ACO算法具有良好的搜索多樣性和收斂速度.文獻[27]的實驗結(jié)果也表明，該算法能夠在CEC’2013多解優(yōu)化測試集上能較MEDA進一步提高多解優(yōu)化的性能.特別地，在包含眾多局部最優(yōu)解的多峰問題如f20上，基于概率分布的演化算法能將全局最優(yōu)解的檢出率從原有其他經(jīng)典方法的0%，到MEDA的24.8%，再到AM-ACO的34.6%.這些實驗結(jié)果證明了基于概率分布的演化算法在求解復雜的多峰多解優(yōu)化問題時，在保持算法的搜索多樣性和提高全局最優(yōu)解的檢出率方面具有明顯的優(yōu)勢.

3 基于概率的集合型離散演化算法框架

基于概率分布的演化方式的另一優(yōu)勢是能通用于連續(xù)和離散空間的決策變量.因此，針對PSO等定義于連續(xù)實數(shù)向量空間的演化算法無法直接應用于離散組合優(yōu)化的瓶頸，我們受基于概率分布的演化方式的啟發(fā)，在文獻[1]提出了基于集合論和概率分布的集合型離散演化算法框架，將PSO等算法拓展至離散空間.該算法框架如圖4所示.

為了將形如式(1)(2)的PSO等算法的演化操作在離散空間中拓展，集合型框架主要包含了4個特征：

1) 集合型解表示.集合是表示離散變量的一般方法.因此，該框架采用集合的方式來表示離散決策變量.例如，在旅行商問題中，問題的一個解(即遍歷所有點一次且僅一次并返回出發(fā)點的哈密頓圈)可以由這條路徑所包含的邊的集合來表示.如圖4所示，路徑1—2—3—4—1的表示方式是集合X={(1,2),(2,3),(3,4),(1,4)}.

2) 學習概率表示.除了解的表示之外，式(1)(2)還含有另一類型的變量——速度，表示個體在更新時將要移動的方向和距離.在連續(xù)空間中，速度仍可以通過連續(xù)實數(shù)向量表示.為了在離散空間中定義相應類型的變量，借鑒概率操作，我們將速度定義為一個帶概率的集合.在圖4的例子中，V={(1,2)/0.8,(1,4)/0.2,(3,4)/0.5,(4,5)/0.3,(5,6)/0.1}定義了一個速度變量，其含義是個體更新時將要學習的元素及其概率.例如，集合V中含有(1,2)/0.8，表示個體將有80%的概率向元素(1,2)(即旅行商問題中(1,2)這條邊)學習來產(chǎn)生新的子代解.這樣，速度集合V事實上定義了一個值得個體用于學習和更新子代的元素的概率分布.

3) 學習概率更新.如式(1)的基于差值運算的演化操作的一個重要特征是：通過求2個解的差值，一方面得到了當前個體向種群的占優(yōu)個體學習的方向，從而引導個體向種群占優(yōu)個體的方向?qū)W習和移動；另一方面得到了搜索的鄰域范圍，使算法能在優(yōu)勢個體的鄰域范圍內(nèi)進一步尋優(yōu)，得到精度更高的解.利用上述基于學習概率表示的速度定義，式(1)定義的基于差值運算的速度更新過程，可以在離散幾何空間中重定義，如圖4的“速度更新”步驟所示.在這一速度更新步驟中，差值運算可以定義為2個解的集合差運算，其意義是找到那些存在于優(yōu)勢解(例如種群的歷史最優(yōu)解GBest集合)而不在個體當前解(即集合X)的那些元素，將這些元素列為值得學習的元素.此外，參數(shù)×集合的運算可以定義為將該參數(shù)作為集合中所有元素的被學習概率(定義于區(qū)間[0,1])，2個帶概率的集合的求和運算則定義為這2個集合的并集，若某元素同時出現(xiàn)在2個集合中則取其概率更高的一項.這樣，傳統(tǒng)上在連續(xù)實數(shù)空間的差值演化運算，就能夠在集合空間中重定義，并且運算的意義是一致的，即發(fā)現(xiàn)當前個體X值得向占優(yōu)個體(例如GBest)學習的地方，并且以一定的概率進行學習.

4) 位置更新.根據(jù)上述更新操作得到的速度Vi，個體Xi將按照Vi所給出的值得學習的元素及其學習概率更新個體的位置，產(chǎn)生子代個體.如圖4所示，為了使產(chǎn)生的新個體能夠滿足問題的約束條件，可選用的解更新策略有2類：①逐步構(gòu)建策略，即從Xi的某個元素開始，在滿足約束條件的前提下，根據(jù)學習概率或者選擇Vi中值得學習的元素，或者仍然采用原有個體Xi中的相應元素，不斷添加元素直至構(gòu)建出整體可行解為止.例如在旅行商問題中，可以從某個城市出發(fā)，逐步向子代解的集合中添加邊，直至完整地構(gòu)建出一個哈密頓圈.②整體構(gòu)建和解修補策略，即先根據(jù)速度Vi和當前解Xi按概率合并得到一個新的解，再通過解的修補策略保證該解能夠滿足問題的約束條件.例如在背包問題中，可以將從Vi中根據(jù)概率選出的物品和Xi中原有的物品全部選擇，再通過特定的解修補策略從中刪除部分物品直至所構(gòu)造的解滿足背包的容量約束.

通過上述的4個特征，基于概率的集合型演化算法框架將PSO等基于實數(shù)差值運算的演化算法在集合空間中重定義，從而將算法從連續(xù)空間拓展至離散空間，提高算法在不同解空間中的可用性.特別地，該框架借助概率分布的思想，將引導個體更新的速度變量定義為待學習元素的概率分布，具有3點優(yōu)勢[1]：

1) 該框架中定義的離散空間中的差值運算與連續(xù)空間中傳統(tǒng)PSO等算法的差值運算的意義一致，從而能夠在離散空間中保留了PSO等算法原有的搜索行為和特征；

2) 由于搜索行為一致，傳統(tǒng)PSO等算法的控制參數(shù)作用和設定，在基于概率和集合的離散算法框架中仍然有效；

3) 各種改進版本的PSO等算法以及其他基于實數(shù)向量差值運算的演化算法版本，都能夠根據(jù)這一框架拓展成相應的離散版本.

目前，基于這一框架的離散演化算法已被成功地應用在旅行商問題[1]、多重背包問題[1]、車輛路由優(yōu)化問題[6]、軟件測試覆蓋集生成問題[55]，并展現(xiàn)出了良好的性能和應用前景.

4 總結(jié)與展望

本文圍繞多峰優(yōu)化難題，對多峰優(yōu)化的演化算法發(fā)展進行了概述.特別地，一類新興的演化算法——分布估計算法(EDA)，其基于概率分布估計的演化方式在搜索多樣性和連續(xù)、離散解空間中的通用性都具有優(yōu)勢.受此啟發(fā)，我們提出了2個基于概率分布的演化算法框架，即多解優(yōu)化的概率分布演化算法框架和基于概率的集合型離散演化算法框架.前者從更廣義的角度理解基于概率分布的演化操作，并將其推廣應用于復雜的多解優(yōu)化問題，有效地提高了算法的搜索多樣性，提高了全局最優(yōu)解的檢出率；后者將集合表示方式和概率分布思想相結(jié)合，實現(xiàn)了將PSO等算法從連續(xù)實數(shù)向量空間到離散空間的重定義，并保留了算法的搜索行為特征，為求解多峰的組合優(yōu)化問題提供新的有效途徑.

基于概率分布的演化算法已經(jīng)在多類復雜優(yōu)化問題中體現(xiàn)了良好的優(yōu)化性能，然而相比于以PSO，DE為代表的基于差值操作的演化算法，該類演化算法發(fā)展相對緩慢，仍有很大發(fā)展空間.結(jié)合基于概率分布的演化算法的特征，我們認為這類算法將在如下的復雜優(yōu)化問題上有重要的發(fā)展和應用前景：

1) 大規(guī)模優(yōu)化.目前大多數(shù)演化算法只能有效處理低維空間的多峰優(yōu)化問題，然而當面對高維度優(yōu)化問題時，這些演化算法的性能大大降低，面臨著“維度詛咒”.一方面，隨著維度的增長，問題的解空間呈幾何式爆炸增長，極大地挑戰(zhàn)著目前演化算法的搜索效率；另一方面，隨著維度的增長，多峰問題解空間中的局部最優(yōu)點往往也呈爆炸式增長，使得目前演化算法陷入局部最優(yōu)的可能性大大增加.為處理以上問題:①需要增加演化算法的多樣性;②需要保持演化算法的收斂速度[56-57].如第2節(jié)和第3節(jié)所述，由于基于概率分布的演化算法在搜索多樣性和全局性上具有顯著的優(yōu)勢，這類算法和局部搜索方法的有機結(jié)合將有望能為突破大規(guī)模優(yōu)化的性能瓶頸提供新的有效途徑.

2) 不確定性優(yōu)化.隨著大數(shù)據(jù)時代的到來，大量優(yōu)化問題都呈現(xiàn)出不確定性，即待解問題的環(huán)境變量也是通過一定的概率分布給出，而非確定性給出.例如項目管理優(yōu)化中企業(yè)的現(xiàn)金流狀況、物流交通優(yōu)化中當前路網(wǎng)的車流狀況，這些環(huán)境變量往往都是不可在優(yōu)化前確定預知的，這些不確定性大大增加了優(yōu)化問題的求解難度，成為了優(yōu)化領(lǐng)域的研究前沿難題.由于基于概率分布的演化算法的核心思想就是構(gòu)建概率分布模型，這與基于概率的不確定性描述方式是相一致的.因此，基于概率分布的演化算法在求解帶不確定性的優(yōu)化問題上具有廣闊的發(fā)展?jié)摿?

3) 實際應用.相對于基于概率分布的演化算法本身的發(fā)展，其實際應用還僅限于傳統(tǒng)的低維度的類TSP問題[58]以及調(diào)度類優(yōu)化問題[7-8,59-60].然而，隨著大數(shù)據(jù)時代的到來，實際生活以及工業(yè)生產(chǎn)產(chǎn)生的多峰優(yōu)化問題愈發(fā)常見.因此，推廣該類演化算法在如網(wǎng)絡檢測[5]、行人識別[61]等大數(shù)據(jù)領(lǐng)域中的應用也是日后發(fā)展演化算法的熱點之一.

[1]Chen Weineng, Zhang Jun, Chung H S H, et al. A novel set-based particle swarm optimization method for discrete optimization problems[J]. IEEE Trans on Evolutionary Computation, 2010, 14(2): 278-300

[2]Xue Bing, Zhang Mengjie, Browne W N, et al. A survey on evolutionary computation approaches to feature selection[J]. IEEE Trans on Evolutionary Computation, 2016, 20(4): 606-626

[3]Jun Zhang, Chung H S H, Lo W L. Pseudocoevolutionary genetic algorithms for power electronic circuits optimization[J]. IEEE Trans on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 2006, 36(4): 590-598

[4]Gong Yuejiao, Shen Meie, Zhang Jun, et al. Optimizing RFID network planning by using a particle swarm optimization algorithm with redundant reader elimination[J]. IEEE Trans on Industrial Informatics, 2012, 8(4): 900-912

[5]Wen Xuyun, Chen Weineng, Lin Ying, et al. A maximal clique based multiobjective evolutionary algorithm for overlapping community detection[J]. IEEE Trans on Evolutionary Computation, DOI: 10.1109/TEVC.2016.2605501

[6]Gong Yuejiao, Zhang Jun, Liu Ou, et al. Optimizing the vehicle routing problem with time windows: A discrete particle swarm optimization approach[J]. IEEE Trans on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 2012, 42(2): 254-267

[7]Chen Weineng, Zhang Jun. An ant colony optimization approach to a grid workflow scheduling problem with various QoS requirements[J]. IEEE Trans on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 2009, 39(1): 29-43

[8]Chen Weineng, Zhang Jun. Ant colony optimization for software project scheduling and staffing with an event-based scheduler[J]. IEEE Trans on Software Engineering, 2013, 39(1): 1-17

[9]Hruschka E R, Campello R J G B, Freitas A A, et al. A survey of evolutionary algorithms for clustering[J]. IEEE Trans on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 2009, 39(2): 133-155

[10]Barros R C, Basgalupp M P, de Carvalho A C P L F, et al. A survey of evolutionary algorithms for decision-tree induction[J]. IEEE Trans on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 2012, 42(3): 291-312

[11]Zhang Jun, Zhan Zhihui, Lin Ying, et al. Evolutionary computation meets machine learning: A survey[J]. IEEE Computational Intelligence Magazine, 2011, 6(4): 68-75

[12]Eiben A E, Smith J. From evolutionary computation to the evolution of things[J]. Nature, 2015, 521(7553): 476-482

[13]Srinivas M, Patnaik L M. Genetic algorithms: A survey[J]. Computer, 1994, 27(6): 17-26

[14]Gustafson S, Vanneschi L. Crossover-based tree distance in genetic programming[J]. IEEE Trans on Evolutionary Computation, 2008, 12(4): 506-524

[15]Francois O. An evolutionary strategy for global minimization and its Markov chain analysis[J]. IEEE Trans on Evolutionary Computation, 1998, 2(3): 77-90

[16]Yao Xin, Liu Yong, Lin Guangming. Evolutionary programming made faster[J]. IEEE Trans on Evolutionary Computation, 1999, 3(2): 82-102

[17]Li Yuanlong, Zhan Zhihui, Gong Yuejiao, et al. Differential evolution with an evolution path: A DEEP evolutionary algorithm[J]. IEEE Trans on Cybernetics, 2015, 45(9): 1798-1810

[18]Hauschild M, Pelikan M. An introduction and survey of estimation of distribution algorithms[J]. Swarm and Evolutionary Computation, 2011, 1(3): 111-128

[19]Chen Weineng, Zhang Jun, Lin Ying, et al. Particle swarm optimization with an aging leader and challengers[J]. IEEE Trans on Evolutionary Computation, 2013, 17(2): 241-258

[20]Dorigo M, Birattari M, Stützle T. Ant colony optimization[J]. IEEE Computational Intelligence Magazine, 2006, 1(4): 28-39

[21]Zhan Zhihui, Zhang Jun, Li Yun, et al. Adaptive particle swarm optimization[J]. IEEE Trans on Systems, Man, and Cybernetics, Part B (Cybernetics), 2009, 39(6): 1362-1381

[22]Zhan Zhihui, Zhang Jun, Li Yun, et al. Orthogonal learning particle swarm optimization[J]. IEEE Trans on Evolutionary Computation, 2011, 15(6): 832-847

[23]Li Yuanlong, Zhan Zhihui, Gong Yuejiao, et al. Fast micro-differential evolution for topological active net optimization[J]. IEEE Trans on Cybernetics, 2016, 46(6): 1411-1423

[24]Yang Qiang, Chen Weineng, Gu Tianlong, et al. Segment-based predominant learning swarm optimizer for large-scale optimization[J]. IEEE Trans on Cybernetics, DOI: 10.1109/TCYB.2016.2616170

[25]Gao Weifeng, Yen G G, Liu Sanyang. A cluster-based differential evolution with self-adaptive strategy for multimodal optimization[J]. IEEE Trans on Cybernetics, 2014, 44(8): 1314-1327

[26]Yang Qiang, Chen Weineng, Li Yun, et al. Multimodal estimation of distribution algorithms[J]. IEEE Trans on Cybernetics, 2017, 47(3): 636-650

[27]Yang Qiang, Chen Weineng, Yu Zhengtao, et al. Adaptive multimodal continuous ant colony optimization[J]. IEEE Trans on Evolutionary Computation, 2017, 21(2): 191-205

[28]Streifel R J, Marks R J, Reed R, et al. Dynamic fuzzy control of genetic algorithm parameter coding[J]. IEEE Trans on Systems, Man, and Cybernetics, Part B (Cybernetics), 1999, 29(3): 426-433

[29]Zhang Jingqiao, Sanderson A C. JADE: Adaptive differential evolution with optional external archive[J]. IEEE Trans on Evolutionary Computation, 2009, 13(5): 945-958

[30]Tang Lixin, Dong Yun, Liu Jiyin. Differential evolution with an individual-dependent mechanism[J]. IEEE Trans on Evolutionary Computation, 2015, 19(4): 560-574

[31]Kennedy J, Mendes R. Population structure and particle swarm performance[C] //Proc of IEEE Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2002, 3: 1-1962

[32]Liang Jing, Qin A Kai, Suganthan P N, et al. Comprehensive learning particle swarm optimizer for global optimization of multimodal functions[J]. IEEE Trans on Evolutionary Computation, 2006, 10(3): 281-295

[33]Cheng Ran, Jin Yaochu. A competitive swarm optimizer for large scale optimization[J]. IEEE Trans on Cybernetics, 2015, 45(2): 191-204

[34]Hansen N. The CMA evolution strategy: A comparing review[C] //Towards a New Evolutionary Computation: Advances in the Estimation of Distribution Algorithms. Berlin: Springer, 2006: 75-102

[35]Wang Yong, Cai Zixing, Zhang Qingfu. Differential evolution with composite trial vector generation strategies and control parameters[J]. IEEE Trans on Evolutionary Computation, 2011, 15(1): 55-66

[36]Hu Mengqi, Wu T, Weir J D. An adaptive particle swarm optimization with multiple adaptive methods[J]. IEEE Trans on Evolutionary Computation, 2013, 17(5): 705-720

[37]Gong Yuejiao, Li Jingjing, Zhou Yicong, et al. Genetic learning particle swarm optimization[J]. IEEE Trans on Cybernetics, 2016, 46(10): 2277-2290

[38]Goldberg D E, Richardson J. Genetic algorithms with sharing for multimodal function optimization[C] //Proc of the 2nd Int Conf on Genetic Algorithms. Hillsdale, NJ: Lawrence Erlbaum, 1987: 41-49

[39]Thomsen R. Multimodal optimization using crowding-based differential evolution[C] //Proc of IEEE Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2004, 2: 1382-1389

[40]Li Xiaodong. Efficient differential evolution using speciation for multimodal function optimization[C] //Proc of the 7th Annual Conf on Genetic and Evolutionary Computation. New York: ACM, 2005: 873-880

[41]Ursem R K. Multinational GAs: Multimodal optimization techniques in dynamic environments[C] //Proc of the 2nd Annual Conf on Genetic and Evolutionary Computation. San Francisco, CA: Morgan Kaufmann, 2000: 19-26

[42]Li Lingxi, Tang Ke. History-based topological speciation for multimodal optimization[J]. IEEE Trans on Evolutionary Computation, 2015, 19(1): 136-150

[43]Qu Boyang, Suganthan P N, Liang Jing. Differential evolution with neighborhood mutation for multimodal optimization[J]. IEEE Trans on Evolutionary Computation, 2012, 16(5): 601-614

[44]Chen Ni, Chen Weineng, Gong Yuejiao, et al. An evolutionary algorithm with double-level archives for multiobjective optimization[J]. IEEE Trans on Cybernetics, 2015, 45(9): 1851-1863

[45]Yao Jie, Kharma N, Grogono P. Bi-objective multipopulation genetic algorithm for multimodal function optimization[J]. IEEE Trans on Evolutionary Computation, 2010, 14(1): 80-102

[46]Deb K, Saha A. Multimodal optimization using a biobjective evolutionary algorithm[J]. Evolutionary Computation, 2012, 20(1): 27-62

[47]Basak A, Das S, Tan K C. Multimodal optimization using a biobjective differential evolution algorithm enhanced with mean distance-based selection[J]. IEEE Trans on Evolutionary Computation, 2013, 17(5): 666-685

[48]Wang Yong, Li Hanxiong, Yen G G, et al. MOMMOP: Multiobjective optimization for locating multiple optimal solutions of multimodal optimization problems[J]. IEEE Trans on Cybernetics, 2015, 45(4): 830-843

[49]Bosman P, Thierens D. Expanding from discrete to continuous estimation of distribution algorithms: The IDEA[C] //Proc of the 6th Int Conf on Parallel Problem Solving from Nature. Berlin: Springer, 2000: 767-776

[51]Mühlenbein H, Mahnig T. FDA-a scalable evolutionary algorithm for the optimization of additively decomposed functions[J]. Evolutionary Computation, 1999, 7(4): 353-376

[52]Mühlenbein H, Paa? G. From recombination of genes to the estimation of distributions I. binary parameters[C] //Proc of the 4th Int Conf on Parallel Problem Solving from Nature. Berlin: Springer, 1993: 178-187

[53]Dorigo M, Stützle T. Ant Colony Optimization[M]. Cambridge, MA: MIT Press, 2004

[54]Socha K, Dorigo M. Ant colony optimization for continuous domains[J]. European Journal of Operational Research, 2008, 185(3): 1155-1173

[55]Wu Huayao, Nie Changhai, Kuo Feiching, et al. A discrete particle swarm optimization for covering array generation[J]. IEEE Trans on Evolutionary Computation, 2015, 19(4): 575-591

[56]Yang Qiang, Xie Hanyu, Chen Weineng, et al. Multiple parents guided differential evolution for large scale optimization[C] //Proc of 2016 IEEE Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2016: 3549-3556

[57]Song An, Yang Qiang, Chen Weineng, et al. Random-based dynamic grouping strategy for large scale multi-objective optimization[C] //Proc of 2016 IEEE Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2016: 468-475

[58]Yu Xue, Chen Weineng, Hu Xiaomin, et al. A set-based comprehensive learning particle swarm optimization with decomposition for multiobjective traveling salesman problem[C] //Proc of the 2015 Annual Conf on Genetic and Evolutionary Computation. New York: ACM, 2015: 89-96

[59]Chen Weineng, Zhang Jun, Chung H S H, et al. Optimizing discounted cash flows in project scheduling—an ant colony optimization approach[J]. IEEE Trans on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 2010, 40(1): 64-77

[60]Liu Yu, Chen Weineng, Hu Xiaomin, et al. An ant colony optimizing algorithm based on scheduling preference for maximizing working time of WSN[C] //Proc of the Annual Conf on Genetic and Evolutionary Computation. New York: ACM, 2015: 41-48

[61]Chen Ni, Chen Weineng, Zhang Jun. Fast detection of human using differential evolution[J]. Signal Processing, 2015, 110: 155-163

Chen Weineng, born in 1983. PhD, professor and PhD supervisor. Member of CCF. His main research interests include swarm intelligence algorithms and their applications on cloud computing, operations research and software engineering.

Yang Qiang, born in 1988. PhD candidate and research assistant. His main research interests include evolutionary algorithms and their applications on real-world problems.

Probability Distribution Based Evolutionary Computation Algorithms for Multimodal Optimization

Chen Weineng1and Yang Qiang1,2

1(SchoolofComputerScienceandEngineering,SouthChinaUniversityofTechnology,Guangzhou510006)

Evolutionary computation (EC) is a category of algorithms which simulate the intelligent evolutionary behavior in nature for solving optimization problems. As EC algorithms do not rely on the mathematical characteristics of the problem model, they have been regarded as an important tool for complex optimization. Estimation of distribution algorithm (EDA) is a new class of EC algorithms, which works by constructing a probability model to estimate the distribution of the predominant individuals in the population, and sampling new individuals based on the probability model. With this probability-based search behavior, EDA is good at maintaining sufficient search diversity, and is applicable in both continuous and discrete search space. In order to promote the research of probability-based EC (PBEC) algorithms, this paper gives a survey on EC algorithms for multimodal optimization, and then further builds two frameworks for PBEC: PBEC framework for seeking multiple solutions in multimodal optimization, and PBEC framework for discrete optimization. The first framework presents a method to combine probability-based evolutionary operators with the niching strategy, so that higher search diversity can be maintained for seeking multiple solutions in multimodal optimization. In particular, the framework understands PBEC algorithms in a broad sense, that is, it allows both explicit PBEC algorithms (e.g. EDA) and implicit PBEC algorithms (e.g. ant colony optimization) to operate in the framework, resulting in two representative algorithms: multimodal EDA (MEDA) and adaptive multimodal ant colony optimization (AM-ACO). The second framework aims at extending the applicability of EC algorithms on both continuous and discrete space. Since some popular EC algorithms are originally defined on continuous real vector space and they cannot be directly used to solve discrete optimization problems, this framework introduces the idea of probability distribution based evolution and redefines their evolutionary operators on discrete set space. As a result, the applicability of these algorithms can be significantly improved.

probability distribution; evolutionary algorithm (EA); evolutionary computation (EC); multimodal optimization; computational intelligence

2016-11-24；

2017-03-31

國家自然科學基金優(yōu)秀青年科學基金項目(61622206)；國家自然科學基金面上項目(61379061) This work was supported by the National Natural Science Foundation of China for Excellent Yong Scientists (61622206) and the General Program of the National Natural Science Foundation of China (61379061).

TP3-0