隨機(jī)性優(yōu)化算法有效性定量對比評價方法

李鵬飛，石正軍

中國工程物理研究院計算機(jī)應(yīng)用研究所，四川綿陽621900

1 引言

實(shí)際工程優(yōu)化問題往往具有大規(guī)模、非線性、多極值、多目標(biāo)、不連續(xù)等特點(diǎn)。傳統(tǒng)優(yōu)化算法，特別是基于梯度的優(yōu)化方法往往不適用于上述情形或得不到滿意解。近年來，隨機(jī)性優(yōu)化算法，特別是群體智能優(yōu)化算法由于其優(yōu)秀的問題適應(yīng)性，良好的全局尋優(yōu)能力，自然的并行性等特點(diǎn)成為優(yōu)化算法領(lǐng)域的研究與應(yīng)用熱點(diǎn)。新的隨機(jī)性優(yōu)化算法以及已有算法的改進(jìn)版本被不斷提出。

隨機(jī)性優(yōu)化算法需要在尋優(yōu)搜索過程中對搜索方向引入隨機(jī)變化，從而降低搜索陷入局部最優(yōu)的風(fēng)險。然而，隨機(jī)性的引入也使得算法尋優(yōu)路徑和最終結(jié)果具有不可重復(fù)性和不確定性，單次尋優(yōu)結(jié)果無法真實(shí)反映算法的有效性（本文所指尋優(yōu)結(jié)果均為算法求得的最優(yōu)目標(biāo)函數(shù)值）。因此，隨機(jī)性優(yōu)化算法的有效性，即算法（下文所指算法均為隨機(jī)性優(yōu)化算法）在一定計算開銷下獲得理想解或滿意近似解的能力，應(yīng)該是算法多次求解結(jié)果表現(xiàn)出的宏觀性質(zhì)。鑒于求解結(jié)果的不確定性，不同算法之間的有效性優(yōu)劣關(guān)系應(yīng)是概率意義上的關(guān)系。

一種簡單易行的對比評價不同算法有效性的方法是比較不同算法針對一個或一組算例的成功率，即獲得滿意解的求解次數(shù)占總求解次數(shù)的比例[1]。這種方法需要已知算例的理論最優(yōu)解及人為設(shè)定“滿意解”的標(biāo)準(zhǔn)。另一種直觀方法是比較不同算法針對同一算例多次求解結(jié)果的均值[2]，或者綜合考慮均值和成功率[3]，但上述方法均為確定性的對比評價方法。

一種基于概率意義的對比評價方法是“t檢驗(yàn)[4]”，該方法對總體符合正態(tài)分布的多個個體（即算法多次求解結(jié)果）進(jìn)行針對總體分布的均值是否滿足既定假設(shè)范圍的假設(shè)檢驗(yàn)[5]。在“t檢驗(yàn)”中，需要已知算例的理論最優(yōu)解，需要人為設(shè)定零假設(shè)中的總體正態(tài)分布的均值與理論最優(yōu)解的接近程度（即假設(shè)的均值取值范圍），最后由不同算法滿足假設(shè)的顯著性高低來判斷不同算法的有效性高低。該方法操作較復(fù)雜，且最終不能得到一個概率來定量反映一種算法較另一種算法有效的可能性大小。

本文方法對兩種算法多次尋優(yōu)結(jié)果進(jìn)行統(tǒng)計分析，最終得到一個因子反映一種算法比另一種算法更有效的可能性大小。該方法理論簡單，易于操作，且不需要已知算例理論最優(yōu)值，是一種概率意義上的有效性定量對比評價方法。

最后，本文給出以該方法對比評價采用同步或異步更新全局最優(yōu)粒子信息模式的兩種標(biāo)準(zhǔn)粒子群優(yōu)化算法版本，在求解無約束單目標(biāo)連續(xù)變量優(yōu)化問題時的有效性相對關(guān)系的實(shí)例。

2 基于概率均值的有效性對比評價方法

2.1 針對單個算例的評價方法

2.1.1 定義

定義2.1.1設(shè)A、B為兩種隨機(jī)性優(yōu)化算法，對單個算例（本文所指算例均為最小化優(yōu)化問題），在既定的同等計算開銷下，A、B算法多次尋優(yōu)得到的目標(biāo)函數(shù)值滿足的總體分布為分別為DA、DB，x、y為隨機(jī)變量。定義

