聚散優(yōu)化算法：一種新的啟發(fā)式算法

李 瑞，趙新超,2+，郭 賽，袁健美

(1.北京郵電大學(xué) 理學(xué)院，北京 100876;2.湘潭大學(xué) 科學(xué)工程計算與數(shù)值仿真湖南省重點實驗室，湘潭 湖南 411105;3.湘潭大學(xué) 數(shù)學(xué)與計算科學(xué)學(xué)院，湘潭 湖南 411105)

0 引言

啟發(fā)式算法是通過對自然界生物種群的行為抽象和模擬構(gòu)造而成的隨機優(yōu)化算法。這些算法的提出往往受到大自然的啟發(fā)，例如Holland[1]通過模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機理的生物進(jìn)化過程提出了遺傳算法(Genetic Algorithm, GA)；Eberhart等[2]通過模擬鳥群在捕食過程中展現(xiàn)的智能行為提出了粒子群算法(Particle Swarm Optimization, PSO)；Dorigo等[3]通過模擬蟻群中螞蟻相互之間通過信息素協(xié)作覓食的行為提出了蟻群優(yōu)化算法(Ant Colony Optimization, ACO)；Storn等[4]在遺傳算法進(jìn)化思想的基礎(chǔ)上提出一類基于群體的自適應(yīng)全局優(yōu)化的差分進(jìn)化算法(Differential Evolution, DE)，是通過對進(jìn)化機制和個體之間的差異信息的模擬提出的；Karaboga等[5]通過模擬蜜蜂的社會分工與協(xié)作覓食的行為提出了人工蜂群(Artificial Bee Colony, ABC)算法；Passino[6]模仿人體食道內(nèi)大腸桿菌的覓食行為，提出了細(xì)菌覓食優(yōu)化(Bactering Foraging Optimization, BFO)算法；頭腦風(fēng)暴優(yōu)化算法[7]于2011年提出，算法模擬了一種人類集思廣益求解問題的集體行為，即頭腦風(fēng)暴過程。自然界中的生物特別是螞蟻、細(xì)菌等，它們每個個體都不具有類似于人類復(fù)雜的高級智能，但它們在食物的刺激下，不斷適應(yīng)環(huán)境，展現(xiàn)出了極高的群體智能，并且群體展現(xiàn)出的這種能力具有自組織的特點。這種現(xiàn)象為人類解決問題提供了新的角度。受此啟發(fā)，本文認(rèn)為可以將傳統(tǒng)方法進(jìn)行種群化改造，將原有的算子擴展為適合種群的算子，從而提出新的算法。目前已有許多專家學(xué)者提出了不同的啟發(fā)式算法，并在實際生產(chǎn)生活中取得了不錯的效果。例如，李軍軍等[8]提出的誘導(dǎo)蟻群粒子群算法有效解決了多自動導(dǎo)引車路徑規(guī)劃中的沖突問題；劉江偉等[9]基于改進(jìn)粒子群算法解決了多工位裝配序列規(guī)劃問題。

本文探究是否可以將局部的傳統(tǒng)優(yōu)化方法進(jìn)行種群化，從而使新設(shè)計的群體優(yōu)化算法具有更好的全局搜索能力。傳統(tǒng)方法多為單點搜索，相比于基于種群的算法，單點搜索更容易陷入局部最優(yōu)，因而傳統(tǒng)方法一般不具備全局搜索能力。另一方面?zhèn)鹘y(tǒng)方法對于一個局部問題的求解往往更加有效，將傳統(tǒng)方法種群化之后，希望在增加傳統(tǒng)方法全局搜索能力的同時，能夠保持傳統(tǒng)方法的搜索性能，從而開發(fā)出新的方法?；谠撓敕?，本文在啟發(fā)式算法和直接方法的研究基礎(chǔ)上，將單純形方法算子種群化，抽象出了聚合算子和分散算子。這兩個算子在每次迭代產(chǎn)生新的種群，在該過程中利用啟發(fā)式信息產(chǎn)生新的解。此外，本文還提出了歸檔重置的策略，該策略可以在一個較為宏觀的尺度上對種群的演變進(jìn)行引導(dǎo)。結(jié)合兩個算子和歸檔重置策略，提出一種新的啟發(fā)式算法并通過大量仿真實驗驗證了算法的有效性。數(shù)值實驗表明在很多的測試函數(shù)上，該算法能夠展現(xiàn)出較以往的啟發(fā)式算法更優(yōu)的性能。

