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

Solving NP-Complete problems by genetic algorithms

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

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

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

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

摘　　要：首先建立了0-1KP问题和3-SAT问题的数学模型;然后分别基于遗传算法(GA)与贪心策略相结合给出了一种求解0-1KP的有效算法,基于GA与局部搜索相结合给出了一种求解3-SAT问题的可行算法;最后通过对0-1KP实例和3-SAT实例的仿真计算验证了算法的可行性与有效性。This paper first introduces two NP-Complete problems, the 0-1 knapsack problem and 3-SAT problem. On the standard genetic algorithm with greedy strategy, the way of sol- ving the 0-1 knapsack problem was discussed. On the standard genetic algorithm with local search strategy, the way of solving the 3-SAT problem was presented. At last, on the simu- lation this paper got the conclusion that these ways are feasible and effective.

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]