计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (29): 10-13.DOI: 10.3778/j.issn.1002-8331.2009.29.003

• 博士论坛 • 上一篇    下一篇

一种求解二元约束满足问题自适应粒子群算法

付宏杰1,2,3,欧阳丹彤1,2,孙吉贵1,2   

  1. 1.吉林大学 计算机科学与技术学院,长春 130012
    2.吉林大学 符号计算与知识工程教育部重点实验室,长春 130012
    3.吉林工程技术师范学院 信息工程学院,长春 130052
  • 收稿日期:2009-07-14 修回日期:2009-08-17 出版日期:2009-10-11 发布日期:2009-10-11
  • 通讯作者: 付宏杰

Self-adaptive particle swarm optimization algorithm for binary CSPs

FU Hong-jie1,2,3,OUYANG Dan-tong1,2,SUN Ji-gui1,2   

  1. 1.College of Computer Science and Technology,Jilin University,Changchun 130012,China
    2.Key Laboratory for Symbolic Computation and Knowledge Engineering of Ministry of Education,Jilin University,Changchun 130012,China
    3.College of Computer Science and Technology,Jilin Teachers Institute of Engineering and Technology,Changchun 130052,China
  • Received:2009-07-14 Revised:2009-08-17 Online:2009-10-11 Published:2009-10-11
  • Contact: FU Hong-jie

摘要: 提出了一种求解二元约束满足问题的自适应粒子群算法(SAPSO),其中每个粒子具有两种状态,定义了一个反应粒子活跃程度的变量以决定粒子所属的状态。为了平衡粒子不同进化阶段的开发和探测能力,在SAPSO中引入了随着每个粒子的进化状态和粒子群的进化状态动态改变的惯性权重。利用自适应的选取方式代替随机选择的盲目搜索方式,使群体在解空间搜索时,能够自适应地去探索新的区域,选择有希望找到更优解的地方搜索。使用随机约束满足问题的实验表明,改进后的算法比原算法(PS-CSP)能以更快的速度收敛到全局解。算法的效率大约提高两倍,平均迭代次数大约为原来的一半。

关键词: 粒子群算法, 二元约束满足问题, 惯性权重, 适应度

Abstract: A Self-Adaptive Particle Swarm algorithm(SAPSO)is proposed.There exist two states for each particle in the SAPSO algorithm and a metric to measure a particle’s activity is defined which is used to choose which state it would reside.In order to ba-lance a particle’s exploration and exploitation capability for different evolving phases,a self-adjusted inertia weight varies dynamically with each particle’s evolution degree and the current swarm evolution degree is introduced into SAPSO algorithm.It uses the self-adaptive selection to select values from domains instead of random selection.This strategy searches in the promising solution space for global solution when the particles exploit the search space.It tests the hybrid algorithm(SAPSO) with random constraint satisfaction problems.The experimental results show that the hybrid particle swarm algorithm(SAPSO) can converge to the global solution faster.The efficiency of algorithm is increased by 2 times and average iteration times are reduced to a half of the former.

Key words: Particle Swarm algorithm(PSO), binary constraint satisfaction problem, inertia weight, fitness

中图分类号: