Multi-objective estimation of distribution algorithm with adaptive opposition-based learning

doi:10.11772/j.issn.1001-9081.2020060908

Abstract

Abstract: Aiming at the defect of poor global convergence of the regularity model-based multi-objective estimation of distribution algorithm, a multi-objective estimation of distribution algorithm based on adaptive Opposition-Based Learning (OBL) was proposed. In the algorithm, whether to carry out OBL was judged according to the change rate of the function. When the change rate of the function was small, the algorithm was easily to fall into the local optimum, so that OBL was performed to increase the diversity of individuals in current population. When the change rate of the function was large, the regularity model-based multi-objective estimation of distribution algorithm was run. In the proposed algorithm, with the timely introduction of OBL strategy, the influences of population diversity and individual distribution on the overall convergence quality and speed of optimization algorithm were reduced. In order to verify the performance of the improved algorithm, Regularity Model-based Multi-objective Estimation of Distribution Algorithm (RM-MEDA), Hybrid Wading across Stream Algorithm-Estimation Distribution Algorithm (HWSA-EDA) and Inverse Modeling based multiObjective Evolutionary Algorithm (IM-MOEA) were selected as comparison algorithms to carry out the test with the proposed algorithm on ZDT and DTLZ test functions respectively. The test results show that the proposed algorithm not only has good global convergence, but also improves the distribution and uniformity of solutions except on DTLZ2 function.

Key words: Multi-objective Optimization Problem (MOP), local optimum, Opposition-Based Learning (OBL), population diversity, convergence

摘要： 针对基于规则模型的多目标分布估计算法全局收敛性较弱的缺陷，提出了一种基于自适应反向学习（OBL）的多目标分布估计算法。该算法根据函数变化率的大小来决定是否进行OBL：当函数变化率较小时，算法可能陷入局部最优，所以进行OBL以提高当前种群中个体的多样性；当函数变化率较大时，运行基于规则模型的多目标分布估计算法。所提算法通过适时地引入OBL策略，减小了种群多样性及个体的分布情况对优化算法整体收敛质量以及收敛速度的影响。为了验证改进算法的性能，选取基于规则模型的多目标分布估计算法（RM-MEDA）、摸石头过河算法与分布估计混合算法（HWSA-EDA）以及基于逆建模的多目标进化算法（IM-MOEA）作为对比算法与所提算法分别在ZDT和DTLZ测试函数上进行测试。测试结果表明，除了在DTLZ2函数上以外，所提算法不仅有良好的全局收敛性，而且解的分布性和均匀性都有所提高。

关键词: 多目标优化问题, 局部最优, 反向学习, 种群多样性, 收敛性

CLC Number:

TP18

LI Erchao, YANG Rongrong. Multi-objective estimation of distribution algorithm with adaptive opposition-based learning[J]. Journal of Computer Applications, 2021, 41(1): 15-21.

李二超, 杨蓉蓉. 基于自适应反向学习的多目标分布估计算法[J]. 计算机应用, 2021, 41(1): 15-21.

References

