多种群伪正态分布估计算法

doi:10.16451/j.cnki.issn1003-6059.202107004

Abstract
Figure/Table
References (44)
Related Citation (4)

Download: PDF (840 KB) HTML (1 KB)
Export: BibTeX | EndNote (RIS)

Abstract

To improve the quality of the candidate solutions and prevent the premature convergence simultaneously, a multiple populations based estimation of pseudo-normal distribution algorithm(MEPDA) is presented. The population is initialized by the good point set method and it is divided into three subgroups. By replacing sample mean with the gravity center of the samples, a pseudo-normal distribution model is obtained consequently. The probabilistic model for the subgroup evolution is built up by a linear combination of the pseudo-normal distribution models of the population and the subgroup. The comparative optimization tests on 23 benchmark functions show that MEPDA produces higher convergence speed and accuracy of the solutions. To solve the parallel assembly optimization problem with multiple constraints, the process pool, employee pool, penalty function and other measures are proposed to transform the discrete combinational optimization problem with constrained procedures and operators to an unconstrained multi-population based estimation of pseudo-normal distribution optimization problem. An engineering application demonstrates that MEPDA can be applied to the discrete combination optimization problem by just replacing the infinite set of the candidate solutions with a finite one.

Key words： Estimation of Distribution Algorithm Normal Distribution Parallel Assembly Problem Multiple Populations

Received: 15 November 2020

ZTFLH:

TP18

Corresponding Authors: YANG Qiwen, Ph.D., associate professor. His research interests include computational intelligence, sys-tem optimization and control.

About author:: YU Shiqi, master student. Her research interests include detection technology and inte-lligent system.ZHANG Meilin, master student. Her research interests include system scheduling and optimization.XUE Yuncan, Ph.D., professor. His research interests include intelligent optimization, process modeling and control.CHEN Junfeng, Ph.D., associate profe-ssor. Her research interests include computational intelligence and big data analysis.

	Service

	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	YANG Qiwen
	YU Shiqi
	ZHANG Meilin
	XUE Yuncan
	CHEN Junfeng

Cite this article:

YANG Qiwen,YU Shiqi,ZHANG Meilin等. Multiple Populations Based Estimation of Pseudo-Normal Distribution Algorithm[J]. , 2021, 34(7): 619-630.

URL:

http://manu46.magtech.com.cn/Jweb_prai/EN/10.16451/j.cnki.issn1003-6059.202107004 OR http://manu46.magtech.com.cn/Jweb_prai/EN/Y2021/V34/I7/619

