| 基于遗传算法求解NPC问题的研究 |
| |
| 引用本文： | 王勋,宋建民,贺毅朝. 基于遗传算法求解NPC问题的研究[J]. 河北省科学院学报, 2014, 0(4): 1-7 |
| |
| 作者姓名： | 王勋 宋建民 贺毅朝 |
| |
| 作者单位： | 1. 石家庄经济学院信息工程学院,河北石家庄,050031
2. 石家庄经济学院数理学院,河北石家庄,050031 |
| |
| 基金项目： | 河北省教育厅自然科学基金 |
| |
| 摘 要： | 首先建立了0-1KP问题和3-SAT问题的数学模型；然后分别基于遗传算法（GA）与贪心策略相结合给出了一种求解0-1KP的有效算法，基于GA与局部搜索相结合给出了一种求解3-SAT问题的可行算法；最后通过对0-1KP实例和3-SAT实例的仿真计算验证了算法的可行性与有效性。
|
| 关 键 词： | NP完全问题 遗传算法 O-1背包问题 可满足问题 |
Solving NP-Complete problems by genetic algorithms |
| |
| WANG Xun,SONG Ji an-min,HE Yi-chao. Solving NP-Complete problems by genetic algorithms[J]. Journal of The Hebei Academy of Sciences, 2014, 0(4): 1-7 |
| |
| Authors: | WANG Xun SONG Ji an-min HE Yi-chao |
| |
| Affiliation: | WANG Xun SONG Jian-min HE Yi-chao (1. College of Information Engineering, Shijiazhuang University of Economics, Shijiazhuang Hebei 050031, China ; 2. Mathematics and Sciences, Shijiazhuang University of Economics, Shijiazhuang Hebei 050031 ,China) |
| |
| Abstract: | 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. |
| |
| Keywords: | NP-complete problem Genetic algorithm 0-1 knapsack problem Satisfiability problem |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
