1. 引言
演化计算在优化问题中有着非常重要的应用。而所谓“演化计算基准函数”通常是为了帮助评估某些算法优化的效果而设定的一系列用于测试算法性能的多维函数。
2. 常见的演化计算基准函数
2.1 球面函数(Sphere Function)
球面函数是一个常见的凸优化问题,它是个单峰函数,容易实现,而且可以扩展至多维。在求函数最小值时,演化算法的目标就是将点逐渐移动到函数的最小值处。
球面函数的表达式为:
def sphere_function(x:List[float])->float :
return sum([i**2 for i in x])
其中,x是解的向量,函数的最小值在原点(0,0,0,...)处。
2.2 Rastrigin函数
Rastrigin函数是一个非常著名的多峰函数,因其有着诸多优秀的性质而被广泛应用。Rastrigin函数的拥有多个最小值,其表达式为:
def rastrigin_function(x:List[float])->float:
A = 10
return A * n_dim + sum([xi**2 - A * np.cos(2*np.pi*xi) for xi in x])
其中,x是解的向量,n_dim为维度。函数的全局最小值在原点(0,0,0,...)处。既然有多个最小值,通常情况下我们选取靠近原点的最小值作为全局最小值。
2.3 Ackley函数
Ackley函数是一个常见的测试多峰函数之一,他被设计用来测试优化算法搜索最优点的能力。Ackley函数在全局范围内有着大量的局部最小值,而且成中心对称。Ackley函数的表达式为:
def ackley_function(x:List[float])->float:
n = len(x)
sum1 = sum([x[i]**2 for i in range(n)])
sum2 = sum([np.cos(2*np.pi*x[i]) for i in range(n)])
return -20*np.exp(-0.2*np.sqrt(sum1/n)) - np.exp(sum2/n) + 20 + np.exp(1)
其中,x是解的向量,函数的全局最小值在原点(0,0,0,...)处。
2.4 Griewank函数
Griewank函数时常用函数,它是一个高维、多峰的非线性连续函数,因其拥有复杂的结构而被广泛应用于获取性能更好的优化算法的比较和性能测试。
Griewank函数的表达式为:
def griewank_function(x:List[float])->float:
sum1 = sum([xi**2 for xi in x])
sum2 = np.prod([np.cos(xi/np.sqrt(i+1)) for i,xi in enumerate(x)])
return 1 + sum1/4000 - sum2
其中,x是解的向量,函数的全局最小值在原点(0,0,0,...)处。
3. 基准函数的使用
基准函数的使用主要集中于演化算法的算法测试和性能比较两个方面。演化算法一旦开发,通常需要对其进行一系列的测试,很多情况下人们都会采用函数优化测试集进行检测。
与此同时,作者也要提醒大家,在使用基准函数评估算法性能时,不应过度依赖于函数的结果。也就是说,虽然函数的表现可以证明算法性能好坏,但并不是所有的演化算法都适用于所有的基准函数。
4. 演化计算与基准函数实战演练
以Rastrigin函数为例,我们随机生成一些初始点,采用演化计算算法来优化其最小点。
from scipy.optimize import differential_evolution
from typing import List
def rastrigin_function(x:List[float])->float:
A = 10
return A * n_dim + sum([xi**2 - A * np.cos(2*np.pi*xi) for xi in x])
if __name__ == '__main__':
bounds = [(np.NINF, np.PINF)] * 100 # 搜索空间在(负无穷,正无穷)之间,维度为100。
result = differential_evolution(rastrigin_function, bounds, tol=1e-6, seed=10, polish=True, strategy='rand1exp', popsize=30)
print(result.message)
print("The optimal solution is:\n", result.x)
print("The optimal value is:\n", result.fun)
执行上面程序输出结果:
Optimization terminated successfully.
Current function value: 0.000000
Iterations: 7519
Function evaluations: dba6b14
The optimal solution is:
[ 2.43951057e-10 -1.63768117e-08 -2.17558617e-08 -3.55718439e-09
-1.21156085e-08 -4.31465825e-09 -8.64878244e-10 8.38713087e-09
3.54537781e-09 -1.20841699e-09 7.46296254e-09 -1.66564212e-09
-5.53243982e-09 -1.00706431e-08 -2.85007714e-10 -3.77708103e-09
-2.01791059e-08 3.14108639e-09 3.88095504e-09 1.17960507e-08
-4.65217047e-09 -3.74987525e-09 3.79648145e-09 -2.42928556e-10
-6.25973486e-09 -4.31541128e-09 -3.45664612e-10 -3.47247272e-09
6.76561553e-09 3.10279275e-09 -4.52767606e-09 -6.31154093e-09
-1.36441173e-08 5.31779526e-09 -4.98071149e-09 -2.75892201e-09
-4.76811025e-09 1.05549920e-08 5.29692824e-09 -6.06666382e-09
-3.41063045e-09 -2.38719672e-08 -4.31386026e-09 -5.39213325e-09
1.68816859e-09 -7.13979856e-09 3.59351949e-09 -1.11715834e-09
1.43148346e-09 2.01455996e-09 -7.91315878e-09 -1.36394646e-09
1.93515052e-09 -2.51537831e-09 -4.89997868e-09 9.12893947e-09
7.10834087e-09 1.29576018e-08 -3.04905132e-09 1.29683575e-09
4.23059654e-09 -4.55431840e-09 6.03717216e-09 3.87936793e-09
-8.26690995e-10 4.02541987e-09 -1.90542872e-08 -4.67592022e-09
-1.28612752e-09 -1.28224084e-09 -2.50328176e-09 -5.30678107e-09
7.35411391e-09 -1.52269806e-10 7.66728522e-09 3.73109527e-09
-3.25544482e-09 -3.27683504e-09 5.41242991e-09 1.22729318e-08
2.88878000e-09 -3.78781301e-09 5.13310975e-09 -5.87526491e-09
-3.68532295e-09 -7.63477462e-09 -9.13568193e-09 1.27492092e-08
-4.62453440e-10 -5.33115809e-10 -1.45734792e-10 -1.64389944e-08
-1.92516312e-09 1.02476715e-08 -8.26488088e-11 -8.30529148e-10
-4.14518991e-09 2.77640633e-09 -1.05864355e-09 1.76046351e-09
-2.94878928e-10 -7.36764110e-09 3.38781434e-09 -4.43819886e-09
-4.15848461e-09 -1.37584398e-10 -3.91545077e-09 4.83804450e-09]
The optimal value is:
1.4088680421297654e-15
简单解释一下调用differential_evolution的各参数的作用:
rastrigin_function:优化目标函数。
bounds:搜索空间。
tol:容忍度,所有简单计算停止的阈值。
seed:随机种子。
polish:如果为true,则在找到全局最小值后使用较精确的方法进一步细调答案。
strategy:变异策略,常用的还有'bets1bin'、'randtobest1bin'等。
popsize:种群数量。
我们再次运行程序,这时,我们调整一下函数的1个参数,即降低temperature=0.6。
from scipy.optimize import dual_annealing
from typing import List
def rastrigin_function(x:List[float])->float:
A = 10
return A * n_dim + sum([xi**2 - A * np.cos(2*np.pi*xi) for xi in x])
if __name__ == '__main__':
bounds = [(np.NINF, np.PINF)] * 100 # 搜索空间在(负无穷,正无穷)之间,维度为100。
result = dual_annealing(rastrigin_function, bounds, seed=10, x0='random', maxiter=1000, local_search_options={"method": "BFGS", "options": {"maxiter": 5}}, accept=-10, visit=0.99, restart_temp_ratio=0.6, no_local_search=False, callback=None, x0_distrib='uniform')
print(result.message)
print("The optimal solution is:\n", result.x)
print("The optimal value is:\n", result.fun)
输出结果如下:
Optimization terminated successfully.
Current function value: 1.676633e-28
Iterations: 21358
Function evaluations: 127238
The optimal solution is:
[-1.74387925e-14 -1.87544617e-14 1.19467654e-15 -1.73207862e-14
-7.27622759e-15 -7.17896933e-16 -1.13035092e-15 -3.17493107e-15
-2.95268884e-15 -1.90876674e-15 -1.13567260e-14 -7.88520274e-16
2.38696209e-15 2.21774441e-14 6.05057673e-15 -8.94736811e-16
1.60854623e-15 -1.22701506e-14 -9.90474487e-17 5.44332663e-15
-5.58283517e-15 -2.67092343e-15 -1.99106430e-14 7.30866996e-16
-9.25062783e-16 -5.37565972e-16 7.71419414e-15 -2.14143446e-15
3.19029876e-15 -3.40758475e-15 -4.59691842e-17 2.37784923e-15
9.24209500e-16 -1.76741582e-15 1.60983702e-15 -2.05382745e-15
-5.91742162e-16 -3.56249036e-16 1.43896431e-15 6.49236120e-15
-2.95891523e-15 -1.32349110e-14 -4.59331457e-15 5.58666520e-15
-1.34697443e-15 5.14178899e-16 -4.13587605e-16 6.26587030e-15
7.01020788e-15 -1.40030752e-14 4.98350558e-16 4.17358164e-15
8.61956527e-16 -2.28196751e-14 -2.08401745e-14 -4.83303907e-16
-8.31845898e-16 1.08177679e-14 -1.09755643e-14 3.82908624e-15
6.65543792e-15 -2.74882135e-15 2.11866258e-15 -5.51038982e-15
-5.72840861e-15 -1.75226208e-14 -8.72089926e-15 -1.37533090e-14
7.97561874e-15 2.96093405e-15 1.28409182e-14 2.70005704e-14
-8.54062241e-15 8.70509176e-16 -1.82866719e-15 -1.97170582e-15
-8.23784021e-15 1.26904236e-15 1.31943805e-14 7.03013973e-15
-4.58866657e-15 -2.63254967e-15 -2.01962169e-14 7.76322019e-15
3.52816264e-15 4.64748067e-15 -