1 單純形法

單純形法是可以不使用導(dǎo)數(shù)信息的一種傳統(tǒng)優(yōu)化方法，該方法是利用比較簡單幾何圖形各頂點的目標(biāo)函數(shù)值，在連續(xù)改變幾何圖形的過程中，逐步以目標(biāo)函數(shù)值較小的頂點取代目標(biāo)函數(shù)值最大的頂點，從而求優(yōu)點的方法。單純形是代數(shù)拓?fù)渲凶罨镜母拍?，是三角形和四面體的一種泛化。k維單純形是指包含k+1個節(jié)點的凸多面體。考慮實數(shù)域的n維向量空間Rn，設(shè)a0,a1,…,a_n是一組向量，使得a0-a1,a1-a2,…,an-1-an線性無關(guān)。設(shè)E={p=s0a0，s1a1，…,snan|s0+s1+…+sn=1}，點集E稱為一個n維單純形。例如：特殊的1維單純形就是線段，2維單純形就是三角形。

X5=X4+α(X4-X1)=-αX1+(1+α)X4。

(1)

則稱為X5為X1關(guān)于X4的反射點，α為反射系數(shù)，一般取α=1。如圖1所示。

由此可以算出X5的函數(shù)值f(X5)可能有下列情形：

(1)f(X5)≤f(X3) 搜索方向正確，可進(jìn)一步擴張，繼續(xù)沿X1X5向前搜索(擴張)。其中α為擴張因子，可取值為1.5。若f(X6)≤f(X5)，則擴張有利，就以X6代替X1構(gòu)成新單純形{X2,X3,X6}；若f(X6)≥f(X5)，則擴張不利，舍去X6，以X5代替X1構(gòu)成新單純形{X2,X3,X5}。

(2)f(X3)≤f(X5)≤f(X2) 這說明搜索方向正確，無須擴張，以X5代替X1構(gòu)成新的單純形{X2,X3,X5}。

(3)f(X2)≤f(X5)≤f(X1) 這表示X5走得太遠(yuǎn)，應(yīng)縮回一些。若以α表示壓縮因子，常取α值為0.5，以X7代替X1構(gòu)成新的單純形{X2,X3,X7}。

(4)f(X5)>f(X1)X2與X1向X3收縮。

2 聚集算子和分散算子

受傳統(tǒng)最優(yōu)化方法中直接方法——單純形方法的啟發(fā)，本文提出了聚集算子和分散算子作為種群中新個體的生成策略，這樣產(chǎn)生新的種群面臨的最大的問題是如何使用原有攜帶群體信息和個體搜索信息的解來產(chǎn)生新的更優(yōu)的解。借鑒單純形方法，在生成每一個新解的時候都在種群中依次選取3個個體，并按照各自的目標(biāo)函數(shù)值確定三者之中的最優(yōu)者Xb，最差者Xw和中間者Xm，最后根據(jù)對3個解不同關(guān)系的討論提出了聚集算子和分散算子。

2.1 聚集算子

聚集算子的目的是使種群在迭代的過程中向某一個有潛力的方向聚集。使用該算子在前期可以獲得較快的收斂速度，后期具有向內(nèi)聚集趨勢的局部搜索能力。給定3個解，依據(jù)目標(biāo)函數(shù)選出Xb,Xw,Xm，則讓三者中最差的解向兩個更優(yōu)解的方向靠攏，為了加快算法的收斂速度，本文使用兩個比較優(yōu)秀的解來引導(dǎo)整個種群的更新。

