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

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

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