2.793

2018影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

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

董易, 施心陵, 王霞, 王耀民, 吕丹桔, 张松海, 李孙寸. 斐波那契树优化算法求解多峰函数全局最优解的可达性分析. 自动化学报, 2018, 44(9): 1679-1689. doi: 10.16383/j.aas.2017.c160703
引用本文: 董易, 施心陵, 王霞, 王耀民, 吕丹桔, 张松海, 李孙寸. 斐波那契树优化算法求解多峰函数全局最优解的可达性分析. 自动化学报, 2018, 44(9): 1679-1689. doi: 10.16383/j.aas.2017.c160703
DONG Yi, SHI Xin-Ling, WANG Xia, WANG Yao-Min, LV Dan-Ju, ZHANG Song-Hai, LI Sun-Cun. On Accessibility of Fibonacci Tree Optimization Algorithm for Global Optima of Multi-modal Functions. ACTA AUTOMATICA SINICA, 2018, 44(9): 1679-1689. doi: 10.16383/j.aas.2017.c160703
Citation: DONG Yi, SHI Xin-Ling, WANG Xia, WANG Yao-Min, LV Dan-Ju, ZHANG Song-Hai, LI Sun-Cun. On Accessibility of Fibonacci Tree Optimization Algorithm for Global Optima of Multi-modal Functions. ACTA AUTOMATICA SINICA, 2018, 44(9): 1679-1689. doi: 10.16383/j.aas.2017.c160703

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


DOI: 10.16383/j.aas.2017.c160703
详细信息
    作者简介:

    施心陵 云南大学信息学院教授.主要研究方向为智能优化算法, 自适应信号处理与信息系统, 医学电子学.E-mail:xlshi@ynu.edu.cn

    王霞 云南大学信息学院博士研究生.2010年获得中南大学物理科学与技术学院硕士学位.主要研究方向为智能优化算法.E-mail:wangxiacsu@163.com

    王耀民 云南大学信息学院博士研究生.2013年获得南京邮电大学通信与信息工程学院硕士学位.主要研究方向为智能优化算法.E-mail:18988081898@189.cn

    吕丹桔 云南大学信息学院博士研究生.2013年获得云南大学信息学院硕士学位.主要研究方向为智能林业信息处理.E-mail:lvdanjv@hotmail.com

    张松海 云南大学信息学硕士研究生.主要研究方向为智能优化算法.E-mail:hai_zs@sina.com

    李孙寸 云南大学信息学院硕士研究生.主要研究方向为智能优化算法.E-mail:lisuncun@outlook.com

    通讯作者: 董易 云南大学信息学院博士研究生.2009年获得云南大学信息学院硕士学位.主要研究方向为智能优化算法.本文通信作者.E-mail:yeo003@163.com
  • 本文责任编委 孙长银
  • 基金项目:

    国家自然科学基金 61661050

    云南省教育厅科学研究基金项目 2017ZZX229

On Accessibility of Fibonacci Tree Optimization Algorithm for Global Optima of Multi-modal Functions

