彭復(fù)明

(南京工業(yè)職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)與軟件學(xué)院，江蘇 南京 210046)

引言

多年來(lái)，人們一直使用傳統(tǒng)函數(shù)作為無(wú)約束優(yōu)化的測(cè)試函數(shù)。這些函數(shù)有一個(gè)共同特點(diǎn)，就是全局最優(yōu)解是已知的。也就是說(shuō)，讓算法去尋找一個(gè)已知具體方位的全局最優(yōu)解，這在現(xiàn)實(shí)世界中是荒唐的。如果某算法聲稱已找到了測(cè)試函數(shù)全局最優(yōu)解，別人如何判別它的真實(shí)性呢?要想得到正確的答案，只有重現(xiàn)算法程序并運(yùn)行。然而，重現(xiàn)別人的算法并不是一項(xiàng)輕松的工作。為了解決這一問(wèn)題，本文構(gòu)造了面向真實(shí)世界的測(cè)試函數(shù)，它的全局最優(yōu)解有可能為零或從正向接近零，但全局最優(yōu)解坐標(biāo)卻是未知的。如果某算法找到了此類測(cè)試函數(shù)值為零的具體坐標(biāo)，那么說(shuō)這個(gè)算法找到了該測(cè)試函數(shù)的全局最優(yōu)解就確信無(wú)疑了。

1 傳統(tǒng)測(cè)試函數(shù)的弊端

下面就舉幾個(gè)典型傳統(tǒng)測(cè)試函數(shù)的例子，說(shuō)明它們不能檢測(cè)出算法的真實(shí)水平［1］。

(1)sphere函數(shù)

(3)Rosenbrock函數(shù)

其中，D表示維數(shù)。

sphere函數(shù)與Rastrigin函數(shù)的最優(yōu)解坐標(biāo)在原點(diǎn)(0，0，…，0)，Rosenbrock 函數(shù)的最優(yōu)解坐標(biāo)為(1，1，…，1)。

現(xiàn)在對(duì)于函數(shù)(1)、(2)，設(shè)計(jì)算子S1如下:

Xk+1=0.5Xk

式中:X0:初值，k:進(jìn)化代數(shù)。

只要S1算子運(yùn)行1000多代，就一定收斂到全局最優(yōu)解。

對(duì)于函數(shù)(3)，當(dāng)進(jìn)化計(jì)算到一定代數(shù)后，有一些優(yōu)良個(gè)體出現(xiàn)優(yōu)良分量(1或接近1)。采用如下策略可以使算法快速收斂到全局最優(yōu)解。

假如有優(yōu)良個(gè)體A(‥，Xi，‥，Xj，‥)，(Xi，Xj為優(yōu)良分量)制作多個(gè) A的副本 B(‥，Xm，‥，Xn，‥)。然后，進(jìn)行以下操作:

式中:i、j、m、n 是滿足 i≠m，j≠n 的隨機(jī)整數(shù)。

在算子S2的作用下，B的優(yōu)良分量有可能比A多，它在競(jìng)爭(zhēng)中被保留下來(lái)。如此這般，所有分量都是優(yōu)良分量的個(gè)體很快就會(huì)出現(xiàn)。

算子S1優(yōu)化全局最優(yōu)解設(shè)在原點(diǎn)的測(cè)試函數(shù)能夠較快收斂，但對(duì)于全局最優(yōu)解不在原點(diǎn)的測(cè)試函數(shù)就無(wú)能為力了。算子S2優(yōu)化全局最優(yōu)解的各個(gè)坐標(biāo)分量完全相同的測(cè)試函數(shù)能夠獲得優(yōu)異的測(cè)試性能，可在現(xiàn)實(shí)的世界中，不太可能會(huì)有這樣的優(yōu)化函數(shù)。所以說(shuō)，算子S1、S2對(duì)三個(gè)傳統(tǒng)測(cè)試函數(shù)的測(cè)試性能優(yōu)良并不能說(shuō)明對(duì)現(xiàn)實(shí)優(yōu)化問(wèn)題就會(huì)有良好的效果。由此可以推斷，此類傳統(tǒng)測(cè)試函數(shù)不能測(cè)試出算法的實(shí)際水平。

另外，還有一類測(cè)試函數(shù)［2］，它對(duì)傳統(tǒng)測(cè)試函數(shù)作了改進(jìn)，將測(cè)試函數(shù)的全局最優(yōu)解坐標(biāo)進(jìn)行隨機(jī)設(shè)置，全局最優(yōu)解坐標(biāo)各分量之間沒(méi)有絲毫關(guān)聯(lián)。但它也有致命的弱點(diǎn)，就是全局最優(yōu)解對(duì)算法來(lái)說(shuō)是已知的［3-4］。人們同樣可以設(shè)計(jì)算子，隨機(jī)抽取部分或全部全局最優(yōu)解坐標(biāo)，把它加入到進(jìn)化過(guò)程中，使算子快速收斂到全局最優(yōu)解，這樣的算子同樣經(jīng)不起現(xiàn)實(shí)世界中優(yōu)化問(wèn)題的考驗(yàn)。

綜上所述，目前迫切需要能夠檢測(cè)出算法真實(shí)水平的測(cè)試函數(shù)。一個(gè)好的測(cè)試函數(shù)不應(yīng)該給算法任何不當(dāng)?shù)臋C(jī)會(huì)找到全局最優(yōu)解。按照這個(gè)原則，下面推出面向真實(shí)世界的測(cè)試函數(shù)。

