遗传算法之 01 背包问题

本文最后更新于:4 年前

利用 Python 实现遗传算法解决 01 背包问题

代码

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
# -*- coding: cp936 -*-
import random,os,time
from matplotlib.pyplot import *
import matplotlib

def Fx(bag):
global values
return sum(map(lambda (a, b):a * b, zip(bag, values)))

def Check(bag):
global maxBag, weights
return sum(map(lambda (a, b):a * b, zip(bag, weights))) <= maxBag

def Across(father, mother):

child1 = map(lambda (a, b):a & b, zip(father, mother))
child2 = map(lambda (a, b):a | b, zip(father, mother))

return [child1, child2]

def Mutate(bag):
r = np.random.randint(0, len(bag))
bag[r] = abs(bag[r] - 1)
return bag

#------------------------------------------------------------------------------------------ 参数设置 ------------------------------------------------------------------------------------------

weights = [3,4,5,1,10,44,78,52,14,96,10,2,44,112,5,3,1,4,55,62,1,3,41,52,13] #物品重量
values = [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] #物品价值
maxBag = 50 #背包容量

population = 5 #种群数量,太多会导致程序假死
mutation_rate = 0.01 #变异概率
add = 0.05 #变异概率随着精英程度递减而增大,0.001
#retain_rat = 0.2 #种群筛选时保留 20% 的精英

#------------------------------------------------------------------------------------------ 参数设置 ------------------------------------------------------------------------------------------

d = 0
items = []
for i in range(len(values)):
items += [random.randint(0, 1)]

x = []

while len(x) < population:
if Check(items):
x += [items[:]]

random.shuffle(items)

print '种群初始化完毕'

xy = sorted([(i, j) for i, j in [(Fx(xi), xi) for xi in x]], reverse = True)
x = [x1 for y1, x1 in xy]
y = [y1 for y1, x1 in xy]

print x[0]
print y[0]

#x = x[:int(population * retain_rat)]

while 1:
length = len(x)

for i in range(length):
for child in Across(random.choice(x), random.choice(x)):
if Check(child):
x += [child[:]]

while len(x) < population: #种群数量过多假死原因
if Check(items):
x += [items[:]]
random.shuffle(items)

each_mutation_rate = mutation_rate

for i in range(len(x)):
if random.uniform(0,1) < each_mutation_rate:
mutate = Mutate(x[i][:])
if Check(mutate):
x[i] = mutate[:]

each_mutation_rate += add

xy = sorted([(i, j) for i, j in [(Fx(xi), xi) for xi in x]], reverse = True)
x = [x1 for y1, x1 in xy]
y = [y1 for y1, x1 in xy]

#x = x[:int(population * retain_rat)]

print d,x[0],sum(map(lambda (a,b):a*b, zip(x[0],weights))),y[0] #代数,选择情况,物品总重量,总价值

d+=1

Emmmmmmmmmmmm

  • 双击运行
  • 结果
    GA01 背包结果
  • 种群数量过多会导致程序假死, 原因是总排列组合数小于规定的种群数量
  • 其实遗传算法不太适合解决这类问题, 动归比较好

    来呀快活呀


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!