More Information
    Author Bio:

    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

    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

    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

    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

    Master student at the School of Information Science and Engineering, Yunnan University. His main research interest is intelligent optimization algorithm

    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
  • Fund Project:

    National Natural Science Foundation of China 61661050

    Science Research Foundation of Yunnan Provincial Department of Education 2017ZZX229

  • 摘要: 为分析和验证斐波那契树优化算法(Fibonacci tree optimization algorithm,FTO)求解多峰函数全局最优解的算法性能,对算法的可达性问题进行研究.本文基于斐波那契法构造一个斐波那契树结构,在搜索空间中进行全局、局部交替搜索,不易陷入局部最优解.对斐波那契树优化算法基于该结构的可达性进行分析和证明.通过跟踪算法求解过程中坐标点的累积分布仿真实验和到达率的对比实验,分析和验证了算法求解多峰函数全局最优解的可达性.
    本文责任编委 孙长银
  • 图  1  FTO算法基本结构

    Fig.  1  Basic structure of FTO

    图  2  斐波那契树生成过程示意图

    Fig.  2  Building procedure of Fibonacci tree

    图  3  FTO算法流程图

    Fig.  3  Algorithm flow chart of FTO

    图  4  函数图像和等高线示意图

    Fig.  4  Function graphs and contour graphs

    图  5  函数Damavandi求解坐标点的累积分布示意图

    Fig.  5  Cumulative distribution of points of function Damavandi

    图  6  函数Langermann求解坐标点的累积分布示意图

    Fig.  6  Cumulative distribution of points of function Langermann

    图  7  仿真实验收敛曲线

    Fig.  7  Convergence curves of simulation experiment

    图  8  对比实验的收敛曲线

    Fig.  8  Convergence curves of comparison experiment

    表  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/jldxzrkxxb201702024

    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 http://d.old.wanfangdata.com.cn/Periodical/jldxzrkxxb201702024
    [3] 高雷阜, 佟盼.遗传-人工蜂群融合算法及其Markov收敛性分析.数学杂志, 2017, 37 (1):215-222 doi:  10.3969/j.issn.0255-7797.2017.01.023

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

    Zhang 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.shtml

    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 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
  • [1] 唐昊, 刘畅, 杨明, 汤必强, 许丹, 吕凯. 考虑电网调峰需求的工业园区主动配电系统调度学习优化[J]. 自动化学报, 2019, 45(): 1-15. doi: 10.16383/j.aas.c190079
    [2] 谢理想, 万刚, 曹雪峰, 王庆贺, 王龙. 基于凸优化改进的相机全局位置估计方法[J]. 自动化学报, 2018, 44(3): 506-516. doi: 10.16383/j.aas.2018.c160639
    [3] 吕柏权, 张静静, 李占培, 刘廷章. 基于变换函数与填充函数的模糊粒子群优化算法[J]. 自动化学报, 2018, 44(1): 74-86. doi: 10.16383/j.aas.2018.c160547
    [4] 陆志君, 安俊秀, 王鹏. 基于划分的多尺度量子谐振子算法多峰优化[J]. 自动化学报, 2016, 42(2): 235-245. doi: 10.16383/j.aas.2016.c150429
    [5] 干梦迪, 王寿光, 周孟初, 李俊, 李月. 无界Petri网的可达树的综述[J]. 自动化学报, 2015, 41(4): 686-693. doi: 10.16383/j.aas.2015.c140097
    [6] 顾启泰, 方靖. 广义联邦滤波器的全局最优性[J]. 自动化学报, 2009, 35(10): 1310-1316. doi: 10.3724/SP.J.1004.2009.01310
    [7] 吴敏, 颜钢锋, 林志赟. 多面体上彷射系统可达性问题研究[J]. 自动化学报, 2009, 35(12): 1528-1533. doi: 10.3724/SP.J.1004.2009.01528
    [8] 李航, 李敏强, 寇纪淞. 遗传算法求解多模态优化问题的动力性[J]. 自动化学报, 2008, 34(2): 180-187. doi: 10.3724/SP.J.1004.2008.00180
    [9] 谭冠政, 贺欢, SLOMAN A. 基于ACS算法的移动机器人实时全局最优路径规划[J]. 自动化学报, 2007, 33(3): 279-285. doi: 10.1360/aas-007-0279
    [10] 张纯刚, 席裕庚. 基于局部探测信息的机器人滚动路径规划[J]. 自动化学报, 2003, 29(1): 38-44.
    [11] 张纯刚, 席裕庚. 一种克服振荡与死循环的机器人实时路径规划方法[J]. 自动化学报, 2003, 29(2): 197-205.
    [12] 李敏强, 寇纪淞. 多模态函数优化的协同多群体遗传算法[J]. 自动化学报, 2002, 28(4): 497-504.
    [13] 张军英, 许进, 保铮. 遗传交叉运算的可达性研究[J]. 自动化学报, 2002, 28(1): 120-125.
    [14] 席裕庚, 张纯刚. 一类动态不确定环境下机器人的滚动路径规划[J]. 自动化学报, 2002, 28(2): 161-175.
    [15] 于歆杰, 王赞基. 自适应调整峰半径的适应值共享遗传算法[J]. 自动化学报, 2002, 28(5): 816-820.
    [16] 阮小娥, 万百五, 高红霞. 具有滞后的饱和非线性工业控制系统的迭代学习控制[J]. 自动化学报, 2001, 27(2): 219-223.
    [17] 李兵, 蒋慰孙. SAGACIA全局优化方法及应用[J]. 自动化学报, 1998, 24(2): 269-271.
    [18] 汪涛, 邢小良, 庄新华. 无对应点三维表面重建的全局优化算法[J]. 自动化学报, 1993, 19(4): 497-499.
    [19] 廖炯生. 解非串并联系统可靠性最优化问题的一个简捷算法[J]. 自动化学报, 1981, 7(1): 77-80.
    [20] 廖炯生. 用优选法解系统可靠性最优化问题的一个简捷算法[J]. 自动化学报, 1980, 6(1): 18-24.
  • 加载中
图(8) / 表(12)
计量
  • 文章访问数:  621
  • HTML全文浏览量:  186
  • PDF下载量:  599
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-10-09
  • 录用日期:  2017-08-08
  • 刊出日期:  2018-09-20

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

