本文共 2963 字，大约阅读时间需要 9 分钟。

考虑体积重量的01背包问题—基于遗传算法

1 背包问题简介

经典背包问题可以描述为：给定一组物品，每种物品都有自己的重量/体积和价值，要求把一定数量的物品放入背包，在满足背包载重/容积的约束下，最大化背包内的物品价值。

2 场景设计

已知货物的重量和体积，在满足背包载重和容积约束的情况下，最大化背包内的物品价值。

3 遗传算法设计

3.1 算子设计

采用二进制编码、锦标赛选择、顺序交叉、基本位变异、一对一生存者竞争。

3.2 适应度设计

适应度用打包的物品的价值进行表征。但是01编码有一个比较大的特点：载重容积有溢出的可能，以3.1图中的编码为例子，取出的1、4、5、6货物可能放不进背包中，这就是不满足约束的解，对此引入惩罚：如果超出约束，取价值的相反数，这样表征对于超过约束的项，价值少的（即货物相对较少）反而是比较好的待优化解，后续操作更容易获得满足约束的解。

3.3 遗传算法设计

import randomimport pandas as pddef package_calFitness(cargo_df,pop,v,m):    """    #计算适应度：解满足约束取正值，不满足约束取负值    输入：cargo_df-货物列表,pop-个体,v-背包容积,m-背包载重    返回：适应值-fit    """    v_sum,m_sum,values_sum= 0,0,0    for j in range(len(pop)):        if pop[j]==1:            v_sum += cargo_df.loc[j,'体积']            m_sum += cargo_df.loc[j,'重量']            values_sum += cargo_df.loc[j,'价值']    #计算(不满足约束的为相反数，即惩罚)    if (v_sum<=v) & (m_sum<=m):        fit = values_sum    else:        fit = -values_sum    return round(fit,3)def tournament_select(population,popsize,fit,tournament_size):    """    锦标赛选择    输入：population-种群,popsize-种群大小,fit-适应度,tournament_size-锦标赛小组个数    返回：选择后种群-new_population    """    new_population = []    while len(new_population)
   
    = pc:            child = parent1#随机生成一个            random.shuffle(child)        else:            #parent1            start_pos = random.randint(0,len(parent1)-1)            end_pos = random.randint(0,len(parent1)-1)            if start_pos>end_pos:start_pos,end_pos = end_pos,start_pos            child[start_pos:end_pos+1] = parent1[start_pos:end_pos+1].copy()            child[0:start_pos] = parent2[0:start_pos].copy()            child[end_pos+1:] = parent2[end_pos+1:].copy()                    child_population.append(child)    return child_populationdef package_mutate(populations,pm):    """    基本位变异    输入：populations-种群,pm-变异概率    返回：变异后种群-population_after_mutate    """    population_after_mutate = []    for i in range(len(populations)):        pop = populations[i].copy()        for i in range(len(pop)):            if random.random() < pm:                if pop[i] == 0:pop[i] = 1                else:pop[i] = 0        population_after_mutate.append(pop)            return population_after_mutatedef package_ga(cargo_df,v,m,pc,pm,tournament_size,popsize,generations):    """    遗传算法主流程    """    Chrom = [[random.randint(0,1) for i in range(len(cargo_df))] for j in range(popsize)]    fit = [-1]*popsize    for i in range(popsize):fit[i] = package_calFitness(cargo_df,Chrom[i],v,m)        best_fit = max(fit)    best_pop= Chrom[fit.index(max(fit))].copy()        iter = 0    while iter
   

3.4 结果

需打包的商品序号： [0, 1, 3, 4, 7, 10, 13, 15, 17, 19, 20, 22, 24, 27, 28, 29, 33, 35, 39, 40, 45, 46, 49, 50, 55, 56, 59, 61, 62, 71, 73, 75, 77, 79, 80, 82, 84, 85, 89, 91, 98]

**【讨论】**这里设置M,V= 200,200，当M和V设置比较小时，需要适当提高迭代次数，因为货物较多时，随机生成的序列中，01串中的0和1数量是接近的，而MV值较小时，对于解的要求就是1少0多，那么需要一定的代数去迭代得到较优解。

背包问题系列

记录学习过程，欢迎指正

转载地址：http://oueai.baihongyu.com/