在傳統(tǒng)單純形方法中，為了使新解向較優(yōu)解靠攏，參數(shù)α的值應(yīng)該大于0，另一方面為確保算法擁有較高的收斂性，通常最高的取值不應(yīng)該超過2，因此參數(shù)α∈(0,2)。綜合考慮式(1)，-α可以認(rèn)為是對較差解x1的罰因子，α是對較好解x4給定的鼓勵因子?，F(xiàn)在仔細(xì)討論一下不同情況時的算法表現(xiàn)，在α∈(0,1)時，由于參數(shù)小于1，說明算法沒有搜索到較好的解，因此應(yīng)當(dāng)適度減弱原有策略的影響，故應(yīng)將因子減小希望能夠找到一個較好的解，此時對較差的解應(yīng)該減弱處罰力度，同時減弱對較好解的鼓勵力度；當(dāng)α∈(1,2)時，說明原來的機制比較好，應(yīng)當(dāng)強化這個策略，增大因子的值可以增強對差解的處罰力度，增強對好解的鼓勵力度。但是這個時候差解的權(quán)重為負(fù)，當(dāng)處于算法后期3個解相差不大的情況下，需要很多獎勵才能彌補這個過重的懲罰，對搜索不利，因此應(yīng)當(dāng)適度地進(jìn)一步加大鼓勵或者適度降低懲罰，從而進(jìn)一步增強算法的效果。注意到將X1的系數(shù)改為1-α?xí)r更符合算法機制。此時，α∈(0,2),(1-α)∈(-1,1)而不是-α∈(-2,0)，即此時對較差解的懲罰相較于原公式大大減弱，符合上述判斷。對式(1)分析易知，由于(X4-X1)的系數(shù)大于0，因此算法在產(chǎn)生新的探測點時很難取到三角形△X1X2X3的內(nèi)部點，例如X8處的點。因此將式(1)中的1用α代替，從而弱化式(1)，使其能夠包含三角形△X1X2X3內(nèi)的點，得

(2)

進(jìn)而引入隨機數(shù)r1∈[0,2]，r2∈[0,1]構(gòu)成凸組合得

X5=(1-r1)X1+r1(r2X2+(1-r2)X3)。

(3)

將算法中的個體帶入上述公式，得到聚集算子的迭代公式，其中l(wèi)BS是個體自身搜索到的最優(yōu)解，gBS是算法到目前為止找到的全局最優(yōu)解，隨機數(shù)r1∈[0,2]，r2∈[0,1]，其中參數(shù)r1的選取范圍是基于想擴大現(xiàn)有幾個解組合的搜索范圍，即屬于擴展凸組合的參數(shù)選取方式。

Xi=(1-r1)Xi+r1(r2lBS+(1-r2)gBS)。

(4)

下面首先在二維空間內(nèi)給出凸組合和擴展凸組合的結(jié)果，然后對式(4)給出一個直觀的說明。

(1)凸組合 如圖2所示，假設(shè)有3個二維平面向量OA，OB，OC，起點均在原點O。并且向量OA，OB不相等，隨機數(shù)r∈[0,1]。則依據(jù)式(5)計算出OC的終點均落在向量OA，OB終點的連接線段AB上。

OC=rOA+(1-r)OB。

(5)

(2)拓展的凸組合 若式(5)中的隨機數(shù)r∈[0，2]，如圖3所示，向量OC的終點均落在線段B′B上，且|B′B|=2|AB|，即在A的另一側(cè)作了和線段AB等長且共線的線段AB′。此時是在B′B直線上以A為中心，|AB|為半徑的區(qū)間內(nèi)進(jìn)行搜索。簡單證明如下：由式(5)可知A、B、C三點共線，且AC=(1-r)AB，故|AC|=|(1-r)AB|，又由于r∈[0,2]，故|AC|∈[-|AB|,|AB|]，因此C點位于A點兩側(cè)的線段B′B上，本文將這中操作稱為拓展的凸組合。

