利用改进的HBDE算法求解MAX-k-SAT问题  

Solving MAX-k-SAT Problems by Improved HBDE Algorithm

作　　者：宋建民[1] 苟海燕[2] 

机构地区：[1]石家庄经济学院数理学院,河北石家庄050031 [2]石家庄经济学院华信学院,河北新乐050700

出　　处：《河北省科学院学报》2014年第1期1-7,共7页Journal of The Hebei Academy of Sciences

基　　金：河北省教育厅高等学校科技研究项目(NO.Z2013110)

摘　　要：目前,利用进化算法求解组合优化问题已成为智能计算领域中的研究热点。本文基于二进制差分演化算法和动态变邻域搜索相结合提出了一种求解最大可满足问题(MAX-k-SAT)的改进算法(记为IBDE),通过与遗传算法和Johnson算法对一系列随机大规模MAX-k-SAT实例的求解比较表明:IBDE是一种求解MAX-k-SAT问题非常有效的新方法。At present,the evolutionary algorithm for solving combinatorial optimization problems has become a hot research topic in the field of intelligent computation.In this paper,we advance an improved binary differential evolution algorithm（denoted as IBDE）which combinations the binary differential evolution algorithm with dynamic variable neighborhood search for solving the maximum satisfiability problem（MAX-k-SAT）.For a series of random largescale instances of MAX-k-SAT,the computational results of IBDE,Genetic algorithm and Johnson algorithm show that：IBDE is a new effective algorithm for MAX-k-SAT.

关 键 词：二进制差分演化 变邻域搜索 组合优化问题 MAX-SAT问题 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]