python - DEAP:实现 NSGA-ii 解决机票问题

Question

我有一个包含 2 个属性的列表，即成本和评级。我需要找到成本较低且评级较高的最佳航类。这是一个具有最小化和最大化目标的多对象优化问题。我如何在 DEAP 中实现这一点？

由于我对 DEAP 很陌生，所以我正在努力实现 individual。

# Attribute generator
toolbox.register("cost", random.randrange, NBR_ITEMS)
toolbox.register("rating", random.randrange, NBR_ITEMS)

# Structure initializers
toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.cost, toolbox.rating) #
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

Answer 1

也许您可以尝试使用二进制数字对成本和评级进行编码。

例如，假设您能买到的最贵机票是 16384 美元，您可以将其存储在 14 位中 (2^14 = 16384)，而评级是从 0 到 10 的数字，因此您可以将其存储在 4 位中位，因此您总共可以使用 18 位来存储您的数据。

现在您需要一个函数来解码它:

def decode_individual(individual):
    decoded_individual = ['', '']

    # Decode cost (14 bits)
    for i in range(0, 14):
        decoded_individual[0] += str(individual[i])

    # Decode rating (4 bits)
    for i in range(1, 3):
        decoded_individual[0] += str(individual[13 + i])

    return tuple(map(lambda x: int(x, 2), decoded_individual))

您需要为多目标问题设置适应度函数，即，您需要为每个函数提供一些权重，如果您试图最大化函数，则需要为正值；如果您试图最小化函数，则需要为负值。就您而言，我猜您正在尝试最大化降级并最小化成本，因此您可以按如下方式进行设置:

creator.create('Fitness', base.Fitness, weights=(1.0, -0.5,))
creator.create('Individual', list, fitness=creator.Fitness)

您的健身方法应返回您尝试按权重中指定的顺序最大化和最小化的函数的结果:

def function_cost(individual):
    decoded_individual = decode_individual(individual)
    return decoded_individual[0]

def function_rating(individual):
    decoded_individual = decode_individual(individual)
    return decoded_individual[1]

def fitness(individual):
    return (function_cost(individual), function_rating(individual)),

然后，不要像示例中那样注册 2 个健身函数，而是只注册一个:

toolbox.register('evaluate', fitness)

配置 DEAP 使用二进制数据:

toolbox.register('attrBinary', random.randint, 0, 1)
toolbox.register('individual', tools.initRepeat, creator.Individual, toolbox.attrBinary, n=18) # Here you need to specify the number of bits you are using
toolbox.register('population', tools.initRepeat, list, toolbox.individual)

# Register the evaluation function (was named fitness in this example)
toolbox.register('evaluate', fitness)

# Configure your mate and mutation methods, e.g.
toolbox.register('mate', tools.cxTwoPoint)
toolbox.register('mutate', tools.mutFlipBit, indpb=0.15)

您的选择方法必须支持多目标问题，NSGA2正如您的问题中指出的，可以使用:

toolbox.register('select', tools.selNSGA2)

然后运行算法，您可以尝试不同的个体数(种群)数、代数以及交配和突变的评级:

num_pop = 50
num_gen = 100
cx_prob = 0.7
mut_prob = 0.2

best = []

for gen in range(num_gen):
    offspring = algorithms.varAnd(population, toolbox, cxpb=cx_prob, mutpb=mut_prob)
    fits = toolbox.map(toolbox.evaluate, offspring)

    for fit, ind in zip(fits, offspring):
        ind.fitness.values = fit

    population = toolbox.select(offspring, k=len(population))
    top = tools.selBest(population, k=1)
    fitness = fitness(top[0])

    print(gen, fitness, decode_individual(top[0]), top[0])
    best.append(fitness[0])

您可能还想在图表中显示每一代的最佳个体:

x = list(range(num_gen))
plt.plot(x, best)
plt.title("Best ticket - Cost / Rating")
plt.show()

我自己还没有对此进行过测试，我在很大程度上受到了我在大学所做的一些练习的启发，因此希望它对您有用。