下圖在二維空間內(nèi)對式(4)給出一個直觀的分析與闡釋。如圖4所示，已知向量OA，OB，OC分別代表lBS，gBS，Xi。首先由向量OA和OB得到一個向量OE，由凸組合情形分析知OE=r2×lBS+(1-r2)gBS的終點落在線段AB上，再由擴展的凸組合情形分析知，最終得到的向量OF會落到三角形區(qū)域A′B′C′內(nèi)。當(dāng)推廣到n維歐式空間時，OF的終點會落到某一平面的某一個三角形區(qū)域內(nèi)，從圖形來看這個三角形區(qū)域是以AB為中位線，并且線段AB是由局部最優(yōu)解和全局最優(yōu)解連接而成，因此線段AB周圍的區(qū)域非常有可能是一個有潛力的搜索區(qū)域。種群的每一個解及其個體最優(yōu)解和當(dāng)前全局最優(yōu)解都會生成各自的三角形區(qū)域，在n維歐式空間，這些點會落到多個相交平面的三角區(qū)域內(nèi)，這些平面相匯于A點。新的種群相較于上一代種群，整體上會以較大的概率向A點靠攏，因此叫做聚集算子。

首先根據(jù)式(4)，由每一個解的局部最優(yōu)解和全局最優(yōu)解生成一個新解，然后在這個解的周圍區(qū)域進(jìn)行搜索。在算法的前期，由于該個體最優(yōu)解和群體發(fā)現(xiàn)的當(dāng)前全局最優(yōu)解的距離往往較大，兩個解合成的臨吋解和這兩個解的距離比較遠(yuǎn)，該算子有較強的全局搜索能力。隨著算法的進(jìn)行，該算子以較大概率將群體中的解拉到算法群體發(fā)現(xiàn)的當(dāng)前最優(yōu)解附近，展現(xiàn)出對種群較強的引導(dǎo)作用。在算法的后期，全局最優(yōu)解和個體最優(yōu)解的距離一般較小，同時和種群內(nèi)其他的解的距離一般也很小，此階段該算子會在一個較小的區(qū)域內(nèi)進(jìn)行局部搜索，因此這時該算子又展現(xiàn)出算法所需要的局部搜索的能力。

2.2 分散算子

引入分散算子旨在算法搜索的后期種群內(nèi)個體相似性較大的情況下，進(jìn)行擴散以免種群陷入局部最優(yōu)，同吋分散算子能夠提供具有外向趨勢的局部搜索能力。因為如果只是強調(diào)種群不斷聚集，而一旦種群陷入局部最優(yōu)解,如果沒有外部驅(qū)動力就很難跳出來，所以本文提出的分散算子能夠有一定的能力使種群始終保持一定的概率分散開，即有一定的概率朝著遠(yuǎn)離當(dāng)前最優(yōu)解的方向散開。具體迭代公式如下：

Xi=(1-2×r3)×Xb+r3×

(r4×Xw+(1-r4)×Xm)。

(6)

首先對下述公式進(jìn)行簡要的分析，其中隨機數(shù)r3，r4∈[0,1]。

OD=(1-2×r3)×OC+r3×

(r4×OA+(1-r4)×OB)。

(7)

如圖5所示，由式(7)得到的向量OD的中點落在線段CE′上。

OD=(1-2r3)×OC+r3(r4OA+(1-r4)×OB)

=OC+r3(r4×OA+(1-r4)×OB-2r3OC)。

(8)

首先令OE=r4×OA+(1-r4)×OB，則由凸組合的性質(zhì)知，點E落在線段AB上。令OC′=2OC，則C′E=r4×OA+(1-r4)OB-2r3OC，則OD=OC+r3×C′E。

當(dāng)r3∈[0,1]時，向量OD的終端會落在圖5所示的三角形△CA′B′區(qū)域中。由圖5不難發(fā)現(xiàn)，沿著CO的方向便可以將三角形△C′AB平移到三角形△CA′B′的位置。

