求解排列问题的分布估计离散粒子群优化算法

周雅兰, 王甲海, 黄聪

电子学报 ›› 2014, Vol. 42 ›› Issue (3) : 561-571.

PDF(996 KB)
PDF(996 KB)
电子学报 ›› 2014, Vol. 42 ›› Issue (3) : 561-571. DOI: 10.3969/j.iss.0372-2012-2014.03.021
科研通信

求解排列问题的分布估计离散粒子群优化算法

  • 周雅兰1, 王甲海2, 黄聪2
作者信息 +

Estimation of Distribution-Discrete Particle Swarm Optimization Algorithm for Permutation-Based Problems

  • ZHOU Ya-lan1, WANG Jia-hai2, HUANG Cong2
Author information +
文章历史 +

摘要

目前粒子群优化算法和分布估计算法较少用于解决排列编码组合优化问题,本文提出了一种新的适用于求解排列问题的分布估计离散粒子群优化算法.提出的算法结合粒子群优化算法和分布估计算法的思想,突破了标准粒子群优化算法速度-位移更新模式.新算法中每个粒子的信息一部分来自该粒子当前解排列与全局最优排列的最长公共子串,另一部分来自描述所有个体最优值分布信息的概率模型.这样粒子的当前解、所有个体最优值和全局最优值都参与了新解的生成过程,提出的算法秉承了粒子群优化算法的思想,同时具有更全面的学习能力,提高了算法的寻优能力以及避免陷入局部最优的能力.在两个经典的排列问题上的实验结果表明提出的算法具有良好的性能.

Abstract

Particle swarm optimization algorithm (PSO) and estimation of distribution algorithm (EDA) are seldom applied to permutation-based combinatorial optimization problems.This paper presents an estimation of distribution-discrete particle swarm optimization algorithm (ED-DPSO) for the permutation-based problems.In ED-DPSO,one part of components of the offspring comes from the longest common subsequence between the current solution and the global best solution,and the other part comes from the probability model built on the distribution information of all personal best solutions.In ED-DPSO,the current solution,all personal best solutions and global best solution contribute to the generation of a new solution.Thus,ED-PSO has more comprehensive learning ability,and can avoid falling into local minima and improve the search ability.Experiment results on two classic permutation-based problems show ED-PSO has superior performance.

关键词

离散粒子群优化 / 分布估计算法 / 排列问题

Key words

discrete particle swarm optimization / estimation of distribution algorithm / permutation-based problems

引用本文

导出引用
周雅兰, 王甲海, 黄聪. 求解排列问题的分布估计离散粒子群优化算法[J]. 电子学报, 2014, 42(3): 561-571. https://doi.org/10.3969/j.iss.0372-2012-2014.03.021
ZHOU Ya-lan, WANG Jia-hai, HUANG Cong. Estimation of Distribution-Discrete Particle Swarm Optimization Algorithm for Permutation-Based Problems[J]. Acta Electronica Sinica, 2014, 42(3): 561-571. https://doi.org/10.3969/j.iss.0372-2012-2014.03.021
中图分类号: TP18   

参考文献

