基于DEAP库的python进化算法–遗传算法实践–背包问题

1147-柳同学

发表文章数:589

热门标签

, ,
首页 » 算法 » 正文

一.背包问题描述

背包问题(knapsack problem)是指从多种物品中选择几件物品装满背包。在不超过背包承受重量的前提下,使装入背包的物品价值最大。假设存在n个不同物品,对于某物品j,其重量为w_j,价值为c_j,背包的最大承重量为W,则背包问题可以用数学语言描述为:
基于DEAP库的python进化算法--遗传算法实践--背包问题
其中x_j为物品j的决策变量,如果物品j被选中,则x_j = 1,否则x_j = 0

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

二.背包问题具体示例

给定物品数目n为20个,重量W限制为40单位
物品的重量与价值如下所示:
基于DEAP库的python进化算法--遗传算法实践--背包问题

三.遗传算法求解背包问题

1.个体编码

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

2.约束处理

在对染色体进行交叉和变异操作的时候,可能会出现解不符合约束的情况,一般有两种处理的思路:

  • 第一种思路是使用惩罚函数降低这种解的适应度,使得不符合约束的解在自然选择中逐渐被淘汰。
  • 另一种思路是使用修复方法,将落在不可行区域的候选解重新移入可行域。

这个背包问题比较简单,使用最简单粗暴的死亡惩罚就能取得较好的结果。

3.代码实现

遗传算法操作:

  1. 编码方式-二进制编码
  2. 评价函数-放入背包的所有物品价值之和,施加死亡惩罚
  3. 育种选择-锦标赛选择
  4. 变异算法-交叉-两点交叉,突变-位翻转突变
  5. 环境选择-精英保留策略
#!usr/bin/env python
# -*- coding:utf-8 _*-
"""
@author: liujie
@software: PyCharm
@file: 背包问题.py
@time: 2020/11/29 14:33
"""
import numpy as np
import matplotlib.pyplot as plt
import random
from deap import creator,tools,base

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

plt.rcParams.update(params)
# print(plt.rcParams.keys())

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

# 个体编码-二进制编码
# 编码长度为物品个数
gen_size = 20
toolbox = base.Toolbox()
toolbox.register('Binary',random.randint,0,1)
# 注册个体
toolbox.register('Individual',tools.initRepeat,creator.Individual,toolbox.Binary,n = gen_size)
# 注册种群
toolbox.register('Population',tools.initRepeat,list,toolbox.Individual)

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 eval(ind):
    return (np.sum(np.dot(np.array(valueList),np.array(ind).T))),

## 施加惩罚
def feasible(ind, W=40):
    '''可行性函数,判断个体是否满足背包总重量约束'''
    weightSum = np.sum(np.dot(np.array(weightList),np.array(ind).T))
    if weightSum < W:
        return True
    return False

toolbox.register('evaluate',eval)
# 当个体不满足总的重量约束时,个体适应度-10
toolbox.decorate('evaluate',tools.DeltaPenality(feasible,-10))
# 注册遗传算法操作-育种选择,交叉、变异
toolbox.register('select',tools.selTournament,tournsize = 2)
toolbox.register('mate',tools.cxTwoPoint)
toolbox.register('mutate',tools.mutFlipBit,indpb=0.5)

# 创建统计对象-用数据记录算法迭代过程
stats = tools.Statistics(key= lambda ind : ind.fitness.values)
stats.register('avg',np.mean)
stats.register('std',np.std)
stats.register('min',np.min)
stats.register('max',np.max)

# 创建日志对象
logbook = tools.Logbook()
logbook.header = 'gen','avg','std','min','max'

# 遗传算法主要操作
pop_size = 100
N_GEN = 100
CXPB = 0.8
MUTPB = 0.2

# 生成族群
pop = toolbox.Population(n = pop_size)

# 评价初代种群
invalid_ind = [ind for ind in pop if not ind.fitness.valid]
fitnesses = list(map(toolbox.evaluate,invalid_ind))
for ind,fit in zip(invalid_ind,fitnesses):
    ind.fitness.values = ind
# 记录
record = stats.compile(pop)
logbook.record(gen = 0,**record)

# 遗传算法迭代
for gen in range(1+N_GEN):
    # 配种选择
    selectTour = toolbox.select(pop,k = pop_size)
    # 复制
    selectInd = list(map(toolbox.clone,selectTour))
    # selectInd = [toolbox.clone(_) for _ in selectTour]

    # 交叉
    for child1,child2 in zip(selectInd[::2],selectInd[1::2]):
        if random.random() < CXPB:
            toolbox.mate(child1,child2)
            del child1.fitness.values
            del child2.fitness.values

    # 变异
    for ind in selectInd:
        if random.random() < MUTPB:
            toolbox.mutate(ind)
            del ind.fitness.values

    # 对于被改变的个体,重新计算其适应度
    invalid_ind = [ind for ind in selectInd if not ind.fitness.valid]
    fitnesses = list(map(toolbox.evaluate,invalid_ind))
    for ind,fit in zip(invalid_ind,fitnesses):
        ind.fitness.values = fit

    # 精英育种
    combinedPop = pop + selectInd
    pop = tools.selBest(combinedPop,pop_size)

    # 记录
    record = stats.compile(pop)
    logbook.record(gen = gen,**record)