由于本文中只有當(dāng)3個解的適應(yīng)度值接近的時候才會啟動分散算子，即當(dāng)3個解大體處于同一個等高線k上時，才會用到分散算子。這時，分散算子能夠以一定概率使新生成的解分布在父代等高線k的兩側(cè)。在算法后期該操作能夠使算法得到的新解有一定的幾率從原來的等高線分散開，從而保證算法在后期能夠獲得一定的跳出局部最優(yōu)解的能力。若點A是已發(fā)現(xiàn)的全局最優(yōu)點，如迭代公式(6)能夠保證該算法搜索是在點A周圍一定的范圍內(nèi)進(jìn)行的。若目標(biāo)函數(shù)是多峰函數(shù)，則極有可能由一個局部極小點跳躍到另外一個更有潛力的局部極小點。

3 允許重復(fù)的存檔和種群重置策略

在啟發(fā)式算法中都需要記錄必要的歷史信息，例如粒子群算法[2]必需要記錄粒子的當(dāng)前位置、速度和歷史最優(yōu)位置；蟻群算法[3]必需要記錄各條邊上的信息素濃度，這些信息主要是每個個體的局部信息。在一些算法中，經(jīng)常使用存檔的方式用于存儲優(yōu)秀的個體，再使用存檔影響整個種群的迭代進(jìn)程，特別是一些改進(jìn)的算法中，使用存檔記錄特定的種群個體的方法能夠使算法充分利用優(yōu)秀個體的信息，從而提高算法的整體性能。例如文化算法使用了知識庫來記錄知識，這種知識庫也是一種記錄優(yōu)秀個體的存檔。

更新存檔的方法也有許多，一般的做法是在保證多樣性的前提下使用較好的個體替代存檔中的個體，而且一般要求存檔中個體彼此質(zhì)檢的差異比較大，以保證存檔個體的多樣性，從而使種群在存檔信息引導(dǎo)的迭代過程中不至于過早地收斂。但是本文釆用的存檔策略并不考慮多樣性的問題，允許存檔個體重復(fù)，故稱之為允許重復(fù)的存檔策略。該策略的思路是在種群迭代的過程中把比較優(yōu)秀的個體保存到存檔中，在種群更新很慢甚至是幾乎停滯不前的時候，使用存檔來重置種群。釆用這種測量的目的是充分利用種群迭代過程中的信息，以期獲得較快的算法收斂速度。該策略包含允許重復(fù)的存檔操作和種群重置操作兩個操作，下面對這兩個操作進(jìn)行詳細(xì)敘述。

3.1 存檔操作

存檔操作即將種群迭代過程中的信息保存到一個存檔之中，在更新存檔的時候并不要求存檔中的個體各不相同。操作方式如下：

(1)首先設(shè)置一個存檔，使存檔的規(guī)模和種群規(guī)模一致，這樣做只是便于直接將存檔賦值給當(dāng)前種群的重置種群操作。

(2)在更新存檔時，依次選擇一個當(dāng)前存檔中的空白個體或者年齡最大的個體作為被更新的個體，在每次迭代過程中需要比較當(dāng)代種群的最優(yōu)個體是否優(yōu)于被更新的個體，如果優(yōu)于被更新的個體則使用當(dāng)代種群的最優(yōu)個體替換被更新的個體，否則不更新。根據(jù)以上操作可知，使用這種方式產(chǎn)生的存檔中會出現(xiàn)相同的個體，尤其在算法的后期所有的個體都差別不大，因此這是一種允許重復(fù)的存檔操作。這種操作仍然有效的原因是：在算法的前期存檔內(nèi)的個體變動比較大，存檔的重置起到了類似于輪盤賭在遺傳算法[1]中的作用，即越是優(yōu)秀的個體在存檔中所占的比率越大，因此契合于適者生存的進(jìn)化法則。這種做法使算法收斂速度加快，但也增加了陷入局部最優(yōu)解的可能。

3.2 種群重置操作

