遗传算法求解背包问题（python）

其实遗传算法是一种处理问题的思想，因为遗传算法整个体系都是在说对于一种问题的处理思路和原则，而不是一个具体的代码编写过程。

1. 算法过程

关键步骤如下：

（1）基因编码：在这个过程中，尝试对一些个体的基因做一个描述，构造这些基因的结构，有点像确定函数自变量的过程。 
（2）设计初始群体：在这里需要造一个种群出来，这些种群有很多生物个体但基因不同。 
（3）适应度计算（剪枝）：这里对那些不符合要求的后代进行剔除，不让他们产生后代。否则他们产生的后代只会让计算量更大而对逼近目标没有增益。 
（4）产生下一代：有3种方法，即：直接选择，基因重组，基因突变 
而后回到步骤（3）进行循环，适应度计算，产生下一代，这样一代一代找下去，直到找到最优解为止。

遗传算法的应用领域：如TSP问题（旅行商问题），九宫问题，生产调度问题，背包问题等。

2. 背包问题
这里用一个具体的示例来说明遗传算法的应用。 
背包问题是一种组合优化的NP（多项式复杂程度的非确定性问题）完全问题，这类问题的特点很明显，即“生成问题的一个解通常比验证一个给定的解需要花更多的时间”。

背包问题的大意是，有N件物品和一个容量为V的背包，第i件物品的重量是w[i]w[i]，价值是v[i]v[i]，求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值的总和最大。 
这种问题就是典型的NP问题，验证一个猜想的解比算出一组解要快的多。

例：假设有一个背包，可以放置80公斤的物品，此外还有表： 

这时如果用普通的算法就有一种是穷举法，这里还可以实施，但如果有128种物品的话，就不能再用穷举法了，这时遗传算法就派上用场了。

（1）基因编码：一共有6种物品，每种物品的有无可以作为一个独立的基因片段，如： 

假如只有物品2，3，6，这时的染色体是：011001

（2）设计初始群体： 
为了计算方便设置初始群体为4个初始生物个体，随机产生。注意：这里的初始个数的选择要视具体情况而定，如果初始数量太少可能会导致在向量空间中覆盖面积过小而导致收敛到了非最优解就终止了算法。

（3）适应度计算：首先适应度计算要用一个适应函数来做标尺，设计适应度的函数为物品的总价值。这里同时还要计算物品的重量，超过80公斤的直接淘汰。然后对剩下的染色体进行一个用类似轮盘赌来进行遴选的过程，每次轮盘转动中奖的基因组就允许繁殖一次，如果一次都没中的基因组将无法得到延续。而遴选的原则是从生物多样化中进行挑选，淘汰比较弱的是可以的，但不建议淘汰的比例太大。

（4）生产下一代 
被轮盘赌选中的基因需要进行基因重组产生下一代，计算过程如下：

其实就是把基因片段从中间的某个地方断开，然后交叉进行组合来形成新的基因，如：

这里基因重组的断开的位置是可以随意进行的，同时注意不要一个基因自身和自身去做重组，没有意义，因为怎样重组还是自己。

这里先暂不考虑基因突变的情况。。。

（5）迭代计算 
这里一代一代用这种规则做下去，直接求重量和价值。这里可以发现一个现象，就是适应度函数的值比上一代的适应度更好了。在迭代的过程中如果发现连续几代的适应度函数值基本不增加或者甚至减少的情况，那说明函数已经收敛了。其实收敛的速度会受到很多因素而变化，如基因的长度，基因重组时的方案，基因变异的程度，每一代产生个体的数量等。

3. 代码实现

来源：璀璨下的一点星辰