用Python实现的遗传算法解决零一背包问题

前言

最近在上智能优化技术的课程,它主要讨论的是使系统达到最优的目标的算法,通常是找到某个多变量函数的极大值或者极小值。因为在实际工程问题中,有很多目标函数没有办法用我们所学高等数学中标准的最大最小值求值方法,比如Rastrigin Function:

面对这种函数传统的数学方法就显得有点无力了。

而智能优化算法就是要解决这类复杂问题。常见的智能优化算法有:遗传算法(Genetic Algorithm)、差分演化算法(Differential Evolution)、免疫算法(Immune Algorithm)、蚁群算法(Ant Colony Optimization)、粒子群算法(Particle Swarm Optimization)、模拟退火算法(Simulated Annealing)、禁忌搜索算法(Tabu Search)等等。这些算法从某些自然现象中受到启发,比如粒子群算法模拟的就是鸟类捕食的过程,鸟群成员可以通过个体间的信息交流与共享获得其他个体的发现与飞行经历。

问题描述

本文将处理的是一个经典的算法问题——零一背包问题。即给定一个背包的大小(Capacity),已知有N种不同的物品,给出它们所占的空间(Space),以及它们所对应的价值(Value),要求求出在不超过背包容量下能装下的最大的物品价值量(MaxValue)。

以前做算法题的时候了解过动态规划解决这个问题的方法,如果大家有兴趣的话在网上可以搜到相应的解决代码。我这里提供一种用Python实现遗传算法解决零一背包问题的方法。

代码运行前

  1. 你的电脑需要安装Python3
  2. 你需要安装Numpy
  3. 如果你想看到绘图结果你还需要安装Matplotlib

算法代码剖析

零一背包问题其实可以简化为这些物品选还是不选的问题,那么我们可以进行编码:我们创建一个物品数量大小的数组,里面只存0和1,1代表我选了这个物品,0代表没选,这个数组就是一个方案的编码,也称作染色体,其中每个0或1称作基因。而我们的种群,就是有很多的方案,每个方案,就是一个个体。

所以你要明白,我们的遗传算法一开始就是随机的给出一定数目(种群大小)的解决方案,然后让它们模拟生物进化,适应值(得到的物品价值总和)越好的就越有机会留下来。留下来的进行杂交,最后经过很多次迭代后留下的就是最好的结果了。

为了避免出现结果是局部最优,比如爬山,有很多山,当种群到达一个中等高度的山顶的时候,它们发现周围的地形都比它们的位置低了,于是就认为这是最高的了(局部最优),就安于现状不动了,觉得到达世界之颠了。实际上在周围可能还有更高的山,超出了它们的视野范围。

所以要引入变异,让有的个体随机蹦到更远的地方,它就有可能蹦到比局部最优更好的地方,在大量的迭代下就能避免其他个体安于局部最优,从而让种群向发现更高山的那个个体靠近,最后得到最好的结果。

但是要注意,智能优化算法能保证一个能让人接受的结果,但并不代表严格数学意义上的最优值。

以下是实现代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
import numpy as np
import matplotlib.pyplot as plt

numOfItems = 10
# numOfItems = 5
# numOfItems = 6
# numOfItems = 7

capacityOfBag = 165
spaceOfItems = [23, 31, 29, 44, 53, 38, 63, 85, 89, 82]
valueOfItems = [92, 57, 49, 68, 60, 43, 67, 84, 87, 72]

# capacityOfBag = 26
# spaceOfItems = [12, 7, 11, 8, 9]
# valueOfItems = [24, 13, 23, 15, 16]

# capacityOfBag = 190
# spaceOfItems = [56, 59, 80, 64, 75, 17]
# valueOfItems = [50, 50, 64, 46, 50, 5]

# capacityOfBag = 50
# spaceOfItems = [31, 10, 20, 19, 4, 3, 6]
# valueOfItems = [70, 20, 39, 37, 7, 5, 10]

numOfPop = 50
#种群二维数组,同时随机初始化(50 x 10)
population = np.random.randint(0, 2, size=(numOfPop, numOfItems))
#种群适应值初始化(50)
popFitness = np.zeros(numOfPop)
#交叉率
crossoverRate = 0.8
#变异率
mutationRate = 0.05
#迭代次数
generations = 100
#惩罚函数系数(注意如果设置太小会出现有的结果惩罚力度不够导致结果错误)
punishmentCoe = 10.0
#每次迭代最好记录
allBest = np.zeros(generations)

# author: Yaron Ho
# blog: https://hoyyy.me

