|
Делаем элитизм. Жесткие и мягкие ограниченияАрхив проекта: ga_7.zip На предыдущем занятии мы с вами решили задачу поиска кратчайших маршрутов в графе относительно заданной вершины. Но, давайте более детально проанализируем, что у нас получилось.
Жесткие и мягкие ограниченияПервое, с чем мы столкнулись – это способ описания задачи на уровне хромосом:
Напомню, что здесь каждый список – это отдельный маршрут от указанной точки до соответствующей вершины графа. Причем, в каждом списке должны присутствовать номера вершин (отсчет начинается с 0) от 0 до 5 без повторов. Это пример жесткого условия, заложенного в генах при решении данной задачи. То есть, оно не должно нарушаться в процессе создания особей нового поколения. Именно поэтому, мы использовали упорядоченное скрещивание (функция cxOrdered) и мутацию в виде обычной перетасовки элементов списка (функция mutShuffleIndexes). Применять здесь другие операторы скрещивания и мутации, которые бы нарушали жесткое условие задачи, недопустимо. Я специально акцентрирую внимание на существование жесткого условия, так как при решении многих реальных задач всегда следует иметь в виду существование ограничений, которые не следует нарушать. И, исходя из этого, уже выбирать соответствующие операторы скрещивания и мутации. Также в нашем примере было еще одно жесткое ограничение, связанное с отсутствием некоторых ребер в графе. Здесь, в отличие от предыдущего ограничения, в хромосомах могут появляться маршруты не соответствующие структуре графа, то есть, проходящие по несуществующим ребрам. Мы допускали такое поведение, но штрафовали его значением inf = 100 единиц. В результате, такое жесткое ограничение могло быть нарушено, но за это особь получала штраф в установленном нами размере. Этот штраф заметно увеличивал длину маршрута и, как следствие, уменьшал приспособленность особи. Поэтому, была надежда, что такие особи постепенно отсеются в процессе отбора. Вообще существует несколько известных стратегий обработки жестких ограничений:
Какой способ контроля жестких ограничений использовать в задаче, конечно же, решает разработчик ГА, исходя из конкретной задачи. Мягкие ограниченияНаряду с жесткими ограничениями могут быть еще и мягкие. Например, решается задача составления расписания для преподавателей вуза. Здесь также есть жесткие ограничения: нельзя ставить более двух лекций подряд и более трех пар подряд для одного преподавателя и т.д. Но могут быть и мягкие в качестве пожеланий преподавателей поставить занятия в определенный день недели и в определенное время. Если мягкое ограничение не учитывается, то это не нарушает общего решения и, как правило, подобные просьбы далеко не всегда берутся в расчет при составлении расписаний. Как же учитывать вклад мягких ограничений в генетическом алгоритме? Очевидно, это делается на уровне вычисления функции приспособленности. Обычно, за каждое нарушение мягкого ограничения также накладывается определенный штраф (не очень большой), который несколько ухудшает приспособленность особи. То есть, с мягкими ограничениями мы обращаемся также как и в любой задаче оптимизации, пытаясь просто сократить их число (не обязательно до нуля). Добавляем элитизм в ГАДавайте теперь немного видоизменим стандартную функцию algorithms.eaSimple() пакета DEAP так, чтобы она могла реализовывать механизм элитизма в главном цикле работы ГА. Ранее мы с вами уже говорили, что для некоторых задач целесообразно в популяции гарантированно сохранять несколько лучших (элитных) особей, то есть, не терять лучшие решения и не переоткрывать их заново. К сожалению, в пакете DEAP такой функционал отсутствует. Но его легко прописать самостоятельно. Итак, я возьму стандартную функцию eaSimple() и перепишу ее следующим образом: from deap import tools from deap.algorithms import varAnd def eaSimpleElitism(population, toolbox, cxpb, mutpb, ngen, stats=None, halloffame=None, verbose=__debug__, callback=None): """Перелеланный алгоритм eaSimple с элементом элитизма """ logbook = tools.Logbook() logbook.header = ['gen', 'nevals'] + (stats.fields if stats else []) # Evaluate the individuals with an invalid fitness invalid_ind = [ind for ind in population if not ind.fitness.valid] fitnesses = toolbox.map(toolbox.evaluate, invalid_ind) for ind, fit in zip(invalid_ind, fitnesses): ind.fitness.values = fit if halloffame is not None: halloffame.update(population) hof_size = len(halloffame.items) if halloffame.items else 0 record = stats.compile(population) if stats else {} logbook.record(gen=0, nevals=len(invalid_ind), **record) if verbose: print(logbook.stream) # Begin the generational process for gen in range(1, ngen + 1): # Select the next generation individuals offspring = toolbox.select(population, len(population) - hof_size) # Vary the pool of individuals offspring = varAnd(offspring, toolbox, cxpb, mutpb) # Evaluate the individuals with an invalid fitness invalid_ind = [ind for ind in offspring if not ind.fitness.valid] fitnesses = toolbox.map(toolbox.evaluate, invalid_ind) for ind, fit in zip(invalid_ind, fitnesses): ind.fitness.values = fit offspring.extend(halloffame.items) # Update the hall of fame with the generated individuals if halloffame is not None: halloffame.update(offspring) # Replace the current population by the offspring population[:] = offspring # Append the current generation statistics to the logbook record = stats.compile(population) if stats else {} logbook.record(gen=gen, nevals=len(invalid_ind), **record) if verbose: print(logbook.stream) if callback: callback[0](*callback[1]) return population, logbook Несмотря на большое число строк кода, все достаточно просто. Здесь используется объект halloffame (зал славы), который содержит список лучших особей в текущей популяции. Он и будет использован для хранения и дублирования элитных особей. Вначале мы определяем размер «зала славы» (переменная hof_size), а затем, в главном цикле делаем отбор индивидуумов меньше на эту величину (так как потом, добавим hof_size элитных особей в эту выборку). После этого выполняются стандартные шаги по скрещиванию и мутации отобранных особей. И только после этого добавляем в популяцию следующего поколения элитных особей. Это гарантирует их неизменность. Далее идет формирование нового списка «зала славы», так как после скрещивания и мутации в популяции могут появиться другие еще более лучшие особи. В результате, на каждой итерации мы всегда имеем неизменное число лучших индивидуумов (решений задачи). Кроме того, в эту же функцию я добавил параметр callback, который позволяет вызывать пользовательскую функцию на каждой итерации работы ГА. С помощью этого параметры мы будем отображать текущее лучшее решение в виде графа. Для этого, мы объявим функцию show(): def show(ax): ax.clear() show_graph(ax, hof.items[0]) plt.draw() plt.gcf().canvas.flush_events() Создадим окно с осями при включенном интерактивном режиме: plt.ion() fig, ax = plt.subplots() Вызовем созданную функцию ГА: population, logbook = algelitism.eaSimpleElitism(population, toolbox, cxpb=P_CROSSOVER/LENGTH_D, mutpb=P_MUTATION/LENGTH_D, ngen=MAX_GENERATIONS, halloffame=hof, stats=stats, callback=(show, (ax, )), verbose=True) Здесь мы в параметре callback указываем ссылку на функцию show(), а вторым элементом – кортеж параметров этой функции. В конце пропишем функцию для получения статистики, отображения лучшего решения в консоли и отключения интерактивного режима: maxFitnessValues, meanFitnessValues = logbook.select("min", "avg") best = hof.items[0] print(best) plt.ioff() plt.show() Теперь, при запуске программы, мы в реальном режиме времени можем наблюдать за улучшением получаемого решения на каждой новой итерации (популяции). Видео по теме |
