6.2.2 佳点集萤火虫算法
1.佳点集
佳点集(good-point set)理论是由华罗庚与王元两位数学家在《数论在近似分析中的应用》一书中提出的,该书说明了佳点集理论的性质:使用佳点集选择点比随机选择点的偏差小得多[12]。清华大学张铃教授利用佳点集理论对遗传算法进行了改进,并从理论与实验的角度分析了算法性能的提高[13]。
佳点集相关定义和定理如下。
①假设Gm是m维欧氏空间中的单位立方体,即〈x〉=(x 1,x 2,…,x s),其中0≤x i≤1(i=1,2,…,s)。③设φ(n)满足φ(n)=C(〈r〉,ε)n-1+ε,其中C(〈r〉,ε)是只与〈r〉和ε(ε是任意小的正数)有关的常数,则称Pn(i)为佳点集,〈r〉为佳点。除此之外,取rj={ej,1≤j≤m},则〈r〉也是佳点[12]。
将佳点集应用到近似积分中,其误差的阶仅仅和样本数n有关系,和样本的空间维数m没有关系,这种特点使得佳点集在高维近似计算中有很好的表现。经过计算分析,佳点集的偏差为O(n-1+ε),而使用随机方法的偏差为O(n-1/2(loglog n)1/2),其表现明显不如佳点集方法[13]。
在图6-1中,在三维空间内随机生成100个点,其中图6-1(a)是采用佳点集算法生成的,图6-1(b)是使用随机算法生成的。可以很直观地看出,佳点集算法生成的点在空间中具有非常好的均匀分布性。
图6-1 佳点集算法示例
2.佳点集萤火虫算法
我们将佳点集与萤火虫算法相结合,提出了佳点集萤火虫算法(Good-point set Firefly Algorithm,GFA),该算法主要是使用佳点集对萤火虫算法初始化萤火虫阶段进行优化,防止初始萤火虫分布不均匀导致陷入局部最优解。佳点集萤火虫算法的主要步骤如下。
步骤1:初始化萤火虫算法的基本参数,包括萤火虫数目、位置维度、最大吸引度、步长因子、最大迭代次数。
步骤2:使用佳点集初始化萤火虫位置,并根据该位置计算该萤火虫的最大荧光度。
步骤3:计算群体中萤火虫之间的相对亮度和吸引度,并进行比较判断移动方向。
步骤4:更新萤火虫的位置,对最佳位置萤火虫进行随机移动。
步骤5:根据更新后的位置,重新生成细胞阵列,并根据新的0/1序列计算亮度。
步骤6:当到达最大搜索次数时,转到下一步;否则进行下一次迭代,迭代次数加1,转到步骤3。
步骤7:输出全局极值点,即最优萤火虫。
3.佳点集萤火虫算法算例
下面用传统萤火虫算法和佳点集萤火虫算法分别对Ackley函数、Drop-Wave函数、Griewank函数、Holder Table函数和Schaffer函数N.2这5个经典的测试函数算例进行求解,通过对收敛次数和收敛稳定性等方面进行统计,对两种算法的性能进行比较。
(1)测试函数
本节采用了5个经典测试函数,其分别如下。
①Ackley函数
a.函数描述
该函数的数学表达式如下:
b.函数介绍
Ackley函数广泛用于测试优化算法,其维度为d。图6-2所示是二维形式的Ackley函数,其特点是外部区域几乎平坦,中央有一个大孔。
图6-2 Ackley函数
c.输入域
Ackley函数通常在超立方体x i∈[-32.768,32.768],i=1,2,…,d上求解,它也可应用于较小的域。
d.全局最小极值点
②Drop-Wave函数
a.函数描述
该函数的数学表达式如下:
b.函数介绍
Drop-Wave函数是一种多模而且非常复杂的函数,维度为2,如图6-3所示。其中,图6-3(b)显示了在较小输入域上的函数表现,表现了其复杂的特征。
图6-3 Drop-Wave函数
c.输入域
Drop-Wave函数通常在二维平面x i∈[-5.12,5.12],i=1,2上求解。
d.全局最小极值点(https://www.daowen.com)
③Griewank函数
a.函数描述
该函数的数学表达式如下:
b.函数介绍
Griewank函数具有许多广泛分布的局部极小值,并且这些局部极小值的分布有规律性,其维度为d。图6-4展示了该函数在不同域中的复杂度。
c.输入域
Griewank函数通常在超立方体x i∈[-32.768,32.768],i=1,2,…,d上求解。
d.全局最小极值点
④Holder Table函数
a.函数描述
该函数的数学表达式如下:
图6-4 Griewank函数
b.函数介绍
Holder Table函数的维度为2,具有多个局部最小值,同使包含全局最小值,具体分布如图6-5所示。
图6-5 Holder Table函数
c.输入域
Holder Table函数通常在二维平面x i∈[-10,10],i=1,2上求解。
d.全局最小极值点
⑤Schaffer函数N.2
a.函数描述
该函数的数学表达式如下:
b.函数介绍
Schaffer函数N.2的维度是2,是Schaffer中的第二个测试函数,其具体的分布如图6-6所示。
图6-6 Schaffer函数N.2
c.输入域
Schaffer函数N.2通常在二维平面x i∈[-100,100],i=1,2上求解。
d.全局最小极值点
(2)佳点集萤火虫算法结果分析
佳点集萤火虫算法主要对比数据为收敛次数、平均迭代次数以及收敛结果的均值和方差。实验结果如表6-2所示。
表6-2 佳点集萤火虫算法的实验结果
续表
通过对结果进行分析发现,在5种函数的100次实验中,传统萤火虫算法总共收敛到全局最优值的次数是75,佳点集萤火虫算法收敛次数是93,有很大的提升。从平均收敛次数来看,佳点集萤火虫算法在5种测试函数中的表现均好于传统萤火虫算法;从收敛均值来看,两者差别较小,佳点集萤火虫算法表现略优。由此可见,引入佳点集技术对于传统萤火虫算法的改进具有较好的效果。