根據(jù)允許重復(fù)的存檔操作的特性，單純使用存檔直接更新種群會增加算法陷入局部最優(yōu)解的可能，因此，對種群重置操作需要增加一些調(diào)整以降低這種風(fēng)險。本文的思路是在重置種群時從多種重置方式中選擇一種重置種群。因此對這種重置策略，重置種群操作中重置時機和重置方式的選擇至關(guān)重要。

3.2.1 兩種重置時機

重置時機的選擇需要根據(jù)種群中最優(yōu)解的變動情況決定。例如先前10代以內(nèi)的種群都未曾產(chǎn)生更優(yōu)秀的解，則一般可以認(rèn)為種群的搜索已經(jīng)陷入了局部陷阱。將種群規(guī)模的影響考慮進(jìn)去，就得到本文所采取的判定方式：PopuSize代以內(nèi)的種群產(chǎn)生優(yōu)解的次數(shù)少于PopuSize/10，則重置種群。但這種觸發(fā)機制并不全面，首先這種觸發(fā)方式很難避免在PopuSize代以內(nèi)的無用操作；其次更新代和更新次數(shù)作為參數(shù)需要人為調(diào)節(jié)。基于此，本文又提出另外一種隨機更新方式，即設(shè)置一個很小的概率用于判斷是否重置種群。這樣可以以一定的概率提前結(jié)束掉無用的操作，但是該種群重置策略的概率閾值比較難確定，本文采用的概率是1/PopuSize。

3.2.2 三種重置方式

本文根據(jù)使用存檔信息的多少將重置種群策略分為直接利用存檔重置，間接利用存檔重置和不利用存檔重置。依據(jù)3種不同的思路，本文提出3種存檔的更新方式。

(9)

([UB]j-[LB]j)。

(10)

(3)不使用存檔重置 這種方式不使用存檔和當(dāng)前群體的歷史信息，完全隨機的重置種群。這種方式雖然可以增加種群多樣性，避免算法陷入局部最優(yōu)，但是由于這種方式完全不使用存檔的信息，因此種群搜索模式變壞的可能性極大，則該操作發(fā)生的概率要足夠的小，否則算法會丟失已獲得的有效信息，從而喪失局部搜索能力。

綜合考慮上述兩種重置時機和3種重置方式之后，本文采取一種混合式的重置方式。首先，當(dāng)PopuSize代以內(nèi)的種群產(chǎn)生更優(yōu)解的次數(shù)不超過PopuSize/10時，采用歸檔直接重置的方式(即方式1)重置；然后，當(dāng)PopuSize代以內(nèi)的種群產(chǎn)生更優(yōu)解的次數(shù)不少于PopuSize/10時，產(chǎn)生一個隨機數(shù)r∈[0,1]，若r<1/PopuSize，則采取3種重置方式的混合形式進(jìn)行重置，否則，不重置。對于3種重置方式的混合策略，本文設(shè)置3種方式的使用概率分別為0.5、0.25、0.25。雖然這種重置方式看似比較復(fù)雜,但是其中的邏輯可以完全自洽，相互之間可以形成比較有效的合力。具體的偽代碼如下。

算法1重置操作。

輸入:連續(xù)每代均生成較優(yōu)解的次數(shù)t。

1：if種群產(chǎn)生更優(yōu)解的次數(shù)t≤PopuSize/10

2：直接使用存檔重置種群；

3：else if r1<1/PopuSize then

4: if r2<0.5 then

5： 直接使用存檔重置種群；

6： else if r2<0.75 then

7： 間接使用存檔重置種群；

8： else

9： 隨機重置種群；

10： end if

11：end if

12：將當(dāng)前存檔中的空白個體或者年齡最大的個體確定為目標(biāo)個體；

13：if當(dāng)代種群的最優(yōu)個體是否優(yōu)于目標(biāo)個體then

14： 使用最優(yōu)個體替換目標(biāo)個體；

15：end if

3.3 聚散算法

結(jié)合聚集算子、分散算子和存檔重置策略，本文提出了聚散算法。算法流程如下：第一步初始化種群，

(11)

算法2聚散算法。

1： stepl:初始化種群，并計算目標(biāo)函數(shù)值；

