M-精英協(xié)同進(jìn)化分子動(dòng)理論優(yōu)化算法

范朝冬，章兢，易靈芝

(湘潭大學(xué) 信息工程學(xué)院，湖南 湘潭 411105)

1 引言

優(yōu)化問(wèn)題是科學(xué)研究和工程應(yīng)用中的一個(gè)熱點(diǎn)問(wèn)題，尋求快速、穩(wěn)健、有效的優(yōu)化技術(shù)是各行各業(yè)長(zhǎng)期探討的課題，其中智能優(yōu)化算法因?qū)崿F(xiàn)簡(jiǎn)單、運(yùn)算速度快、優(yōu)化效果好，已引起國(guó)內(nèi)外學(xué)者的廣泛關(guān)注。依據(jù)原理的不同，現(xiàn)有的智能優(yōu)化算法大致可分為3類：①基于遺傳進(jìn)化機(jī)制的優(yōu)化算法，如遺傳算法[1]、進(jìn)化策略[2]、進(jìn)化規(guī)劃[3]等；②基于生物群體智能的優(yōu)化算法，如微粒群算法[4]、猴群算法[5]、人工蜂群算法[6]等；③基于物理現(xiàn)象或規(guī)律的優(yōu)化算法，如類電磁機(jī)制優(yōu)化算法[7]、中心力算法[8]、萬(wàn)有引力算法[9]等。由于物理學(xué)的高度發(fā)展，模擬物理現(xiàn)象或物理規(guī)律的優(yōu)化算法因具有理論來(lái)源清晰、算法模型簡(jiǎn)單、規(guī)范且尋優(yōu)效果較好等諸多優(yōu)點(diǎn)，正逐漸成為優(yōu)化算法研究的熱點(diǎn)。

鑒于基于物理規(guī)律優(yōu)化算法的諸多優(yōu)點(diǎn)，通過(guò)模擬分子機(jī)制，筆者于2013年首次提出了分子動(dòng)理論優(yōu)化算法(KMTOA)并將其應(yīng)用于函數(shù)優(yōu)化問(wèn)題[10]。KMTOA能較好地兼顧收斂性和種群多樣性，在快速收斂的同時(shí)能盡量避免陷入局部極值，表現(xiàn)出良好的優(yōu)化性能。2014年，筆者將其與斜分 Otsu法相結(jié)合以對(duì)氧化鋁回轉(zhuǎn)窯火焰圖像進(jìn)行分割，取得了理想的分割效果[11]。KMTOA雖然具備良好的優(yōu)化性能，但仍然存在一些不足，如缺乏局部搜索機(jī)制，求解精度有待提高；當(dāng)前最優(yōu)值為局部極值時(shí)，算法可能發(fā)生錯(cuò)誤引導(dǎo)。

協(xié)同進(jìn)化思想能充分地考慮種群與種群間、種群與環(huán)境間在進(jìn)化過(guò)程中的相互協(xié)調(diào)關(guān)系，通過(guò)協(xié)同進(jìn)化以改善各自性能，已成為智能優(yōu)化領(lǐng)域的研究熱點(diǎn)[12,13]。精英通常指種群中適應(yīng)值較高的個(gè)體，這些個(gè)體對(duì)整個(gè)種群的進(jìn)化起著重要的引導(dǎo)作用[14,15]。慕彩紅等基于M個(gè)精英來(lái)建立團(tuán)隊(duì)，提出了M-精英協(xié)同進(jìn)化算法并將其應(yīng)用于函數(shù)優(yōu)化，取得了較好的效果[16,17]。因此，本文針對(duì)KMTOA的不足，提出了一種M-精英協(xié)同進(jìn)化分子動(dòng)理論優(yōu)化算法(MECKMTOA,M-elite coevolutionary KMTOA)。該算法采用M個(gè)精英代替單個(gè)精英來(lái)實(shí)現(xiàn)引導(dǎo)操作，以減小發(fā)生錯(cuò)誤性引導(dǎo)的概率；基于學(xué)習(xí)與協(xié)作機(jī)制，精英能學(xué)習(xí)其他精英的先進(jìn)知識(shí)而對(duì)自身進(jìn)行優(yōu)化搜索，從而提高算法的收斂精度；設(shè)計(jì)了一種自適應(yīng)的波動(dòng)算子，以防止算法陷入按維早熟。實(shí)驗(yàn)結(jié)果表明，MECKMTOA不僅具備更好的求解精度和算法穩(wěn)定性，而且能更好地求解高維函數(shù)問(wèn)題。