[1] 王圣尧,王凌,方晨,等.分布估计算法研究进展.控制与决策, 2012, 27(7): 961-966, 974.
(WANG S Y, WANG L, FANG C, et al. Advances in Estimation of Distribution Algorithms. Control and Decision, 2012, 27(7): 961-966, 974.)
[2] 王赞,樊向宇,邹雨果,等.一种基于遗传算法的多缺陷定位方法.软件学报, 2016, 27(4): 879-900.
(WANG Z, FAN X Y, ZOU Y G, et al. Genetic Algorithm Based Multiple Faults Localization Technique. Journal of Software, 2016, 27(4): 879-900.)
[3] 韩红桂,卢薇,乔俊飞.一种基于多样性信息和收敛度的多目标粒子群优化算法.电子学报, 2018, 46(2): 315-324.
(HAN H G, LU W, QIAO J F. A Multiobjective Particle Swarm Optimization Algorithm Based on the Diversity Information and Convergence Degree. Acta Electronica Sinica, 2018, 46(2): 315-324.)
[4] 段其昌,唐若笠,徐宏英,等.粒子群优化鱼群算法仿真分析.控制与决策, 2013, 28(9): 1436-1440.
(DUAN Q C, TANG R L, XU H Y, et al. Simulation Analysis of the Fish Swarm Algorithm Optimized by PSO. Control and Decision, 2013, 28(9): 1436-1440.)
[5] 许凯波,鲁海燕,黄洋,等.基于双层蚁群算法和动态环境的机器人路径规划方法.电子学报, 2019, 47(10): 2166-2176.
(XU K B, LU H Y, HUANG Y, et al. Robot Path Planning Based on Double-Layer Ant Colony Optimization Algorithm and Dynamic Environment. Acta Electronica Sinica, 2019, 47(10): 2166-2176.)
[6] PELIKAN M, GOLDBERG D E, LOBO F G. A Survey of Optimization by Building and Using Probabilistic Models. Computational Optimization and Applications, 2002, 21(1): 5-20.
[7] MÜHLENBEIN H. The Equation for Response to Selection and Its Use for Prediction. Evolutionary Computation, 1997, 5(3): 303-346.
[8] HARIK G R, LOBO F G, GOLDBERG D E. The Compact Genetic Algorithm. IEEE Transactions on Evolutionary Computation, 1999, 3(4): 287-297.
[9] 周树德,孙增圻.分布估计算法综述.自动化学报, 2007, 33(2): 113-124.
(ZHOU S D, SUN Z Q. A Survey on Estimation of Distribution Algorithms. Acta Automatica Sinica, 2007, 33(2): 113-124.)
[10] BALUJA S, DAVIES S. Using Optimal Dependency-Trees for Com-binatorial Optimization//Proc of the 14th International Conference on Machine Learning. New York, USA: ACM, 1997: 30-38.
[11] MÜHLENBEIN H, MAHNIG T. Convergence Theory and Applications of the Factorized Distribution Algorithm. Journal of Computing and Information Technology, 1999, 7(1): 19-32.
[12] PELIKAN M, GOLDBERG D E, CANTU P E. BOA: The Baye-sian Optimization Algorithm//Proc of the 1st Annual Conference on Genetic and Evolutionary Computation. New York, USA: ACM, 1999, I: 525-532.
[13] 左先亮,郭莉莉,高尚.改进分布估计算法解决多约束集装箱装载问题.科学技术与工程, 2014, 14(11): 216-220.
(ZUO X L, GUO L L, GAO S. Solution to Multi-constraints Container Loading Problem Based on Improved Estimation of Distribution Algorithm. Science Technology and Engineering, 2014, 14(11): 216-220.)
[14] 张建华,曾建潮.经验分布函数概率模型的分布估计算法.计算机工程与应用, 2011, 47(8): 33-35.
(ZHANG J H, ZENG J C. Estimation of Distribution Algorithms Using Empirical Distribution Function as Probability Model. Computer Engineering and Applications, 2011, 47(8): 33-35.)
[15] 王丽芳,曾建潮,洪毅.利用Copula函数估计概率模型并采样的分布估计算法.控制与决策, 2011, 26(9): 1333-1337, 1342.
(WANG L F, ZENG J C, HONG Y. Estimation of Distribution Algorithm Modeling and Sampling by Means of Copula. Control and Decision, 2011, 26(9): 1333-1337, 1342.)
[16] PEÑA J M, ROBLES V, LARRANAGA P, et al. GA-EDA: Hybrid Evolutionary Algorithm Using Genetic and Estimation of Distribution Algorithms//Proc of the International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems. Berlin, Germany: Springer, 2004: 361-371.
[17] 王雪松,程玉虎,郝名林.基于细菌觅食行为的分布估计算法在预测控制中的应用.电子学报, 2010, 38(2): 333-339.
(WANG X S, CHENG Y H, HAO M L. Estimation of Distribution Algorithm Based on Bacterial Foraging and Its Application in Predictive Control. Acta Electronica Sinica, 2010, 38(2): 333-339.)
[18] 李静.一种基于单纯形法的分布式估计算法.科学技术与工程, 2014, 14(32): 262-265.
(LI J. Estimation of Distribution Algorithms Based on Simplex Method. Science Technology and Engineering, 2014, 14(32): 262-265.)
[19] LIANG Y S, REN Z G, HE M, et al. An Efficient Estimation of Distribution Algorithm with Rank-One Modification and Population Reduction. Biosystems, 2019, 181: 58-70.
[20] POURMOHAMMADBAGHER L, EBADZADEH M M, SAFABAKHSH R. Graphical Model Based Continuous Estimation of Distribution Algorithm. Applied Soft Computing, 2017, 58(1): 388-400.
[21] 陈静,林雅婷,周清旭,等.基于峰值匹配分布式估计算法的光纤布拉格光栅传感网络重叠光谱的波长解调.光子学报, 2019, 48(4): 79-86.
(CHEN J, LIN Y T, ZHOU Q X, et al. Wavelength Demodulation of a Spectrally Overlapped Fiber Bragg Grating Sensor Network Based on Peak Match Estimation of Distribution Algorithm. Acta Photonica Sinica, 2019, 48(4): 79-86.)
[22] 杨晓林,胡蓉,钱斌,等.增强分布估计算法求解低碳分布式流水线调度.控制理论与应用, 2019, 36(5): 803-815.
(YANG X L, HU R, QIAN B, et al. Enhanced Estimation of Distribution Algorithm for Low Carbon Scheduling of Distributed Flow Shop Problem. Control Theory and Applications, 2019, 36(5): 803-815.)
[23] 杨志家,王子,汪扬,等.车辆合乘问题的两阶段分布式估计算法.交通运输系统工程与信息, 2016, 16(2): 164-169.
(YANG Z J, WANG Z, WANG Y, et al. Two-Stage Estimation of Distribution Algorithm to Solve Multi-vehicle Carpooling Problem. Journal of Transportation Systems Engineering and Information Technology, 2016, 16(2): 164-169.)
[24] 张建.分布式估计算法在考虑差异工件的并行批处理机调度中的应用.计算机系统应用, 2019, 28(6): 213-220.
(ZHANG J. Application of Estimation of Distribution Algorithm to Parallel Batch Processing Machines with Non-identical Job Sizes. Computer Systems and Applications, 2019, 28(6): 213-220.)
[25] HAO X, GEN M, LIN L, et al. Effective Multi-objective EDA for Bi-criteria Stochastic Job-Shop Scheduling Problem. Journal of Intelligent Manufacturing, 2017, 28(3): 833-845.
[26] 杨启文,杨远慧,薛云灿,等.全局最优的邻域估计.控制与决策, 2012, 27(8): 1269-1272.
(YANG Q W, YANG Y H, XUE Y C, et al. Prospecting Neighborhood of Global Optimum. Control and Decision, 2012, 27(8): 1269-1272.)
[27] 杨启文,王术彬,薛云灿,等.蛇形缠绕机理及其在视觉定位中的应用.计算机科学与应用, 2013, 3(1): 30-35.
(YANG Q W, WANG S B, XUE Y C, et al. The Mechanism of Snake-Enlacing and Its Application to Visual Positioning. Compu-ter Science and Application, 2013, 3(1): 30-35.)
[28] 蔡自兴,江中央,王勇,等.一种新的基于正交实验设计的约束优化进化算法.计算机学报, 2010, 33(5): 855-864.
(CAI Z X, JIANG Z Y, WANG Y, et al. A Novel Constrained Optimization Evolutionary Algorithm Based on Orthogonal Experimental Design. Chinese Journal of Computers, 2010, 33(5): 855-864.)
[29] 陈明华,周本达,任哲.随机化均匀设计遗传算法.高校应用数学学报A辑, 2010, 25(3): 279-284.
(CHEN M H, ZHOU B D, REN Z. Genetic Algorithm Based on Random Uniform Design. Applied Mathematics: A Journal of Chinese Universities(Series A), 2010, 25(3): 279-284.)
[30] 龙文,梁昔明,徐松金,等.聚类佳点集交叉的约束优化混合进化算法.计算机研究与发展, 2012, 49(8): 1753-1761.
(LONG W, LIANG X M, XU S J, et al. A Hybrid Evolutionary Algorithm Based on Clustering Good-Point Set Crossover for Constrained Optimization. Journal of Computer Research and Development, 2012, 49(8): 1753-1761.)
[31] 张铃,张钹.佳点集遗传算法.计算机学报, 2001, 24(9): 917-922.
(ZHANG L, ZHANG B. Good Point Set Based Genetic Algorithm. Chinese Journal of Computers, 2001, 24(9): 917-922.)
[32] YAO X, LIU Y, LIN G M. Evolutionary Programming Made Faster. IEEE Transactions on Evolutionary Computation, 1999, 3(2): 82-102.
[33] SEBAG M, DUCOULOMBIER A. Extending Population-Based Incremental Learning to Continuous Search Spaces//Proc of the International Conference on Parallel Problem Solving from Nature. Berlin, Germany: Springer, 1998: 418-427.
[34] 余胜威.MATLAB优化算法案例分析与应用.北京:清华大学出版社, 2014.
(YU S W. Case Analysis and Application of MATLAB Optimization Algorithm. Beijing, China: Tsinghua University Press, 2014.)
[35] LIAN Z G. A Local and Global Search Combine Particle Swarm Optimization Algorithm for Job-Shop Scheduling to Minimize Ma-kespan. Discrete Dynamics in Nature and Society, 2010(4). DOI: 10.1155/2010/838596.
[36] CHEN C H, YAN S Y, CHEN M. Applying Lagrangian Relaxation-Based Algorithms for Airline Coordinated Flight Scheduling Problems. Computers and Industrial Engineering, 2010, 59(3): 398-410.
[37] TOLEDO C F M, DE SILVA ARANTES M, DE OLIVEIRA R R R, et al. Glass Container Production Scheduling through Hybrid Multi-population Based Evolutionary Algorithm. Applied Soft Computing Journal, 2013, 13(3): 1352-1364.
[38] DAO S D, ABHARY K, MARIAN R. Optimization of Partner Selection and Collaborative Transportation Scheduling in Virtual Enterprises Using GA. Expert Systems with Applications, 2014, 41(15): 6701-6717.
[39] KRESS D, MÜLLER D, NOSSACK J. A Worker Constrained Flexible Job Shop Scheduling Problem with Sequence-Dependent Setup Times. OR Spectrum, 2018, 41(2): 179-217.
[40] WANG Z, ZHANG J H, YANG S X. An Improved Particle Swarm Optimization Algorithm for Dynamic Job Shop Scheduling Problems with Random Job Arrivals. Swarm and Evolutionary Computation, 2019, 51. DOI: 10.1016/j.swevo.2019.100594.
[41] ZHU Z W, ZHOU X H. An Efficient Evolutionary Grey Wolf Optimizer for Multi-objective Flexible Job Shop Scheduling Problem with Hierarchical Job Precedence Constraints. Computers and Industrial Engineering, 2020, 140. DOI: 10.1016/j.cie.2020.106280.
[42] ZHANG G H, HU Y F, SUN J H, et al. An Improved Genetic Algorithm for the Flexible Job Shop Scheduling Problem with Multiple Time Constraints. Swarm and Evolutionary Computation, 2020, 54. DOI: 10.1016/j.swevo.2020.100664.
[43] 李强,刘晓峰.基于模拟植物生长算法的云作业调度模型.系统仿真学报, 2018, 30(12): 4649-4658.
(LI Q, LIU X F. Cloud Job Scheduling Model Based on Improved Plant Growth Algorithm. Journal of System Simulation, 2018, 30(12): 4649-4658.)
[44] LIU M, YAO X F, LI Y X. Hybrid Whale Optimization Algorithm Enhanced with Lévy Flight and Differential Evolution for Job Shop Scheduling Problems. Applied Soft Computing, 2020, 87. DOI: 10.1016/j.asoc.2019.105954.