Что такое генетический алгоритм
Генетический алгоритм vs алгоритм роя частиц
Введение
К задачам поиска лучшего варианта решения (объекта, параметров или других данных) сводятся многие из проблем математики, экономики, статистики и т.д. Эти проблемы возникают, когда приходится строить математическую модель ситуации. При обработке полученной математической модели не всегда является возможным перебрать все данные, предоставленные системой, поэтому возникает потребность в разработке таких алгоритмов, которые могли бы искать оптимальные данные с некоторыми погрешностями, чтобы ограничить зону обработки данных для поиска последующих лучших значений.
В данной статье под задачей оптимизации понимается нахождение экстремума (минимума) некоторой вещественной функции в заданной области. Будут рассмотрены два самых важных алгоритма в оптимизации: генетический алгоритм и алгоритм роя частиц.
Генетический алгоритм
Краткое описание
Первым алгоритмом оптимизации будет генетический алгоритм, который, в свою очередь, является одним из эволюционных алгоритмов, то есть в его основе лежат процессы отбора, мутации и комбинирования (скрещивания). Поскольку мы оптимизируем задачу поиска глобального экстремума функции, то стоит более подробно рассмотреть каждый шаг генетического алгоритма:
Каждая особь популяции будет обладать тремя основными параметрами: положением по оси Х, положением по оси У и значением целевой функции (именно это значение будет выступать в роли основного параметра при селекции).
На первом этапе происходит создание начальной популяции, где каждая особь случайным образом получает свои координаты по Х и У. Эта популяция может быть далека от идеала, но в процессе эволюции алгоритм должен будет исправить это.
Далее идет процесс размножения. Случайным образом выбирается пара родителей, которые производят потомков. Потомки должны наследовать черты родителей. Для того, чтобы не произошло доминирования со стороны одной особи, в размножении участвуют гены обоих родителей.
После размножения отбирается часть особей, которая подвергается случайным мутациям в генах. В случае с поиском экстремума будет меняться положение индивида по координатам Х и У.
В самом конце должен произойти отбор наиболее приспособленных особей. Особи с наименьшим показателем значения целевой функции проходят дальше. Для того, чтобы популяция не росла беспрерывно, её численность регулируется определенным заданным параметром.
Шаги “размножение”, “мутация” и “отбор” повторяются до тех пор, пока не будет достигнута точка Останова. В качестве конца алгоритма зачастую выбирают либо достижение максимального числа итераций алгоритма, либо ….
Иногда добавляют новые правила для изменения популяции, например, добавляют оператор инверсии (в случае с бинарными генами) или ограничивают время жизни каждой особи. Также добавляют условия на поиск пары для скрещивания, где оба родителя будут схожи по каким-либо признакам или наоборот, будут сильно отличаться.
Реализация
Для начала необходимо реализовать класс одной особи, в качестве параметров он будет принимать: пределы области поиска экстремума, количество шагов для мутации и целевую функцию, а также у индивида будет 2 поля, отвечающих за позицию по Х и У координатам, и поле, отвечающее за значение функции в текущей позиции:
Теперь реализуем функцию мутации в классе самой особи:
Теперь реализуем сам класс для исполнения алгоритма. В качестве параметров в класс будем передавать: размер популяции; процент популяции, который сможет воспроизводить потомство; количество шагов для мутации; шанс мутации особи; количество исполнений алгоритма (количество раз для появления нового потомства), целевую функцию, а также область поиска экстремума. Также в классе будут храниться: наилучшее значение целевой функции для всех итераций и точка (х, у),в которой было получено наилучшее значение:
Реализуем функцию кроссовера (скрещивания). Новые координаты по Х будут находиться случайным образом между координатами первого родителя и второго родителя по Х, аналогичным образом определяются координаты потомка по У:
Теперь можно приступать к написанию функции запуска самого генетического алгоритма (назовем её startGenetic в классе Genetic). Сначала необходимо создать стартовую популяцию нашей колонии:
В качестве конца алгоритма будем считать количество итераций, которые пережила колония. В каждой новой итерации сортируем популяцию в порядке убывания (для нахождения минимума функции) и выбираем ту часть популяции, которая будет принимать участие в размножении:
И для каждой особи находим случайную пару, с которой она сможет дать потомство:
Проводим мутации над каждой особью и отбираем наиболее приспособленных особей в новой популяции, содержащей детей:
И в конце каждой итерации проверяем лучшую особь в новой популяции на наилучшее значение целевой функции в течение всего времени:
На этом весь алгоритм можно считать завершенным. Запустим и проверим алгоритм на функции сферы (её минимум находится в точке 0,0):
Как видно, алгоритм смог найти минимум функции с точностью до 5 знаков после запятой, что является очень хорошим результатом.
Алгоритм роя частиц
Немного об алгоритме
Основная идея алгоритма роя частиц заключается в коллективном поведении некоторых агентов, которые могут взаимодействовать друг с другом и с окружающей средой для решения определенной задачи. Благодаря взаимодействию частиц получается успешно решать задачи.
При решении задачи нахождения экстремума функции каждая частица характеризуется тремя параметрами: координатами в пространстве и значением целевой функции. При этом на каждом шаге частицы помнят точку, где значение целевой функции было наилучшим, и пытаются туда вернуться. Каждая частица знает координаты лучшей точки, в которой была любая другая частица. Также на перемещение каждой влияет случайное отклонение и скорость.
В классической реализации алгоритма роя частиц для определения скорости частицы используется формула:
Однако для улучшения алгоритма можно использовать другие формулы, например
Реализация алгоритма
Первым делом реализуем класс роя, который на вход будет принимать размер роя, коэффициенты приоритетов смещения частиц к разным точкам, количество итераций алгоритма, целевую функцию и область поиска экстремума:
Также для реализации необходимо создать класс для одной частицы:
Реализуем логику для расчета новой позиции частицы:
Теперь создадим метод для реализации алгоритма в классе Swarm и протестируем:
Сравниваем алгоритмы
В википедии есть несколько функций, которые чаще всего используют для проверки алгоритмов оптимизации. Наиболее интересными, на мой взгляд, являются функции Химмельблау и Табличная функция Хольдера, так как они имеют несколько глобальных минимумов. Для того, чтобы посмотреть, как работает алгоритм, можно создать GIF при помощи библиотек matplotlib (для отрисовки графиков) и imageio (для создания GIF). Создадим обе функции:
Запустим по 2 раза каждый алгоритм с целевой функцией Хольдера. Первым проверим, как работает генетический алгоритм:
Посмотрим, как сходится алгоритм (для первого теста):
До первых 30 итераций все особи распределялись по первым найденным точкам минимума, но после этого все собираются в одной точке. Так как этот алгоритм подразумевает случайные изменения, то при каждом новом запуске программы в одной из 4х точек минимума может начать доминировать один ген и все будущие поколения будут сходиться в этой одной точке.
Давайте посмотрим, как сработает алгоритм роя частиц:
Посмотрим на сходимость роя частиц для теста №1:
В отличии от генетического алгоритма все частицы начали плавно перемещаться в одну точку. Посмотрим на более простой пример, как сходится генетический алгоритм для функции Экли (у этой функции один минимум в точке (0,0)):
И эта же функция с использованием роя частиц:
Генетический алгоритм хуже сходится в одну точку, так как каждую новую итерацию в случайной позиции (между родителями) появляется новая особь, а также случайные мутации, которые не всегда могут попадать в нужную точку. Рой частиц плавно приближался к найденному минимуму.
Вывод
Как итог было реализовано и протестировано, как работают два алгоритма оптимизации. Есть еще и другие алгоритмы, например, пчелиный алгоритм, алгоритм иммунной системы и другие. Каждый алгоритм имеет свои плюсы и минусы, некоторые быстрее сходятся в первой найденной точке, другие пытаются найти несколько минимумов и плавно приближаются к каждому из них. Зачастую используют смесь нескольких алгоритмов для того, чтобы избавить один из алгоритмов от имеющихся недочетов.
Играем с генетическими алгоритмами
Одним субботним декабрьским вечером сидел я над книгой The Blind Watchmaker (Слепой Часовщик), как на глаза мне попался невероятно интересный эксперимент: возьмём любое предложение, например Шекспировскую строку: Methinks it is like a weasel и случайную строку такой же длины: wdltmnlt dtjbkwirzrezlmqco p и начнем вносить в неё случайные изменения. Через сколько поколений эта случайная строка превратится в Шекспировскую строку, если выживать будут лишь потомки более похожие на Шекспировскую?
Сегодня мы повторим этот эксперимент, но в уже совершенно другом масштабе.
Что такое генетический алгоритм
В области искусственного интеллекта под генетическим алгоритмом подразумевается эвристика поиска решений, основанная на естественном отборе. Как правило применяется для задач, где пространство поиска насколько огромно, что точное решение найти невозможно и эвристическое решение удовлетворяет требованиям. Сама задача имеет некоторую функцию качества решения, которую необходимо максимизировать.
В самом простом виде генетический алгоритм имеет следующую структуру (см. схему): начинаем с некоторым решением, в нашем случае, это случайная строка; вносим мутации, например, меняем случайно выбранную букву в строке на случайно выбранную букву и получаем новый набор строк (k мутаций на строку); из них отбираем только те, которые ближе к шекспировской (по количеству совпадающих символом), например 10 таких строк, если шекспировской среди них нет, то запускаем процесс заново.
Почему это работает
Во многом генетические алгоритмы похожи на классические методы оптимизации, популяция — это набор текущих точек, мутации — это исследование соседних точек, отбор — это выбор новых точек для поиска решения в условиях ограниченных вычислительных ресурсов.
Популяция всегда стремится к ближайшему максимуму, так как мы отбираем текущие точки поиска, как имеющие максимальное значение (все остальные точки «умрут», не выдержат конкуренции с ближайшим максимумом). Так как размер популяции значительный, а значит вероятность сделать хотя бы один шаг в направлении максимума не пренебрежимо мала, то через некоторое количество шагов популяция сместится в сторону локального максимума. А потомки точки, смещенной ближе к максимуму, имеют большую «выживаемость». Значит через достаточное количество шагов, потомки этой точки начнут доминировать в популяции и вся она сместится к максимуму.
Визуализация популяции стремящейся к локальному максимуму:
(due to Randy Olson)
Формализуем задачу со случайной строкой
Входные данные: строка S
Выходные данные: натуральное число N, равное количеству поколений необходимых для преобразования случайной строки длины len(S) в строку S
Что в нашем случае мутация? Под мутацией строки S мы понимаем замену одного случайно выбранного символа из строки S на другой произвольный символ алфавита. В данной задаче мы используем только символы нижнего регистра латиницы и пробел.
Что такое изначальная популяция (initial population в схеме)? Это случайная строка равная по длине входной строке S.
Что такое потомки (offsprings)? Пусть мы зафиксировали количество мутаций одной строки на константу k, тогда потомки — это k мутаций каждой строки текущего поколения.
Что такое выжившие (survivors)? Пусть мы зафиксировали размер популяции на константу h, тогда выжившие — это h строк максимально похожих на входную строку S.
В псевдокоде (подозрительно похожем на python) это выглядит следующим образом:
Пример работы алгоритма
Рассмотрим следующую строку: The quick brown fox jumps over the lazy dog и воспроизведём для неё вывод нашей программы:
Рассмотрим цепочку изменений (слева номер поколения):
Как мы видим каждое поколение отличается не более, чем на один символ друг от друга. Всего потребовалось 46 поколений, чтобы добраться от rbbzmffwfhwtxnjjiozz ujhhlxeoyhezarquvmopyk до the quick brown fox jumps over the lazy dog с помощью мутаций и отбора.
Эксперименты с классикой
Отдельные примеры, шекспировской строка или английская панграмма про лису, интересны, но не слишком убедительны. Поэтому и решил рассмотреть более интересный вопрос: что будет если взять пару классических произведений, разбить их на предложения и посчитать число поколений для каждого из них? Какой будет характер зависимости количества поколений от строки (например, от её длины)?
В качестве классических произведений выбрал To Kill a Mocking Bird by Harper Lee (Убить Пересмешника, Харпер Ли) и Catcher in the Rye by J.D. Salinger (Над Пропастью во Ржи, Джей Ди Сэлинджер). Мы будем измерять два параметра — распределение количества поколений по предложениям и зависимость количества поколений от длины строки (есть ли корреляция?).
Параметры были следующие: количество потомков у строки: 100; количество выживших в поколении: 10.
Результаты
Как мы видим, для большинства предложений получилось достичь строку достаточно быстро, требуются менее 100 итераций, практически для всех предложений достаточно 200 итераций (среди всех предложений было только одно, которому потребовалось 1135 итераций, судя по предложению алгоритм разбивки ошибся и склеил несколько предложений в одно):
Корреляция между длиной строки и количеством поколений идеальная. Это означает, что практически в каждом поколении удавалось продвинуться на шаг ближе к целевой строке.
R^2 равен 0.996 и 0.997 соответственно.
Таким образом экспериментально установили, что в условиях нашей задачи для любой входной строки S, количество поколений линейно зависит от длины строки, что согласуется с исходными предположениями.
Код и данные
Весь код, python — генетический алгоритм\обработка текста и R — визуализация, доступен в github:
github.com/SergeyParamonov/genetics-experiments
Выводы
Мы разобрались с базовой структурой генетических алгоритмов и применили для решения задачи о мутации строки. В результате экспериментов с классическими текстами мы обнаружили, что в наших условиях существуют линейная зависимость между длиной строки и количеством поколений необходимых для достижения входной строки.
Так же мы отметили, что базовая структура поиска может быть модифицирована (например, с помощью сrossover — использования несколько членов поколения для создания потомков) для решения широкого класса задач оптимизации, где слишком сложно искать точное решение.
Что такое генетические алгоритмы
Естественный отбор
Процесс естественного отбора начинается с выбора сильных особей из популяции. Их потомство наследует характеристики родителей и является частью следующего поколения особей. Если оба родителя сильные, то их потомство будет сильнее родителей.
Это итеративный процесс и завершается, когда найдены наиболее сильные особи. Эта идея применяется для задачи поиска. Рассматривается набор решений для проблемы и отбирается набор лучших из них.
5 шагов генетического алгоритма
Процесс обучения генетического алгоритма делится на 5 этапов:
В генетическом алгоритме набор генов особи представлен в виде бинарной строки. Закодированная комбинация генов называется хромосомой.
Популяция, хромосомы и гены
Функция силы
Функция силы определяет, насколько сильна отдельная особь. Сила определяется как способность особи конкурировать с остальными особями по заданной метрике. Функция присваивает каждой особи уровень силы. Вероятность того, что особь будет выбрана для произведения следующей популяции, основывается на уровне силы особи.
Отбор
Идея отбора заключается в том, чтобы отобрать наиболее сильных особей и передать их гены следующему поколению особей. N пар особей (родители) отбирается на основании их силы.
Скрещивание
Скрещивание — это основная часть генетического алгоритма. Для каждой пары родителей. Рандомно выбирается точка в бинарной строке хромосомы, до которой особи обмениваются генами. После этого модифицированные особи называются потомством.
Точка скрещивания
Потомство создается через процесс обмена генами родителей до случайно заданной позиции в строке. Ниже можно увидеть, как родители обмениваются генами, когда точка скрещивания = 3.
После обмена генами между родителями потомство добавляется в новую популяцию.
Мутация
Какая-то часть генов будет маловероятной. Чтобы поддерживать разнообразие популяции, отдельно прописывается процесс мутации новых особей.
Пример мутации особи
Завершение алгоритма
Алгоритм завершает работу, когда популяция сошлась, то есть не производит потомство, которое значительно отличается от предыдущего поколения. Когда алгоритм сошелся, на выходе получается набор оптимальных решений заданной проблемы.
Псевдокод процесса обучения генетического алгоритма:
Генетические алгоритмы в глубоком обучении
Генетический алгоритм — наглядная реализация
Года четыре назад, в универе услышал о таком методе оптимизации, как генетический алгоритм. О нем везде сообщалось ровно два факта: он клёвый и он не работает. Вернее, работает, но медленно, ненадежно, и нигде его не стоит использовать. Зато он красиво может продемонстрировать механизмы эволюции. В этой статье я покажу красивый способ вживую посмотреть на процессы эволюции на примере работы этого простого метода. Нужно лишь немного математики, программирования и все это приправить воображением.
Кратко об алгоритме
Итак, что же такое генетический алгоритм? Это, прежде всего, метод многомерной оптимизации, т.е. метод поиска минимума многомерной функции. Потенциально этот метод можно использовать для глобальной оптимизации, но с этим возникают сложности, опишу их позднее.
Сама суть метода заключается в том, что мы модулируем эволюционный процесс: у нас есть какая-то популяция (набор векторов), которая размножается, на которую воздействуют мутации и производится естественный отбор на основании минимизации целевой функции. Рассмотрим подробнее эти процессы.
Итак, прежде всего наша популяция должна размножаться. Основной принцип размножения — потомок похож на своих родителей. Т.е. мы должны задать какой-то механизм наследования. И лучше будет, если он будет включать элемент случайности. Но скорость развития таких систем очень низкая — разнообразие генетическое падает, популяция вырождается. Т.е. значение функции перестает минимизироваться.
Для решения этой проблемы был введен механизм мутации, который заключается в случайном изменении каких-то особей. Этот механизм позволяет привнести что-то новое в генетическое разнообразие.
Следующий важный механизм — селекция. Как было сказано, селекция — отбор особей (можно из только родившихся, а можно из всех — практика показывает, что это не играет решающую роль), которые лучше минимизируют функцию. Обычно отбирают столько особей, сколько было до размножения, чтобы из эпохи в эпоху у нас было постоянное количество особей в популяции. Также принято отбирать «счастливчиков» — какое-то число особей, которые, возможно, плохо минимизируют функцию, но зато внесут разнообразия в последующие поколения.
Этих трех механизмов чаще всего недостаточно, чтобы минимизировать функцию. Так популяция вырождается — рано или поздно локальный минимум забивает своим значением всю популяцию. Когда такое происходит, проводят процесс, называемый встряской (в природе аналогии — глобальные катаклизмы), когда уничтожается почти вся популяция, и добавляются новые (случайные) особи.
Вот описание классического генетического алгоритма, он прост в реализации и есть место для фантазии и исследований.
Постановка задачи
Итак, когда я уже решил, что хочу попробовать реализовать этот легендарный (пусть и неудачливый) алгоритм, речь зашла о том, что же я буду минизимировать? Обычно берут какую-нибудь страшную многомерную функцию с синусами, косинусами и т.д. Но это не очень интересно и вообще не наглядно. Пришла одна незатейливая идея — для отображения многомерного вектора отлично подходит изображение, где значение отвечает за яркость. Таким образом, мы можем ввести простую функцию — расстояние до нашего целевого изображения, измеряемое в разности яркости пикселей. Для простоты и скорости я взял изображения с яркостью 0, либо 255.
С точки зрения математики такая оптимизация — сущий пустяк. График такой функции представляет собой огромную многомерную «яму» (как трехмерный парабалоид на рисунке), в которую неизбежно скатишься, если идти по градиенту. Единственный локальный минимум является глобальным. .
Проблема только в том, что уже близко к минимуму количество путей, по которым можно спуститься вниз сильно сокращается, а всего у нас столько направлений, сколько измерений (т.е. количество пикселей). Очевидно, что решать эту задачу при помощи генетического алгоритма не стоит, но мы можем посмотреть на интересные процессы, протекающие в нашей популяции.
Реализация
Были реализованы все механизмы, описанные в первом параграфе. Размножение проводилось простым скрещиванием случайных пикселей от «мамы» и от «папы». Мутации производились путем изменения значения случайного пикселя у случайной особи на противоположное. А встряска производилась, если минимум не меняется на протяжении пяти шагов. Тогда производится «экстремальная мутация» — замена происходит более интенсивно, чем обычно.
В качестве исходных картинок я брал нонограмы («японские сканворды»), но, по правде говоря, можно брать просто черные квадраты — нет абсолютно никакой разницы. Ниже показаны результаты для нескольких изображений. Здесь для всех, кроме «домика», количество мутаций было 100 в среднем на каждую особь, особей в популяции было 100, при размножении популяция увеличивалась в 4 раза. Счастливчиков было 30% в каждой эпохе. Для домика значения были выбраны меньшие (30 особей в популяции, мутаций по 50 на особь).
Экспериментально я установил, что использование «счастливчиков» в селекции понижает скорость стремления популяции к минимуму, но зато помогает выбираться из стагнации — без «счастливчиков» стагнация будет постоянна. Что можно увидеть из графиков: левый график — развитие популяции «фараона» со счастливчиками, правый — без счастливчиков.
Таким образом, мы видим, что этот алгоритм позволяет решить поставленную задачу, пусть и за очень долгое время. Слишком большое количество встрясок, в случае больших изображений, может решить большее количество особей в популяции. Оптимальный подбор параметров для разных размерностей я оставляю за рамками данного поста.
Глобальная оптимизация
Как было сказано, локальная оптимизация — задача довольно тривиальная, даже для многомерных случаев. Гораздо интересней посмтреть, как будет алгоритм справляться с глобальной оптимизацией. Но для этого нужно сначала построить функцию со множеством локальных минимумов. А это в нашем случае не так сложно. Достаточно брать минимум из расстояний до нескольких изображений (домик, динозаврик, рыбка, кораблик). Тогда первоначальный алгоритм будет «скатываться» в какую-то случайную ямку. И можно просто запускать его несколько раз.
Но есть более интересное решение данной проблемы: можно понять, что мы скатились в локальный минимум, сделать сильную встряску (или вообще инициировать особи заново), и в дальнейшем добавлять штрафы при приближении к известному минимуму. Как видно, картинки чередуются. Замечу, что мы не имеем права трогать исходную функцию. Но мы можем запоминать локальные минимумы и самостоятельно добавлять штрафы.
На этой картинке изображен результат, когда при достижении локального минимума (сильная стагнация), популяция просто вымирает.
Здесь популяция вымирает, и добавляется небольшой штраф (в размере обычного расстояния до известного минимума). Это сильно снижает вероятность повторов.
Более интересно, когда популяция не вымирает, а просто начинает подстрариваться под новые условия (след. рисунок). Это достигается при помощи штрафа в виде 0.000001 * sum ^ 4. В таком случае, новые образы становятся немного зашумлены:
Этот шум устраняется путем ограничения штрафа в max( 0.000001 * sum ^ 4, 20). Но мы видим, что четвертого локального минимума (динозавра) достичь не удается — скорее всего, потому, что он слишком близко расположен к какому-то другому.
Биологическая интерпретация
Какие же выводы мы можем сделать из, не побоюсь этого слова, моделирования? Прежде всего, мы видим, половое размножение — важнейший двигатель развития и приспосабливаемости. Но только его не достаточно. Роль случайных, маленьких изменений чрезвычайна важна. Именно они обеспечивают возникновение новых видов животных в процессе эволюции, а у нас обеспечивает разнообразие популяции.
Важнейшую роль в эволюции Земли играли природные катаклизмы и массовые вымирания (вымирания динозавров, насекомых и т.д. — крупных всего было около десяти — см. диаграмму ниже). Это было подтверждено и нашим моделированием. А отбор «счастливчиков» показал, что самые слабые организмы на сегодня способны в будущем стать основой для последующих поколений.
Как говорится, все как в жизни. Этот метод «сделай эволюцию сам» наглядно показывает интересные механизмы и их роль в развитии. Конечно, существует много более стоящих эволюционных моделей (основанных, конечно, на дифурах), учитывающих больше факторов, более приближенные к жизни. Конечно, существуют более эффективные методы оптимизации.
Писал программу на Matlab (вернее, даже на Octave), потому что тут все — голимые матрицы, и есть инструменты для работы с картинками. Исходный код прилагается.