遗传算法实践(三) 背包问题

2019-07-15 本文已影响0人 ChaoesLuol

背包问题描述

背包问题(knapsack problem)是指从多种物品中选择几件物品装满背包。在不超过背包承受重量的前提下，使装入背包的物品价值最大。假设存在 $n$ 个不同物品，对于某物品 $j$ ，其重量为 $w_j$ ，价值为 $c_j$ ，背包的最大承重量为 $W$ ，则背包问题可以用数学语言描述为：
$max\ f(x)=\sum_{j=1}^{n}c_jx_j \\s.t. g(x)=\sum_{j=1}^{n}w_jx_j \le W \\x_j=0 \ or\ 1, j=1,2,3,...,n$
其中 $x_j$ 为物品 $j$ 的决策变量，如果物品 $j$ 被选中，则 $x_j=1$ 否则 $x_j=0$ 。

背包问题理论上是一个NP-hard问题，目前还没有多项式时间内可以求解最优解的算法。但很多情况下，用遗传算法在短时间内能求解到比较高质量的解。

背包问题具体示例

给定物品数目 $n$ 为20个，重量 $W$ 限制为40单位。

物品的重量与价值如下表所示：

物品编号( $j$ )	物品重量( $w_j$ )	物品价值( $c_j$ )
1	2	5
2	5	10
3	18	12
4	3	4
5	2	3
6	5	11
7	10	13
8	4	10
9	8	7
10	12	15
11	5	8
12	10	19
13	7	1
14	15	17
15	11	12
16	2	9
17	8	15
18	10	20
19	5	2
20	9	6

遗传算法求解背包问题

个体编码

求解背包问题时，比较自然的编码方式是采用二进制编码，即用长度为物品个数的二进制序列来表示问题的候选解，序列中每一位表示物品的选择情况，当该位为1时，代表物品被选中，否则代表物品未被放入背包。

约束处理

在对染色体进行交叉和变异操作的时候，可能会出现解不符合约束的情况，一般有两种处理的思路：第一种是使用惩罚函数降低这种解的适应度，使得不符合约束的解在自然选择中逐渐被淘汰；另一种思路是使用修复方法，将落在不可行区域的候选解重新移入可行域。

由于这个背包问题较为简单，使用最简便粗暴的死亡惩罚就能取得较好的效果。

其他遗传算法操作

评价函数：放入背包的所有物品价值之和
育种选择：binary锦标赛选择
变异算法：交叉-两点交叉，突变-位翻转突变
环境选择：精英保留策略

代码示例

这里的代码是为了解释问题，追求清晰明了，而非效率向的代码；如果为了求解速度请自行改造

## 环境设定
import numpy as np
import matplotlib.pyplot as plt
from deap import base, tools, creator, algorithms
import random

params = {
    'font.family': 'serif',
    'figure.dpi': 300,
    'savefig.dpi': 300,
    'font.size': 12,
    'legend.fontsize': 'small'
}
plt.rcParams.update(params)

# -------------------
## 问题定义
creator.create('FitnessMax', base.Fitness, weights=(1.0,)) # 最大问题
creator.create('Individual', list, fitness=creator.FitnessMax)

## 个体编码 - 二进制编码
geneLength = 20
toolbox = base.Toolbox()
toolbox.register('genBinary', random.randint, 0, 1)
toolbox.register('individual', tools.initRepeat, creator.Individual,toolbox.genBinary, geneLength)

## 评价函数
weightList = [2, 5, 18, 3, 2, 5, 10, 4, 8, 12, 5, 10, 7, 15, 11, 2, 8, 10, 5, 9]
valueList = [5, 10, 12, 4, 3, 11, 13, 10, 7, 15, 8, 19, 1, 17, 12, 9, 15, 20, 2, 6]
def evaluate(ind):
    return (np.sum(np.asarray(valueList)*np.asarray(ind))),
toolbox.register('evaluate', evaluate)

## 施加惩罚
def feasible(ind, W=40):
    '''可行性函数，判断个体是否满足背包总重量约束'''
    weightSum = np.sum(np.asarray(weightList)*np.asarray(ind))
    if weightSum <= W:
        return True
    return False
# 死亡惩罚，当个体不满足总重量约束时，设置其个体适应度为-10
toolbox.decorate('evaluate', tools.DeltaPenalty(feasible, -10))

## 注册工具
toolbox.register('select', tools.selTournament, tournsize=2)
toolbox.register('mate', tools.cxTwoPoint)
toolbox.register('mutate', tools.mutFlipBit, indpb=0.5)

# 生成族群
popSize = 100
toolbox.register('population', tools.initRepeat, list, toolbox.individual)
pop = toolbox.population(popSize)

# 迭代数据
stats = tools.Statistics(key=lambda ind:ind.fitness.values)
stats.register('max', np.max)
stats.register('avg', np.mean)
stats.register('std', np.std)
logbook = tools.Logbook()
logbook.header = ['gen', 'nevals'] + (stats.fields)

# -------------------
# 评价初始族群
invalid_ind = [ind for ind in pop if not ind.fitness.valid]
fitnesses = toolbox.map(toolbox.evaluate, invalid_ind)
for fitness, ind in zip(fitnesses, invalid_ind):
    ind.fitness.values = fitness

# 记录第0代的数据
record = stats.compile(pop)
logbook.record(gen=0, nevals=len(invalid_ind),**record)

# 参数设置
ngen = 200
cxpb = 0.8
mutpb = 0.2

# 遗传算法迭代
for gen in range(1, ngen+1):
    # 育种选择
    offspring = toolbox.select(pop, popSize)
    offspring = [toolbox.clone(_) for _ in offspring]
    # 交叉
    for ind1, ind2 in zip(offspring[::2], offspring[1::2]):
        if random.random()<cxpb:
            toolbox.mate(ind1, ind2)
            del ind1.fitness.values
            del ind2.fitness.values
    # 突变
    for ind in offspring:
        if random.random()<mutpb:
            toolbox.mutate(ind)
            del ind.fitness.values
    # 评价子代
    invalid_ind = [ind for ind in offspring if not ind.fitness.valid]
    fitnesses = toolbox.map(toolbox.evaluate, invalid_ind)
    for fitness, ind in zip(fitnesses, invalid_ind):
        ind.fitness.values = fitness
    # 环境选择
    combindPop = pop + offspring
    pop = tools.selBest(combindPop, popSize)
    # 记录数据
    record = stats.compile(pop)
    logbook.record(gen = gen, nevals = len(invalid_ind), **record)
print(logbook)

输出结果：

## 输出结果
bestInd = tools.selBest(pop,1)[0]
bestFit = bestInd.fitness.values[0]
weightSum = np.sum(np.asarray(weightList)*np.asarray(bestInd))
print('最优解为: '+str(bestInd))
print('函数最大值为: '+str(bestFit))
print('背包重量为: '+str(weightSum))

## 可视化迭代过程
maxFit = logbook.select('max')
avgFit = logbook.select('avg')
plt.plot(maxFit, 'b-', label='Maximum Fitness')
plt.plot(avgFit, 'r-', label='Average Fitness')
plt.xlabel('# Gen')
plt.ylabel('Fitness')
plt.legend(loc='best')

## 结果
# 最优解为: [0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0]
# 函数最大值为: 83.0
# 背包重量为: 39

knapsack problem iteration