斐波那契树优化算法求解多峰函数全局最优解的可达性分析

董易 施心陵 王霞 王耀民 吕丹桔 张松海 李孙寸

经典的智能优化算法在求解多峰函数全局最优解时,存在易陷入局部最优解的早熟收敛问题[1−3].例如作为典型代表的遗传算法(Genetic algorithm,GA)[4−5]和粒子群算法(Particle swarm optimization,PSO)[6−9].因此,算法求解全局最优解的可达性是一项重要的评价指标.对GA算法的理论研究表明其单点交叉运算只是在已有空间的一个特定局部上做非均匀搜索,对于搜索空间是非均匀可达的,而且不是全空间可达的[10];而对于变异运算,可达性的下降与染色体长度的增加几乎呈线性关系[11].对PSO的拓扑结构分析表明最优的粒子数量的增长不严格依赖于有效计算量的增长[12].这一结论反应出在相同的计算参数配置下,PSO对于多峰函数全局最优解的求解能力是受限的.对PSO粒子轨迹在离散和连续时间上的模型分析表明,对于求解多峰函数等较复杂的测试函数,并不需要制定针对性的参数设置,最重要的影响是粒子之间的交互性[13].对PSO算法的交互性和随机性分析表明,对于多峰函数的优化,PSO算法能依概率收敛到群体最优位置,但无法保证对全局最优解可达[14].一种结合演化博弈理论的PSO改进算法[15],从理论上保证了收敛性并提高了收敛速度,但对于多峰函数的搜索性能并未进行验证.

为解决求解多峰函数全局最优解时存在的早熟收敛问题,本文基于斐波那契法的思想,在n维欧氏空间中构造一个斐波那契树结构.每次迭代都生成全局随机点,在搜索空间中进行全局、局部交替搜索.使得斐波那契树优化算法在求解多峰函数全局最优解时,不易陷入局部最优解,具有良好的可达性指标.

本文首先简要介绍斐波那契法,然后详细说明斐波那契树的生成规则和斐波那契树优化算法流程,分析和证明斐波那契树优化算法的可达性.通过两个实验来分析和验证斐波那契树优化算法求解多峰函数全局最优解的可达性:1)跟踪算法求解过程中坐标点的累积分布仿真实验;2)独立重复求解实验,计算到达率,并对算法收敛曲线进行分析.

1 斐波那契法最优化原理概述

令f(x)为区间[a,b]上的一维单峰函数,x∗是区间[a,b]上的极小值,由于极大值问题只需将目标函数乘以−1即可转为极小值问题,所以只讨论求解极小值问题.在区间[a,b]上取两点.根据新的点来缩短搜索区间长度.设第i次迭代时的搜索区间为[ai,bi],在该区间内取的两个点为xi和.则区间缩短规则为:

根据规则,每次迭代搜索区间长度缩短为bi+1−ai+1=α(bi−ai),其中α为搜索区间长度的缩短率.

斐波那契法用斐波那契数计算缩短率α.斐波那契数列{Fn}计算公式为

斐波那契法相关计算公式为

搜索区间长度缩短为bi+1−ai+1=Fi/Fi+1(bi−ai).斐波那契法的缩短率α线性收敛,是分割方法求解一维单峰函数的最优策略[16].

2 斐波那契树优化算法

斐波那契树优化算法(Fibonacci tree optimization algorithm,FTO)基于斐波那契法最优化原理构造一个斐波那契树结构来求解最优化问题.FTO在斐波那契法基础上扩展到n维空间,并引入随机性.

斐波那契树的生成基于一个基本结构,每次生成新的点都包括覆盖全局搜索区域的随机点和在斐波那契树结构内的局部点.FTO求解目标函数的过程就是迭代生成斐波那契树的过程.FTO在搜索空间内进行全局局部交替搜索.

新点的生成依据斐波那契法的比例关系进行计算.设当前斐波那契数列第i项为Fi,第i+1项为Fi+1,则从已有的两点计算新点的比例关系为Fi/Fi+1.

2.1 基本结构

FTO算法在n维空间中构造一个基本结构,如图1所示.

图1 FTO算法基本结构Fig.1 Basic structure of FTO

其中,Fi是斐波那契数列第i项.设目标函数为f,基本结构中的解值至少不差于,即.则点的坐标计算公式为

2.2 斐波那契树

FTO基于基本结构用两个迭代规则构造斐波那契树.规则1主要完成全局搜索过程,规则2主要完成局部搜索过程.设FTO当前处理的点集为S,集合大小满足斐波那契数|S|=Fi(i=1,2,···),i