[1] WANG X,XING K,LI X,et al. An estimation of distribution algorithm for scheduling problem of flexible manufacturing systems using Petri nets[J]. Applied Mathematical Modelling,2018,55:776-788.
[2] KREJCA M S,WITT C. Lower bounds on the run time of the univariate marginal distribution algorithm on OneMax[J]. Theoretical Computer Science,2020,832:143-165.
[3] 陈杨. 面向个性化搜索的交互式分布估计算法[D]. 徐州:中国矿业大学,2019:11-79.(CHEN Y. Interactive estimation of distribution algorithm for personalized search[D]. Xuzhou:China University of Mining and Technology,2019:11-79.)
[4] 刘可, 巩敦卫. 用于指尖定位的多目标分布估计算法[J]. 郑州大学学报(工学版),2019,40(4):68-72,79.(LIU K,GONG D W. A multi-objective estimation of distribution algorithm for fingertip localization[J]. Journal of Zhengzhou University (Engineering Edition),2019,40(4):68-72,79.)
[5] DEB K,PRATAP A,AGARWAL S,et al. A fast and elitist multiobjective genetic algorithm:NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.
[6] COELLO C A C, PULIDO G T, LECHUGA M S. Handling multiple objectives with particle swarm optimization[J]. IEEE Transactions on Evolutionary Computation,2004,8(3):256-279.
[7] DORIGO M,BLUM C. Ant colony optimization theory:a survey[J]. Theoretical Computer Science,2005,344(2/3):243-278.
[8] LARRAÑGA P, LOZANO J A. Estimation of Distribution Algorithms:A New Tool for Evolutionary Computation,GENA 2[M]. Boston:Springer,2001:455-460.
[9] ZHANG Q,ZHOU A,JIN Y. RM-MEDA:a regularity modelbased multiobjective estimation of distribution algorithm[J]. IEEE Transactions on Evolutionary Computation,2008,12(1):41-63.
[10] 高尚, 曹存根. 摸石头过河算法与分布估计混合算法[J]. 计算机科学,2016,43(1):81-84.(GAO S,CAO C G. Solving continuous optimization problem by hybrid wading across stream algorithm-estimation distribution algorithm[J]. Computer Science,2016,43(1):81-84.)
[11] 高尚, 刘勇. 基于分布估计算法的多目标优化[J]. 软件, 2017, 38(12):25-28. (GAO S, LIU Y. Multi-objective optimization problem solved by estimation of distribution algorithm[J]. Computer Engineering and Software,2017,38(12):25-28.)
[12] 罗辞勇, 卢斌, 陈民铀. 采用两步训练法的多目标分布估计算法[J]. 控制与决策,2010,25(7):1105-1108,1112.(LUO C Y,LU B,CHEN M Y. Regularity model-based multiobjective estimation of distribution algorithm with two steps training method[J]. Control and Decision,2010,25(7):1105-1108,1112.)
[13] CHENG R,JIN Y,NARUKAWA K,et al. A multiobjective evolutionary algorithm using Gaussian process-based inverse modeling[J]. IEEE Transactions on Evolutionary Computation, 2015,19(6):838-856.
[14] 王慧君. 基于规则模型学习的多目标分布估计算法研究[D]. 西安:西安理工大学,2019:30-48.(WANG H J. Research on multi-objective estimation of distribution algorithms based on regularity model learning[D]. Xi'an:Xi'an University of Technology,2019:30-48.)
[15] 吴烨烨, 高尚. 改进的分布估计算法求解多目标优化问题[J]. 计算机与数字工程,2019,47(6):1357-1363.(WU Y Y,GAO S. Improved estimation of distribution algorithm for multi-objective optimization problems[J]. Computer and Digital Engineering, 2019,47(6):1357-1363.)
[16] TIZHOOSH H R. Opposition-based reinforcement learning[J]. Journal of Advanced Computational Intelligence and Intelligent Informatics,2006,10(4):578-585.
[17] SHAHZAD F,MASOOD S,KHAN N K. Probabilistic oppositionbased particle swarm optimization with velocity clamping[J]. Knowledge and Information Systems,2014,39(3):703-737.
[18] RAHNAMAYAN S, TIZHOOSH H R, SALAMA M M A. Opposition-based differential evolution[J]. IEEE Transactions on Evolutionary computation,2008,12(1):64-79.
[19] GUO Z,WANG S,YUE X,et al. Global harmony search with generalized opposition-based learning[J]. Soft Computing,2017, 21(8):2129-2137.
[20] 梁玉洁, 许峰. 自适应混合多目标分布估计进化算法[J]. 计算机工程与应用,2014,50(5):46-50,207.(LIANG Y J,XU F. Adaptive hybrid multi-objective estimation of distribution evolutionary algorithm[J]. Computer Engineering and Applications,2014,50(5):46-50,207.)
[21] BOSMAN P A N,THIERENS D. The balance between proximity and diversity in multiobjective evolutionary algorithms[J]. IEEE Transactions on Evolutionary Computation,2003,7(2):174-188.
[22] ZITZLER E,THIELE L. Multiobjective evolutionary algorithms:a comparative case study and the strength Pareto approach[J]. IEEE Transactions on Evolutionary Computation,1999,3(4):257-271.