2 分子動(dòng)理論優(yōu)化算法及其不足

2.1 算法簡(jiǎn)介

在基于群體的優(yōu)化算法中，算法由可行域中的一組隨機(jī)點(diǎn)出發(fā)，依據(jù)隨機(jī)點(diǎn)的目標(biāo)函數(shù)值，通過(guò)一定的搜索策略使其收斂到問(wèn)題的最優(yōu)解。依據(jù)不同的原理各種算法采用了不同的搜索策略，其中KMTOA是受分子動(dòng)理論的啟發(fā)而提出的一種全局優(yōu)化算法。該算法將問(wèn)題的每個(gè)解視為一個(gè)分子，各分子在當(dāng)前最優(yōu)分子的吸引或排斥作用下運(yùn)動(dòng)而完成搜索過(guò)程；為增強(qiáng)算法跳出局部極值的能力，對(duì)于不受力的分子，通過(guò)模擬分子熱運(yùn)動(dòng)而進(jìn)行隨機(jī)擾動(dòng)?；诜肿酉嗷プ饔煤蜔徇\(yùn)動(dòng)機(jī)制，KMTOA在搜索過(guò)程中能較好地兼顧收斂性和種群多樣性。

設(shè)分子總數(shù)為N，問(wèn)題維數(shù)為D，分子i的位置和質(zhì)量分別為xi和mi，當(dāng)前最優(yōu)分子的位置和質(zhì)量分別為分別表示分子受當(dāng)前最優(yōu)分子吸引、排斥和不受力的概率；當(dāng)分子不受力時(shí)，對(duì)其進(jìn)行隨機(jī)擾動(dòng)以增強(qiáng)算法的全局搜索能力。KMTOA可簡(jiǎn)要描述如下[10]。

2.2 算法存在的不足

KMTOA僅依靠種群中的當(dāng)前最優(yōu)分子來(lái)實(shí)現(xiàn)尋優(yōu)操作，故算法在優(yōu)化過(guò)程中易出現(xiàn)圖1所示的情形：當(dāng)前最優(yōu)分子xBest為一局部極值，其他分子受其引導(dǎo)向該局部極值收斂，從而造成了算法的錯(cuò)誤收斂。雖然波動(dòng)算子使算法具有跳出局部極值的能力，但是波動(dòng)率和變異率都很小，且變異是隨機(jī)的，故算法跳出局部極值的過(guò)程是艱難而漫長(zhǎng)的?？梢?jiàn)，KMTOA僅依靠當(dāng)前最優(yōu)分子來(lái)引導(dǎo)搜索過(guò)程，存在一定的片面性。雖然當(dāng)問(wèn)題僅含一個(gè)極值時(shí)，算法效率較高；但是當(dāng)問(wèn)題包含多個(gè)局部極值時(shí)，該機(jī)制將嚴(yán)重影響算法的效率。

圖1 KMTOA的錯(cuò)誤性引導(dǎo)

定義 1在算法迭代過(guò)程中，如種群中的所有分子均滿足

則稱算法陷入按維早熟。其中，x·j表示種群中所有分子的第j維分量所構(gòu)成的向量，max(x·j)和min(x·j)分別表示種群中所有分子第j維分量的最大、最小值，ε為一極小量。

由式(6)可知，當(dāng)算法陷入按維早熟時(shí)，種群中的所有分子在某一維上的差異極小。此時(shí)，分子在其他維上仍然可能繼續(xù)進(jìn)化，故算法此時(shí)也許尚未發(fā)生真正的早熟，但如任其發(fā)展，則算法極有可能發(fā)生早熟。正是為了區(qū)別于傳統(tǒng)概念上的早熟，本文將其稱為按維早熟。由KMTOA的實(shí)現(xiàn)過(guò)程可知，當(dāng)陷入按維早熟時(shí)，要使分子在該維上出現(xiàn)差異(即跳出按維早熟)是較為困難的。此外，KMTOA還缺乏局部尋優(yōu)機(jī)制，其尋優(yōu)精度有待提高。