规则1.令基本结构端点,端点取搜索空间中的随机点.对于,,D为向量维度,,且xd是满足均匀分布的随机变量,概率分布为,集合大小满足斐波那契数,根据式(4)求解出分割点.

规则2.令基本结构端点为S当前最优解,,根据式(4)求解出分割点.

根据两个规则迭代完成之后合并S与新生成的点集,包括随机端点集合{xb},分割点集合{xg1}与{xg2}.保留前Fi+1项较优解,丢弃其余解,更新点集S,同时集合大小更新为|S|=Fi+1.

斐波那契树生成过程如图2所示.其中黑色实心圆点表示集合S,集合大小为|S|=Fi,斜线圆点表示全局随机的端点集合{xb},白色实线圆点表示分割点集合{xg},每一行白色虚线圆点表示上一轮迭代处理的点集S.图2中有3个斐波那契树结构.图2(a)为规则1的生成过程示意图,通过全局随机的端点{xb}与端点{xa}生成分割点{xg1};图2(b)为规则2的生成过程示意图,通过当前集合S中的最优解xa与其余解{xb}生成分割点{xg2};图2(c)表示合并集合S,新生成的端点集合{xb}与分割点集合{xg1}与{xg2}之后,保留前Fi+1项较优解,集合S大小更新为|S|=Fi+1.

图2 斐波那契树生成过程示意图Fig.2 Building procedure of Fibonacci tree

2.3 算法流程

FTO算法流程图如图3所示.内层循环迭代生成一个斐波那契树结构.集合S初始化完成之后,通过规则1和规则2更新S,直至斐波那契树深度为N.外层循环基于前一次迭代生成的点集S重复生成新的斐波那契树,直至满足算法最大迭代次数.

图3 FTO算法流程图Fig.3 Algorithm flow chart of FTO

3 FTO算法的可达性分析

定义1.设D维欧氏空间中点集A⊂RD,经过算法F计算生成新的点集B=F(A),对于∀x∈B,称是F(A)可达的,B是A的可达集合.

定义2.设算法F的可达集合为B,如果目标函数存在最优解f(x∗),且x∗∈B,称算法F是最优解可达的.

定理1.目标函数定义域内的解集是斐波那契树优化算法的可达集合.

证明.根据斐波那契树优化算法原理,经过足够多的迭代次数n<∞,考虑斐波那契树生成规则1中的基本结构端点集合{xb},对于∀ x∈{xb},x=(xd)D×1,D为向量维度,xd∈[xmin,xmax],且xd是满足均匀分布的随机变量,概率分布为P(xd)=U(xmin,xmax),则{xb}在目标函数定义域B内满足:

由上可知,∀ x∈{xb}以概率1满足x∈B,即B是{xb}的可达集合.□

定理2.斐波那契树优化算法是最优解可达的.

证明.设目标函数定义域B中存在全局最优解f(x∗).根据定理1,x∗在{xb}的可达集合中.所以,斐波那契树优化优化算法是最优解可达的.□

定理3.设定义域中随机点服从均匀分布的概率为p,则斐波那契树优化算法陷入局部最优解的概率小于p.

证明.设当前算法求解得局部最优解f(x′),根据定理1,经过次迭代后算法陷入局部最优解的概率为,则limn→+∞p′=0

4 可达性仿真实验与分析

为验证FTO算法的可达性,利用PSO算法容易陷入局部最优解的特性,将两个算法针对目标函数的求解过程进行对比.实验步骤如下:

1)用算法从初始化到既定迭代次数时刻所处理过的解坐标历史记录,绘制解坐标的累积分布函数图像,直观反映出算法在搜索空间中的求解过程.

2)绘制出算法求解的收敛曲线,并进行对比分析.

算法参数设置见表2.表1是函数Damavandi和Langermann的局部极值点,其中局部极值1是全局最优解,局部极值2是一个次优解.实验使用表3中的函数Damavandi和Langermann进行求解.

图4(a)和图4(b)分别是函数Damavandi的图像和等高线示意图;图4(c)和图4(d)分别是函数Langermann的图像和等高线示意图.每个等高线图中都标识出表1中局部极值点的坐标.

表1 函数局部极值点Table 1 Local optima of benchmark functions

图4 函数图像和等高线示意图Fig.4 Function graphs and contour graphs

