遗传算法之 01 背包问题

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

代码

# -*- 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

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

  来呀快活呀