基于遗传算法求解NPC的研究  

Solving NP-Complete problems by genetic algorithms

作　　者：王勋[1] 宋建民[2] 贺毅朝[1] 

机构地区：[1]石家庄经济学院信息工程学院,河北石家庄050031 [2]石家庄经济学院数理学院,河北石家庄050031

出　　处：《河南科技学院学报（自然科学版）》2014年第6期40-45,共6页Journal of Henan Institute of Science and Technology(Natural Science Edition)

基　　金：河北省教育厅自然科学基金(Z2013110)

摘　　要：首先建立了0-1KP和3-SAT的数学模型;然后分别基于遗传算法(GA)与贪心策略相结合给出了一种求解0-1KP的有效算法,基于GA与局部搜索相结合给出了一种求解3-SAT的可行算法;最后通过对0-1KP实例和3-SAT实例的仿真计算,验证了算法的可行性与有效性.Two NP-Complete problems：the 0-1 knapsack problem and 3-SAT problem were introduced firstly in this paper.An efficient algorithm for solving 0-1KP was given based on genetic algorithm combining with greedy strategy,and an efficient algorithm for solving 3-SAT problem was presented based on genetic algorithm combining with local search strategy.At last,the feasible and effective of the algorithm were verified by 0-1KP instances and 3-SAT instances of simulation.

关 键 词：NP完全问题 遗传算法 0-1背包问题 可满足问题 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]