图5是对函数Damavandi求解的坐标点累积分布示意图.从对PSO算法求解过程的4次绘制图像中可以看出,PSO算法的粒子逐渐汇聚到局部极值2.随着迭代次数的增加,每次绘制在局部极值1周围区域几乎没有粒子的分布,反映出PSO算法陷入局部最优解的情形.从FTO算法的绘制结果可以看出,第50次迭代时刻的第1次绘制结果中在局部极值1和局部极值2的周围已经有坐标点的分布,随着迭代次数的增加,两个局部极值周围的坐标点汇聚都在逐渐增多.从FTO算法端点集合{xa}与{xb}坐标点的累积分布图可以看出,由于斐波那契树的生成规则1生成目标函数定义域范围内的全局随机点{xb},随着迭代次数的增加,全局随机点的累积分布几乎覆盖到整个定义域,包括局部极值1和局部极值2所在区域.同时,求解过程中生成的端点{xa}与分割点{xg}使得局部极值附近的坐标点分布更加密集.

图6是对函数Langermann求解的坐标累积分布示意图.与图5的情形相同,随着迭代次数的增加,PSO算法的粒子运动方向没有进入局部极值1附近区域,而在局部极值2附近区域逐渐汇聚,无法跳出局部最优解.从FTO算法的坐标点累积分布图可以看出,坐标点的分布除了局部极值1和局部极值2之外,还覆盖到了Langermann函数的一些其他局部极值区域.FTO算法端点集合{xa}与{xb}坐标点的累积分布图同样反映出FTO算法生成的全局随机点在整个目标函数定义域的累积分布情况.

图5 函数Damavandi求解坐标点的累积分布示意图Fig.5 Cumulative distribution of points of function Damavandi

图6 函数Langermann求解坐标点的累积分布示意图Fig.6 Cumulative distribution of points of function Langermann

图7是算法求解的收敛曲线.图7(a)是函数Damavandi的收敛曲线.可以看出PSO算法在求解到局部极值2之后随着迭代次数的增加收敛曲线不再变化.从FTO算法的收敛曲线可以看出有一个函数值的跳跃变化过程,反映出FTO算法从局部极值2跳出之后逐渐收敛到局部极值1的过程.图7(b)是函数Langermann的收敛曲线.同样反映出PSO算法陷入局部最优解,FTO算法的收敛到全局最优解的情形.

实验利用PSO算法容易陷入局部最优解的特性与FTO算法进行对比.通过算法求解过程的坐标点累积分布图和收敛曲线反映出FTO算法不容易陷入局部最优解,验证了FTO算法可达性.

5 对比实验与分析

为对比和验证FTO算法的可达性,对目标函数独立重复求解,统计全局最优解的到达率r,并与遗传算法(GA)、粒子群算法(PSO)、综合学习策略的粒子群算法(Comprehensive learning particle swarm optimizer,CLPSO)[17]进行对比实验.GA和PSO算法已被证明其算法机制存在易陷入局部最优解的特性,CLPSO对PSO早熟收敛问题进行了改进,在实验中与FTO不易陷入局部最优解的特性进行对比.到达率r计算如下:

其中,N是对目标函数独立重复求解次数,为求解结果为全局最优解的次数,记为N∗.f(x∗)为目标函数全局最优解,f(xi)为第i次求解结果,ε为可接受的精度误差.

实验独立重复求解50次,最大迭代次数=1000,函数最大评价次数FEs=5.0E+4,向量维数=2.实验硬件环境为Intel Core i5 2.8GHz处理器,4GB内存.软件环境为Windows 8.1专业版操作系统,MATLAB 2015b版本编程语言.各算法参数设置见表2.

实验选择8个典型多峰函数进行测试,全局最优解均为最小值.其中Damavandi,Michalewicz和YangStandingWave 3个函数的全局最优解均位于频率较高的局部区域,对于随机算法来说命中概率较低,其他区域则存在频率较低的次优解,命中概率较高,适合用于测试算法对于全局最优解的可达性.Langermann函数在两个方向上分别存在一个全局最优解和一个次优解,适合用于测试算法跳出局部最优解的能力.cec2005[18]的4个多峰函数是较为复杂的合成函数,能够对算法性能进行较为全面的测试.测试函数及相关参数列表3.

图7 仿真实验收敛曲线Fig.7 Convergence curves of simulation experiment

表2 算法参数设置Table 2 Parameters setting of algorithms

表3 测试函数列表Table 3 Benchmark functions

5.1 实验结果分析