2 面向真實(shí)世界的測(cè)試函數(shù)

2.1 基本測(cè)試函數(shù)

構(gòu)造基本測(cè)試函數(shù)的原則是永遠(yuǎn)不讓人找到它的全局最優(yōu)解［5］。這里一共創(chuàng)建了5個(gè)函數(shù)，下面就是這些函數(shù)的具體描述。

2.2 發(fā)展測(cè)試函數(shù)

在基本測(cè)試函數(shù)的基礎(chǔ)上構(gòu)建了6個(gè)發(fā)展測(cè)試函數(shù)(簡(jiǎn)稱發(fā)展函數(shù)，用 DF(X)表示)。構(gòu)建 DF(X)有三個(gè)要求。1)DF(X)≥0。2)DF(X)的全局最優(yōu)解盡可能設(shè)置為零。3)DF(X)的全局最優(yōu)解的坐標(biāo)是未知的。下面是發(fā)展函數(shù)的具體描述。

式中:N=5，表示基本測(cè)試函數(shù)的個(gè)數(shù)，X∈［－ 5，5］D。

3 實(shí)驗(yàn)數(shù)據(jù)與分析

本文作者使用了協(xié)同進(jìn)化數(shù)值優(yōu)化算法(Coevolutionary Algorithm for Numerical Optimization，簡(jiǎn)稱CANO)對(duì)6個(gè)發(fā)展函數(shù)進(jìn)行數(shù)值優(yōu)化。具體的最優(yōu)解數(shù)據(jù)見(jiàn)表1，表2、表3是CANO算法對(duì)DF5(X)、DF6(X)進(jìn)行數(shù)值優(yōu)化的最優(yōu)解坐標(biāo)，其他4個(gè)函數(shù)的最優(yōu)解坐標(biāo)公布在相關(guān)網(wǎng)站上。

從表1可以看出，已有DF5(X)、DF6(X)的最優(yōu)解達(dá)到零，說(shuō)明算法已找到了DF5(X)、DF6(X)的全局最優(yōu)解。其他4個(gè)發(fā)展函數(shù)的最優(yōu)解也都非常接近零。在沒(méi)有找到使DF(X0)=0的X0坐標(biāo)之前，誰(shuí)也不敢斷言DF(X)的全局最優(yōu)解為零。所以說(shuō)，DF1-4(X)的全局最優(yōu)解是否為零還不得而知。

表1 CANO優(yōu)化發(fā)展函數(shù)的最優(yōu)解

表2 CANO算法對(duì)DF5(X)進(jìn)行數(shù)值優(yōu)化的最優(yōu)解坐標(biāo)

表3 CANO算法對(duì)DF6(X)進(jìn)行數(shù)值優(yōu)化的最優(yōu)解坐標(biāo)

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

由于傳統(tǒng)測(cè)試函數(shù)的全局最優(yōu)解坐標(biāo)是已知的，所以它不能完完全全地檢測(cè)出算法的真實(shí)水平［6］。面向真實(shí)世界的測(cè)試函數(shù)很好地隱藏了全局最優(yōu)解坐標(biāo)，算法只能憑借自身實(shí)力搜索全局最優(yōu)解。所以，它能檢測(cè)出算法的真正水平。面向真實(shí)世界的測(cè)試函數(shù)系統(tǒng)要求算法研究者在http://testfunctions.niit.edu.cn/網(wǎng)站上輸入最優(yōu)解坐標(biāo)。這樣，算法優(yōu)化測(cè)試函數(shù)最優(yōu)解的各項(xiàng)數(shù)據(jù)就自動(dòng)產(chǎn)生了。這些數(shù)據(jù)可以看作第三方的認(rèn)證，提供給雜志社與審稿專家，作為算法優(yōu)劣的有力證據(jù)。

［1］ YAO Xin，LIU Yong，LIN Guang-ming.Evolutionary Programming Made Faster［J］.IEEE Transactions on Evolutionary Computation，1999，3(2):82-102.

［2］ LIANG J J，SUGANTHAN P N，DEB K.Novel Composition Test Functions for Numerical Global Optimization［M］//Proceedings of IEEE International Swarm Intelligence Symposium.Italy:Messina，2005:68-75.

［3］ TANG Ke，LI Xiao-dong，SUGANTHAN P N，YANG Zhenyu，WEISE Thomas.Benchmark Functions for the CEC'2010 Special Session and Competition on Large-Scale Global Optimization［EB/OL］.［2014-2-25］.http://www.researchgate.net/publication/228932005_Benchmark_functions_for_the_CEC%272008_special_session_and_competition_on_large_scale_global_optimization.

［4］ TANG Ke，LI Xiao-dong，SUGANTHAN P N，YANG Zhenyu，WEISE Thomas.Benchmark Functions for the CEC'2008 Special Session and Competition on Large Scale Global Optimization［EB/OL］.［2014-2-25］.http://www.researchgate.net/publication/228932005_Benchmark_functions_for_the_CEC%272008_special_session_and_competition_on_large_scale_global_optimization

［5］ PENG Fu-ming.Real World Oriented Test Functions［M］//The Proceedings of 2011 International Conference on Computer Science and Service System.2011，2:1499-1505.

［6］ PENG Fu-ming.Novel Composition Test Functions Algorithm for Numerical Optimization M］//The Proceedings of 2011 International Conference on Computer Science and Service System.2011，4:3348-3352.