Генетические алгоритмы
Введение
Существует ряд задач, классические алгоритмы решения которых довольно медленны, сложны в реализации в условиях многопоточного программирования. К таким задачам, например, относятся задача коммивояжера, задача упаковки контейнеров, обучение особо больших нейросетей и многие другие задачи оптимизации.
Однако примерно в 50-х годах ХХ века ученые предложили универсальный подход к решению подобного рода задач: подход, подсмотренный у самой природы. В 1954 ученый Нильс Аалл Барричелли начал проводить первые эксперименты по компьютерной симуляции эволюции, однако широкое признание эволюционные алгоритмы получили лишь в 60-х годах после публикации работы Инго Рехенберга и Ханса-Пауля Швефеля.
Суть эволюционного или, как его более широко принято называть, генетического алгоритма сводится к простой идее: порождению множества случайных решений претендующих на оптимальность, отбору из них наилучших, которые затем используются для порождения следующего поколения решений, над которым так же совершается процедура отбора и цикл замыкается, пока не будет найдено приемлемое решение.
Генетический алгоритм (ГА), в отличие от классических, не гарантирует, что будет найдено на 100% лучшее решение, он как и все численные методы, подвержен скатыванию в локальные экстремумы. Однако ГА позволяет приблизиться к оптимальному решению, а в случае не очень большого числа переменных, даже найти его, если повезет, за приемлемое время.
Основная схема генетического алгоритма
Чтобы приступить к решению какой-либо задачи при помощи ГА, необходимо формализовать задачу таким образом, чтобы ее решение могло быть представлено в виде строки чисел (в классической формулировке двоичной строки).
Далее необходимо определиться с тем, как вы будете оценивать эту строку чисел, если быть более точным, как сравнивать между собой два решения.
В случае простых задач, вроде поиска минимума функции, критерий оценки решения (в англоязычной литературе ее принято называть fitness function) довольно очевиден — само значение функции. В некоторых же случаях определение рейтинга решения может вылиться в нетривиальную задачу.
Допустим решение задачи состоит из трех целых чисел размерности Byte (здесь и далее применятся терминология Java), представим это решения как строку чисел.
То же самое решение можно представить как строку битов:
Здесь и далее будем называть решение ДНК и считать, что оно представляется строкой битов. Хотя принципиальной разницы, что находится в ячейках таблицы — биты или числа, нет.
Рассмотрим дальнейшие действия по шагам:
- Породим множество ДНК (генофонд) со случайным набором битов (чем больше переменых — тем больше множество, конкретное число определяется экспериментально).
- Сосчитаем рейтинги каждого решения и отсортируем ДНК в порядке убывания рейтинга.
- Используя определенную стратегию селекции (о конкретных стратегиях поговорим позже) будем выбирать попарно ДНК и порождать их потомков путем смешения (кроссовера) генов ДНК-родителей (о стратегиях репликации поговорим тоже чуть позже). Часть ДНК-потомков подвергнем мутациям — случайным изменениям генов (битов, чисел).
- Поместим вновь порожденные ДНК в генофонд, удалив оттуда часть ДНК с низким рейтингом.
- Будем повторять шаги 2-4 до тех пор, пока не пройдет определенное время, или пока не будет найдено решение с заранее определенным рейтингом.
- Таков общий алгоритм, теперь поговорим о вариациях.
Стратегии селекции
Под селекцией понимается алгоритм выбора ДНК родителей для дальнейшего размножения.
Существует несколько подходов. Самым простым алгоритмом селекции является выбор двух ДНК с наивысшим рейтингом и порождению всех ДНК потомков от них.
Традиционным считается выбор родителей случайным образом с вероятностью обратно пропорциональной рейтингу (месту в генофонде).
Турнирный алгоритм, является модификацией традиционного подхода. В начале случайным образом выбирается несколько ДНК из генофонда (равновероятно). Затем, с некой предопределенной вероятностью p выбирается первая ДНК (лучшая), с вероятностью p*(1-p) — вторая, с вероятность p*((1-p)^2) — третья и т. д.
Читатели могут предложить собственные алгоритмы выбора наилучших ДНК для кроссовера, главное чтобы соблюдалось правило, что ДНК с большим рейтингом должны попадать на стадию размножения чаще ДНК с плохим рейтингом.
Стратегии кроссовера (репликации)
Название «кроссовер» происходит от аналогичного процесса происходящего во время деления биологических клеток мейозом, при этом две хромосомы обмениваются гомологичными участками.
Продемонстрируем наглядно, как это происходит в ГА.
Как видно из схемы при кроссовере хромосом (ДНК), выбирается случайное место разрезания и происходит обмен частями.
Далее существует два подхода: а) получившиеся ДНК заменяют родителей, б) родители остаются без изменения, а одна или обе результирующие ДНК добавляются в генофонд. Оба подхода имеют право на жизнь, ибо имеют свои достоинства и недостатки. При втором подходе, гарантированно сохраняется однажды найденное высоко рейтинговое решение, однако он ведет к скатыванию в локальный экстремум, из-за того, что со временем гены чемпиона начинают доминировать в популяции, тем самым, снижая вероятность найти соседний более выгодный экстремум. Первый же подход, обеспечивает большую вариабельность, но есть риск потерять хорошее решение со временем, по этому популяцию желательно регулярно мониторить и запоминать хорошие решения.
Кроссовер не обязательно производить в одном месте, допускается разрезать ДНК в двух и более местах. Более того, некторые теоретики ГА указывают на возможность случайного перемешивания генов ДНК родителей (в примерно равной пропорции), при этом результирующая ДНК может выглядеть как (разным цветом нарисованы гены разных родителей):
Как и почти все в ГА, алгоритм кроссовера довольно гибок, читатели могут, например, порождать новые решения смешением генов трех или даже более родителей, если уверены, что это быстрее приведет их к лучшему результату.
Стратегии мутации
Вслед за кроссовером популяцию подвергают мутации. Некоторые ученые заявляют, что мутация является более важным процессом, нежели кроссовер. По их словам, для ряда задач можно обойтись без кроссовера, а использовать одну лишь мутацию для достижения наилучших результатов.
Исследования показывают, что это справедливо лишь от части, и работает лишь для ограниченного круга задач.
В классическом ГА мутации каждую ДНК с определенной заранее заданной вероятностью подвергают либо не подвергают мутации. При мутации, опять таки, с определенной вероятностью случайным образом меняются гены.
В случае если ДНК бинарная, простейшая мутация заключается в изменении значений случайных битов, на противоположные. Если ДНК представлена набором чисел, то в качестве мутации может выступить изменение некоторых из них на случайные, либо добавление случайного смещения.
Конкретную стратегию следует выбирать исходя из конкретной задачи. Например, если мы знаем, что какая то переменная в решаемой задаче не может быть отрицательной, то желательно алгоритм мутации организовать таким образом, чтобы он не порождал отрицательных значений, это позволит улучшить эффективность алгоритма, за счет времени которое было бы потрачено на рассмотрение заведомо неверных решений.
Кроме того вероятности мутации членов генофонда, а так же вероятности и величину мутации генов следует назначать из следующих соображений:
- слишком малая вероятность мутации ведет к медленному прогрессу, или к заполнению генофонда копиями чемпиона, что останавливает прогресс вообще
- слишком высокая вероятность и размер мутации снижают вероятности нахождения оптимального решения, так как колония на каждой итерации будет, как бы проскакивать мимо, с другой стороны, это позволяет охватить большее пространство значений и выскочить из локального экстремума.
Вполне разумным является адаптивный алгоритм мутации, при котором вероятности изменения членов генофонда динамически изменяются в зависимости от текущей ситуации.
Например, если наблюдается стойкая тенденция к улучшению решения, то мутацию можно держать на среднем уровне. Если же в течение нескольких последних поколений не наблюдается улучшений — мутацию можно усилить.
Стратегии назначения рейтинга
Присвоение рейтинга ДНК является самым важным процессом в ГА, так как именно правильно назначенный рейтинг позволяет быстрее достичь требуемого решения.
Для некоторых задач, как упоминалось во введении, стратегия назначения рейтинга очевидна, в других же случаях процесс назначения рейтинга во многом творческий и не тривиальный, особенно если существуют ограничения на значения переменных составляющих решение. Например, необходимо решить, как сравнить между собой два решения, одно из которых соответствует всем ограничениям, но имеет низкое качество, а второе имеет потенциально более высокое качество, но нарушает ограничение по какой-либо из переменных.
Рейтинг всегда должен выражаться числом и не может быть логической переменной, так как это не позволит эффективно выбирать наилучшие решения.
Рейтинг не обязательно вычислять по какой-то формуле. Например, если мы подбираем наилучшее сочетание характеристик у героя ролевой игры (Сила, Ловкость, Интеллект и.т.д.), то при назначении рейтинга можно проводить состязания по правилам игры между членами генофонда, а рейтинг назначать пропорционально количеству выигранных схваток (нанесенным повреждениям) и т.д.
Как правило, выставление оценок ДНК занимает большую часть времени во время итерации ГА.
Момент назначения рейтинга — это шанс избавиться от «двойников», так как присутствие одинаковых ДНК (особенно высоко рейтинговых) снижают эффективность ГА и ускоряет скатывание в локальный экстремум. В этом случае одному из «близнецов» назначается истинный рейтинг, а второму рейтинг в районе отрицательной бесконечности.
Многопоточность
ГА очень хорошо поддается распараллеливанию.
Первым подходом является распараллеливание отдельных шагов алгоритма: селекции и репликации, мутации, назначения рейтинга. При этом генофонд разделяется на блоки, над каждым из которых работает отдельный поток. Однако, такой подход не очень удобен в программировании, по сравнению с двумя другими.
При втором подходе, его еще называют островной моделью, заводят несколько независимых генофондов (островов) каждый из которых итерируют в отдельном потоке. Затем, каждые несколько итераций (допустим 5) устраивают «миграцию» - переселение ДНК между всем «островами». Стратегию переселения можно выбирать свободно: можно переселять чемпиона, можно — случайную ДНК (или несколько ДНК). Однако, стоит помнить, что слишком частые миграции, а так же миграции большого числа ДНК нивелируют со временем популяции на разных «островах»
Такой подход имеет неоспоримые преимущества. Во-первых, его легко воплотить программно, так как не требуются затраты на синхронизацию потоков. Во-вторых, на каждом «острове» можно использовать различные стратегии мутации, размножения и т.д, что приведет к более широкому охвату области возможных значений переменных и с большей вероятностью приведет к глобальному экстремуму, нежели к локальному.
Третий подход, является модификацией островной модели из расчета на массовый параллелизм. Его называют клеточной моделью. Такой подход можно использовать, когда речь идет о вычислениях в кластере. Суть клеточной модели в следующем: пусть у нас имеется множество процессоров (машин) расположим их логически в виде таблицы.
Каждая ячейка таблицы представляет собой один процессор. Каждый процессор итерируют отдельную популяцию, со своим набором стратегий размножения, мутации и т.д. По окончании определенного числа итераций происходят миграции между соседними ячейками таблицы.
Такой подход применим лишь на многоядерных машинах, либо в кластерах, так как на машинах с малым числом ядер возникнут большие накладные расходы, связанные с переключение контекста потока, что резко снизит эффективность параллельных вычислений.
Преимуществом клеточной модели перед островной является резкое снижение вероятности скатывания в локальный минимум, так как перемешивание происходит не между всеми популяциями, как в островной модели, а лишь между соседними, что снижает скорость выравнивания генофонда между популяциями. Градациями серого на рисунке выше приведен пример того, как могут распределиться популяции с различными генами (рейтингами чемпионов) в массиве.
Ссылки
Загрузка...