Эволюционные алгоритмы - мощное решение различных проблем оптимизации. Эволюционные алгоритмы помогают найти подходящее решение в случае, если найти его строгими методами настолько сложно, что можно сказать, что это невозможно. Один из самых популярных вариантов эволюционных алгоритмов - генетический алгоритм. Подробнее о генетических алгоритмах можно прочитать в статье Введение в генетические алгоритмы - включая пример кода.
Иногда, если проблема сложная и люди тяжелые, может оказаться невозможным реализовать эффективный генетический алгоритм, потому что вычисления занимают слишком много времени и невозможно сохранить все необходимые данные в памяти. Чтобы преодолеть вторую проблему, можно сохранить некоторые индивидуумы на диске и загрузить их в память, когда они понадобятся. Это не решает проблем с производительностью, более того, приносит еще одну: чтение (и, возможно, десериализация) отдельного человека с диска в память может еще больше замедлить работу всей системы. Более того, все люди, которых когда-либо видел алгоритм, были созданы с использованием одних и тех же генетических операторов и, следовательно, могут иметь слишком много общего, так что алгоритм будет обходить локальные оптимумы. Есть ли способ решить эту проблему? Возможно, да: мы можем использовать параллельный или распределенный генетический алгоритм.
В этой статье описаны два варианта генетических алгоритмов, оба предназначены для повышения производительности алгоритмов: параллельные и распределенные генетические алгоритмы.
Параллельный генетический алгоритм
Параллельный генетический алгоритм - это такой алгоритм, который использует несколько генетических алгоритмов для решения одной задачи [1]. Все эти алгоритмы пытаются решить одну и ту же задачу, и после того, как они завершили свою работу, выбирается лучший индивидуум для каждого алгоритма, затем выбирается лучший из них, и это решение проблемы. Это один из самых популярных подходов к параллельным генетическим алгоритмам, хотя есть и другие. Этот подход часто называют «островной моделью», потому что популяции изолированы друг от друга, подобно тому, как популяции реальных существ могут быть изолированы, живя на разных островах. Изображение 1 иллюстрирует это.
Эти генетические алгоритмы не зависят друг от друга, в результате они могут работать параллельно, используя преимущества многоядерного процессора. У каждого алгоритма есть свой собственный набор индивидов, в результате эти люди могут отличаться от индивидов другого алгоритма, потому что у них разная история мутаций / кроссоверов.
В статье [2] описан параллельный генетический алгоритм, который использует два независимых алгоритма для повышения своей производительности. Разница между этими двумя алгоритмами заключается в том, как люди отбираются для мутации и скрещивания. Более того, некоторым существам с наибольшим соответствием разрешено «мигрировать» с одного алгоритма на другой. Хотя иногда этого может быть достаточно, но когда задачу очень сложно решить или человек представляет собой сложную сущность, нам может потребоваться еще большее разнообразие внутри людей.
Чтобы достичь этого, мы можем использовать как можно больше алгоритмов (скажем, в два раза больше, чем количество ядер процессора, которое у нас есть) и изменять почти все свойства алгоритма. В результате каждый алгоритм имеет свой собственный набор индивидов, которые были созданы с использованием методов, которые отличаются от методов, используемых другими алгоритмами. Это тоже «модель острова», хотя «острова» больше отличаются друг от друга. Единственное ограничение заключается в том, что все алгоритмы используют одну и ту же функцию подбора для оценки людей, чтобы можно было сравнивать людей, принадлежащих к разным алгоритмам. В результате эти генетические алгоритмы могут отличаться по следующим аспектам:
- как создаются новые личности;
- как мутируют особи и как они отбираются для мутации;
- как люди переходят и как их отбирают для кроссовера;
- сколько человек принимает участие в одном перекрестном событии и сколько людей создается в результате;
- сколько особей выживают после каждой итерации алгоритма и как отбираются эти существа;
- сколько особей содержится в каждом поколении;
- через сколько поколений проходит алгоритм.
Варьируя эти характеристики, можно создать множество различных генетических алгоритмов, которые решают одну и ту же задачу, но имеют совершенно разных людей.
Важно отметить, что эти независимые генетические алгоритмы имеют ту же структуру, что и любой другой традиционный генетический алгоритм, поэтому их можно извлечь из параллельного генетического алгоритма и использовать самостоятельно.
Кроссовер между алгоритмами
Итак, что у нас есть? У нас есть несколько генетических алгоритмов, которые работают независимо и имеют свои собственные наборы индивидов. Мы можем выбрать людей, принадлежащих к разным алгоритмам, и пересечь их. В результате функции, которые появляются у отдельных лиц одного алгоритма, будут доступны для другого. Это позволяет создавать таких индивидуумов, которых нельзя создать с помощью одного только алгоритма, привнося в них еще больше разнообразия и распространяя удобные функции.
Проиллюстрируем это на примере. Допустим, у нас есть три независимых генетических алгоритма, и мы хотим скрестить их попарно. Берем первый алгоритм и случайным образом выбираем второй элемент пары. Итак, мы создаем столько пар, сколько алгоритмов у нас есть, в каждой паре первый элемент выбирается последовательно, а второй - случайный. Затем мы выполняем кроссовер на популяциях этих двух алгоритмов, беря индивидуумов из них обоих. Мы отбираем индивидов для пересечения таким образом, чтобы индивиды из разных алгоритмов пересекались вместе. Мы используем механизмы кроссовера, которые используются первым алгоритмом пары, и этот алгоритм получает всех индивидов, которые были созданы в результате кроссовера; второй алгоритм пары - это просто донор, который предоставляет свои особи. Следовательно, каждый алгоритм получает новых индивидов, когда он является первым элементом пары. Если для алгоритма кроссовера требуется более двух индивидов, дополнительные индивиды могут быть взяты из любого алгоритма пары, только рекомендуется, чтобы здесь ни один алгоритм не доминировал.
Также возможно использование специальной техники кроссовера, когда речь идет о кроссовере между алгоритмами, который применяется только для кроссовера между алгоритмами.
Рекомендуется использовать кроссовер между алгоритмами где-то посередине процесса (или даже несколько раз), а не в самом начале или в конце. В самом начале у каждого алгоритма есть свежие особи, на которых не повлияли мутации или кроссоверы, в результате чего их особенности, характерные для конкретного алгоритма, не ярко выражены. В конце концов, больше нет поколений, которые могут влиять на новых особей, рожденных в результате кроссовера, в результате они не будут соревноваться с другими особями, чтобы определить, какой из них лучше.
Заключение
Параллельный генетический алгоритм может занять немного больше времени, чем непараллельный, потому что он использует несколько вычислительных потоков, которые, в свою очередь, заставляют операционную систему чаще выполнять переключение контекста. Тем не менее, параллельный генетический алгоритм, как правило, дает лучшие результаты и дает больше оптимальных индивидуумов, чем непараллельный.
Несмотря на то, что параллельное выполнение может значительно улучшить результат, в некоторых случаях даже этого может быть недостаточно. В этом случае мы можем использовать…
Распределенный генетический алгоритм
Распределенный генетический алгоритм - это фактически параллельный генетический алгоритм, независимые алгоритмы которого работают на разных машинах. Более того, в этом случае каждый из этих алгоритмов может быть, в свою очередь, параллельным генетическим алгоритмом! Распределенный генетический алгоритм также реализует «модель острова», и каждый «остров» еще более изолирован от других. Если каждая машина запускает параллельный генетический алгоритм, мы можем назвать это «моделью архипелага», потому что у нас есть группы островов. На самом деле не имеет значения, что такое единственный генетический алгоритм, потому что распределенный генетический алгоритм предполагает наличие нескольких машин, выполняющих независимые генетические алгоритмы для решения одной и той же задачи. Изображение 2 иллюстрирует это.
Распределенный генетический алгоритм также может помочь, когда нам нужно создать много индивидуумов, чтобы наблюдать за всем доменом, но невозможно сохранить их все в памяти одной машины.
Когда мы обсуждали параллельный генетический алгоритм, мы ввели термин «кроссовер между алгоритмами». Распределенный генетический алгоритм позволяет нам выполнять кроссовер между отдельными машинами!
В случае распределенного генетического алгоритма у нас есть своего рода «главный разум», который контролирует общий прогресс и координирует работу этих машин. Он также управляет кроссовером между машинами, выбирая, как машины будут соединены вместе для выполнения кроссовера. В целом процесс такой же, как и в случае параллельного генетического алгоритма, за исключением того, что люди перемещаются по сети с одной машины на другую. Чтобы избежать переноса отдельных лиц дважды, рекомендуется отправлять лиц к машине, которая будет принимать новых лиц, созданных в результате операции кроссовера. «Главный разум» также выбирает лучшего человека из лиц вторичных машин, к которым он подключен и которые фактически выполняли вычисления. В результате этот «главный разум» является точкой входа в распределенный генетический алгоритм, который взаимодействует с тем, кто запрашивает у него решение.
Реализация
Эта статья в основном посвящена теории, но когда дело доходит до реализации, можно иметь «структуру распределенного генетического алгоритма», которая позаботится об управлении вторичными машинами и передаче людей по сети. В общем, такая структура способна позаботиться обо всем, кроме действий, которые необходимо знать внутренней структуре человека. Следовательно, пользователю необходимо выполнить всего несколько операций:
- индивидуальное создание и утилизация;
- индивидуальный кроссовер;
- индивидуальная мутация;
- подходящая функция, оценивающая людей.
Все остальное универсально и может быть реализовано в рамках. Такая структура может запускать несколько распределенных генетических алгоритмов одновременно, не зная, какая проблема решается.
Заключение
Используя параллельные и распределенные генетические алгоритмы, можно повысить производительность системы, использующей эволюционные алгоритмы. В любом случае, мы должны помнить, что эволюционные алгоритмы не гарантируют, что решение когда-либо будет найдено, и что нет более оптимальных решений, чем то, которое было найдено.
Одна из основных проблем, с которыми нам приходится иметь дело при использовании генетических алгоритмов, - это предварительная конвергенция к подмножеству индивидов, которые доминируют над другими. Параллельные и распределенные генетические алгоритмы пытаются решить эту проблему, вводя различия между алгоритмами, которые заставляют их иметь разный набор индивидов.
С параллельными и распределенными генетическими алгоритмами индивидуумы более расходятся, в результате можно создать меньше индивидуумов, чем при использовании непараллельного генетического алгоритма, сохраняя при этом качество решения на том же уровне.
