On Accessibility of Fibonacci Tree Optimization Algorithm for Global Optima of Multi-modal Functions
-
摘要: 为分析和验证斐波那契树优化算法（Fibonacci tree optimization algorithm，FTO）求解多峰函数全局最优解的算法性能，对算法的可达性问题进行研究.本文基于斐波那契法构造一个斐波那契树结构，在搜索空间中进行全局、局部交替搜索，不易陷入局部最优解.对斐波那契树优化算法基于该结构的可达性进行分析和证明.通过跟踪算法求解过程中坐标点的累积分布仿真实验和到达率的对比实验，分析和验证了算法求解多峰函数全局最优解的可达性.Abstract: This paper investigates the accessibility of Fibonacci tree optimization algorithm (FTO) in order to analyze and prove its ability in solving the problem of global optima of multi-modal functions. A structure called Fibonacci tree based on Fibonacci search method is created, which conducts alternating global and local retrievals in the search space of the target function with lower probability of trapping into local optima. The accessibility of FTO is analyzed and proved on the basis of Fibonacci tree. A simulation experiment of tracing accumulation distribution of solution coordinates validates the global optima accessibility of FTO, and a contrast experiment of accessible rate further points to the better accessibility of FTO.
-
经典的智能优化算法在求解多峰函数全局最优解时, 存在易陷入局部最优解的早熟收敛问题[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] $ 上取两点$ x_1 $ 和$ \tilde{x}_1 $ , $x_1$ < $\tilde{x}_1 $ .根据新的点来缩短搜索区间长度.设第$ i$ 次迭代时的搜索区间为$ [a_i, b_i] $ , 在该区间内取的两个点为$ x_i $ 和$\tilde{x}_i $ , $ x_i < \tilde{x}_i $ .则区间缩短规则为:
1) 当$ f(x_i )\leq f(\tilde{x}_i ) $ , 令$ a_{i+1}=a_i $ , $b_{i+1}=\tilde{x}_i $ ;
2) 当$ f(x_i )>f(\tilde{x}_i ) $ , 令$ a_{i+1}=x_i $ , $ b_{i+1}=b_i $ .
根据规则, 每次迭代搜索区间长度缩短为$ b_{i+1}-a_{i+1}=\alpha (b_i-a_i) $ , 其中$ \alpha $ 为搜索区间长度的缩短率.
斐波那契法用斐波那契数计算缩短率$ \alpha $ .斐波那契数列$ \{F_n \}$ 计算公式为
$ \begin{cases} F_1=F_2 =1 \\ F_i = F_{i-1}+F_{i-2}, \;\;\; i\geq 3 \end{cases} $
(1) 斐波那契法相关计算公式为
$ \begin{align} &x_i=a_i+\left(1-\frac{F_i}{F_{i+1}}\right)(b_i-a_i)\notag\\[1mm] &\tilde{x}_i=a_i+\frac{F_i}{F_{i+1}}(b_i-a_i) \end{align} $
(2) 搜索区间长度缩短为$ b_{i+1}-a_{i+1}=F_i/F_{i+1} (b_i-a_i )$ .斐波那契法的缩短率$ \alpha$ 线性收敛, 是分割方法求解一维单峰函数的最优策略[16].
2. 斐波那契树优化算法
斐波那契树优化算法(Fibonacci tree optimization algorithm, FTO)基于斐波那契法最优化原理构造一个斐波那契树结构来求解最优化问题.FTO在斐波那契法基础上扩展到$ n $ 维空间, 并引入随机性.
斐波那契树的生成基于一个基本结构, 每次生成新的点都包括覆盖全局搜索区域的随机点和在斐波那契树结构内的局部点.FTO求解目标函数的过程就是迭代生成斐波那契树的过程.FTO在搜索空间内进行全局局部交替搜索.
新点的生成依据斐波那契法的比例关系进行计算.设当前斐波那契数列第$ i$ 项为$ F_i $ , 第$ i+1 $ 项为$ F_{i+1}$ , 则从已有的两点计算新点的比例关系为$ F_i/$ $F_{i+1} $ .
2.1 基本结构
FTO算法在$ n $ 维空间中构造一个基本结构, 如图 1所示.
图 1中, $ {\boldsymbol x}_a $ 和$ {\boldsymbol x}_b $ 称为端点, $ {\boldsymbol x}_g$ 称为分割点. 3个向量的范数满足如下比例关系:
$ \begin{align} \frac{\|{\boldsymbol x}_g-{\boldsymbol x}_a\|}{\|{\boldsymbol x}_b-{\boldsymbol x}_a\|}=\frac{\|{\boldsymbol x}_b-{\boldsymbol x}_g\|}{\|{\boldsymbol x}_g-{\boldsymbol x}_a\|}=\frac{F_i}{F_{i+1}} \end{align} $
(3) 其中, $ F_i $ 是斐波那契数列第$ i $ 项.设目标函数为$ f$ , 基本结构中的解值$ f({\boldsymbol x}_a) $ 至少不差于$ f({\boldsymbol x}_b) $ , 即$f({\boldsymbol x}_a)$ $\succcurlyeq$ $f({\boldsymbol x}_b) $ .则点$ {\boldsymbol x}_g$ 的坐标计算公式为
$ \begin{align} {\boldsymbol x}_g=\frac{F_i}{F_{i+1}}({\boldsymbol x}_b-{\boldsymbol x}_a)+{\boldsymbol x}_a \end{align} $
(4) 2.2 斐波那契树
FTO基于基本结构用两个迭代规则构造斐波那契树.规则1主要完成全局搜索过程, 规则2主要完成局部搜索过程.设FTO当前处理的点集为$S $ , 集合大小满足斐波那契数$ |S|=F_i$ $(i=1, 2, \cdots)$ , $i$ < $N $ , $ N $ 称为斐波那契树深度.根据FTO的基本结构, 按两种规则指定点$ {\boldsymbol x}_a $ 和$ {\boldsymbol x}_b $ 的值, 并根据式(4)求解出$ {\boldsymbol x}_g $ , 用$ {\boldsymbol x}_a $ , $ {\boldsymbol x}_b $ 和$ {\boldsymbol x}_g$ 根据斐波那契数列生成规则来更新点集$ S $ .
规则1. 令基本结构端点$\{{\boldsymbol x}_a \}=S$ , 端点$\{{\boldsymbol x}_b\}$ 取搜索空间中的随机点.对于$\forall{\boldsymbol x}\in\{{\boldsymbol x}_b\}$ , ${\boldsymbol x}=(x_d)_{D\times1} $ , $D$ 为向量维度, $x_d\in[x_{\min}, x_{\max}]$ , 且$ x_d$ 是满足均匀分布的随机变量, 概率分布为$P(x_d )=U(x_{\min}, x_{\max})$ , 集合大小满足斐波那契数$|\{{\boldsymbol x}_b\}|=F_i$ , 根据式(4)求解出分割点$ \{{\boldsymbol x}_{g1}\} $ .
规则2. 令基本结构端点$ {\boldsymbol x}_a={\boldsymbol x}_{\rm best}\in S $ 为$ S $ 当前最优解, $ \{{\boldsymbol x}_b \}=\{{\boldsymbol x}_i |{\boldsymbol x}_i\in S \wedge {\boldsymbol x}_i\neq {\boldsymbol x}_a \}$ , 根据式(4)求解出分割点$ \{{\boldsymbol x}_{g2}\} $ .
根据两个规则迭代完成之后合并$ S $ 与新生成的点集, 包括随机端点集合$\{ {\boldsymbol x}_b \}$ , 分割点集合$ \{{\boldsymbol x}_{g1}\} $ 与$ \{{\boldsymbol x}_{g2}\} $ .保留前$ F_{i+1}$ 项较优解, 丢弃其余解, 更新点集S, 同时集合大小更新为$ |S|=F_{i+1} $ .
斐波那契树生成过程如图 2所示.其中黑色实心圆点表示集合$ S$ , 集合大小为$ |S|=F_i $ , 斜线圆点表示全局随机的端点集合$ \{ {\boldsymbol x}_b \}$ , 白色实线圆点表示分割点集合$\{ {\boldsymbol x}_g\}$ , 每一行白色虚线圆点表示上一轮迭代处理的点集$ S $ .图 2中有3个斐波那契树结构. 图 2 (a)为规则1的生成过程示意图, 通过全局随机的端点$ \{{\boldsymbol x}_b\}$ 与端点$ \{{\boldsymbol x}_a\} $ 生成分割点$ \{{\boldsymbol x}_{g1}\} $ ; 图 2 (b)为规则2的生成过程示意图, 通过当前集合$ S $ 中的最优解$ {\boldsymbol x}_a $ 与其余解$ \{{\boldsymbol x}_b\} $ 生成分割点$ \{{\boldsymbol x}_{g2}\} $ ; 图 2 (c)表示合并集合$ S $ , 新生成的端点集合$ \{{\boldsymbol x}_b\}$ 与分割点集合$ \{{\boldsymbol x}_{g1}\} $ 与$ \{{\boldsymbol x}_{g2}\}$ 之后, 保留前$ F_{i+1} $ 项较优解, 集合$ S $ 大小更新为$ |S|=F_{i+1}$ .
2.3 算法流程
FTO算法流程图如图 3所示.内层循环迭代生成一个斐波那契树结构.集合$ S$ 初始化完成之后, 通过规则1和规则2更新$ S $ , 直至斐波那契树深度为$ N$ .外层循环基于前一次迭代生成的点集$ S$ 重复生成新的斐波那契树, 直至满足算法最大迭代次数.
3. FTO算法的可达性分析
定义1. 设$ D $ 维欧氏空间中点集$ A\subset {\bf R}^D$ , 经过算法$ F $ 计算生成新的点集$ B=F(A) $ , 对于$ \forall {\boldsymbol x}$ $\in$ $B $ , 称$ {\boldsymbol x} $ 是$ F(A) $ 可达的, $ B $ 是$ A $ 的可达集合.
定义2. 设算法$ F $ 的可达集合为$ B$ , 如果目标函数存在最优解$ f({\boldsymbol x}^*) $ , 且$ {\boldsymbol x}^*\in B$ , 称算法$ F $ 是最优解可达的.
定理1. 目标函数定义域内的解集是斐波那契树优化算法的可达集合.
证明. 根据斐波那契树优化算法原理, 经过足够多的迭代次数$n < \infty $ , 考虑斐波那契树生成规则1中的基本结构端点集合$ \{{\boldsymbol x}_b\} $ , 对于$ \forall {\boldsymbol x}\in \{{\boldsymbol x}_b\} $ , $ {\boldsymbol x}=(x_d)_{D\times1} $ , $ D $ 为向量维度, $ x_d\in[x_{\min}, x_{\max}]$ , 且$ x_d $ 是满足均匀分布的随机变量, 概率分布为$ P(x_d )=U(x_{\min}, x_{\max }) $ , 则$ \{{\boldsymbol x}_b\} $ 在目标函数定义域$ B $ 内满足:
$ \begin{align} \underbrace{\idotsint}_D\frac{1}{x_{\max}-x_{\min}}{\rm d}x_d=1 \end{align} $
(5) 由上可知, $ \forall {\boldsymbol x}\in \{{\boldsymbol x}_b\} $ 以概率1满足$ {\boldsymbol x}\in B $ , 即$ B $ 是$ \{{\boldsymbol x}_b\} $ 的可达集合.
定理2. 斐波那契树优化算法是最优解可达的.
证明. 设目标函数定义域$ B $ 中存在全局最优解$ f({\boldsymbol x}^*) $ .根据定理1, $ {\boldsymbol x}^* $ 在$ \{{\boldsymbol x}_b \}$ 的可达集合中.所以, 斐波那契树优化优化算法是最优解可达的.
定理3. 设定义域中随机点服从均匀分布的概率为$ p$ , 则斐波那契树优化算法陷入局部最优解的概率小于$ p $ .
证明. 设当前算法求解得局部最优解$ f({\boldsymbol x}')$ , 根据定理1, 经过$ n < \infty $ 次迭代后算法陷入局部最优解的概率为$p'\leq \prod_{i=1}^n(1-p) $ , 则$ \lim_{n\to +\infty}p'=0 < p$ .
4. 可达性仿真实验与分析
为验证FTO算法的可达性, 利用PSO算法容易陷入局部最优解的特性, 将两个算法针对目标函数的求解过程进行对比.实验步骤如下:
1) 用算法从初始化到既定迭代次数时刻所处理过的解坐标历史记录, 绘制解坐标的累积分布函数图像, 直观反映出算法在搜索空间中的求解过程.
2) 绘制出算法求解的收敛曲线, 并进行对比分析.
算法参数设置见表 2.表 1是函数Damavandi和Langermann的局部极值点, 其中局部极值1是全局最优解, 局部极值2是一个次优解.实验使用表 3中的函数Damavandi和Langermann进行求解.
表 2 算法参数设置Table 2 Parameters setting of algorithmsGA PSO CLPS FTO 交叉概率 0.7 惯性权重 0.9~0.5 惯性权重 0.9~0.5 斐波那契树深度 6 变异概率 0.01 加速常数$ c1 $ 2 加速常数$ c1 $ 1.49445 精英保留概率 0.05 加速常数$ c2 $ 2 加速常数$ c2 $ 1.49445 二进制位数 20 种群个数 20 学习概率 0.5~0.05 种群个数 20 种群个数 20 表 1 函数局部极值点Table 1 Local optima of benchmark functions局部极值1 (全局最优解) 局部极值2 Damavandi $ f(2, 2)=0 $ $ f(7, 7)=2 $ Langermann $ f(2.003, 1.006)=-5.1621 $ $ f(7, 9)=-3 $ 表 3 测试函数列表Table 3 Benchmark functions函数名称 表达式 定义域 全局最优解 Damavandi $ [1-|\frac{\sin[\pi(x_1-2)]\sin[\pi(x_2-2)]}{\pi^2(x_1-2)(x_2-2)}|^5][2+(x_1-7)^2+(x_2-7)^2]- $ $ \sum\limits_{i=1}^5 c_i\cos(z_i\pi){\rm e}^{-\frac{z_i}{\pi}} $ $[0, 14]$ 0 $ z_i=(x_1-a_i)^2+(x_2-b_i)^2 $ Langermann $ a=[3, 5, 2, 1, 7] $ $[0, 10]$ $-5.1621$ $ b=[5, 2, 1, 4, 9] $ $ c=[1, 2, 5, 2, 3] $ Michalewicz $ \sum\limits_{i=1}^d \sin(\frac{ix_i^2}{\pi})^{20}\sin(x_i) $ $[0, 5] $ $ -1.9679$ YangStandingWave $ {\rm e}^{-\sum\limits_{i=1}^d(\frac{x_i}{15})^6}-2{\rm e}^{-\sum\limits_{i=1}^d x_i^2}\prod\limits_{i=1}^d \cos^2(x_i)$ $[-20, 20]$ $ -1 $ cec2005 15 HCF1 $[-5, 5]$ 120 cec2005 16 RHCF1 Hybrid composition functions $[-5, 5]$ 120 cec2005 18 RHCF2 $[-5, 5]$ 10 cec2005 21 RHCF3 $[-5, 5]$ 360 图 4 (a)和图 4 (b)分别是函数Damavandi的图像和等高线示意图; 图 4 (c)和图 4 (d)分别是函数Langermann的图像和等高线示意图.每个等高线图中都标识出表 1中局部极值点的坐标.
图 5是对函数Damavandi求解的坐标点累积分布示意图.从对PSO算法求解过程的4次绘制图像中可以看出, PSO算法的粒子逐渐汇聚到局部极值2.随着迭代次数的增加, 每次绘制在局部极值1周围区域几乎没有粒子的分布, 反映出PSO算法陷入局部最优解的情形.从FTO算法的绘制结果可以看出, 第50次迭代时刻的第1次绘制结果中在局部极值1和局部极值2的周围已经有坐标点的分布, 随着迭代次数的增加, 两个局部极值周围的坐标点汇聚都在逐渐增多.从FTO算法端点集合$\{{\boldsymbol x}_a\} $ 与$ \{{\boldsymbol x}_b\}$ 坐标点的累积分布图可以看出, 由于斐波那契树的生成规则1生成目标函数定义域范围内的全局随机点$\{{\boldsymbol x}_b\}$ , 随着迭代次数的增加, 全局随机点的累积分布几乎覆盖到整个定义域, 包括局部极值1和局部极值2所在区域.同时, 求解过程中生成的端点$\{{\boldsymbol x}_a\} $ 与分割点$ \{{\boldsymbol x}_g\}$ 使得局部极值附近的坐标点分布更加密集.
图 5 函数Damavandi求解坐标点的累积分布示意图Fig. 5 Cumulative distribution of points of function Damavandi图 6是对函数Langermann求解的坐标累积分布示意图.与图 5的情形相同, 随着迭代次数的增加, PSO算法的粒子运动方向没有进入局部极值1附近区域, 而在局部极值2附近区域逐渐汇聚, 无法跳出局部最优解.从FTO算法的坐标点累积分布图可以看出, 坐标点的分布除了局部极值1和局部极值2之外, 还覆盖到了Langermann函数的一些其他局部极值区域.FTO算法端点集合$ \{{\boldsymbol x}_a\} $ 与$ \{{\boldsymbol x}_b\}$ 坐标点的累积分布图同样反映出FTO算法生成的全局随机点在整个目标函数定义域的累积分布情况.
图 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 $ 计算如下:
$ \begin{align} r=\dfrac{\sum\limits_{i=1}^N k}{N}, \quad \begin{cases} k=1, &|f({\boldsymbol x}^*)-f({\boldsymbol x}_i)| < \epsilon \\ k=0, &|f({\boldsymbol x}^*)-f({\boldsymbol x}_i)| \geq \epsilon \end{cases} \end{align} $
(6) 其中, $ N $ 是对目标函数独立重复求解次数, $ \sum_{i=1}^N k $ 为求解结果为全局最优解的次数, 记为$ N^* $ . $ f({\boldsymbol x}^* )$ 为目标函数全局最优解, $ f({\boldsymbol x}_i ) $ 为第$ i $ 次求解结果, $\varepsilon $ 为可接受的精度误差.
实验独立重复求解50次, 最大迭代次数= 1 000, 函数最大评价次数FEs = 5.0E+4, 向量维数= 2.实验硬件环境为Intel Core i5 2.8 GHz处理器, 4 GB内存.软件环境为Windows 8.1专业版操作系统, MATLAB 2015b版本编程语言.各算法参数设置见表 2.
实验选择8个典型多峰函数进行测试, 全局最优解均为最小值.其中Damavandi, Michalewicz和YangStandingWave 3个函数的全局最优解均位于频率较高的局部区域, 对于随机算法来说命中概率较低, 其他区域则存在频率较低的次优解, 命中概率较高, 适合用于测试算法对于全局最优解的可达性. Langermann函数在两个方向上分别存在一个全局最优解和一个次优解, 适合用于测试算法跳出局部最优解的能力. cec2005[18]的4个多峰函数是较为复杂的合成函数, 能够对算法性能进行较为全面的测试.测试函数及相关参数列表 3.
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函数 最优解 可接受范围 Damavandi 0.0000E+00 $ < 1.0000$ E$-$ 02 Langermann $-5.1621$ E+00 $ < -5.1000$ E+00 Michalewicz $-1.9679$ E+00 $ < -1.9500$ E+00 YangStandingWave $-1.0000$ E+00 $ < 0.0000$ E+00 HCF1 1.2000E+02 $ < 1.2900$ E+02 RHCF1 1.2000E+02 $ < 1.2900$ E+02 RHCF2 1.0000E+01 $ < 1.1000$ E+01 RHCF3 3.6000E+02 $ < 3.6100$ E+02 表 5 Damavandi实验结果Table 5 Result of Damavandi in experiment算法 到达均值 标准差1 未达均值 标准差2 $N$ $r$ (%) GA / / 2.0000E+00 / PSO -8.5487E-14 1.3213E-23 2.0000E+00 0.0000E+00 2 4 CLPSO / / 2.0000E+00 / FTO 1.1168E-06 1.4894E-06 2.0000E+00 1.7888E-09 12 24 表 6 Langermann实验结果Table 6 Result of Langermann in experiment算法 到达均值 标准差1 未达均值 标准差2 $N$ $r$ (%) GA $-5.1621$ E+00 1.8078E-15 $-2.9938$ E+00 3.6444E-01 29 58 PSO $-5.1621$ E+00 2.6968E-15 $-3.0000$ E+00 4.7475E-16 42 84 CLPSO $-5.1615$ E+00 4.3819E-03 / / 50 100 FTO $-5.1621$ E+00 5.0777E-08 / / 50 100 表 7 Michalewicz实验结果Table 7 Result of Michalewicz in experiment算法 到达均值 标准差1 未达均值 标准差2 $N$ $r$ (%) GA $-1.9679$ E+00 4.5325E-16 -1.7979E+00 9.6821E-02 25 50 PSO $-1.9678$ E+00 3.9389E-05 -9.9196E-01 1.6075E-02 46 92 CLPSO $-1.9679$ E+00 7.4886E-09 / / 50 100 FTO $-1.9679$ E+00 7.0607E-07 / / 50 100 表 8 YangStandingWave实验结果Table 8 Result of YangStandingWave in experiment算法 到达均值 标准差1 未达均值 标准差2 $N$ $r$ (%) GA $-1.0000$ E+00 5.6277E-16 1.3173E-05 3.5265E-21 37 74 PSO $-1.0000$ E+00 0.0000E+00 1.5571E-05 1.2516E-06 4 8 CLPSO $-7.0208$ E-01 2.6415E-01 1.2852E-05 2.0573E-06 9 18 FTO $-1.0000$ E+00 1.8775E-09 / / 50 100 表 9 HCF1实验结果Table 9 Result of HCF1 in experiment算法 到达均值 标准差1 未达均值 标准差2 $N$ $r$ (%) GA 1.2000E+02 3.6311E-06 2.6457E+02 1.2548E+02 27 54 PSO 1.2000E+02 0.0000E+00 3.2000E+02 0.0000E+00 45 90 CLPSO 1.2008E+02 2.7377E-01 1.4330E+02 1.4567E+01 48 96 FTO 1.2000E+02 1.3480E-05 / / 50 100 表 10 RHCF1实验结果Table 10 Result of RHCF1 in experiment算法 到达均值 标准差1 未达均值 标准差2 $N$ $r$ (%) GA 1.2000E+02 0.0000E+00 2.1146E+02 5.0191E+01 7 14 PSO 1.2000E+02 0.0000E+00 2.1597E+02 1.5598E+01 35 70 CLPSO 1.2155E+02 2.6034E+00 1.9118E+02 $-3.3710$ E+01 41 82 FTO 1.2000E+02 2.3951E-05 2.2000E+02 0.0000E+00 49 98 表 11 RHCF2实验结果Table 11 Result of RHCF2 in experiment算法 到达均值 标准差1 未达均值 标准差2 $N$ $r$ (%) GA 1.0006E+01 0.0000E+00 3.8551E+02 9.0210E+01 1 2 PSO 1.0000E+01 0.0000E+00 3.8500E+02 6.0356E+01 14 28 CLPSO / / 2.6217E+02 / FTO 1.0043E+01 3.1468E-02 1.1011E+02 8.2284E-02 44 88 表 12 RHCF3实验结果Table 12 Result of RHCF3 in experiment算法 到达均值 标准差1 未达均值 标准差2 $N$ $r$ (%) GA 3.6000E+02 0.0000E+00 7.8881E+02 1.6723E+02 1 2 PSO / / 6.9800E+02 / CLPSO / / 6.0613E+02 / FTO 3.6000E+02 5.1019E-04 5.5474E+02 2.2942E+01 31 62 从表中可以看出, 对于测试函数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算法表现出更强的全局搜索能力.
从到达均值的指标来看, 所有算法测试结果到达均值的标准差都接近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算法由于设置了更多终止迭代条件, 在判断函数值在一定阈值范围内不再变化之后算法终止, 所以不会完整绘制出迭代到1 000次的变化曲线.
6. 结论
本文描述了FTO算法的基本结构和斐波那契树的生成规则, 证明了FTO算法是以概率1全局最优解可达的.对于求解多峰函数全局最优解的优化问题, FTO算法不易陷入局部最优解.通过跟踪解坐标累积分布的可达性仿真实验, 验证了FTO算法的可达性.通过50次独立重复求解8个多峰函数的对比实验, 计算算法的到达率, 与GA, PSO和CLPSO算法进行对比, 并对一组收敛曲线进行分析, 验证了FTO算法全局最优解的可达性.
-
图 5 函数Damavandi求解坐标点的累积分布示意图
Fig. 5 Cumulative distribution of points of function Damavandi
图 6 函数Langermann求解坐标点的累积分布示意图
Fig. 6 Cumulative distribution of points of function Langermann
表 2 算法参数设置
Table 2 Parameters setting of algorithms
GA PSO CLPS FTO 交叉概率 0.7 惯性权重 0.9~0.5 惯性权重 0.9~0.5 斐波那契树深度 6 变异概率 0.01 加速常数$ c1 $ 2 加速常数$ c1 $ 1.49445 精英保留概率 0.05 加速常数$ c2 $ 2 加速常数$ c2 $ 1.49445 二进制位数 20 种群个数 20 学习概率 0.5~0.05 种群个数 20 种群个数 20 
下载: 导出CSV
表 1 函数局部极值点
Table 1 Local optima of benchmark functions
局部极值1 (全局最优解) 局部极值2 Damavandi $ f(2, 2)=0 $ $ f(7, 7)=2 $ Langermann $ f(2.003, 1.006)=-5.1621 $ $ f(7, 9)=-3 $
下载: 导出CSV
表 3 测试函数列表
Table 3 Benchmark functions
函数名称 表达式 定义域 全局最优解 Damavandi $ [1-|\frac{\sin[\pi(x_1-2)]\sin[\pi(x_2-2)]}{\pi^2(x_1-2)(x_2-2)}|^5][2+(x_1-7)^2+(x_2-7)^2]- $ $ \sum\limits_{i=1}^5 c_i\cos(z_i\pi){\rm e}^{-\frac{z_i}{\pi}} $ $[0, 14]$ 0 $ z_i=(x_1-a_i)^2+(x_2-b_i)^2 $ Langermann $ a=[3, 5, 2, 1, 7] $ $[0, 10]$ $-5.1621$ $ b=[5, 2, 1, 4, 9] $ $ c=[1, 2, 5, 2, 3] $ Michalewicz $ \sum\limits_{i=1}^d \sin(\frac{ix_i^2}{\pi})^{20}\sin(x_i) $ $[0, 5] $ $ -1.9679$ YangStandingWave $ {\rm e}^{-\sum\limits_{i=1}^d(\frac{x_i}{15})^6}-2{\rm e}^{-\sum\limits_{i=1}^d x_i^2}\prod\limits_{i=1}^d \cos^2(x_i)$ $[-20, 20]$ $ -1 $ cec2005 15 HCF1 $[-5, 5]$ 120 cec2005 16 RHCF1 Hybrid composition functions $[-5, 5]$ 120 cec2005 18 RHCF2 $[-5, 5]$ 10 cec2005 21 RHCF3 $[-5, 5]$ 360
下载: 导出CSV
表 4 实验函数的最优解及可接受范围
Table 4 The optimal solution and acceptable range of the functions in experiment
函数 最优解 可接受范围 Damavandi 0.0000E+00 $ < 1.0000$ E$-$ 02 Langermann $-5.1621$ E+00 $ < -5.1000$ E+00 Michalewicz $-1.9679$ E+00 $ < -1.9500$ E+00 YangStandingWave $-1.0000$ E+00 $ < 0.0000$ E+00 HCF1 1.2000E+02 $ < 1.2900$ E+02 RHCF1 1.2000E+02 $ < 1.2900$ E+02 RHCF2 1.0000E+01 $ < 1.1000$ E+01 RHCF3 3.6000E+02 $ < 3.6100$ E+02
下载: 导出CSV
表 5 Damavandi实验结果
Table 5 Result of Damavandi in experiment
算法 到达均值 标准差1 未达均值 标准差2 $N$ $r$ (%) GA / / 2.0000E+00 / PSO -8.5487E-14 1.3213E-23 2.0000E+00 0.0000E+00 2 4 CLPSO / / 2.0000E+00 / FTO 1.1168E-06 1.4894E-06 2.0000E+00 1.7888E-09 12 24
下载: 导出CSV
表 6 Langermann实验结果
Table 6 Result of Langermann in experiment
算法 到达均值 标准差1 未达均值 标准差2 $N$ $r$ (%) GA $-5.1621$ E+00 1.8078E-15 $-2.9938$ E+00 3.6444E-01 29 58 PSO $-5.1621$ E+00 2.6968E-15 $-3.0000$ E+00 4.7475E-16 42 84 CLPSO $-5.1615$ E+00 4.3819E-03 / / 50 100 FTO $-5.1621$ E+00 5.0777E-08 / / 50 100
下载: 导出CSV
表 7 Michalewicz实验结果
Table 7 Result of Michalewicz in experiment
算法 到达均值 标准差1 未达均值 标准差2 $N$ $r$ (%) GA $-1.9679$ E+00 4.5325E-16 -1.7979E+00 9.6821E-02 25 50 PSO $-1.9678$ E+00 3.9389E-05 -9.9196E-01 1.6075E-02 46 92 CLPSO $-1.9679$ E+00 7.4886E-09 / / 50 100 FTO $-1.9679$ E+00 7.0607E-07 / / 50 100
下载: 导出CSV
表 8 YangStandingWave实验结果
Table 8 Result of YangStandingWave in experiment
算法 到达均值 标准差1 未达均值 标准差2 $N$ $r$ (%) GA $-1.0000$ E+00 5.6277E-16 1.3173E-05 3.5265E-21 37 74 PSO $-1.0000$ E+00 0.0000E+00 1.5571E-05 1.2516E-06 4 8 CLPSO $-7.0208$ E-01 2.6415E-01 1.2852E-05 2.0573E-06 9 18 FTO $-1.0000$ E+00 1.8775E-09 / / 50 100
下载: 导出CSV
表 9 HCF1实验结果
Table 9 Result of HCF1 in experiment
算法 到达均值 标准差1 未达均值 标准差2 $N$ $r$ (%) GA 1.2000E+02 3.6311E-06 2.6457E+02 1.2548E+02 27 54 PSO 1.2000E+02 0.0000E+00 3.2000E+02 0.0000E+00 45 90 CLPSO 1.2008E+02 2.7377E-01 1.4330E+02 1.4567E+01 48 96 FTO 1.2000E+02 1.3480E-05 / / 50 100
下载: 导出CSV
表 10 RHCF1实验结果
Table 10 Result of RHCF1 in experiment
算法 到达均值 标准差1 未达均值 标准差2 $N$ $r$ (%) GA 1.2000E+02 0.0000E+00 2.1146E+02 5.0191E+01 7 14 PSO 1.2000E+02 0.0000E+00 2.1597E+02 1.5598E+01 35 70 CLPSO 1.2155E+02 2.6034E+00 1.9118E+02 $-3.3710$ E+01 41 82 FTO 1.2000E+02 2.3951E-05 2.2000E+02 0.0000E+00 49 98
下载: 导出CSV
表 11 RHCF2实验结果
Table 11 Result of RHCF2 in experiment
算法 到达均值 标准差1 未达均值 标准差2 $N$ $r$ (%) GA 1.0006E+01 0.0000E+00 3.8551E+02 9.0210E+01 1 2 PSO 1.0000E+01 0.0000E+00 3.8500E+02 6.0356E+01 14 28 CLPSO / / 2.6217E+02 / FTO 1.0043E+01 3.1468E-02 1.1011E+02 8.2284E-02 44 88
下载: 导出CSV
表 12 RHCF3实验结果
Table 12 Result of RHCF3 in experiment
算法 到达均值 标准差1 未达均值 标准差2 $N$ $r$ (%) GA 3.6000E+02 0.0000E+00 7.8881E+02 1.6723E+02 1 2 PSO / / 6.9800E+02 / CLPSO / / 6.0613E+02 / FTO 3.6000E+02 5.1019E-04 5.5474E+02 2.2942E+01 31 62
下载: 导出CSV
-
[1] Boussad I, Lepagnot J, Siarry P. A survey on optimization metaheuristics. Information Sciences, 2013, 237:82-117 doi: 10.1016/j.ins.2013.02.041 [2] 李建平, 宫耀华, 赵思远, 卢爱平, 李盼池.粒子群优化算法的改进及数值仿真.吉林大学学报(理学版), 2017, 55(2):322-332 http://d.old.wanfangdata.com.cn/Periodical/jldxzrkxxb201702024Li Jian-Ping, Gong Yao-Hua, Zhao Si-Yuan, Lu Ai-Ping, Li Pan-Chi. Improvement of particle swarm optimization algorithm and numerical simulation. Journal of Jilin University (Science Edition), 2017, 55 (2):322-332 http://d.old.wanfangdata.com.cn/Periodical/jldxzrkxxb201702024 [3] 高雷阜, 佟盼.遗传-人工蜂群融合算法及其Markov收敛性分析.数学杂志, 2017, 37 (1):215-222 doi: 10.3969/j.issn.0255-7797.2017.01.023Gao Lei-Fu, Tong Pan. Combination algorithm of genetic-artificial bee colony and its Markov convergence analysis. Journal of Mathematics, 2017, 37 (1):215-222 doi: 10.3969/j.issn.0255-7797.2017.01.023 [4] Whitley D. A genetic algorithm tutorial. Statistics and Computing, 1994, 4 (2):65-85 http://d.old.wanfangdata.com.cn/OAPaper/oai_doaj-articles_c227a5f223e4c1bc4e93b3863a92a817 [5] Mareda T, Gaudard L, Romerio F. A parametric genetic algorithm approach to assess complementary options of large scale wind-solar coupling. IEEE/CAA Journal of Automatica Sinica, 2017, 4 (2), 260-272 doi: 10.1109/JAS.2017.7510523 [6] Kennedy J, Eberhart R. Particle swarm optimization. In: Proceedings of the 1995 IEEE International Conference on Neural Networks. Perth, WA, Australia: IEEE, 1995, 4: 1942-1948 [7] Poli R. The sampling distribution of particle swarm optimisers and their stability[Online], available: http://cswww.essex.ac.uk/technical-reports/2007/csm-465.pdf, 2007. [8] Zhang Y D, Wang S H, Ji G L. A comprehensive survey on particle swarm optimization algorithm and its applications. Mathematical Problems in Engineering, 2015, 2015:Article No. 931256 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=Doaj000004037005 [9] Han Z, Zhao J, Wang W. An optimized oxygen system scheduling with electricity cost consideration in steel industry. IEEE/CAA Journal of Automatica Sinica, 2017, 4 (2), 216-222 doi: 10.1109/JAS.2017.7510439 [10] 张军英, 许进, 保铮.遗传交叉运算的可达性研究.自动化学报, 2002, 28 (1):120-125 http://www.aas.net.cn/CN/abstract/abstract15509.shtmlZhang Jun-Ying, Xu Jin, Bao Zheng. Attainability of genetic crossover operator. Acta Automatica Sinica, 2002, 28 (1):120-125 http://www.aas.net.cn/CN/abstract/abstract15509.shtml [11] Zhang Y A, Ma Q L, Sakamoto M, Furutani H. Effect of mutation to distribution of optimum solution in genetic algorithm. Natural Computing. Tokyo, Japan:Springer, 2010. 380-387 [12] Liu Q F, Wei W H, Yuan H Q, Zhan Z H, Li Y. Topology selection for particle swarm optimization. Information Sciences, 2016, 363:154-173 doi: 10.1016/j.ins.2016.04.050 [13] Clerc M, Kennedy J. The particle swarm-explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation, 2002, 6 (1):58-73 doi: 10.1109/4235.985692 [14] 刘建华, 刘国买, 杨荣华, 胡文瑜.粒子群算法的交互性与随机性分析.自动化学报, 2012, 38 (9):1471-1484 http://www.aas.net.cn/CN/abstract/abstract17757.shtmlLiu Jian-Hua, Liu Guo-Mai, Yang Rong-Hua, Hu Wen-Yu. Analysis of interactivity and randomness in particle swarm optimization. Acta Automatica Sinica, 2012, 38 (9):1471-1484 http://www.aas.net.cn/CN/abstract/abstract17757.shtml [15] Leboucher C, Shin H S, Siarry P, Le Ménec S, Chelouah R, Tsourdos A. Convergence proof of an enhanced particle swarm optimisation method integrated with evolutionary game theory. Information Sciences, 2016, 346-347:389-411 doi: 10.1016/j.ins.2016.01.011 [16] Subasi M, Yildirim N, Yildiz B. An improvement on Fibonacci search method in optimization theory. Applied Mathematics and Computation, 2004, 147 (3):893-901 doi: 10.1016/S0096-3003(02)00828-7 [17] Liang J J, Qin A K, Suganthan P N, Baskar S. Comprehensive learning particle swarm optimizer for global optimization of multimodal functions. IEEE Transactions on Evolutionary Computation, 2006, 10 (3):281-295 doi: 10.1109/TEVC.2005.857610 [18] Suganthan P N, Hansen N, Liang J J, Deb K, Chen Y P, Auger A, Tiwari S. Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization. Singapore: Nanyang Technological University[Online], available: http://web.mysites.ntu.edu.sg/epn-sugan/PublicSite/Shared 期刊类型引用(6)
1. 董润婷，吴利，黄建强，王晓英. 基于矩阵嵌套的CESM负载均衡优化方案检索策略. 电子技术应用. 2022(01): 24-30 . 
百度学术2. 汤国生，修孝微，王明婷，常旺贤. 催化剂和温度对制备C4烯烃的影响. 实验室研究与探索. 2022(11): 28-32+75 . 百度学术3. 王霞，王耀民，施心陵，高莲，李鹏. 噪声环境下基于蒲丰距离的依概率多峰优化算法. 自动化学报. 2021(11): 2691-2714 . 本站查看4. 盛四清，畅达，张文朝，张振宇，王吉利，柯贤波. 基于斐波那契树辨识算法的区域电网调速系统参数辨识. 电测与仪表. 2020(08): 51-58 . 百度学术5. 杨辉，代文豪，陆荣秀，朱建勇. 基于分离系数校正的稀土萃取流程模拟. 化工学报. 2020(07): 3180-3190 . 百度学术6. 王耀民，王霞，董易，高莲，张松海，施心陵. 面向云数据中心的多业务差异化流量管理优化策略. 通信学报. 2019(11): 45-56 . 百度学术其他类型引用(7)
-
下载:
计量
- 文章访问数: 2370
- HTML全文浏览量: 515
- PDF下载量: 669
- 被引次数: 13
