隨機(jī)性優(yōu)化算法有效性定量對(duì)比評(píng)價(jià)方法

李鵬飛，石正軍

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

1 引言

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

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

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

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

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

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

2 基于概率均值的有效性對(duì)比評(píng)價(jià)方法

2.1 針對(duì)單個(gè)算例的評(píng)價(jià)方法

2.1.1 定義

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

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

定義2.1.2 如果

EAB＞0.5

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

2.1.2 計(jì)算公式

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

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

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

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

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

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

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

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

由此可知，EAB的統(tǒng)計(jì)意義即為從分布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算法在求解該算例時(shí)更有效，這是得益于XA的均值較小。但是，由于XA的方差較大，A算法的有效性優(yōu)勢(shì)并不顯著。

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

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

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

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

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

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

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

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

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

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

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

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

如圖4印證了上述推斷。

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

2.1.5 替代評(píng)價(jià)值

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

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

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

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

對(duì)每一個(gè)優(yōu)化結(jié)果f，定義其替代評(píng)價(jià)值falt：

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

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

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

2.2 針對(duì)算例集的評(píng)價(jià)方法

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

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

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

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

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

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

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

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

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

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

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

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

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

表4 異步模式對(duì)同步模式的相對(duì)有效概率列表

4 結(jié)論

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

以同步更新PSO算法和異步更新PSO算法為對(duì)比評(píng)價(jià)對(duì)象，將上述方法實(shí)例化。針對(duì)無(wú)約束單目標(biāo)連續(xù)變量?jī)?yōu)化函數(shù)算例集的評(píng)價(jià)結(jié)果表明，異步更新模式PSO算法在該類問(wèn)題上綜合有效性較高，與早期研究觀點(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.