遗传算法(Genetic Algorithm)之deap学习笔记(三): 多目标优化算法1：背包问题

2023-12-30 04:37| 来源: 网络整理| 查看: 265

背包问(The knapsack problem)是一个多目标问题：给定一组可能的物品，每个物品都有一个重量和一个值，最大化袋中物品的价值，同时最小化重量。对包内物品的数量也有重量限制和数量限制。

定义问题 import random import numpy import operator NBR_ITEMS = 100 # 物品的总数量 IND_INIT_SIZE = 5 # 每个背包一开始的物品数量 MAX_ITEM = 50 # 一个背包最多可以装多少个物品 MAX_WEIGHT = 50 # 一个背包最大的重量

创建一个字典储存，名字是整数，值是元组

NBR_ITEMS items = {} for i in range(NBR_ITEMS): items[i] = (random.randint(1, 10), random.uniform(0, 100))

遗传算法 from deap import algorithms from deap import base from deap import creator from deap import tools # 如何创建请看之前的笔记 creator.create("Fitness", base.Fitness, weights=(-1.0, 1.0)) creator.create("Individual", set, fitness=creator.Fitness) # 这里使用set可以更好的表达问题

创建toolbox

toolbox = base.Toolbox() toolbox.register("attr_item", random.randrange, NBR_ITEMS) toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_item, IND_INIT_SIZE) toolbox.register("population", tools.initRepeat, list, toolbox.individual)

建立evaluation function

这里会返回两个fitness值（重量和数量）

# 把weight设置成10000如果超过了界限 def evalKnapsack(individual): weight = 0.0 value = 0.0 for item in individual: weight += items[item][0] value += items[item][1] if len(individual) > MAX_ITEM or weight > MAX_WEIGHT: return 10000, 0 return weight, value

在set里面不可以使用crossover和mutation，所以我们要自己定义

def cxSet(ind1, ind2): temp = set(ind1) ind1 &= ind2 # Intersection (inplace) ind2 ^= temp # Abslute difference (inplace) return ind1, ind2

定义mutation方程

def mutSet(individual): if random.random() < 0.5: if len(individual) > 0: individual.remove(random.choice(sorted(tuple(individual)))) else: individual.add(random.randrange(NBR_ITEMS)) return individual, toolbox.register("evaluate", evalKnapsack) toolbox.register("mate", cxSet) toolbox.register("mutate", mutSet) # 注册选择函数，并使用selNSGA2算法 toolbox.register("select", tools.selNSGA2) inv1 = toolbox.individual() print(inv1) # Individual({58, 35, 13, 39})

设置概率以及数量等

NGEN = 500 popSize = MU = 200 LAMBDA = 400 CXPB = 0.5 MUTPB = 0.2

下面使用内置算法。在这里，我们使用 Mu + Lambda 算法。 Lambda 是繁殖到下一代的个体数量（我们只是将其设置为恒定的种群大小），Mu 是每一代要生产的孩子数量。我们将其设置为人口规模的两倍，以便我们在选择时有选择。

def pareto_eq(ind1, ind2): return numpy.allclose(ind1.fitness.values, ind2.fitness.values) pop = toolbox.population(n=popSize) hof = tools.ParetoFront(similar=pareto_eq) stats = tools.Statistics(lambda ind: ind.fitness.values) stats.register("avg", numpy.mean, axis=0) stats.register("std", numpy.std, axis=0) stats.register("min", numpy.min, axis=0) stats.register("max", numpy.max, axis=0) pop, log = algorithms.eaMuPlusLambda(pop, toolbox, MU, LAMBDA, CXPB, MUTPB, NGEN, stats, halloffame=hof) 结果 import matplotlib.pyplot as plt %matplotlib inline gen = log.select("gen") avgs = log.select("avg") stds = log.select("std") avgs_weight = [item[0] for item in avgs] avgs_value = [item[1] for item in avgs] avgs

画个图看一下结果

plt.rc('axes', labelsize=14) plt.rc('xtick', labelsize=14) plt.rc('ytick', labelsize=14) plt.rc('legend', fontsize=14) fig, ax1 = plt.subplots() line1 = ax1.plot(gen, avgs_weight) ax1.set_xlabel("Generation") ax1.set_ylabel("Fitness (weight)") # weight

fig2, ax2 = plt.subplots() line2 = ax2.plot(gen, avgs_value) ax2.set_xlabel("Generation") ax2.set_ylabel("Fitness (value)") # value

【本文地址】

公司简介

联系我们