﻿ 斐波那契树优化算法求解多峰函数全局最优解的可达性分析
 首页 关于本刊 编 委 会 期刊动态 作者中心 审者中心 读者中心 下载中心 联系我们 English
 自动化学报  2018, Vol. 44 Issue (9): 1679-1689 PDF

1. 云南大学信息学院 昆明 650504

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)
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.
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 斐波那契法最优化原理概述

$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$ .

 $\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)

2 斐波那契树优化算法

2.1 基本结构

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

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

 \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)

 \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$ .

 图 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算法的可达性分析

 \begin{align} \underbrace{\idotsint}_D\frac{1}{x_{\max}-x_{\min}}{\rm d}x_d=1 \end{align} (5)

4 可达性仿真实验与分析

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

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

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

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

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

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

5 对比实验与分析

 \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)

5.1 实验结果分析

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

5.2 收敛曲线分析

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

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

6 结论

 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