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
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]
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]
print d,x[0],sum(map(lambda (a,b):a*b, zip(x[0],weights))),y[0]
d+=1