# 打印迭代情况
print(logbook)

# 打印最终结果
bestInd = tools.selBest(pop,1)[0]
bestFit = bestInd.fitness.values[0]
weightSum = np.sum(np.dot(np.array(weightList),np.array(bestInd).T))
print('最优解为:',str(bestInd))
print('对应函数的最大值为:',bestFit)
print('背包重量为:',weightSum)

# 迭代过程可视化
avg = logbook.select('avg')
max = logbook.select('max')
gen = logbook.select('gen')
plt.plot(gen,avg,'r-',label='AVG_FITNESS')
plt.plot(gen,max,'b-',label='MAX_FITNESS')
plt.legend(loc = 'best')
plt.xlabel('gen')
plt.ylabel('fit')
plt.tight_layout()
plt.show()

运行结果

gen	avg  	std    	min	max
0  	0.51 	0.4999 	0  	1  
0  	1.92 	7.47353	0  	56 
1  	6.91 	16.5784	0  	69 
2  	12.39	21.2028	1  	69 
3  	27.06	25.4023	1  	69 
4  	52.23	8.44258	34 	78 
5  	58.82	4.91606	54 	78 
6  	63.04	5.65671	56 	78 
7  	66.95	4.76943	61 	78 
8  	70.95	4.16023	66 	81 
9  	75.22	3.53152	70 	81 
10 	79.05	1.43091	78 	81 
11 	80.4 	1.2    	78 	81 
12 	81   	0      	81 	81 
13 	81   	0      	81 	81 
14 	81   	0      	81 	81 
15 	81   	0      	81 	81 
16 	81   	0      	81 	81 
17 	81   	0      	81 	81 
18 	81   	0      	81 	81 
19 	81   	0      	81 	81 
20 	81   	0      	81 	81 
21 	81   	0      	81 	81 
22 	81   	0      	81 	81 
23 	81   	0      	81 	81 
24 	81   	0      	81 	81 
25 	81   	0      	81 	81 
26 	81   	0      	81 	81 
27 	81   	0      	81 	81 
28 	81   	0      	81 	81 
29 	81   	0      	81 	81 
30 	81   	0      	81 	81 
31 	81   	0      	81 	81 
32 	81   	0      	81 	81 
33 	81   	0      	81 	81 
34 	81   	0      	81 	81 
35 	81   	0      	81 	81 
36 	81   	0      	81 	81 
37 	81   	0      	81 	81 
38 	81   	0      	81 	81 
39 	81   	0      	81 	81 
40 	81   	0      	81 	81 
41 	81   	0      	81 	81 
42 	81   	0      	81 	81 
43 	81   	0      	81 	81 
44 	81   	0      	81 	81 
45 	81   	0      	81 	81 
46 	81   	0      	81 	81 
47 	81   	0      	81 	81 
48 	81   	0      	81 	81 
49 	81   	0      	81 	81 
50 	81   	0      	81 	81 
51 	81   	0      	81 	81 
52 	81   	0      	81 	81 
53 	81   	0      	81 	81 
54 	81   	0      	81 	81 
55 	81   	0      	81 	81 
56 	81   	0      	81 	81 
57 	81   	0      	81 	81 
58 	81   	0      	81 	81 
59 	81   	0      	81 	81 
60 	81   	0      	81 	81 
61 	81   	0      	81 	81 
62 	81   	0      	81 	81 
63 	81   	0      	81 	81 
64 	81   	0      	81 	81 
65 	81   	0      	81 	81 
66 	81   	0      	81 	81 
67 	81   	0      	81 	81 
68 	81   	0      	81 	81 
69 	81   	0      	81 	81 
70 	81   	0      	81 	81 
71 	81   	0      	81 	81 
72 	81   	0      	81 	81 
73 	81   	0      	81 	81 
74 	81   	0      	81 	81 
75 	81   	0      	81 	81 
76 	81   	0      	81 	81 
77 	81   	0      	81 	81 
78 	81   	0      	81 	81 
79 	81   	0      	81 	81 
80 	81   	0      	81 	81 
81 	81   	0      	81 	81 
82 	81   	0      	81 	81 
83 	81   	0      	81 	81 
84 	81   	0      	81 	81 
85 	81   	0      	81 	81 
86 	81   	0      	81 	81 
87 	81   	0      	81 	81 
88 	81   	0      	81 	81 
89 	81   	0      	81 	81 
90 	81   	0      	81 	81 
91 	81   	0      	81 	81 
92 	81   	0      	81 	81 
93 	81   	0      	81 	81 
94 	81   	0      	81 	81 
95 	81   	0      	81 	81 
96 	81   	0      	81 	81 
97 	81   	0      	81 	81 
98 	81   	0      	81 	81 
99 	81   	0      	81 	81 
100	81   	0      	81 	81 
最优解为: [1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0]
对应函数的最大值为: 81.0
背包重量为: 39

可视化
基于DEAP库的python进化算法--遗传算法实践--背包问题

未经允许不得转载:作者:1147-柳同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《基于DEAP库的python进化算法–遗传算法实践–背包问题》 发布于2020-11-29

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录