自动化学报  2018, Vol. 44 Issue (9): 1679-1689   PDF    
斐波那契树优化算法求解多峰函数全局最优解的可达性分析
董易1, 施心陵1, 王霞1, 王耀民1, 吕丹桔1, 张松海1, 李孙寸1     
1. 云南大学信息学院 昆明 650504
摘要: 为分析和验证斐波那契树优化算法(Fibonacci tree optimization algorithm,FTO)求解多峰函数全局最优解的算法性能,对算法的可达性问题进行研究.本文基于斐波那契法构造一个斐波那契树结构,在搜索空间中进行全局、局部交替搜索,不易陷入局部最优解.对斐波那契树优化算法基于该结构的可达性进行分析和证明.通过跟踪算法求解过程中坐标点的累积分布仿真实验和到达率的对比实验,分析和验证了算法求解多峰函数全局最优解的可达性.
关键词: 斐波那契树优化算法     可达性     多峰函数优化     全局最优解    
On Accessibility of Fibonacci Tree Optimization Algorithm for Global Optima of Multi-modal Functions
DONG Yi1, SHI Xin-Ling1, WANG Xia1, WANG Yao-Min1, LV Dan-Ju1, ZHANG Song-Hai1, LI Sun-Cun1     
1. School of Information Science and Engineering, Yunnan University, Kunming 650504
Manuscript received : October 9, 2016, accepted: August 8, 2017.
Foundation Item: Supported by National Natural Science Foundation of China (61661050) and Science Research Foundation of Yunnan Provincial Department of Education (2017ZZX229)
Author brief: SHI Xin-Ling Professor at the School of Information Science and Engineering, Yunnan University. His research interest covers intelligent optimization algorithm, adaptive signal processing, information system, and medical electronics;
WANG Xia Ph. D. candidate at the School of Information Science and Engineering, Yunnan University. She received her master degree from the College of Physical Science and Technology, Central South University in 2010. Her main research interest is intelligent optimization algorithm;
WANG Yao-Min Ph. D. candidate at the School of Information Science and Engineering, Yunnan University. He received his master degree from the College of Telecommunications and Information Engineering, Nangjing University of Posts and Telecommunications in 2013. His main research interest is intelligent optimization algorithm;
LV Dan-Ju Ph. D. candidate at the School of Information Science and Engineering, Yunnan University. She received her master degree from the School of Information Science and Engineering, Yunnan University in 2013. Her main research interest is intelligent forestry information processing;
ZHANG Song-Hai Master student at the School of Information Science and Engineering, Yunnan University. His main research interest is intelligent optimization algorithm;
LI Sun-Cun Master student at the Science and Engineering, Yunnan University. Her main research interest is intelligent optimization algorithm.
Corresponding author. DONG Yi Ph. D. candidate at the School of Information Science and Engineering, Yunnan University. He received his master degree from the School of Information Science and Engineering, Yunnan University in 2009. His main research interest is intelligent optimization algorithm. Corresponding author of this paper.
Recommended by Associate Editor SUN Chang-Yin
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.
Key words: Fibonacci tree optimization algorithm (FTO)     accessibility     multi-modal functions optimization     global optima    

经典的智能优化算法在求解多峰函数全局最优解时, 存在易陷入局部最优解的早熟收敛问题[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 FTO算法基本结构 Figure 1 Basic structure of FTO

图 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 斐波那契树生成过程示意图 Figure 2 Building procedure of Fibonacci tree
2.3 算法流程

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

图 3 FTO算法流程图 Figure 3 Algorithm flow chart of FTO
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 algorithms
表 1 函数局部极值点 Table 1 Local optima of benchmark functions
表 3 测试函数列表 Table 3 Benchmark functions

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

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

图 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求解坐标点的累积分布示意图 Figure 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求解坐标点的累积分布示意图 Figure 6 Cumulative distribution of points of function Langermann

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

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

实验利用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
表 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

从表中可以看出, 对于测试函数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算法的全局搜索能力较好.

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

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

6 结论

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

参考文献
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
Li 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.
( 李建平, 宫耀华, 赵思远, 卢爱平, 李盼池. 粒子群优化算法的改进及数值仿真. 吉林大学学报(理学版), 2017, 55(2): 322-332.)
3
Gao Lei-Fu, Tong Pan. Combination algorithm of genetic-artificial bee colony and its Markov convergence analysis. Journal of Mathematics, 2017, 37(1): 215-222.
( 高雷阜, 佟盼. 遗传-人工蜂群融合算法及其Markov收敛性分析. 数学杂志, 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.
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.
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
Zhang Jun-Ying, Xu Jin, Bao Zheng. Attainability of genetic crossover operator. Acta Automatica Sinica, 2002, 28(1): 120-125.
( 张军英, 许进, 保铮. 遗传交叉运算的可达性研究. 自动化学报, 2002, 28(1): 120-125.)
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
Liu 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.
( 刘建华, 刘国买, 杨荣华, 胡文瑜. 粒子群算法的交互性与随机性分析. 自动化学报, 2012, 38(9): 1471-1484.)
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