遗传算法解决01背包问题

2015 ～

2016 学年第二学期

学生姓名专学

业号

2016年 6 月

1

目录

一：问题描述.......................................................3 二：遗传算法原理及特点.............................................3 三：背包问题的遗传算法求解.........................................3

1.文字描述.....................................................3 2.遗传算法中的抽象概念在背包问题的具体化四：算法实现.......................................................4

1.数据结构.....................................................4 2.部分代码.....................................................5 五：结论...........................................................8 六：参考文献.......................................................8

.......................3

3.算法求解的基本步骤...........................................4

2

一、问题描述

0-1背包问题属于组合优化问题的一个例子，求解0-1背包问题的过程可以被视作在很多可行解当中求解一个最优解。

01背包问题的一般描述如下：

给定n个物品和一个背包，物品i的重量为Wi，其价值为Vi，背包的容量为C。问应如何选择合适的物品装入背包，使得背包中装入的物品的总价值最大。注意的一点是，背包内的物品的重量之和不能大于背包的容量C。在选择装入背包的物品时，对每种物品i只有两种选择：即装入背包或者不装入背包，不能讲物品i装入背包多次，也不能只装入部分的物品，称此类问题为0/1背包问题。

二、遗传算法原理及特点

遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法有着鲜明的优点：(1)遗传算法的操作对象是一组可行解,而非单个可行解;搜索轨道有多条,而非单条,因而具有良好的并行性.(2)遗传算法只需利用目标的取值信息,而无需递度等高价值信息,因而适用于任何规模,高度非线形的不连续多峰函数的优化以及无解析表达式的目标函数的优化,具有很强的通用性.(3)遗传算法择优机制是一种“软”选择,加上良好的并行性,使它具有良好的全局优化性和稳健性.(4)遗传算法操作的可行解集是经过编码化的(通常采用二进制编码),目标函数解释为编码化个体(可行解)的适应值,因而具有良好的可操作性与简单性.

三、背包问题的遗传算法求解

1、文字描述

0-1背包问题传统的解决方法有动态规划法、分支界限法、回溯法等等。传统的方法不能有效地解决0-1背包问题。在物品不是很多的时候用这些算法来处理背包问题效率上还是可以接受的，一旦物品过多（如50件物品）这些算法的效率就大打折扣了，因此采用一些智能的启发式搜索算法来处理就显得很有必要，遗传算法（Genetic Algorithms）则是一种适合于在大量的可行解中搜索最优（或次优）解的有效算法。

2、遗传算法中的抽象概念在背包问题的具体化

（1）基因：0或1，代表相应的商品选还是不选。

（2）染色体：本实验中固定有50个商品，所以染色体就是50个基因序列，也就是40个0、1串，代表了一种往包里装商品的组合。一个染色体例：0111101101011011110101110101010101011110。

（3）群体：一定数量的基因个体组成了群体(population),群体中个体的数量叫做群体大小。本实验的背包问题中，种群大小为100，代表100个往包里装商品的组合。

（4）适应度:各个个体对环境的适应程度叫做适应度。本实验的背包问题中，每染色体个体的适应度为选入包中的商品的价值和。

3