Введение в алгоритм BRKGA-MP-IPR

Автор оригинала: João Marcelo Freitas de Almeida.

Недавно я провел исследование совершенно нового эволюционного алгоритма под названием BRKGA-MP-IPR_[1]_. Цель этой статьи-немного объяснить, из чего состоит алгоритм, его основные особенности и новшества.

Что вообще означает это длинное имя?

Давайте разберем его на три части, чтобы нам было легче получить его.

Во-первых, BRKGA расшифровывается как Предвзятый генетический алгоритм случайного ключа , это ветвь классического генетического алгоритма (сокращенно GA). Во-вторых, MP расшифровывается как Multi parenting , что является просто методом отбора отдельных лиц (мы объясним это позже), и , наконец, IPR расшифровывается как Неявная ссылка на путь , новая версия метода локального поиска Path relink|/, обычно используемого для улучшения решений, найденных эвристиками, путем их объединения.

Понимание основных концепций

Чтобы более четко увидеть общую картину BRKGA-MP-IPR_[1]_, нам нужно понять основные концепции, на которые опирается алгоритм, и это:

Генетический алгоритм;
Предвзятые Случайные Ключи;
Многодетное Воспитание;
Перелинковка пути;

1. Генетический алгоритм

Генетические алгоритмы (GAs) – это семейство метаэвристик, глубоко вдохновленных теорией естественной эволюции. Они реализуются таким образом, что отражают различные процессы естественного отбора, такие как выживание наиболее приспособленных особей, размножение, мутация и, конечно, эволюция особей. Обычное использование газа включает в себя проблемы глобальной оптимизации и планирования, хотя с момента его первоначальной разработки были разработаны многочисленные варианты газа, соответствующие очень широкому кругу реальных проблем ( См. Список Здесь ).

С точки зрения кода, простейшие версии GAs просты для понимания. Я ссылаюсь здесь на наиболее релевантные реализации, перечисленные Github , если вы хотите изучить, как это выглядит в реальном коде.

2. Предвзятые Случайные Ключи

Чтобы представить возможное решение проблемы, ГА кодирует решение в виде отдельного человека. Простейшим примером этого может быть популяция людей, которые могут быть декодированы в решения для экземпляра TSP ( Проблема коммивояжера ). Ниже приведен пример такого представления:

2.1. Простое кодирование

# a possible solution as a list of numbers
print(population[individual_index])
# output: [1,2,3,4,5]

В этом примере переменная individual хранит порядок посещения городов в туре продавца, и, как и в этом случае, каждое число является ребром графика.

2.2. Кодирование случайных ключей

Как правило, случайный ключ является плавающим в интервале [0,1] . Случайные ключи будут представлять информацию, аналогичную приведенному выше примеру, но с некоторыми дополнительными преимуществами: теперь нам не придется беспокоиться о возможном создании недействительных новых особей во время размножения или мутации (скажем, мутировавший ген указывает на несуществующий город в экземпляре TSP), и мы будем представлять особей независимым от проблем способом (проблемы перестановок, как правило, просто представлены случайными ключами). Вот тот же пример кода сверху, теперь с использованием схемы случайного ключа:

# a possible solution as a list of random keys print(population[some_individual_index])
# output: [0.54,0.89,0.32,0.11,0.73]

# decode the individual to a real solution
print(decode(population[some_individual_index]))
# output: [3,2,0,4,1]

Мы можем заметить, что независимо от того, какие гены были сгенерированы во время размножения и мутации, все решения верны (учитывая, что декодирование будет выполняться на индивидууме).

Теперь последнее, что касается случайных ключей, – это то, как метод декодера преобразует список случайных ключей в возможное решение. На самом деле это может быть довольно просто, в приведенной выше схеме декодирования мы просто отсортировали аллели в порядке возрастания (упорядоченный массив [0.11,0.32,0.54,0.73,0.89] ) и сопоставил упорядоченные ключи с их исходным индексом в списке (таким образом, мы получаем решение [3,2,0,4,1] ). Существуют и другие методы декодирования решений, это просто самый простой из них.

Если вы ищете дополнительную информацию, пожалуйста, обратитесь к оригинальной публикации _ [2]_.

2.3. Предвзятый Случайный ключ

Эта вариация кодирования случайных ключей предлагается в качестве двух изменений в методе селекции:

Один из родителей, выбранных для спаривания, склонен быть более приспособленным, чем другой родитель. Стратегия всегда иметь предвзятую пару индивидуумов состоит в том, чтобы выбрать одного из них из элитной группы (меньшая часть населения, содержащая индивидуумов с текущей наилучшей приспособленностью).
Вероятность того, что потомство унаследует аллель своего элитного родителя, выше, чем от его неэлитного родителя. Эмпирическая интуиция этого алгоритмического выбора заключается в том, что предубежденное к элите потомство повысит общее качество популяции и, следовательно, приведет к лучшему выполнению эволюционного процесса.
|/Figure: |/Flowchart of a BRKGA//Source://J.Ф. Гонсалвес, М.Г.С. Ресенде

|/Figure: |/Flowchart of a BRKGA//Source://J.Ф. Гонсалвес, М.Г.С. Ресенде

Первой из двух основных новинок в алгоритме BRKGA-MP-IPR является схема с несколькими родителями. Вместо того, чтобы выбирать одного родителя из элиты и одного из неэлиты, теперь n особи будут отобраны для выведения новой особи, и из них e являются особями из элиты и n-e не являются. В дополнение к этому, каждый из n родителей будет иметь смещение отбора, пропорциональное его пригодности. Так же, как и предвзятые случайные ключи, мультиродитель-это попытка повысить качество решений, не оставляя за собой возможности диверсификации населения.