3 改進(jìn)的分子動(dòng)理論優(yōu)化算法

3.1 基于能力的團(tuán)隊(duì)構(gòu)建算子

在M-精英協(xié)同進(jìn)化算法中，每個(gè)精英團(tuán)隊(duì)的規(guī)模都相等[16,17]，這與自然界中優(yōu)勝劣汰的生存法則嚴(yán)重不符。自然界中能力強(qiáng)的個(gè)體在競(jìng)爭(zhēng)過(guò)程中將處于優(yōu)勢(shì)地位，往往占據(jù)更多的資源，能夠繁殖更多后代[18]，故其團(tuán)隊(duì)規(guī)模也相對(duì)較大。在優(yōu)化過(guò)程中，精英的能力越強(qiáng)，則意味著問(wèn)題的解在其附近的可能性越大。因此，對(duì)于能力較強(qiáng)的精英，應(yīng)組建規(guī)模較大的團(tuán)隊(duì)，以便引導(dǎo)更多分子進(jìn)行優(yōu)化搜索，這對(duì)提高算法效率具有重要意義?；谏鲜鏊枷?，本文設(shè)計(jì)了一種基于能力的團(tuán)隊(duì)構(gòu)建算子，將每個(gè)精英的能力定義為

其中，M表示精英種群的規(guī)模，xworst和f(xworst)分別表示當(dāng)前種群中的最差分子及其函數(shù)值。根據(jù)精英能力的定義，其團(tuán)隊(duì)規(guī)?？捎?jì)算如下

其中，Membersi表示精英i所能構(gòu)建團(tuán)隊(duì)的規(guī)模，Popsize表示種群規(guī)模?？梢?jiàn)，精英的目標(biāo)函數(shù)值越小，其能力越強(qiáng)，能夠組建團(tuán)隊(duì)的規(guī)模就越大，引導(dǎo)分子搜索到最小值的可能性也就越大。

3.2 基于學(xué)習(xí)機(jī)制的精英協(xié)作算子

在KMTOA中，由于缺乏相應(yīng)的局部搜索機(jī)制，當(dāng)求解復(fù)雜問(wèn)題時(shí)，其求解精度往往難以令人滿意。對(duì)此，當(dāng)團(tuán)隊(duì)成員屬于精英種群時(shí)，基于學(xué)習(xí)機(jī)制設(shè)計(jì)了一種協(xié)作算子。該算子通過(guò)在精英間交換信息以引導(dǎo)精英對(duì)其鄰域進(jìn)行搜索，從而實(shí)現(xiàn)局部搜索。基于學(xué)習(xí)機(jī)制的精英協(xié)作算子定義如下

其中，i≠j,xik表示精英i的第k維分量，N(0,1)為服從標(biāo)準(zhǔn)正態(tài)分布的隨機(jī)變量，D為解向量的維數(shù)，ui為協(xié)作過(guò)程完成后所得到的臨時(shí)個(gè)體。

得到精英xi的臨時(shí)個(gè)體ui后，可分別按式(10)、式(11)對(duì)精英xi、xj進(jìn)行更新。

由上式可知，如臨時(shí)個(gè)體ui對(duì)精英xi進(jìn)行了更新，則ui將不會(huì)對(duì)xj進(jìn)行更新，這樣做是為了防止種群快速收斂到同一個(gè)值而造成算法早熟。

3.3 防按維早熟的波動(dòng)算子

當(dāng)用KMTOA求解復(fù)雜性問(wèn)題時(shí)，算法可能出現(xiàn)按維早熟。由KMTOA的實(shí)現(xiàn)過(guò)程可知，當(dāng)出現(xiàn)按維早熟時(shí)，算法主要依靠波動(dòng)算子來(lái)跳出局部極值；但是KMTOA中的波動(dòng)率和變異率都比較小，這就決定了算法跳出局部極值的可能性較小。對(duì)此，本文設(shè)計(jì)了一種防按維早熟的波動(dòng)算子，該算子依據(jù)種群在當(dāng)前維上的差異來(lái)對(duì)變異率進(jìn)行計(jì)算；如差異較小，則該維變異率較大，以使分子能以較大的概率發(fā)生變異而保持種群多樣性。防按維早熟的變異率計(jì)算公式為