doi: 10.16383/j.aas.2017.c160703
    基金项目:

    国家自然科学基金 61661050

    云南省教育厅科学研究基金项目 2017ZZX229

    作者简介:

    施心陵 云南大学信息学院教授.主要研究方向为智能优化算法, 自适应信号处理与信息系统, 医学电子学.E-mail:xlshi@ynu.edu.cn

    王霞 云南大学信息学院博士研究生.2010年获得中南大学物理科学与技术学院硕士学位.主要研究方向为智能优化算法.E-mail:wangxiacsu@163.com

    王耀民 云南大学信息学院博士研究生.2013年获得南京邮电大学通信与信息工程学院硕士学位.主要研究方向为智能优化算法.E-mail:18988081898@189.cn

    吕丹桔 云南大学信息学院博士研究生.2013年获得云南大学信息学院硕士学位.主要研究方向为智能林业信息处理.E-mail:lvdanjv@hotmail.com

    张松海 云南大学信息学硕士研究生.主要研究方向为智能优化算法.E-mail:hai_zs@sina.com

    李孙寸 云南大学信息学院硕士研究生.主要研究方向为智能优化算法.E-mail:lisuncun@outlook.com

    通讯作者: 董易 云南大学信息学院博士研究生.2009年获得云南大学信息学院硕士学位.主要研究方向为智能优化算法.本文通信作者.E-mail:yeo003@163.com
  • 本文责任编委 孙长银

摘要: 为分析和验证斐波那契树优化算法(Fibonacci tree optimization algorithm,FTO)求解多峰函数全局最优解的算法性能,对算法的可达性问题进行研究.本文基于斐波那契法构造一个斐波那契树结构,在搜索空间中进行全局、局部交替搜索,不易陷入局部最优解.对斐波那契树优化算法基于该结构的可达性进行分析和证明.通过跟踪算法求解过程中坐标点的累积分布仿真实验和到达率的对比实验,分析和验证了算法求解多峰函数全局最优解的可达性.

本文责任编委 孙长银

English Abstract

董易, 施心陵, 王霞, 王耀民, 吕丹桔, 张松海, 李孙寸. 斐波那契树优化算法求解多峰函数全局最优解的可达性分析. 自动化学报, 2018, 44(9): 1679-1689. doi: 10.16383/j.aas.2017.c160703
引用本文: 董易, 施心陵, 王霞, 王耀民, 吕丹桔, 张松海, 李孙寸. 斐波那契树优化算法求解多峰函数全局最优解的可达性分析. 自动化学报, 2018, 44(9): 1679-1689. doi: 10.16383/j.aas.2017.c160703
DONG Yi, SHI Xin-Ling, WANG Xia, WANG Yao-Min, LV Dan-Ju, ZHANG Song-Hai, LI Sun-Cun. On Accessibility of Fibonacci Tree Optimization Algorithm for Global Optima of Multi-modal Functions. ACTA AUTOMATICA SINICA, 2018, 44(9): 1679-1689. doi: 10.16383/j.aas.2017.c160703
Citation: DONG Yi, SHI Xin-Ling, WANG Xia, WANG Yao-Min, LV Dan-Ju, ZHANG Song-Hai, LI Sun-Cun. On Accessibility of Fibonacci Tree Optimization Algorithm for Global Optima of Multi-modal Functions. ACTA AUTOMATICA SINICA, 2018, 44(9): 1679-1689. doi: 10.16383/j.aas.2017.c160703
  • 经典的智能优化算法在求解多峰函数全局最优解时, 存在易陷入局部最优解的早熟收敛问题[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)独立重复求解实验, 计算到达率, 并对算法收敛曲线进行分析.

    • 令$ 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].

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

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

      新点的生成依据斐波那契法的比例关系进行计算.设当前斐波那契数列第$ i$ 项为$ F_i $ , 第$ i+1 $ 项为$ F_{i+1}$ , 则从已有的两点计算新点的比例关系为$ F_i/$ $F_{i+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)
    • 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

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

      图  3  FTO算法流程图

      Figure 3.  Algorithm flow chart of 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$ .

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

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

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

      算法参数设置见表 2.表 1是函数Damavandi和Langermann的局部极值点, 其中局部极值1是全局最优解, 局部极值2是一个次优解.实验使用表 3中的函数Damavandi和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

      表 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中局部极值点的坐标.

      图  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算法可达性.

    • 为对比和验证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.

    • 实验结果如表 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测试函数的未达均值都大于全局最优解.

    • 从收敛曲线的变化来分析和验证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次的变化曲线.

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

参考文献 (18)

目录

    /

    返回文章
    返回