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

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

Abstract

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

CLC Number:

TP301

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.

References

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