|
|||||
|
|
| 稀疏二元约束满足问题的环割集粒子群算法 | |
| 引用本文： | 杨轻云,孙吉贵,张居阳,王纯杰.稀疏二元约束满足问题的环割集粒子群算法[J].广西师范大学学报(自然科学版),2006,24(4):135-138. |
| 作者姓名： | 杨轻云 孙吉贵 张居阳 王纯杰 |
| 作者单位： | 1. 吉林大学,计算机科学与技术学院,吉林,长春,130012;吉林大学,符号计算与知识工程教育部重点实验室,吉林,长春,130012 2. 吉林大学,计算机科学与技术学院,吉林,长春,130012;吉林大学,符号计算与知识工程教育部重点实验室,吉林,长春,130012;复旦大学,智能信息处理开放实验室,上海,200433 3. 长春工业大学,基础科学学院,吉林,长春,130012 |
| 摘 要： | 提出了一个基于环割集的粒子群算法求解稀疏二元约束满足问题,把环割集和粒子群算法结合在一起,利用环割集减少粒子群算法中粒子的维数。用随机的稀疏二元约束满足问题进行实验,结果表明改进后的粒子群算法是有效的,迭代次数约为原算法的十分之一,运行时间比原算法运行时间少约7倍。 |
| 关 键 词： | 二元约束满足问题 粒子群算法 环割集 弧相容 |
| 文章编号： | 1001-6600（2006）04-0135-04 |
| 收稿时间： | 2006-05-31 |
| 修稿时间： | 2006年5月31日 |
Particle Swarm Algorithm with Cycle-Cutset for Sparse Binary CSPs |
|
| YANG Qing-yun,SUN Ji-gui,ZHANG Ju-yang,WANG Chun-jie.Particle Swarm Algorithm with Cycle-Cutset for Sparse Binary CSPs[J].Journal of Guangxi Normal University(Natural Science Edition),2006,24(4):135-138. | |
| Authors: | YANG Qing-yun SUN Ji-gui ZHANG Ju-yang WANG Chun-jie |
| Institution: | 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. Open Laboratory for Intelligence Information Processing,Fudan University, Shanghai 200433, China ; 4. College of Basic Sciences ,Changchun University of Technology,Changchun 130012 ,China |
| Abstract: | 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. |
| Keywords: | binary constraint satisfaction problem (BCSP) particle swarm cycle-cutset arc consistency |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |