算法分析
进化算法求解背包问题研究
黄林峰
(淄博职业学院信息工程系山东淄博255314)
事共与或用
摘要:01肯包问题(KnapsackProblem)是运筹学中一个经典的优化难题,在现实生活中有着非常广泛的实际应用肯景(如预算控制、货物装载、项日选择等)。骨包同题的求解算法很多，进化计算作为其中的一种，具有不侬赖于初始群体的全局技索能力，比较适含用来求解骨包同题。本文研究了利用进化算法求解骨包同题的其体实现对于现实中背包问题实际应用的求解有重要的意义。
关键词：肯包问题进化算法进化策略
中图分类号：TP181 1进化算法简介
文献标识码：A
进化算法(EvolutionaryAlgorithms，简称EA)也称为进化计算(EvolutionaryComputation，简称EC),是基于自然界中的进化策略，模拟自然生物进化面形成的自适应全局优化搜索算法。它以一个初始种群为对象，通过随机选择种群中个体进行重组，变异来产生新的个体。这些个体根据适应能力强弱而被选择或淘汰，被选择的个体形成新一代种群。重组、变异，选择组成了进化算法的三个基本操作。个体编码,适应度函数计算等是进化算法的重要内客。基于对生物进化的模拟，共产生了三种典型的进化算法模型：
(1)遗传算法(GeneticAlgorithms，简称GA)，(2)进化策略(EvolutionStrategy，简称ES)
(3)进化规划(EvolutionaryProgramming，简称EP)。
这些进化模型基于不同的生物进化背录，有不同的侧重点，它们的进化框架是一样的，只是在具体的重组、变异或选择算子上有所不同。
2背包问题定义
背包间题(KP)是运筹学中一个典型的优化难题，在现实生活中有着广泛的实际应用背录(如预算控制、货物装载.项目选择等)，基本的0/1背包问题的形式化定义如下2
定义1
KP:
w,x, ≤c,
x, (0,1),J =1,2,--"
ALGORITHM 1
(公式1)
文章编号:1007-9416(2016)12-0142-01
其中，Ⅱ为所有物品的数目，D和w分别为第个物品的价值和重量分别，c为背包的容量。背包问题的目标就是从给定物品的集合中选出一个子集，使得选中的所有物品的价值和最大，但是重量和不能超过背包的容量c。
3进化算法求解背包问题框架
进化算法是一种启发式的群体搜索算法，符合达尔文“适者生存和随机信息交换的思想。进化算法与传统优化方法相比具有不依赖于初始群体的全局搜索能力等多方面的优势，因此被广泛的用来求解现实中的各种优化问题，其中包括背包问题。图1给出了进化
算法求解背包问题的伪代码。 4结语
背包间题是一种NP难解间题，不存在多项式时间算法能求得其精确解，进化算法由于其自身特点比较适合用来求解背包问题，
并得到了很多具体的应用。参考文献
[1JDeb K. Multi20bjective 0pt imization Using Evolutionary Algorithms. Chicester, UK: Johnwiley & Sons, 2001.
[2JHans Kellerer U1rich Pferschy, David Pisinger. Knapsack Problems, SpringerVerlag Berlin,2004.
(Evolutionary Algorithms)
Step1产生初始化种群P(gene) Step2计算初始化种群适应度 Step3重组
(reconb):
Step4变异
(Mutation):
(InitielPopu) :
(Calculateitness) :
Step5计算所有新产生个体的适应度 Step6选择产生新的种群P(++gene)
(Gsl rulntePitnrs) :(Selection) :
Step7判断终止条件是否满足，
则退出：否则，GOTOStep3.
若是，
图1进化算法伪代码
收移日期：2016-11-07
作者简介：黄林峰(1981一),男,汉族,山东烟台人,毕业于中国科技大学,现就职于满博职业学院,研究生,制教投,研究方向：进化计算、物联
网智能信息处理等。
万方数据