2： step2:更新存檔；

3： step3:判斷是否需要重置種群；

4： step4:使用聚散算子生成新的個體并計算目標(biāo)函數(shù)值；

5： step5:根據(jù)目標(biāo)函數(shù)值更新種群；

6： step6:判斷是否結(jié)束算法，如果不滿足結(jié)束條件就返回到step2.

4 算法對比仿真實驗

為驗證算法的有效性，本文選取CEC測試庫的20個測試函數(shù)，4個經(jīng)典群智能算法：標(biāo)準(zhǔn)粒子群優(yōu)化算法[10](Standard Particle Swarm Optimisation, SPSO2011)，帶復(fù)合實驗向量生成策略和控制參數(shù)的差分進(jìn)化算法[11](Differential Evolution with Composite trial vector generation strategies and control parameters, CoDE)，策略適應(yīng)性的差分進(jìn)化算法[12](Differential Evolution algorithm with Strategy adaptation, SaDE)，智能全局的和聲搜索算法[13](an Intelligent Global Harmony search, IGHS)，并對其進(jìn)行了大量的仿真模擬實驗。這4種優(yōu)化算法屬于3種不同的優(yōu)化框架和搜索機理，能夠反映選擇的比較算法對象的多樣性，其中SPSO是一個十分經(jīng)典的粒子群算法，CoDE和SaDE是經(jīng)典的差分進(jìn)化算法變種，IGHS是一個優(yōu)秀的和聲搜索算法變種，這些算法的收斂速度快、搜索效率高，是常用的基準(zhǔn)算法。本文實驗平臺是：CPU：Intel i7-3770，3.4 GH，內(nèi)存：4 G，軟件：MATLAB 2015b。

4.1 測試函數(shù)

本文在CEC2005[14]和CEC2014[15]測試函數(shù)集中選取了20個測試函數(shù)。具體函數(shù)名稱或表達(dá)式如表1所示，其中fi(x*)是理論計算的函數(shù)最優(yōu)值，每一維的搜索空間均為[-100，100]30，f1～f7是單峰函數(shù)，其余均為多峰函數(shù)。

表1 測試函數(shù)

續(xù)表1

4.2 實驗仿真結(jié)果對比與分析

為驗證算法的有效性，每個算法均獨立運行30次，種群規(guī)模均設(shè)置為10，最大函數(shù)計算次數(shù)為60 000，算法所需的其余參數(shù)均遵循相關(guān)參考文獻(xiàn)的建議。圖6給出5種算法在求解優(yōu)化問題過程在每一次迭代中的最優(yōu)函數(shù)值隨著迭代變量的變化曲線，該在線最優(yōu)函數(shù)值的對比能夠反映每一個算法在整體搜索過程中的動態(tài)變化趨勢。表2給出5種算法求解函數(shù)優(yōu)化問題獲得的最終的最優(yōu)結(jié)果，該結(jié)果能夠反映算法的整體優(yōu)化性能。

從不同算法收斂曲線對比圖6可以直觀看出本文提出的聚散算法GAD的整體性能較為優(yōu)異，具有較優(yōu)的探索功能和收斂性能，在大多數(shù)測試函數(shù)中能夠取得和其他算法相近或更優(yōu)秀的解，從而說明本文提出的聚散算子以及相應(yīng)算法的有效性。

數(shù)值實驗的最終結(jié)果如表2所示，通過對具體實驗數(shù)據(jù)的分析進(jìn)一步說明算法的有效性。表2中分別記錄了每個算法在30次獨立運行中獲得的最優(yōu)的最終函數(shù)值、平均最優(yōu)函數(shù)值、中位值和標(biāo)準(zhǔn)差以及每個算法相對于本文提出的新算法GAD所獲結(jié)果t-檢驗值。通過對平均最優(yōu)值和最小的最優(yōu)值的比較可以看出本文提出的算法在11個函數(shù)中能夠得到相比于其他算法更優(yōu)秀的解。在其他函數(shù)上得到的解和其他算法得到的最優(yōu)解相差不大。

