面向真實世界的測試函數(shù)Ⅱ

彭復(fù)明

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

引言

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

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

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

(1)sphere函數(shù)

(3)Rosenbrock函數(shù)

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

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

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

Xk+1=0.5Xk

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

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

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

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

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

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

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

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

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

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

2.1 基本測試函數(shù)

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

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

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

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

3 實驗數(shù)據(jù)與分析

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

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

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

表2 CANO算法對DF5(X)進行數(shù)值優(yōu)化的最優(yōu)解坐標

表3 CANO算法對DF6(X)進行數(shù)值優(yōu)化的最優(yōu)解坐標

4 結(jié)束語

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