為A算法相對B算法在該算例上的相對有效概率，其中p(x＜y)表示x小于y的概率。

定義2.1.2 如果

EAB＞0.5

則稱A算法比B算法在該算例上更有效。

2.1.2 計算公式

針對某特定算例，在既定的同等計算開銷下，由A、B兩種算法分別進(jìn)行na、nb次獨(dú)立尋優(yōu)求解，獲得相應(yīng)的優(yōu)化結(jié)果樣本集合XA及XB。“獨(dú)立”即指各次求解過程中的偽隨機(jī)數(shù)序列無關(guān)。

與t檢驗(yàn)類似，需假設(shè)

根據(jù)大數(shù)定理知

實(shí)際情況不可能對一種算法執(zhí)行無限多次，往往綜合考慮算法開銷和評價精度設(shè)定執(zhí)行次數(shù)。根據(jù)所獲得的樣本集合XA及XB求得樣本的均值與方差后，即可由式（1）得到對應(yīng)的總體正態(tài)分布DA及DB的均值與方差。

在分布DB中隨機(jī)選取一個隨機(jī)變量y，其值大于（即劣于）給定值x0的概率如下：

將x0視為變量，設(shè)函數(shù)P(x)表示B算法單次求得解的值劣于變量x的概率，則有

進(jìn)一步地，設(shè)x～DA，則P(x)在分布DA上的均值表示如下：

將式（2）代入式（3），結(jié)合定義2.1.1，可知相對有效概率的計算公式為：

由此可知，EAB的統(tǒng)計意義即為從分布DA與DB中分別單次隨機(jī)抽樣x與y，x小于y（即A算法單次尋優(yōu)結(jié)果較B算法更準(zhǔn)確）的概率平均值。

2.1.3 示例

設(shè)XA、XB分別為A、B算法多次求解某最小化優(yōu)化算例最優(yōu)目標(biāo)函數(shù)值的樣本集合，不妨設(shè)XA～N(0，1)，XB～N(0.2，0.25)，xa∈XA，xb∈XB。xa與xb滿足的概率密度函數(shù)如圖1所示。

由式（4）易得EAB≈0.571。由定義2.1.2可知，A算法較B算法在求解該算例時更有效，這是得益于XA的均值較小。但是，由于XA的方差較大，A算法的有效性優(yōu)勢并不顯著。

2.1.4 相對有效概率與均值和方差的關(guān)系

（1）與均值的關(guān)系

圖1 N(0，1)與N(0.2，0.5)概率密度函數(shù)

由于式（4）不涉及被測試算例的理論最優(yōu)值，在固定DA與DB方差的前提下，相對有效概率EAB由DA與DB的相對位置決定，即EAB只與二者的均值差(μB-μA)有關(guān)。由圖2可知，EAB與均值差的關(guān)系有如下特點(diǎn)：

（i）EAB隨(μB-μA)單調(diào)上升。DA的均值比DB的均值越小，A算法相對B算法越有效。

（ii）在(μB-μA)～EAB平面上，(μB-μA)與EAB關(guān)于點(diǎn)（0，0.5）中心對稱。特別地，A算法比B算法有效的充要條件即是μA＜μB，這與t檢驗(yàn)類似。

圖2 相對有效概率與均值差關(guān)系

（2）與方差的關(guān)系

固定DB的方差，圖3反映了在不同DA方差條件下相對有效概率與均值差關(guān)系曲線的變化。

圖3 不同DA方差條件下的相對有效概率與均值差關(guān)系

由圖3可以看出，當(dāng)μA<μB時，隨著σA增大，同等均值差條件下，A算法對B算法的有效性逐漸減小。意味著采用該方法評價，即使A算法求得的解分布的均值占優(yōu)，如果其方差變大，即算法的穩(wěn)定性變差，A算法的相對有效性優(yōu)勢會下降。反之，當(dāng)μA＞μB時，隨著σA增大，同等均值差條件下，A算法對B算法的有效性逐漸增大。即尋優(yōu)結(jié)果的均值處于劣勢的算法，若求解結(jié)果的分散性變大，算法有效性的劣勢會減小，這是因?yàn)橛懈嗟木盗觿菟惴ǖ慕庥袡C(jī)會落在均值優(yōu)勢算法解分布的主體區(qū)間內(nèi)。

