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

doi:10.16451/j.cnki.issn1003-6059.202107004

摘要
图/表
参考文献(44)
相关文章 (4)

全文: PDF (840 KB) HTML (1 KB)
输出: BibTeX | EndNote (RIS)

摘要

为了提高基于正态分布模型的分布估计算法子代候选解的质量,防止早熟收敛,文中提出多种群伪正态分布估计算法.首先,采用佳点集方法进行种群初始化,将种群分为3个子群.然后,采用样本重心取代样本均值的方式,获得伪正态分布模型.最后,融合种群与子群伪正态分布模型,得到子群进化的概率模型.23个基准函数的对比测试表明,文中算法在求解质量和收敛速度上较优.针对多约束条件下的并行装配优化问题,提出工序池、员工池、罚函数等措施,将具有工序约束和人员约束的离散组合优化问题转化为无约束的多种群伪正态分布估计优化问题.工程应用结果表明,只需要将候选解的无限集合修正为有限集合,文中算法可方便地用于离散组合优化问题的快速求解.

	服务

	把本文推荐给朋友
	加入我的书架
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	杨启文
	余诗琦
	张美琳
	薛云灿
	陈俊风

关键词 ：分布估计算法, 正态分布, 并行装配问题, 多种群

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

收稿日期: 2020-11-15

ZTFLH:

TP18

通讯作者: 杨启文,博士,副教授,主要研究方向为计算智能、系统优化与控制.E-mail:yangqw@hhu.edu.cn.

作者简介: 余诗琦,硕士研究生,主要研究方向为检测技术、智能系统.E-mail:445603497@qq.com.张美琳,硕士研究生,主要研究方向为系统调度与优化.E-mail:Zhang_Merlin@163.com.薛云灿,博士,教授,主要研究方向为智能优化、过程建模与控制.E-mail:ycxue@hhuc.edu.cn.陈俊风,博士,副教授,主要研究方向为计算智能、大数据分析.E-mail:chen-1997@163.com.

引用本文:

杨启文, 余诗琦, 张美琳, 薛云灿, 陈俊风. 多种群伪正态分布估计算法[J]. 模式识别与人工智能, 2021, 34(7): 619-630. YANG Qiwen, YU Shiqi, ZHANG Meilin, XUE Yuncan, CHEN Junfeng. Multiple Populations Based Estimation of Pseudo-Normal Distribution Algorithm. , 2021, 34(7): 619-630.

链接本文:

http://manu46.magtech.com.cn/Jweb_prai/CN/10.16451/j.cnki.issn1003-6059.202107004 或 http://manu46.magtech.com.cn/Jweb_prai/CN/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.