3.4 基于分子動(dòng)理論的引導(dǎo)算子

當(dāng)團(tuán)隊(duì)成員xj來(lái)自普通種群時(shí)，精英xi通過(guò)引導(dǎo)操作引導(dǎo)普通分子進(jìn)行優(yōu)化搜索。在引導(dǎo)過(guò)程中，精英分別依據(jù)吸引率Pattraction、排斥率Prepulsion和波動(dòng)率Pwave來(lái)判斷對(duì)分子進(jìn)行何種引導(dǎo)，具體操作如下：①當(dāng)精英對(duì)普通分子進(jìn)行吸引操作時(shí)，按式(1)計(jì)算其相應(yīng)的引力加速度；②當(dāng)精英對(duì)普通分子進(jìn)行排斥操作時(shí)，按式(2)計(jì)算其相應(yīng)的斥力加速度；③當(dāng)普通分子進(jìn)行隨機(jī)擾動(dòng)時(shí)，分別按式(12)、式(3)計(jì)算其相應(yīng)的變異率和波動(dòng)加速度。

計(jì)算出普通分子的加速度aj后，根據(jù)式(4)計(jì)算其速度Vj，并計(jì)算其臨時(shí)個(gè)體Tmp為

根據(jù)臨時(shí)個(gè)體Tmp，分別按式(14)、式(15)對(duì)精英xi和普通分子xj進(jìn)行更新

由上式可知，只有當(dāng)臨時(shí)個(gè)體Tmp比精英xi好時(shí)，Tmp才會(huì)取代xi而成為新的精英；而無(wú)論如何，臨時(shí)個(gè)體Tmp都會(huì)取代xj而成為新的普通分子。這么做一方面能夠避免精英退化，另一方面又能較好地維持普通種群的多樣性。

3.5 算法流程

MECKMTOA的算法流程如圖2所示。

4 算法收斂性分析

定理1在算法運(yùn)行過(guò)程中，MECKMTOA的種群序列｛Xt,t≥ 0 ｝為有限齊次Markov鏈。

證明 MECKMTOA采用實(shí)數(shù)編碼，如設(shè)定精度為ε，則解空間S可視為的離散空間，故種群序列有限；由算法過(guò)程可知，第t+1代的種群Xt+1僅與其上代種群Xt有關(guān)。因此，種群序列為有限齊次的Markov鏈。

圖2 MECKMTOA算法流程

定義2設(shè)f為S上的目標(biāo)函數(shù)，f*為全局最優(yōu)值，則最優(yōu)解集s*可表示為

5 數(shù)值仿真與分析

為便于與 KMTOA比較，選擇文獻(xiàn)[10]中的f6～f2015個(gè)經(jīng)典測(cè)試函數(shù)作為測(cè)試對(duì)象(記為F1～F15)，對(duì)MECKMTOA的性能進(jìn)行測(cè)試。測(cè)試實(shí)驗(yàn)分為4個(gè)部分：第1部分為M取值及相關(guān)算子的合理性分析實(shí)驗(yàn)，主要討論M的取值及各算子對(duì)算法性能的影響；第2部分為縱向比較實(shí)驗(yàn)，對(duì)改進(jìn)前后算法的性能進(jìn)行比較，以驗(yàn)證改進(jìn)措施的有效性；第3部分為橫向比較實(shí)驗(yàn)，將MECKMTOA與組織進(jìn)化算法(OEA, organizational evolutionary algorithm)和M-精英協(xié)同進(jìn)化算法(MECA,M-elite coevolutionary algorithm)等協(xié)同進(jìn)化算法進(jìn)行比較；第 4部分為高維及超高維函數(shù)測(cè)試實(shí)驗(yàn)，測(cè)試MECKMTOA解決高維及超高維問(wèn)題的能力。所有實(shí)驗(yàn)運(yùn)行的硬件平臺(tái)均為：Intel(R) Celeron(R) 1.50 GHz的CPU，2 GB內(nèi)存，Windows 7操作系統(tǒng)，編程語(yǔ)言為Matlab R2011a。

5.1 M及相關(guān)算子合理性分析

