王勋,宋建民,贺毅朝

（1.石家庄经济学院信息工程学院,河北石家庄050031；2.石家庄经济学院数理学院,河北石家庄050031）

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

王勋1,宋建民2,贺毅朝1

（1.石家庄经济学院信息工程学院,河北石家庄050031；2.石家庄经济学院数理学院,河北石家庄050031）

首先建立了0-1KP和3-SAT的数学模型；然后分别基于遗传算法（GA）与贪心策略相结合给出了一种求解0-1KP的有效算法,基于GA与局部搜索相结合给出了一种求解3-SAT的可行算法；最后通过对0-1KP实例和3-SAT实例的仿真计算,验证了算法的可行性与有效性.

NP完全问题；遗传算法；0-1背包问题；可满足问题

NP完全问题（NP-Complete problem,NPC）[1-2]是理论计算机科学中非常重要的一类难解问题,对于计算复杂性的研究起着关键的作用.0-1背包问题（0-1Knapsack problem,0-1KP）[2-6]和SAT（Satisfiability problem,SAT）[2,7-10]均为NPC中非常经典的问题,同时也是组合优化问题[11-12],其中KP在预算控制和货物装载等领域有广泛的应用,而SAT在逻辑推理和人工智能等领域有广泛的应用.本文利用遗传算法与某些策略相结合求解0-1KP和SAT,并且通过具体的实例计算验证了其可行性和有效性.

1 遗传算法简介

遗传算法（Genetic algorithm,GA）[13-14]是1975年由美国密西根大学的Holland D J教授借鉴生物进化机制提出来的一种仿生算法.在GA中,将待求解问题的每一个可行解看作是群体中的一个染色体个体,利用二进制（或十进制）编码表示,其优劣由适应度来衡量（适应度不一定是目标函数值）.在GA的进化中,利用交叉算子和变异算子作用于当前群体中的个体而产生新的个体,根据新个体的适应度由……