#适应值函数,判断一个个体的优劣
def func(gene, space, value, capacity, punish):
#获取当前组合的价值总和
fit = 0.0
for i in range(numOfItems):
fit += value[i] * gene[i]
#获取当前组合的空间总和
size = 0.0
for i in range(numOfItems):
size += space[i] * gene[i]
#如果空间超出了,说明该组合是不行的,就对该算法惩罚性降低其适应值
if size > capacity:
fit -= punish * (size - capacity)
return fit

#进行迭代
for iteration in range(0, generations):
#计算每个个体的适应值
for index, individual in enumerate(population):
popFitness[index] = func(gene=individual, space=spaceOfItems, value=valueOfItems, capacity=capacityOfBag, punish=punishmentCoe)
#获得种群中最高的适应值
maxFit = popFitness.max()
#获取种群中最低的适应值
minFit = popFitness.min()
#获得最佳个体的索引
maxIndex = np.argmax(popFitness)
#通过索引获得最佳个体的基因序列(即组合序列)
bestIndividual = population[maxIndex]

#归一化
for index, fitness in enumerate(popFitness):
popFitness[index] = (fitness - minFit) / (maxFit - minFit)

sumFit = popFitness.sum()
#然后每个的优劣程度与总和的比就构成了转盘中它们所占块的大小
fitRatio = popFitness / sumFit
#把除第一个外,每一个个体的优劣程度与之前的进行累加,那么就能形成很多连续的区间,好利于之后循环判断
fitRatio = np.cumsum(fitRatio)

#转针随机数组,大小和种群大小相同
pointer = np.random.random(numOfPop)
#把这些转针转到的位置从小到大进行排序,就可以和对应的个体在转盘中的位置进行比较
pointer.sort()
#初始化一个新的空种群,用来作为经选择、交叉、变异后的后一代种群
newPopulation = np.zeros((numOfPop, numOfItems), dtype=int)

#进行选择
#当前要进行复制的下一代的索引
newPopIndex = 0
#前一代候选的个体的索引
fitRatioIndex = 0
#种群遍历
while newPopIndex < numOfPop:
if pointer[newPopIndex] < fitRatio[fitRatioIndex]:
newPopulation[newPopIndex] = population[fitRatioIndex]
newPopIndex += 1
else:
fitRatioIndex += 1

for i in range(0, numOfPop, 2):
#获得一个0到1的随机小数
p = np.random.random()
#按概率进行操作,小于我们设置的交叉概率我们才进行交叉
if p < crossoverRate:
#这是一个随机获得的选择数组,如果是0,则这个位置的基因不进行交叉,1则进行交叉
crossChoice = np.random.randint(0, 2, numOfItems)
#遍历当前个体的每个基因
for j in range(0, numOfItems):
#判断选择数组这个位置的值
if crossChoice[j] == 1:
#这是一个标准的值交换步骤,它是当前个体与后面一个个体进行的,所以步幅长度为2
temp = newPopulation[i][j]
newPopulation[i][j] = newPopulation[i + 1][j]
newPopulation[i + 1][j] = temp

#基于概率的变异操作
#遍历每个个体
for m in range(0, numOfPop):
#遍历个体的每个基因
for n in range(0, numOfItems):
#获得一个0到1之间的随机小数
p = np.random.random()
#如果这个小数小于我们设置的变异几率,才进行变异
if p < mutationRate:
#变异很简单,就是0变1,1变0,即选择物品我不要了,没选的则选上
if newPopulation[m][n] == 0:
newPopulation[m][n] = 1
else:
newPopulation[m][n] = 0

population = newPopulation.copy()
#同时保留最优的个体在第一个位置中(万一这么好的家伙被前面的步骤搞没了呢?)
population[0] = bestIndividual
#同时将每代中最好的适应值存储,其最后一个也就是我们迭代结束后的最终结果
allBest[iteration] = maxFit

#输出最终最好的结果
print(allBest[-1])
print(bestIndividual)

#这里是绘图过程
x = range(0, generations)
plt.scatter(x, allBest)
plt.show()

得到的结果:

绘图跟踪每次迭代:

后记

在写这个算法之前,我还从没写过Python,原本是打算用C++写的,但是我参考的是《智能优化算法及其MATLAB实例(第2版)》,里面都是Matlab实现,要用C++写出类似思想的算法真的很僵硬。而我不是很喜欢Matlab的语法,加上Matlab正版软件太贵了,学校没有购买,尽量还是不用盗版吧。早闻Numpy的大名,也听说Python不是很难,所以我用一个上午的时间查资料熟悉了一下Python的语法和Numpy的使用,粗略写下了如上算法,如果在阅读过程中有Python大佬发现我的语法不规范还请谅解。(不得不说Python的语法真是放飞自我)

关于引用

如果有需要转载文章或者使用源代码,只需要在文首加上:
原作者:Yaron Ho
作者Blog:https://hoyyy.me

十分感谢。