实验结果如表4～12所示,实验计算的指标包括:1)50次独立重复求解的到达次数N∗和到达率r;2)N∗次结果的均值和标准差1,其中均值在表中记为到达均值;3)未求解到全局最优解的其他独立重复求解结果的均值和标准差2,其中均值在表中记为未达均值.

表4 实验函数的最优解及可接受范围Table 4 The optimal solution and acceptable range of the functions in experiment

从表中可以看出,对于测试函数Langermann,Michalewicz,YangStandingWave,HCF1,FTO算法没有陷入局部最优,到达率为100%.其余4个测试函数由于其全局最优解所在的局部区域命中概率较低,50次独立求解过程没有全部求解到全局最优解,到达率没有达到100%.在迭代次数和斐波那契树深度参数限制的条件下,FTO算法的50次独立求解没有出现到达率为0的情况,验证了FTO算法是全局最优解可达的.

从与其余3个算法对比来看,FTO到达率为100%的函数个数为4个,其次是CLPSO算法,有2个函数(Langermann和Michalewicz)到达率为100%,GA和PSO算法的到达率均未达100%.在到达率未达100%的实验结果中,FTO的到达率均高于其他算法.CLPSO算法由于改进了对全局最优解的搜索能力,有4个测试函数到达率高于GA和PSO算法,分别是Langermann,Michalewicz,HCF1和RHCF1.

GA和PSO算法由于自身特点,陷入局部最优解之后难以跳出,所以到达率都较低,例如Damavandi和RHCF3.由于种群个体限制,在初始化阶段命中全局最优解所在的局部区域概率较低,导致实验结果的到达率为0.FTO算法与GA,PSO,CLPSO的对比实验结果表明,在同样的迭代次数和种群个体数的条件限制下,FTO算法表现出更强的全局搜索能力.

表5 Damavandi实验结果Table 5 Result of Damavandi in experiment

表6 Langermann实验结果Table 6 Result of Langermann in experiment

表7 Michalewicz实验结果Table 7 Result of Michalewicz in experiment

表8 YangStandingWave实验结果Table 8 Result of YangStandingWave in experiment

表9 HCF1实验结果Table 9 Result of HCF1 in experiment

表10 RHCF1实验结果Table 10 Result of RHCF1 in experiment

表11 RHCF2实验结果Table 11 Result of RHCF2 in experiment

表12 RHCF3实验结果Table 12 Result of RHCF3 in experiment

图8 对比实验的收敛曲线Fig.8 Convergence curves of comparison experiment

从到达均值的指标来看,所有算法测试结果到达均值的标准差都接近0或等于0.反映出50次独立重复求解过程在没有陷入局部最优解的次数中,在可接受的精度范围内求解到全局最优解.未达均值的标准差反映出两种情况:1)接近0或等于0的情况,说明被测算法的每次独立求解均陷入同一个局部最优解,例如PSO算法对于Langermann函数有8次独立求解,得到同一个局部最优解;2)未达均值的标准差较高的情况,反映出被测算法的多次独立求解过程分别陷入了多个局部最优解,例如GA和PSO算法对于HCF1和RHCF1测试函数的未达均值都大于全局最优解.

5.2 收敛曲线分析

从收敛曲线的变化来分析和验证FTO算法求解全局最优解的可达性.图8是50次独立重复实验随机选择某次求解过程的收敛曲线.从图8可以出,除了Damavandi和Michalewicz函数之外,FTO算法收敛到全局最优解的速度都快于其他算法.从Damavandi,Michalewicz和RHCF2的收敛曲线可以看出,对比其他算法,FTO算法有一个从局部最优解跳出到全局最优解的过程.从GA和PSO算法的收敛曲线可以看出,算法陷入局部最优解之后无法跳出,收敛曲线不再变化,这个特点也可以对比看出FTO算法的全局搜索能力较好.

CLPSO算法由于设置了更多终止迭代条件,在判断函数值在一定阈值范围内不再变化之后算法终止,所以不会完整绘制出迭代到1000次的变化曲线.

6 结论

本文描述了FTO算法的基本结构和斐波那契树的生成规则,证明了FTO算法是以概率1全局最优解可达的.对于求解多峰函数全局最优解的优化问题,FTO算法不易陷入局部最优解.通过跟踪解坐标累积分布的可达性仿真实验,验证了FTO算法的可达性.通过50次独立重复求解8个多峰函数的对比实验,计算算法的到达率,与GA,PSO和CLPSO算法进行对比,并对一组收敛曲线进行分析,验证了FTO算法全局最优解的可达性.