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

• 科研通信 • 上一篇    下一篇

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

周雅兰1, 王甲海2, 黄聪2   

  1. 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-lan1, WANG Jia-hai2, HUANG Cong2   

  1. 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: 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

中图分类号: