CAJ | 학술논문

提出了一个基于环割集的粒子群算法求解稀疏二元约束满足问题,把环割集和粒子群算法结合在一起,利用环割集减少粒子群算法中粒子的维数.用随机的稀疏二元约束满足问题进行实验,结果表明改进后的粒子群算法是有效的,迭代次数约为原算法的十分之一,运行时间比原算法运行时间少约7倍.
제출료일개기우배할집적입자군산법구해희소이원약속만족문제,파배할집화입자군산법결합재일기,이용배할집감소입자군산법중입자적유수.용수궤적희소이원약속만족문제진행실험,결과표명개진후적입자군산법시유효적,질대차수약위원산법적십분지일,운행시간비원산법운행시간소약7배.
Discrete particle swarm algorithm combining the cycle-cutset is proposed to solve the binary constraint satisfaction problems.Coupling the cycle-cutset with the particle swarm,the cycle-cutset is set to decrease the particles' dimension in the particle swarm,and particle swarm algorithm is only used to solve the cycle-cutset and the rest variables are solved by arc consistency algorithm with polynomial time complexity.The experimental results indicate that the hybrid algorithm is effective,which can reduce the iterations and searching times dramatically.