[1] KENNEDY J, EBERHART R C.Particle swarm optimization[A].IEEE International Conference on Neural Networks[C].Piscataway:IEEE Press, 1995.1942-1948.
[2] SHI Y H, EBERHART R.A modified particle swarm optimizer[A].IEEE World Congress on Computational Intelligence[C].Piscataway:IEEE Press, 1998.69-73.
[3] [JP3]DEL VALLE Y, VENAYAGAMOORTHY G K, MOHAGHEGHI S, HERNANDEZ J C, HARLEY R G.Particle swarm optimization:basic concepts, variants and applications in power systems[J].IEEE Transactions on Evolutionary Computation, 2008, 12(2):171-195.
[4] WU H, GENG J, JIN R, QIU J, LIU W, CHEN J, LIU S.An improved comprehensive learning particle swarm optimization and its application to the semiautomatic design of antennas[J].IEEE Transactions on Antennas and Propagation, 2009, 57(10):3018-3028.
[5] KENNEDY J, EBERHART R C.A discrete binary version of the particle swarm algorithm[A].IEEE International Conference on Systems, Man and Cybernetics[C].Piscataway:IEEE Press, 1997.4104-4108.
[6] YANG S Y, WANG M, JIAO L C.A quantum particle swarm optimization[A].IEEE Congress Evolutionary Computation[C].Piscataway:IEEE Press, 2004.320-324.
[7] JARBOUI B, IBRAHIM S, SIARRY P, et al.A combinatorial particle swarm optimization for solving permutation flowshop problems[J].Computers & Industrial Engineering, 2008, 54(3):526-538.
[8] 钟一文, 蔡荣英.求解二次分配问题的离散粒子群优化算法[J].自动化学报, 2007, 33(8):871-874. ZHONG Yi-wen, CAI Rong-ying.Discrete particle swarm optimization algorithm for QAP[J].Acta Automatica Sinica, 2007, 33(8):871-874.(in Chinese)
[9] 张长胜, 孙吉贵, 欧阳丹彤.一种自适应离散粒子群算法及其应用研究[J].电子学报, 2009, 37(2):299-304. ZHANG Chang-sheng, SUN Ji-gui, OUYANG Dan-tong.A self-adaptive discrete particle swarm optimization algorithm[J].Acta Electronica Sinica, 2009, 37(2):299-304.(in Chinese)
[10] CHEN W N, ZHANG J, CHUNG H S H, et al.A novel set-based particle swarm optimization method for discrete optimization problems[J].IEEE Transactions on Evolutionary Computation, 2010, 14(2):278-300.
[11] 黄岚, 齐季, 谭颖, 杨滨.一种求解矩形排样问题的遗传-离散粒子群优化算法[J].电子学报, 2012, 40(6):1103-1107. HUANG Lan, QI Ji, TAN Ying, YANG Bin.A genetic-discrete particle swarm optimization algorithm for rectangular packing[J].Acta Electronica Sinica, 2012, 40(6):1103-1107.(in Chinese)
[12] 高海兵, 周驰, 高亮.广义粒子群优化模型[J].计算机学报, 2005, 28(12):1980-1987. GAO Hai-bing, ZHOU Chi, GAO Liang.General particle swarm optimization model[J].Chinese Journal of Computers, 2005, 28(12):1980-1987.(in Chinese)
[13] 周雅兰, 王甲海, 印鉴.一种基于分布估计的离散粒子群优化算法[J].电子学报, 2008, 36(6):1242-1248. ZHOU Ya-lan, WANG Jia-hai, YIN Jian.A discrete particle swarm optimization algorithm based on estimation of distribution[J].Acta Electronica Sinica, 2008, 36(6):1242-1248.(in Chinese)
[14] WANG J H, CAI Y Q, ZHOU Y L, et al.Discrete particle swarm optimization based on estimation of distribution for terminal assignment problems[J].Computers & Industrial Engineering, 2011, 60(4):566-575.
[15] BALUJA S.Population-based Incremental Learning:A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning[R].Pittsburgh:School of Computer Science, Carnegie Mellon University, 1994.
[16] 王圣尧, 王凌, 方晨, 许烨.分布估计算法研究进展[J].控制与决策, 2012, 27(7):961-966. WANG Sheng-yao, WANG Ling, FANG Chen, XU Ye.Advances in estimation of distribution algorithms[J].Control and Decision, 2012, 27(7):961-966.(in Chinese)
[17] CEBERIO J, IRUROZKI E, MENDIBURU A, LOZANO J A.A review on estimation of distribution algorithms in permutation-based combinatorial optim-ization problem[J].Progress in Artificial Intelligence, 2012, 1(1):103-117.
[18] EI-ABD M, KAMEL M S.A cooperative particle swarm optimizer with migration of heterogeneous probabilistic models[J].Swarm Intelligence, 2010, 4:57-89.
[19] CORMEN T H, LEISERSON C E, RIVEST R L, STEIN C.Introduction to Algorithms (2nd edition)[M].Cambridge, MA:MIT Press, 2006.
[20] ZHANG Y, LI X P.Estimation of distribution algorithm for permutation flow shops with total flowtime minimization[J].Computers & Operations Research, 2011, 60(4):706-718.
[21] SALHI A, RODRíGUEZ J A V, ZHANG Q.An estimation of distribution algorithm with guided mutation for a complex flow shop scheduling problem[A].The 9th Annual Conference on Genetic and Evolutionary Computation(GECCO)[C].New York:ACM Press, 2010.570-576.

基金

国家自然科学基金 (No.60905038,No.60805026,No.61070076); 广东市珠江科技新星专项 (No.2011J2200093,No.2012J2200085); 广东商学院科研创新团队建设计划

PDF(996 KB)

2540

Accesses

0

Citation

Detail

段落导航
相关文章

/