Path-relinking намеревается найти лучшее решение, которое находится где-то между двумя уже известными решениями элитного населения, надеясь, что такое промежуточное решение улучшит качество и разнообразие элитного населения.

Рисунок: Визуальный пример пересылки путей Источник: Conci A., Бразилия A.[3]

Из приведенного выше изображения мы видим, что с помощью некоторых итерационных шагов алгоритм заменяет части базового решения частями направляющего решения , и если на каком-либо из этих этапов замены частей пригодность, связанная с этим промежуточным индивидуумом, лучше, чем то, что у нас есть в настоящее время, мы можем считать поиск успешным и добавить этого нового индивидуума в популяцию.

4.2. Что в этом подразумевается?

Точно так же, как кодирование случайного ключа, повторная привязка пути не должна зависеть от проблем или реализации. Эти методы предназначены для общих подходов к широкому спектру проблем, и, как это, алгоритм пересылки путей неявно пытается найти промежуточные решения, не зная о структуре проблемы, которую вы пытаетесь решить. Что, в конце концов, приведет вас к более быстрому и простому использованию BRKGA-MP-IPR.

Наконец, я хотел бы сказать, что существует два варианта этого алгоритма: прямая версия и версия на основе перестановок . Они очень похожи по реализации, но немного отличаются в некоторых деталях. Если вы хотите получить более подробную информацию об этом, я рекомендую вам ознакомиться с оригинальной статьей [1] .

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

5. Реализация К. Э. Андраде

Для уточнения я настоятельно рекомендую вам проверить невероятную реализацию python BRKGA-MP-IPR , разработанную Карлосом Андраде . Он содержит отличный код, документацию и пошаговые руководства. Наряду с реализацией python вы также можете найти версии C++ и Julia. В этом разделе мы выполняем пример алгоритма, используемого для оптимизации маршрутов на примере задачи коммивояжера.

5.1. Простой пример выполнения

Реализация доступна в виде пакета python, поэтому, предполагая, что у вас есть по крайней мере версия 3.7 Python, которую вы можете выполнить:

pip install brkga-mp-ipr docopt

(Нам также нужен пакет docopt для анализа аргументов командной строки)

Получите копию репозитория, чтобы мы могли получить доступ к папке examples, где у нас есть скрипт, содержащий очень хороший и простой пример решения экземпляра TSP:

git clone https://github.com/ceandrade/brkga_mp_ipr_python.git cd brkga_mp_ipr_python/examples/tsp

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

Теперь, чтобы увидеть, как работает этот эволюционный алгоритм, вы можете использовать эту команду:

python3.7 main_complete.py -c config.conf -s 2700001 -r Generations -a 100 -t 60 -i instances/brazil58.dat

Где -c укажите файл, содержащий все параметры оптимизации, – s для случайного семени, – r для правила остановки, – t для максимального времени выполнения и -i укажите файл, содержащий графическое представление экземпляра коммивояжера.

После его выполнения вы получите результат, аналогичный этому:

------------------------------------------------------ > 
Experiment started at 2020-03-05 12:45:18.612186 
> Instance: instances/brazil58.dat 
> Configuration: config.conf 
> Algorithm Parameters: 
> -population_size 2000 
> -elite_percentage 0.3 
> -mutants_percentage 0.15 
> -num_elite_parents 2 
> -total_parents 3 
> -bias_type LOGINVERSE 
> -num_independent_populations 3 
> -pr_number_pairs 0 
> -pr_minimum_distance 0.15 
> -pr_type PERMUTATION 
> -pr_selection BESTSOLUTION 
> -alpha_block_size 1.0 
> -pr_percentage 1.0 
> -exchange_interval 200 
> -num_exchange_indivuduals 2 
> -reset_interval 600 
> Seed: 2700001 
> Stop rule: GENERATIONS 
> Stop argument: 100 
> Maximum time (s): 60.0 
------------------------------------------------------ 
[2020-03-05 12:45:18.627376] Reading TSP data... Number of nodes: 58 
[2020-03-05 12:45:18.651178] Generating initial tour... Initial cost: 30774.0 [2020-03-05 12:45:18.652157] Building BRKGA data... New population size: 580 [2020-03-05 12:45:18.652539] Initializing BRKGA data... [2020-03-05 12:45:18.858128] Warming up... 
[2020-03-05 12:45:20.052183] Evolving... * Iteration | Cost | CurrentTime * 1 | 30774 | 0.51 * 74 | 30759 | 43.13 * 78 | 30721 | 45.42 * 79 | 30371 | 46.12 * 81 | 30350 | 47.19 
[2020-03-05 12:46:17.117151] End of optimization 
Total number of iterations: 100 
Last update iteration: 81 
Total optimization time: 57.06
Last update time: 47.19
Large number of iterations between improvements: 73
% Best tour cost: 30350.00
% Best tour: 41 0 29 12 39 24 8 31 19 52 49 3 17 43 23 57 4 26 42 11 56 22 53 54 1 40 34 9 51 50 46 48 2 47 28 35 16 25 18 5 27 32 13 36 33 45 55 44 14 20 38 10 15 21 7 37 30 6 
   Instance,Seed,NumNodes,TotalIterations,TotalTime,LargeOffset,LastUpdateIteration,LastUpdateTime,Cost
   brazil58.dat,2700001,58,100,57.06,73,81,47.19,30350

6. Заключение

Теперь у нас есть хорошее первоначальное понимание алгоритма, включая его основные концепции. Мы также можем выполнить алгоритм, следуя шагам из документов реализации. Следующим шагом будет найти проблему по вашему выбору и использовать этот алгоритм для ее решения. Чтение оригинальной статьи также является хорошим вариантом для углубленного изучения деталей.