一个约束可满足性问题的演化算法求解  

An Approach to a Constraint Satisfaction Problem Using Genetic Algorithm

作　　者：李景治[1] 康立山[1] 方宁[1] 

机构地区：[1]武汉大学软件工程国家重点实验室,武汉430072

出　　处：《计算机科学》2004年第4期137-139,共3页Computer Science

基　　金：国家自然科学基金(编号:60073043;70071042;60133010)

摘　　要：约束可满足性问题是一大类常出现于现实应用中的复杂问题,因其繁多的约束条件而出名。本文针对一个经典的约束可满足性问题——斑马属谁问题,基于演化算法的框架进行求解。我们采用矩阵的表示方式,并设计了相应的杂交和变异算子。实验表明,演化算法能高效地解决该问题。Constraint satisfaction problems are a large category of complex problems in real world applications, noted for various constraints. Based on the framework of evolutionary algorithm (EA), we solve the zebra-belong-to-who problem, a classical constraint satisfaction problem in this paper. We devise the matrix encoding and its corresponding crossover and mutation operators. Experiments show that EA can solve the problem effectively.

关 键 词：约束可满足性问题 演化算法 斑马属谁问题 优化问题 计算机 

分 类 号：O224[理学—运筹学与控制论] TP301.6[理学—数学]