從式（4）可以推斷，如果兩個解分布的方差相對均值差極大，那么，二者所滿足的正態(tài)分布將退化為均勻分布。按照定義2.1.1，此時EAB應(yīng)恒為0.5。反之，若兩個解分布的方差相對均值差極小，此時正態(tài)分布退化為狄拉克δ分布，只在二者的均值附近存在概率密度，此時相對有效概率應(yīng)該滿足如下的分段函數(shù)：

如圖4印證了上述推斷。

圖4 極端方差情形下的相對有效概率與均值差關(guān)系

2.1.5 替代評價值

采用上述有效性對比評價方法，必須首先根據(jù)算法多次尋優(yōu)結(jié)果計算出總體分布的均值和方差。然而，在實(shí)際優(yōu)化問題中，特別是在目標(biāo)函數(shù)高度非線性以及存在多極值點(diǎn)的情形，同一算法不同次優(yōu)化同一問題的結(jié)果可能相差若干量級。

表1表示用標(biāo)準(zhǔn)粒子群算法（PSO）在一定計算開銷前提下10次獨(dú)立求解二維Rosenbrock函數(shù)最小值的結(jié)果，該函數(shù)的理論最優(yōu)值為0，由表1可認(rèn)為有8次求解結(jié)果有效。

表1 PSO算法求解Rosenbrock函數(shù)最小值10次結(jié)果

由表1直接計算出優(yōu)化結(jié)果的均值約為1.80，顯然，這個均值并不能真實(shí)反映這10組解與理論解接近程度的平均水平。這是由于量級差異巨大，多數(shù)相對極小的有效解被少數(shù)相對極大的錯誤解覆蓋。要解決這一問題，需要對真實(shí)的目標(biāo)函數(shù)值做一定變換再進(jìn)行有效性評價。

對每一個優(yōu)化結(jié)果f，定義其替代評價值falt：

其中，fopt為算例函數(shù)的理論最優(yōu)值，如果理論值未知，則令

其中，fbest為需對比的兩種算法多次求解該問題所有結(jié)果的最佳值，ε為一個小量，不妨設(shè)為10-20。

經(jīng)過以上變換后，10次求解結(jié)果的替代評價值的均值約為－9.7，表示10次求解結(jié)果與理論最優(yōu)值或?qū)崪y最佳值的差距平均數(shù)量級約為－9.7，較真實(shí)地反映了10組解的有效水平。

2.2 針對算例集的評價方法

比較兩種算法有效性的優(yōu)劣并不能只針對一個算例，而要針對一個算例集，且這個算例集應(yīng)盡可能包含該算法可能遇到的所有實(shí)際優(yōu)化問題類型。

如果一種算法相對另一種算法在一個近似代表某類優(yōu)化問題的算例集上綜合表現(xiàn)出的有效性更高，就可以認(rèn)為該算法在該類實(shí)際優(yōu)化問題中較后者更有效。

定義2.2設(shè)S為包含n個測試算例的集合，si∈S，i=1，2，…，n，為A算法相對B算法針對算例si的相對有效概率，如果，則稱A算法相對B算法在求解算例集S上更有效。

3 粒子群優(yōu)化算法有效性對比評價實(shí)例

Eberhart與Kennedy提出的粒子群優(yōu)化算法（PSO）是一種典型的基于群體智能的隨機(jī)性優(yōu)化算法[6-7]。PSO算法具有概念簡單，容易實(shí)現(xiàn)，調(diào)節(jié)參數(shù)少等優(yōu)點(diǎn)，已經(jīng)成為智能優(yōu)化算法的研究熱點(diǎn)。

標(biāo)準(zhǔn)PSO算法中各個粒子的位置更新公式如下：其中，vk、xk分別為在第k次迭代過程中該粒子的速度和位置矢量，pb、pg分別為該粒子的歷史最優(yōu)位置和整個粒子群的全局最優(yōu)位置矢量，ω、c1、c2為算法控制參數(shù)，rand1、rand2為隨機(jī)數(shù)。

根據(jù)pg更新方式的不同，可將標(biāo)準(zhǔn)PSO算法分為同步更新和異步更新兩種模式。在同步更新模式中，同一代的所有粒子適應(yīng)度計算完畢后再更新pg；在異步更新模式中，任一粒子完成適應(yīng)度計算后即與當(dāng)前pg比較，實(shí)時更新pg。同步模式算法的早熟風(fēng)險較小，但收斂速度較慢；異步模式的算法收斂速度快，并行性能好，但是早熟風(fēng)險較大。在求解多數(shù)優(yōu)化問題時，異步模式更為有效[8]。

作為第2章方法的實(shí)例，本章以10個無約束單目標(biāo)函數(shù)優(yōu)化算例組成的算例集為測試對象，對采用同步或異步全局最優(yōu)粒子信息更新模式的兩種標(biāo)準(zhǔn)PSO算法版本進(jìn)行有效性對比評價。該測試算例集包含了單極值、多極值、周期性、間斷梯度、病態(tài)梯度、含奇異點(diǎn)、罰函數(shù)形式、超平面解集、m in（max）等多種函數(shù)形態(tài)，大致代表無約束單目標(biāo)連續(xù)變量優(yōu)化這一類問題。

兩種算法模式在同等計算開銷前提下（最大進(jìn)化代數(shù)均為150），對上述算例集中各個算例各自獨(dú)立求解100次的結(jié)果如表2、表3所示。

設(shè)異步模式PSO算法為A算法，同步模式PSO算法為B算法，由式（4）可計算出A算法相對B算法在各個算例與整個算例集上的相對有效概率，如表4所示。

通過表4可以看出，按照定義2.1.2，異步模式PSO算法對同步模式PSO算法在所有測試算例上更有效。按照定義2.2，前者比后者在該算例集上更有效，且相對有效概率約為0.709。如果假設(shè)該算例集能夠較好地近似代表無約束單目標(biāo)優(yōu)化問題，則可以認(rèn)為對于某典型無約束單目標(biāo)連續(xù)變量優(yōu)化問題，異步模式PSO算法相比同步模式PSO算法求得更有效解的可能性為70.9%左右，這也印證了文獻(xiàn)[8]的觀點(diǎn)。

表2 異步更新模式PSO算法針對算例集的求解結(jié)果

表3 同步更新模式PSO算法針對算例集的求解結(jié)果

表4 異步模式對同步模式的相對有效概率列表

4 結(jié)論

提出了一種基于概率均值的隨機(jī)性優(yōu)化算法有效性定量對比評價方法，定義了一個因子，定量反映一種算法相對另一種算法在求解單個算例上更有效的可能性大小。對該因子的理論基礎(chǔ)、計算公式進(jìn)行了說明，討論了該因子與兩種算法多次求解結(jié)果的均值和方差之間的關(guān)系。進(jìn)一步將該方法推廣到針對一個算例集，以代表在一類實(shí)際優(yōu)化問題上對兩種算法進(jìn)行有效性對比評價。

以同步更新PSO算法和異步更新PSO算法為對比評價對象，將上述方法實(shí)例化。針對無約束單目標(biāo)連續(xù)變量優(yōu)化函數(shù)算例集的評價結(jié)果表明，異步更新模式PSO算法在該類問題上綜合有效性較高，與早期研究觀點(diǎn)一致。

[1]Ali M M，T?rn A.Population set-based global optimization algorithms：some modifications and numerical studies[J].Computers and Operations Research，2004，31（10）：1703-1725.

[2]Zaharaa E，Kao Y T.Hybrid Nelder-Mead simplex search and particle swarm optimization for constrained engineering design problem s[J].Expert Systems with Applications，2009，36（2）：3880-3886.

[3]Qin A K，Huang V L，Suganthan P N.Differential evolution algorithm with strategy adaptation for global numerical optimization[J].IEEE Trans on Evolutionary Computation，2009，13（2）：398-417.

[4]Harnett D.Statistical methods[M].3rd ed.Reading：Addison-Wesley，1982：247-297.

[5]Hassan R，Cohanim B，De Weck O，et al.A comparison of particle swarm optimization and the genetic algorithm[C]//Proceedings of the 46th A IAA/ASME/ASCE/AHS/ASC Structures，Structural Dynamics and Materials Conference，Austin，TX，2005：1-13.

[6]Kennedy J，Eberhart R C.Particle swarm optimization[C]//Proceedings of the IEEE International Conference on Neural Networks，Piscataway，NJ，1995：1942-1948.

[7]Shi Yuhui，Eberhart R C.A modified particle swarm optimizer[C]//Proceedings of the IEEE Congress on Evolutionary Computation（CEC 1998），Piscataway，NJ，1998：69-73.

[8]Kennedy J.Methods of agreement：inference among the eleMentals[C]//Proceedings of the 1998 International Symposium on Intelligent Control，Piscataway，NJ，1998：883-887.