面向真實世界的測試函數Ⅱ

彭復明

(南京工業職業技術學院 計算機與軟件學院，江蘇 南京 210046)

引言

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

1 傳統測試函數的弊端

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

(1)sphere函數

(3)Rosenbrock函數

其中，D表示維數。

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

現在對于函數(1)、(2)，設計算子S1如下:

Xk+1=0.5Xk

式中:X0:初值，k:進化代數。

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

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

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

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

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

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

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

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

2 面向真實世界的測試函數

2.1 基本測試函數

構造基本測試函數的原則是永遠不讓人找到它的全局最優解［5］。這里一共創建了5個函數，下面就是這些函數的具體描述。

2.2 發展測試函數

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

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

3 實驗數據與分析

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

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

表1 CANO優化發展函數的最優解

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

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

4 結束語

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

［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.