高级检索

    最大度二元约束满足问题粒子群算法

    Improvements of Particle Swarm in Binary CSPs with Maximal Degree Variables Ordering

    • 摘要: 约束满足问题是人工智能的一个重要研究领域,使用粒子群搜索算法来求解约束满足问题逐渐受到人们的重视.把变量的最大度静态变量序关系引入到评估函数中,区别对待每个变量,通过静态变量序关系改变适应度函数,从而影响算法对最优粒子的选择.使用随机约束满足问题实验表明,改进后的算法比原算法具有更好的搜索能力,能以更快的速度收敛到全局解.

       

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

       

    /

    返回文章
    返回