為測(cè)試精英數(shù)量M及各算子對(duì) MECKMTOA性能的影響，分別選用F5、F6和F9這3個(gè)復(fù)雜函數(shù)對(duì)MECKMTOA進(jìn)行測(cè)試。為便于后續(xù)與文獻(xiàn)[16]中的MECA和OEA進(jìn)行比較，MECKMTOA的種群規(guī)模取100，算法的最大迭代次數(shù)取3 000，每種情況下算法均獨(dú)立運(yùn)行50次，實(shí)驗(yàn)結(jié)果取50次測(cè)試的平均值。

5.1.1M取值分析

為測(cè)試精英種群的規(guī)模M對(duì)MECKMTOA的影響，首先從種群規(guī)模范圍內(nèi)選取部分值作為M的取值，以確定M的大致取值范圍，然后在該范圍內(nèi)對(duì)M的取值做進(jìn)一步的討論。參照文獻(xiàn)[16]，分別取M=3,5,10,15,20, 30,40,50,70,90，對(duì) MECKMTOA的不同結(jié)果進(jìn)行比較以確定M的大致取值范圍。由表1可知：對(duì)于函數(shù)F5、F6和F9，當(dāng)M取值小于10時(shí)，算法的優(yōu)化效果較好；當(dāng)M大于10時(shí)，算法的求解結(jié)果隨M的增大而越來(lái)越差，故M的理想取值應(yīng)小于10。

為討論M的具體取值，對(duì)M=1,2,3,4,5,6,7,8,9,10時(shí)，MECKMTOA的不同結(jié)果進(jìn)行了比較，比較結(jié)果如表2所示。由表2可知：對(duì)于函數(shù)F5、F6和F9，M取4～6的值時(shí)算法能取得較好的效果；M過(guò)大或過(guò)小，都將對(duì)算法的性能造成影響；當(dāng)M取5左右時(shí)，MECKMTOA的實(shí)驗(yàn)結(jié)果相對(duì)較好。

表1 M對(duì)MECKMTOA的影響1

表2 M對(duì)MECKMTOA的影響2

為分析M取值的合理性，借鑒文獻(xiàn)[19]閾值Q的分析方法，對(duì)F1～F15在M分別取1,2,…,10時(shí)的不同情況進(jìn)行測(cè)試，并運(yùn)用最小二乘法對(duì)測(cè)試結(jié)果的均值及其平均標(biāo)準(zhǔn)差進(jìn)行擬合。擬合結(jié)果如下，其擬合曲線分別如圖3和圖4所示。

圖3 M取不同值時(shí)，平均適應(yīng)值擬合曲線

圖4 M取不同值時(shí)，平均標(biāo)準(zhǔn)差擬合曲線

擬合結(jié)果表明：當(dāng)M分別取5.170 9和5.026 0時(shí)，平均適應(yīng)值和平均標(biāo)準(zhǔn)差能取得最小值。M過(guò)大、過(guò)小都會(huì)影響算法效果，這是因?yàn)镸過(guò)大，種群過(guò)于分散，不利于算法收斂；M過(guò)小，則種群多樣性差，易造成欺騙性引導(dǎo)。又因M取值為整數(shù)，故在后續(xù)的所有實(shí)驗(yàn)中均取M=5。擬合結(jié)果有力地驗(yàn)證了前文的分析。

5.1.2 相關(guān)算子分析

為改善算法的性能，本文設(shè)計(jì)了基于學(xué)習(xí)機(jī)制的精英協(xié)作算子、基于能力的團(tuán)隊(duì)構(gòu)建算子及防按維“早熟”的波動(dòng)算子。為驗(yàn)證各算子對(duì)算法性能的影響，用MECKMTOA1表示MECKMTOA中剔除了精英協(xié)作算子的算法，用MECKMTOA2表示MECKMTOA中固定了團(tuán)隊(duì)規(guī)模的算法，用MECKMTOA3表示MECKMTOA中采用了傳統(tǒng)波動(dòng)算子的算法，4種算法對(duì)函數(shù)F5、F6和F9的測(cè)試結(jié)果如表3所示。由表3可知，3個(gè)算子中基于能力的團(tuán)隊(duì)構(gòu)建算子對(duì)MECKMTOA的影響最小，但因基于能力的團(tuán)隊(duì)構(gòu)建算子能召集更多的成員對(duì)優(yōu)秀分子附近進(jìn)行搜索，故該算子對(duì)提高算法收斂的速度和精度具有一定影響；基于學(xué)習(xí)機(jī)制的精英協(xié)作算子通過(guò)在精英間進(jìn)行交換信息，對(duì)精英附近進(jìn)行搜索，故對(duì)提高算法的收斂精度具有重要影響；防按維早熟的波動(dòng)算子能根據(jù)每維的情況自適應(yīng)地調(diào)整變異率，能較好地防止算法陷入局部極值，如去掉該算子，則算法的性能將大幅下降。綜合考慮，3個(gè)算子能從不同的角度對(duì)算法的性能進(jìn)行改進(jìn)，故同時(shí)采用該3個(gè)算子的MECKMTOA最為理想。