表2 SPSO2011,SaDE,IGHS,CoDE和GAD算法結(jié)果比較

續(xù)表2

續(xù)表2

通過表2可以看出相較于其他算法，本文提出的聚散優(yōu)化算法無論在獲得最優(yōu)解的數(shù)量還是求解的精度上都具有更大的優(yōu)勢。其中算法GAD對CEC2014中的復(fù)合函數(shù)取得的結(jié)果更加優(yōu)秀而穩(wěn)定，其原因是本文對單純形算法的引入和延伸，表明該算法有求解復(fù)雜問題中的巨大潛力。觀察表格中的標(biāo)準(zhǔn)差可以看出，聚散算法的標(biāo)準(zhǔn)差往往較小于其他算法，說明在多次運行的過程中，算法得到的解更加穩(wěn)定，因而具有更好的算法穩(wěn)定性。觀察中位數(shù)和平均值，兩者的差值往往小于其他算法，進(jìn)一步說明了算法的穩(wěn)定性比較好。綜合以上兩個指標(biāo)的分析可以看出，雖然本文提出的聚散優(yōu)化算法GAD本質(zhì)說上是一種隨機優(yōu)化算法，但算法GAD在實現(xiàn)較好搜索的同時，能夠得到更加穩(wěn)定的實驗結(jié)果和算法性能。

4.3 實驗仿真結(jié)果綜合分析

表3給出了5種優(yōu)化算法在求解所有優(yōu)化函數(shù)上相對排名的平均結(jié)果，該數(shù)值越小表明該算法在所有測試函數(shù)上的排名越高，其綜合平均性也就越好。本文提出的聚散優(yōu)化算法GAD在全體函數(shù)上的平均排名是1.65，略優(yōu)于經(jīng)典的多策略集成的差分算法CoDE，明顯的優(yōu)于標(biāo)準(zhǔn)粒子群優(yōu)化算法SPSO2011、策略適應(yīng)性的差分進(jìn)化算法SaDE和智能和聲搜索算法IGHS，進(jìn)一步驗證了所提策略和算法框架的有效性。

表3 SPSO2011,SaDE,IGHS,CoDE和GAD算法排名結(jié)果比較

通過仿真實驗結(jié)果可以看出，本文提出的聚散搜索算子以及相應(yīng)的優(yōu)化算法不僅可以一定程度上保持單純形算法本就具有的局部勘探能力，還具有群體優(yōu)化算法較好的全局搜索能力，因此具有更優(yōu)秀、更穩(wěn)定的算法性能。

5 結(jié)束語

本文在單純形算法的啟發(fā)下，首先提出了聚集算子、分散算子和允許重復(fù)的歸檔重置策略，進(jìn)而提出了聚散算法。通過比較聚散算法與幾個經(jīng)典優(yōu)化算法在求解20個測試函數(shù)時的性能指標(biāo)，說明了聚散算法的有效性和穩(wěn)定性，尤其是對復(fù)雜函數(shù)的求解表現(xiàn)出巨大潛力，從而在進(jìn)化算法中引入確定性優(yōu)化思想的可行性與有效性。允許重復(fù)的歸檔重置策略使算法記錄每次迭代中的有益信息，并且利用當(dāng)前信息引導(dǎo)新的種群的生成，實質(zhì)上是在算法的不同代之間進(jìn)行搜索消息的傳遞與分享，對算法的進(jìn)化方向進(jìn)行宏觀調(diào)控。通過將算子進(jìn)行種群化調(diào)整，成功地將傳統(tǒng)局部搜索的方法拓展成了全局搜索算法，這也初步顯示了種群化是一種將傳統(tǒng)方法全局化拓展的有效方式。未來將嘗試將其他傳統(tǒng)的優(yōu)化方法包括基于梯度的方法進(jìn)行種群化，以期賦予更多具有較強局部搜索能力的傳統(tǒng)優(yōu)化方法以一定程度的全局搜索能力，從而提升相應(yīng)算法的性能。