多精英采样与个体差分学习的分布估计算法

doi:10.16182/j.issn1004731x.joss.18-0836

系统仿真学报 ›› 2020, Vol. 32 ›› Issue (3): 382-393.doi: 10.16182/j.issn1004731x.joss.18-0836

多精英采样与个体差分学习的分布估计算法

喻飞¹, 吴瑞峰^2*, 魏波², 张应龙¹, 夏学文¹

1. 闽南师范大学物理与信息工程学院,福建漳州 363000;
2. 华东交通大学软件学院,江西南昌 330013

收稿日期:2018-12-17 修回日期:2019-05-13 出版日期:2020-03-18 发布日期:2020-03-25
作者简介:喻飞(1981-),男,湖北钟祥,博士,副教授,研究方向为计算智能及其应用,机器学习等。
基金资助:
国家自然科学基金(61663009,61762036,61806204,61876136),江西省自然科学基金(20171BAB202012),福建省本科高校重大教育教学改革研究项目(FBJG20180015),江西省交通厅科研项目(2017D0038)

An Estimation of Distribution Algorithm Based on Multiple Elites Sampling and Individuals Differential Search

Yu Fei¹, Wu Ruifeng^2*, Wei Bo², Zhang Yinglong¹, Xia Xuewen¹

1. Min Nan Normal University, School of Physics and Information Engineering, Zhangzhou 363000, China;
2. East China Jiaotong University, School of Software, Nanchang 330013, China

Received:2018-12-17 Revised:2019-05-13 Online:2020-03-18 Published:2020-03-25

摘要/Abstract

摘要： 提出了基于多精英采样和差分搜索的分布估计算法EDA-M/D (Estimation distribution algorithm based on multiple elites sampling and individuals differential search)。EDA-M/D利用多精英个体独立采样生成子代来提升算法全局搜索能力,利用精英群体分布的σ²约束采样半径,实现种群从全局搜索逐步过度到局部搜索。当精英群体停滞时,劣势个体借助精英群体的μ和种群历史最优解进行差分搜索,帮助种群跳出局部最优解。通过多精英采样与差分搜索的自适应协同实现种群宏观信息与个体微观信息的有机融合。实验结果表明EDA-M/D在稳定性和搜索能力方面均表现出明显的优势。

关键词: 分布估计算法, 多精英采样, 差分搜索, 基因修复

Abstract: An estimation distribution algorithm based on the multiple elites sampling and the individuals differential search (EDA-M/D) is proposed. In EDA-M/D, the elites carry out the sampling to generate the offspring independently and enhance the exploration. Meanwhile, the variance of the population distributionis selected to control the sampling radius. Thus, the target of the population can be gradually transited from exploration to exploitation. If the elite population stagnates, the nonentities will choose the mean value of the elites distribution μ and the population historical best solution as the two exemplars to execute a differential search operator, and then help the population jump out of a potential local optimum. Based on the adaptive strategy, two generation methods for the offspring, i.e., basing on the multiple elites sampling and the differential search, can be hybridized. Hence, the macro information of population and the micro information of individuals can be organically integrated. Experimental results show that EDA-M/D outperforms the other peer algorithms in the algorithm stability and the global optimal search capability.

Key words: estimation of distribution algorithm, multiple elites sampling, differential search, gene rectification

中图分类号:

TP301

喻飞, 吴瑞峰, 魏波, 张应龙, 夏学文. 多精英采样与个体差分学习的分布估计算法[J]. 系统仿真学报, 2020, 32(3): 382-393.

Yu Fei, Wu Ruifeng, Wei Bo, Zhang Yinglong, Xia Xuewen. An Estimation of Distribution Algorithm Based on Multiple Elites Sampling and Individuals Differential Search[J]. Journal of System Simulation, 2020, 32(3): 382-393.

参考文献

