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

doi:10.3969/j.iss.0372-2012-2014.03.021

电子学报 ›› 2014, Vol. 42 ›› Issue (3): 561-571.DOI: 10.3969/j.iss.0372-2012-2014.03.021

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

周雅兰¹, 王甲海², 黄聪²

1. 广东财经大学信息学院, 广东广州 510320;
2. 中山大学计算机科学系, 广东广州 510006

收稿日期:2012-09-27 修回日期:2013-02-25 出版日期:2014-03-25
- 作者简介:
- 周雅兰 女，1979年3月出生于湖南省常德市.现为广东财经大学信息学院副教授.主要研究方向为人工智能与数据挖掘.Email：zhouylan@163.com
- 基金资助:
- 国家自然科学基金 (No.60905038，No.60805026，No.61070076）; 广东市珠江科技新星专项 (No.2011J2200093，No.2012J2200085）; 广东商学院科研创新团队建设计划

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

ZHOU Ya-lan¹, WANG Jia-hai², HUANG Cong²

1. Information Science School, Guangdong University of Finance & Economics, Guangzhou, Guangdong 510320, China;
2. Department of Computer Science, Sun Yat-sen University, Guangzhou, Guangdong 510006, China

Received:2012-09-27 Revised:2013-02-25 Online:2014-03-25 Published:2014-03-25
- Supported by:
- National Natural Science Foundation of China (No.60905038, No.60805026, No.61070076); Zhujiang Science&Technology New-star Project of Guangzhou, China (No.2011J2200093, No.2012J2200085); Research and Innovation Team Construction Project of Guangdong University of Finance & Economics

摘要/Abstract

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

关键词: 离散粒子群优化, 分布估计算法, 排列问题

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

中图分类号:

TP18

周雅兰, 王甲海, 黄聪. 求解排列问题的分布估计离散粒子群优化算法[J]. 电子学报, 2014, 42(3): 561-571.

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.

参考文献

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

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 11

编辑推荐

Metrics

[1]	姚友杰, 钱斌, 董钰明, 胡蓉, 王凌. 基于EDA的绿色零等待作业车间调度问题求解[J]. 电子学报, 2021, 49(2): 225-232.
[2]	周丰顺, 胡蓉, 钱斌, 张长胜, 向凤红. 超启发式三维分布估计算法求解分布式流水线和车辆运输集成调度问题[J]. 电子学报, 2021, 49(12): 2419-2427.
[3]	曹政才, 林诚然, 黄冉. 带等待时间约束并行机调度问题的Copula分布估计算法[J]. 电子学报, 2017, 45(12): 2949-2956.
[4]	尹浩, 张长胜, 张斌, 孙若男, 刘婷婷. 一种求解SLA等级感知服务组合问题的多目标离散粒子群优化算法[J]. 电子学报, 2014, 42(10): 1983-1990.
[5]	黄岚, 齐季, 谭颖, 杨滨. 一种求解矩形排样问题的遗传-离散粒子群优化算法[J]. 电子学报, 2012, 40(6): 1103-1107.
[6]	何小娟;曾建潮;王丽芳. 一种基于信息传递的分布估计算法[J]. 电子学报, 2011, 39(4): 967-970.
[7]	程玉虎;王雪松;郝名林. 一种多样性保持的分布估计算法[J]. 电子学报, 2010, 38(3): 591-597.
[8]	王雪松;;程玉虎;郝名林. 基于细菌觅食行为的分布估计算法在预测控制中的应用[J]. 电子学报, 2010, 38(2): 333-339.
[9]	张建华;;曾建潮. 基于序贯重点采样粒子滤波的分布估计算法[J]. 电子学报, 2010, 38(12): 2929-2932.
[10]	张国富, 蒋建国, 夏娜, 苏兆品. 基于离散粒子群算法求解复杂联盟生成问题[J]. 电子学报, 2007, 35(2): 323-327.
[11]	赵中煜, 彭宇, 彭喜元. 基于分布估计算法的组合电路测试生成[J]. 电子学报, 2006, 34(S1): 2384-2386.