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) 本文责任编委 孙长银
-
图 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 -
计量
- 文章访问数: 2323
- HTML全文浏览量: 478
- PDF下载量: 656
- 被引次数: 0