[1] Larrañaga P, Lozano JA.Estimation of distribution algorithms[J]. Genetic Algorithms & Evolutionary Computation (S1063-6560), 2001, 64(5): 454-468.
[2] 周树德, 孙增圻. 分布估计算法综述[J]. 自动化学报, 2007, 33(2): 113-124.
Zhou Shude, Sun Zengqi.A survey estimation of distribution algorithms[J]. Acta Automatica Sinica, 2007, 33(2): 113-124.
[3] 任志刚, 梁永胜, 张爱民, 等. 基于一般二阶混合矩的高斯分布估计算法[J]. 自动化学报, 2018, 44(4): 635-645.
Ren Zhigang, Liang Yongsheng, Zhang Aimin, et al.A gaussian estimation of distribution algorithm using general second-order mixed moment[J]. Acta Automatica Sinice, 2018, 44(4): 635-645.
[4] Zhou A M, Sun J Y, Zhang Q F.An estimation of distribution algorithm with cheap and expensive local search methods[J]. IEEE Transactions on Evolutionary Computation (S1089-778X), 2015, 19(6): 807-822.
[5] Wang J, Tang K, Lozano JA, et al.Estimation of the distribution algorithm with a stochastic local search for uncertain capacitated arc routing problems[J]. IEEE Transactions on Evolutionary Computation (S1089-778X), 2016, 20(1): 96-109.
[6] 陈伟能, 杨强. 基于概率分布的多峰演化算法[J]. 计算机研究与发展, 2017, 54(6): 1185-1197.
Chen Weineng, Yang Qiang.Probability distribution based evolutionary computation algorithms for multimodal optimization[J]. Journal of Computer Research and Development, 2017, 54(6): 1185-1197.
[7] Baluja S.Population-Based Incremental Learning. A method for integrating genetic search based function optimization and competitive learning[R]. Technical Report CMU-CS-94-163, Pittsburgh, PA: Carnegie Mellon University, 1994.
[8] Sebag M, Ducoulombier A.Extending population-based incremental learning to continuous domains by learning and simulation of Gaussian networks[C]. Proc. of the 5th Conference on Parallel Problem Solving from Nature. Amsterdam, Netherlands: Springer, 1998: 418-427.
[9] Mühlenbein H, Paass G.From recombination of genes to the estimation of distributions[C]. Proc. of the 4th Parallel Problem Solving from Nature. Berlin, Germany: Springer, 1996: 178-187.
[10] Mühlenbein H.The equation for response to selection and its use for prediction[J]. Evolutionary Computation (S1063-6560), 2014, 5(3): 303-346.
[11] Larranaga P, Etxeberria R, Lozano JA, Pena JM.Optimization in continuous domains by learning and simulation of Gaussian networks[C]. Proc. of the 2000 Genetic and Evolutionary Computation Conference Workshop Program. Nevada, USA: ACM, 2000: 201-204.
[12] Harik G R, Lobo F G, Goldberg D E.The compact genetic algorithm[J]. IEEE Transactions on Evolutionary Computation (S1089-778X), 1999, 3(4): 287-297.
[13] Krejca M S, Witt C.Lower bounds on the run time of the univariate marginal distribution algorithm on onemax[C]. Proc. of Acm/sigevo Conference on Foundations of Genetic Algorithms. Copenhagen, Denmark: ACM, 2017: 65-79.
[14] Baluja S, Davies S.Using optimal dependency-trees for combinatorial optimization: learning the structure of the search space[C]. Proc. of International Conference on Machine Learning. San Francisco, USA: ACM, 1997: 30-38.
[15] Henry E C, Rodrigo C B, Marcio P B.Estimation of distribution algorithms for decision-tree induction[C]. Proc. of IEEE Congress on Evolutionary Computation. San Sebastian, Spain: IEEE, 2017: 2022-2029.
[16] 邱玲, 高尚, 曹存根. 改进的正态分布的分布估计算法[J]. 计算机科学, 2015, 42(8): 32-35.
Qiu Ling, Gao Shang, Cao Cungen.Improved estimation of distribution algorithms based on normal distribution[J]. Computer Science, 2015, 42(8): 32-35.
[17] 刘小龙, 李荣钧, 杨萍. 基于高斯分布估计的细菌觅食优化算法[J]. 控制与决策, 2011, 26(8): 1233-1238.
Liu Xiaolong, Li Rongjun, Yang Ping.Bacterial foraging optimization algorithm based on estimation of distribution[J]. Control and Decision, 2011, 26(8): 1233-1238.
[18] El-Abd M.Preventing premature convergence in a PSO and EDA hybrid[C]. Proc. of IEEE Congress on Evolutionary Computation. Trondheim, Norway: IEEE, 2009: 3060-3066.
[19] Shao W, Shang L, Ma L, et al.Hybrid Differential Evolution/Estimation of Distribution Algorithm Based on Adaptive Incremental Learning[J]. Journal of Computational Information Systems (S0887-4417), 2014, 10(12): 5355-5364.
[20] Peña J M, Robles V, Larrañaga P, et al.GA-EDA: Hybrid evolutionary algorithm using Genetic and estimation of distribution algorithms[C]. Proc. Of the 17th International Conference on Innovations in Applied Artificial Intelligence. Ottawa, Canada: ACM, 2004: 361-371.
[21] Awad N H, Ali M Z, Liang J J, et al.Problem definitions and evaluation criteria for the CEC 2017 special session and competition on single objective real-parameter numerical optimization[R]. Nanyang Technological University, Singapore, Technical Report, 2016.

多精英采样与个体差分学习的分布估计算法

An Estimation of Distribution Algorithm Based on Multiple Elites Sampling and Individuals Differential Search

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价