DEAP: внедрение NSGA-ii для решения проблемы с авиабилетами - PullRequest
Новая
       62

DEAP: внедрение NSGA-ii для решения проблемы с авиабилетами

1 голос
/ 26 июня 2019

У меня есть список, состоящий из 2 атрибутов: стоимость и рейтинг . Мне нужно найти возможные лучшие рейсы, которые имеют более низкую стоимость и более высокий рейтинг. Это многоцелевая задача оптимизации с минимизацией и максимизацией целей. Как я могу реализовать это в DEAP?

Я изо всех сил пытаюсь реализовать Individual, так как я очень плохо знаком с 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)

1 Ответ

1 голос
/ 01 июля 2019

Возможно, вы могли бы попытаться закодировать стоимость и рейтинг, используя двоичные числа.

Например, предположим, что самый дорогой билет на самолет, который вы можете получить, составляет $ 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()

Я сам не проверял это, и я был во многом вдохновлен некоторыми упражнениями, которые я делал в университете, так что, надеюсь, этоЯ буду работать на вас.

...