摘要
约束满足问题是人工智能的一个重要研究领域,使用粒子群搜索算法来求解约束满足问题逐渐受到人们的重视.把变量的最大度静态变量序关系引入到评估函数中,区别对待每个变量,通过静态变量序关系改变适应度函数,从而影响算法对最优粒子的选择.使用随机约束满足问题实验表明,改进后的算法比原算法具有更好的搜索能力,能以更快的速度收敛到全局解.
Constraint satisfaction problems is an important research area in artificial intelligence. People now pay more attention to particle swarm intelligence to solve CSPs. But the calculation of evaluation in particle swarm of CSPs is to determine whether the conflict is zero in one variable with its related variables. This way treats each variable equally. Adding max-degree static variable ordering of variables to fitness function is proposed, and now each variable is treated differently. Thus certain variables＇ instantiation satisfies some constraints firstly with high probability and affects the direction of the whole swarm by selecting the global best particle and local best particles. Random generated constraints satisfaction problems show that this improvement is efficient, which has better capacity in searching and could converge to global solution faster.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2006年第3期436-441,共6页
Journal of Computer Research and Development
基金
国家自然科学基金项目(60273080
60473003)
吉林省杰出青年基金项目(20030107)~~
关键词
粒子群
约束满足问题
适应度
最大度变量序
particle swarm
constraint satisfaction problem
fitness
max-degree variable ordering