表3 各算子對(duì)MECKMTOA的影響

表4 MECKMTOA與KMTOA的性能對(duì)比

5.2 改進(jìn)前后算法性能比較

為測(cè)試MECKMTOA的性能，將MECKMTOA與 KMTOA進(jìn)行比較。2種算法的種群規(guī)模均為100，最大迭代次數(shù)均為3 000，吸引率、排斥率、波動(dòng)率等與文獻(xiàn)[10]中一致，每個(gè)算法獨(dú)立運(yùn)行50次，選用 50次結(jié)果中的最小值、最大值、平均值和標(biāo)準(zhǔn)差4項(xiàng)指標(biāo)對(duì)算法的性能進(jìn)行比較，比較結(jié)果如表4所示。由表4可知：對(duì)于F1等KMTOA能取得最優(yōu)值的函數(shù)，MECKMTOA也均能取得最優(yōu)值；對(duì)于F2等KMTOA未能取得最優(yōu)值的函數(shù)，雖然MECKMTOA也未能取得最優(yōu)值，但是其求解精度具有明顯改善，如對(duì)于F2、F14等函數(shù)，MECKMTOA的求解精度甚至比KMTOA高幾個(gè)數(shù)量級(jí)。此外，由比較結(jié)果還能看出MECKMTOA幾乎在各項(xiàng)指標(biāo)上均優(yōu)于KMTOA。

5.3 與其他協(xié)同進(jìn)化算法的性能比較

為進(jìn)一步驗(yàn)證MECKMTOA的性能，將其與文獻(xiàn)[16]中的MECA和OEA這2種協(xié)同進(jìn)化算法進(jìn)行比較。實(shí)驗(yàn)選取本文與文獻(xiàn)[16]所共有的 8個(gè)測(cè)試函數(shù)作為測(cè)試對(duì)象，表5為3種算法的比較結(jié)果，其中MECA和OEA的數(shù)據(jù)選自文獻(xiàn)[16]。由表5可知：除F5和F9外，MECKMTOA能對(duì)所有的函數(shù)求得最優(yōu)值；對(duì)于F5，雖然 MECKMTOA未能求得最優(yōu)值，但其求解精度仍比MECA和OEA高1～2個(gè)數(shù)量級(jí)；在8個(gè)測(cè)試函數(shù)中，MECKMTOA只有對(duì)f14的求解結(jié)果比MECA和OEA差。故總體考慮，MECKMTOA在求解精度、算法穩(wěn)定性等方面比MECA和OEA具有更好的效果。

5.4 高維及超高維函數(shù)測(cè)試

為檢驗(yàn) MECKMTOA求解復(fù)雜問(wèn)題的能力以及問(wèn)題復(fù)雜度的增加對(duì)算法性能的影響，用MECKMTOA 分別求解高維(維數(shù)為 10～1 000)和超高維(維數(shù)1 000以上)條件下的F10和F13，并將其求解結(jié)果與文獻(xiàn)[20]中的免疫記憶克隆規(guī)劃算法(IMCPA, immune memory clonal programming algorithm)及無(wú)記憶功能的免疫記憶克隆規(guī)劃算法(nIMCPA)進(jìn)行比較。算法終止條件為為算法當(dāng)前的最優(yōu)值，ε為算法的收斂精度。參照文獻(xiàn)[20]，對(duì)于高維函數(shù)，平均函數(shù)評(píng)價(jià)次數(shù)取算法 10次運(yùn)行的平均值；對(duì)于超高維函數(shù)，平均函數(shù)評(píng)價(jià)次數(shù)取算法 5次運(yùn)行的平均值；IMCPA和nIMCPA的數(shù)據(jù)選自文獻(xiàn)[20]，“—”表示沒(méi)有進(jìn)行該實(shí)驗(yàn)。

由表6可知：與IMCPA和nIMCPA相比，在相同的收斂精度下，MECKMTOA所需的平均函數(shù)評(píng)價(jià)次數(shù)相對(duì)較少；隨著維數(shù)的增加，MECKMTOA、IMCPA和nIMCPA的平均函數(shù)評(píng)價(jià)次數(shù)均有所增長(zhǎng)，但MECKMTOA的平均函數(shù)評(píng)價(jià)次數(shù)增長(zhǎng)的相對(duì)緩慢。比較結(jié)果表明：MECKMTOA即使在超高維條件下仍能表現(xiàn)出良好的性能，且其性能不隨問(wèn)題維數(shù)的增加而迅速下降。

6 結(jié)束語(yǔ)

表5 MECKMTOA與MECA及OEA的比較

表6 高維及超高維函數(shù)測(cè)試結(jié)果

針對(duì)KMTOA存在的不足，通過(guò)引入精英和協(xié)同進(jìn)化思想，提出了一種M精英協(xié)同分子動(dòng)理論優(yōu)化算法。該算法采用M個(gè)精英，減小了傳統(tǒng)算法發(fā)生錯(cuò)誤性引導(dǎo)的概率，改善了算法的收斂效率；精英通過(guò)協(xié)作算子，學(xué)習(xí)先進(jìn)知識(shí)以改善自己，提高了算法的收斂精度；防按維早熟的波動(dòng)算子因能自適應(yīng)地調(diào)節(jié)波動(dòng)率，能有效地防止算法發(fā)生早熟。為分析M的取值對(duì)算法性能的影響，討論了M的不同取值情況，確定了其大致取值。為驗(yàn)證各算子的合理性，分析了各算子對(duì)算法所造成的影響。與KMTOA的縱向比較表明，MECKMTOA的改進(jìn)策略是有效的；與MECA和OEA這2種協(xié)同進(jìn)化算法的橫向比較結(jié)果表明，MECKMTOA的協(xié)同引導(dǎo)機(jī)制具有明顯優(yōu)勢(shì)；對(duì)高維及超高維函數(shù)的測(cè)試結(jié)果表明，MECKMTOA具備求解復(fù)雜性問(wèn)題的能力，且其性能受問(wèn)題維數(shù)的影響相對(duì)較小。綜合考慮，MECKMTOA具備較強(qiáng)的優(yōu)化性能，有望應(yīng)用于復(fù)雜問(wèn)題的求解，具有重要的理論研究意義和工程應(yīng)用價(jià)值。

[1] LIN C H, CHOY K L, HO G T S, NG T W. A genetic algorithm-based optimization model for supporting green transportation operations[J].Expert Systems with Applications, 2014, 41(7): 3284-3296.

[2] DONG W Y, ZHOU M C. Gaussian classifier-based evolutionary strategy for multimodal optimization[J]. IEEE Transactions on Neural Networks & Learning Systems, 2014, 25(6): 1200-1216.

[3] KHATOD D K, PANT V, SHARMA J. Evolutionary programming based optimal placement of renewable distributed generators[J]. IEEE Transactions on Power Systems, 2013, 28(2): 683-695.

[4] MIRJALILI S, LEWIS A, SADIQ A S. Autonomous particles groups for particle swarm optimization[J]. Arabian Journal for Science and Engineering, 2014, 39(6): 4683-4697.

[5] ZHENG L. An improved monkey algorithm with dynamic adaptation[J].Applied Mathematics and Computation, 2013, 222(1): 645-657.

[6] 張冬麗，唐英干，關(guān)新平. 用改進(jìn)的人工蜂群算法設(shè)計(jì)AVR系統(tǒng)最優(yōu)分?jǐn)?shù)階PID控制器[J].自動(dòng)化學(xué)報(bào)，2014, 40(5): 973-979.ZHANG D L, TANG Y G, GUAN X P. Optimum design of fractional order pid controller for an avr system using an improved artificial bee colony algorithm[J]. Acta Automatica Sinica, 2014, 40(5): 973-979.

