1

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

我正在努力实施个人，因为我对 DEAP 很陌生。

# 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)
4

1 回答 1

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()

我自己还没有测试过这个，我在很大程度上受到了我在大学做的一些练习的启发，所以希望它对你有用。

于 2019-07-01T19:42:13.160 回答