[7] ZHANG C J, LI X Y, GAO L WU Q. An improved electromagnetism-like mechanism algorithm for constrained optimization[J]. Expert Systems with Applications, 2013, 40(14): 5621-5634.

[8] FORMATO R A. Central force optimization with variable initial probes and adaptive decision space[J]. Applied Mathematics and Computation, 2011, 2(17): 8866-8872.

[9] MIRJALILI S, LEWIS A. Adaptive gbest-guided gravitational search algorithm[J]. Neural Computing and Applications, 2014, 25(7):1569-1584.

[10] FAN C D, OUYANG H L, ZHANG Y J,et al. Optimization algorithm based on kinetic-molecular theory[J]. Journal of Central South University, 2013, 20(12): 3504-3512.

[11] 范朝冬, 張英杰, 歐陽(yáng)紅林等. 基于改進(jìn)斜分Otsu法的回轉(zhuǎn)窯火焰圖像分割[J]. 自動(dòng)化學(xué)報(bào), 2014, 40(11): 2480-2489.FAN C D, ZHANG Y J, OUYANG H L,et al. Improved Otsu method based on histogram oblique segmentation for segmentation of rotary kiln flame image[J]. Acta Automatica Sinica, 2014, 40(11):2480-2489.

[12] JIAO L C, WANG H D, SHANG R H,et al. A co-evolutionary multi-objective optimization algorithm based on direction vectors[J]. Information Sciences, 2013, 228(10): 90-112.

[13] LI H C, FANG L. Co-evolutionary algorithm: an efficient approach for bilevel programming problems[J]. Engineering Optimization, 2014,46(3): 361-376.

[14] CHEN P H. Two-level hierarchical approach to unit commitment using expert system and elite PSO[J]. IEEE Transactions on Power Systems,2012, 27(2): 780-789.

[15] YOUSEFIKHOSHBAKHT M, DIDEHVAR F, RAHMATI F. An efficient solution for the vrp by using a hybrid elite ant system[J]. International Journal of Computers Communications & Control, 2014,9(3): 340-347.

[16] 慕彩紅, 焦李成, 劉逸.M-精英協(xié)同進(jìn)化數(shù)值優(yōu)化算法[J]. 軟件學(xué)報(bào), 2009, 20(11): 2925-2938.MU C H, JIAO L C, LIU Y.M-elite coevolutionary algorithm for numerical optimization[J]. Journal of Software, 2009, 20(11): 2925-2938.

[17] 慕彩紅, 焦李成, 劉逸.M-精英協(xié)同進(jìn)化算法及其在 V-BLAST系統(tǒng)中的應(yīng)用[J]. 電子與信息學(xué)報(bào), 2009, 31(10): 2443-2448.MU C H, JIAO L C, LIU Y.M-elitist evolutionary algorithm and its application to v-blast system[J]. Journal of Electronics & Information Technology, 2009, 31(10): 2443-2448.

[18] 秦進(jìn), 李歆. 一種簡(jiǎn)單的資源受限的群體演化模型[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 2009, 6(2): 82-86.QIN J, LI X. A simple model of population evolution with limited resource[J]. Complex Systems and Complexity Science, 2009, 6(2):82-86.

[19] 范朝冬, 歐陽(yáng)紅林, 肖樂(lè)意. 基于空間截面投影的Otsu圖像分割算法[J]. 通信學(xué)報(bào), 2014, 35(5): 70-78.FAN C D, OUYANG H L, XIAO L Y. Otsu thresholding method based on projection of cross section for image segmentation[J]. Journal on Communications, 2014, 35(5): 70-78.

[20] 杜海峰, 公茂果, 焦李成等. 用于高維函數(shù)優(yōu)化的免疫記憶克隆規(guī)劃算法[J]. 自然科學(xué)進(jìn)展, 2004, 14(8): 925-933.DU H F, GONG M G, LIAO L C,et al. Immune memory clonal programming algorithm for high dimension function optimization[J].Progress in Natural Science, 2004, 14(8): 925-93.