что такое генетические алгоритмы

Генетический алгоритм — наглядная реализация

Года четыре назад, в универе услышал о таком методе оптимизации, как генетический алгоритм. О нем везде сообщалось ровно два факта: он клёвый и он не работает. Вернее, работает, но медленно, ненадежно, и нигде его не стоит использовать. Зато он красиво может продемонстрировать механизмы эволюции. В этой статье я покажу красивый способ вживую посмотреть на процессы эволюции на примере работы этого простого метода. Нужно лишь немного математики, программирования и все это приправить воображением.

Кратко об алгоритме

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

Сама суть метода заключается в том, что мы модулируем эволюционный процесс: у нас есть какая-то популяция (набор векторов), которая размножается, на которую воздействуют мутации и производится естественный отбор на основании минимизации целевой функции. Рассмотрим подробнее эти процессы.

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

Для решения этой проблемы был введен механизм мутации, который заключается в случайном изменении каких-то особей. Этот механизм позволяет привнести что-то новое в генетическое разнообразие.
Следующий важный механизм — селекция. Как было сказано, селекция — отбор особей (можно из только родившихся, а можно из всех — практика показывает, что это не играет решающую роль), которые лучше минимизируют функцию. Обычно отбирают столько особей, сколько было до размножения, чтобы из эпохи в эпоху у нас было постоянное количество особей в популяции. Также принято отбирать «счастливчиков» — какое-то число особей, которые, возможно, плохо минимизируют функцию, но зато внесут разнообразия в последующие поколения.

Этих трех механизмов чаще всего недостаточно, чтобы минимизировать функцию. Так популяция вырождается — рано или поздно локальный минимум забивает своим значением всю популяцию. Когда такое происходит, проводят процесс, называемый встряской (в природе аналогии — глобальные катаклизмы), когда уничтожается почти вся популяция, и добавляются новые (случайные) особи.

Вот описание классического генетического алгоритма, он прост в реализации и есть место для фантазии и исследований.

Постановка задачи

Итак, когда я уже решил, что хочу попробовать реализовать этот легендарный (пусть и неудачливый) алгоритм, речь зашла о том, что же я буду минизимировать? Обычно берут какую-нибудь страшную многомерную функцию с синусами, косинусами и т.д. Но это не очень интересно и вообще не наглядно. Пришла одна незатейливая идея — для отображения многомерного вектора отлично подходит изображение, где значение отвечает за яркость. Таким образом, мы можем ввести простую функцию — расстояние до нашего целевого изображения, измеряемое в разности яркости пикселей. Для простоты и скорости я взял изображения с яркостью 0, либо 255.

С точки зрения математики такая оптимизация — сущий пустяк. График такой функции представляет собой огромную многомерную «яму» (как трехмерный парабалоид на рисунке), в которую неизбежно скатишься, если идти по градиенту. Единственный локальный минимум является глобальным. .

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

Реализация

Были реализованы все механизмы, описанные в первом параграфе. Размножение проводилось простым скрещиванием случайных пикселей от «мамы» и от «папы». Мутации производились путем изменения значения случайного пикселя у случайной особи на противоположное. А встряска производилась, если минимум не меняется на протяжении пяти шагов. Тогда производится «экстремальная мутация» — замена происходит более интенсивно, чем обычно.

В качестве исходных картинок я брал нонограмы («японские сканворды»), но, по правде говоря, можно брать просто черные квадраты — нет абсолютно никакой разницы. Ниже показаны результаты для нескольких изображений. Здесь для всех, кроме «домика», количество мутаций было 100 в среднем на каждую особь, особей в популяции было 100, при размножении популяция увеличивалась в 4 раза. Счастливчиков было 30% в каждой эпохе. Для домика значения были выбраны меньшие (30 особей в популяции, мутаций по 50 на особь).

Экспериментально я установил, что использование «счастливчиков» в селекции понижает скорость стремления популяции к минимуму, но зато помогает выбираться из стагнации — без «счастливчиков» стагнация будет постоянна. Что можно увидеть из графиков: левый график — развитие популяции «фараона» со счастливчиками, правый — без счастливчиков.

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

Глобальная оптимизация

Как было сказано, локальная оптимизация — задача довольно тривиальная, даже для многомерных случаев. Гораздо интересней посмтреть, как будет алгоритм справляться с глобальной оптимизацией. Но для этого нужно сначала построить функцию со множеством локальных минимумов. А это в нашем случае не так сложно. Достаточно брать минимум из расстояний до нескольких изображений (домик, динозаврик, рыбка, кораблик). Тогда первоначальный алгоритм будет «скатываться» в какую-то случайную ямку. И можно просто запускать его несколько раз.

Но есть более интересное решение данной проблемы: можно понять, что мы скатились в локальный минимум, сделать сильную встряску (или вообще инициировать особи заново), и в дальнейшем добавлять штрафы при приближении к известному минимуму. Как видно, картинки чередуются. Замечу, что мы не имеем права трогать исходную функцию. Но мы можем запоминать локальные минимумы и самостоятельно добавлять штрафы.

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

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

Более интересно, когда популяция не вымирает, а просто начинает подстрариваться под новые условия (след. рисунок). Это достигается при помощи штрафа в виде 0.000001 * sum ^ 4. В таком случае, новые образы становятся немного зашумлены:

Этот шум устраняется путем ограничения штрафа в max( 0.000001 * sum ^ 4, 20). Но мы видим, что четвертого локального минимума (динозавра) достичь не удается — скорее всего, потому, что он слишком близко расположен к какому-то другому.

Биологическая интерпретация

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

Важнейшую роль в эволюции Земли играли природные катаклизмы и массовые вымирания (вымирания динозавров, насекомых и т.д. — крупных всего было около десяти — см. диаграмму ниже). Это было подтверждено и нашим моделированием. А отбор «счастливчиков» показал, что самые слабые организмы на сегодня способны в будущем стать основой для последующих поколений.

Как говорится, все как в жизни. Этот метод «сделай эволюцию сам» наглядно показывает интересные механизмы и их роль в развитии. Конечно, существует много более стоящих эволюционных моделей (основанных, конечно, на дифурах), учитывающих больше факторов, более приближенные к жизни. Конечно, существуют более эффективные методы оптимизации.

Писал программу на Matlab (вернее, даже на Octave), потому что тут все — голимые матрицы, и есть инструменты для работы с картинками. Исходный код прилагается.

Источник

Генетические алгоритмы. От теории к практике

Добрый день. В последнее время решил заняться самообразованием. Решено было начать с генетических алгоритмов.

Одно из замечатльных свойств ГА это то, что процедуры Селекции, Скрещивания и Мутации представления не имеют о Индивидах в Поколениях — для них это всего-лишь 0 и 1. Единстенная функция, которая знает, что же из себя представляют эти самые 0 и 1 — это ФитнессФункция.

Поэтому я решил, что было бы неплохо написать класс-каркас для любого ГА. Об это и будет данная статья. Предполагается, что вы уже знакомы с основами генетических алгоритмов.

Кому интресно, прошу под кат.

Код будет написан на Java.

Несмотря на то, что мы пишем каркас, нам нобходимо его тестировать. Для этого я взял классическую NP-полную задачу — задачу коммивояжёра.

Немного об архитектуре приложения:

Для представления Генома(Индивида) будем использовать long[]. Мне почему-то показался этот вариант лучше чем boolean[].

Так же нам необходим интерфейс:

Разрабатываемый нами класс:

Так как мы пишем «универсальный» класс, необходимо, чтобы он поддреживал разные варианты скрещивания и селекции, поэтому были добавлены 2 перечисления (Enum):

… и некоторые приватные поля:

Для них есть сеттеры и геттеры.

А теперь о всем по порядку…

Генерация первого поколения.

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

Селекция.

Несколько замечаний «от себя»:

Скрещивание.

Несколько замечаний «от себя»:

*Для функция скрещивания и мутации я использовал бинарные операции. Поэтому пришлось объявить несколько статических перменных.

Функция для скрещивания двух геномов:
(Приведн код только для Поэлементное Скрещивание)

Пояснения:
Чтобы обменять между собой числа a и b необходимо:
swapMask = a xor b;
a = a xor swapMask;
b = b xor swapMask;

А если на swapMask мы наложим (and) mask, то у a и b поменяются только те биты, которые == 1 в числе mask.

swapMask = (a xor b) and mask;
a = a xor swapMask;
b = b xor swapMask;

Мутация.

Чтобы инвертировать бит необходимо:
bit = bit xor 1;
Следовательно, чтобы инвертировать любой бит в числе необходимо сдвинуть единицу на нужную позицию.

И основная функция, которая связывает все предыдущие:

Применение.

Использовать это все достаточно просто:
Сначала нужно описать класс ФитнессФункции.
А дальше…

Вернемся к задаче коммивояжёра.

Так как растояние между городами заполнялось рандомом «random.nextInt(256)». То смею предположить, что среднее расстояние между 2 городами = 128. => Средняя длина маршрута по всем городам = 128*256=32768. (! могу ошибаться).

ГА находит путь = 10000-12000 за 6-7 сек. Что в 3 раза лучше Среднего.

5500-7000 за минуту.

Код работает около 15 часов. и находит маршрут = 3500-4000.

Куда расти дальше.

UPD2:LeoCcoder нашел ошибку в Рулетке(в бинарном поиске). Исправлено.

Источник

Выращиваем ИИ — Генетические алгоритмы: введение

(сгенерированое изображение)

Существует множество способов создать искусственную нейронную сеть или даже «искусственный интеллект». Но все эти способы обескураживают, от части сложностью которую я не до конца понимаю, отчасти от того, что все сводится к математическим формулам.

В таких подходах нет нечего плохого, они помогают решать поставленные перед ними задачи. Но похоже мне очень хочется написать велосипед.

Зачем, что и почему?

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

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

Нейронная клетка в мозгу +- нечем не отличается от других клеток. Зачастую многие ставят под вопрос, то как передаются сигналы от нейрона к нейрону? Но как по мне, куда более важный вопрос — как формируется нейронная сеть? Как один нейрон находит другой «нужный нейрон»?

Этот вопрос до конца не изучен Axon guidance.

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

Что влияет на выбор пути:

Нетрины
Эфрины и Eph-рецепторы
Семафорины
Рецепторы: плексины, интегрины, нейропилины;
Участники сигнальной цепочки: CRMP-семейство (CRMP1, CRMP2, CRMP3, CRMP4, CRMP5)

Аксон, как правило, находит только один другой нейрон. Но дендритам одного нейрона могут посылать свои сигналы несколько аксонов. Не редки случаи когда от аксона идет несколько ответвлений.

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

(Генерация поверх изображения)

(Напечатанная на 3д принтере оптическая нейронная сеть — работает за счет света)

Я долго искал как, пытался физически располагать нейроны в координатах и соединять их, рисовать рандомные деревья, представляя, что это дендриты, в общем пытался найти в хаосе хоть какой-то смысл.

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

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

Генетические алгоритмы

Сегодня мы рассмотрим базис генетических алгоритмов и напишем простенькую программку.

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

Начнем с традиционного компьютерного генетического алгоритма. Этот алгоритм был разработан для решения задач, в которых пространство решения настолько велико, что алгоритм «грубой силы» просто занял бы слишком много времени. Например: я думаю о числе. Число от одного до одного миллиарда. Сколько времени вам потребуется, чтобы угадать это? Решение проблемы с помощью «грубой силы» относится к процессу проверки каждого возможного решения. Это один? Это два? Это три? Это четыре? И так, и так далее. Хотя удача играет здесь важную роль, с грубой силой мы будем ожидаем годы, пока вы сосчитаете до одного миллиарда. Однако что, если бы я мог сказать вам, был ли ваш ответ хорошим или плохим? Тепло или холодно? Жарко? Супер, супер холодно? Если бы вы могли оценить, насколько «подходит» предположение, вы могли бы выбрать другие числа ближе к этому предположению и быстрее найти ответ. Ваш ответ может развиваться.

Почему генетические алгоритмы?

Хотя компьютерное моделирование эволюционных процессов восходит к 1950-м годам, большая часть того, что мы сегодня называем генетическими алгоритмами (также известными как «GA»), была разработана Джоном Холландом, профессором Мичиганского университета, чья книга Adaptation in Natural and Artificial Systems была первая в исследованиях GA. Сегодня все больше генетических алгоритмов являются частью более широкой области исследований, часто называемой «Эволюционные вычисления».

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

«Теорема о бесконечной обезьяне» сформулирована следующим образом: Обезьяна, случайно нажимающая клавиши на пишущей машинке, в конечном итоге напечатает все произведения Шекспира (учитывая бесконечное количество времени). Проблема этой теории заключается в том, что вероятность того, что указанная обезьяна действительно напечатала Шекспира, настолько мала, что даже если бы эта обезьяна начинала с Большого взрыва, маловероятно, что у нас будет Гамлет к текущему моменту.

Давайте рассмотрим обезьяну по имени Вова. Вова печатает на уменьшенной пишущей машинке, содержащей только двадцать семь символов: двадцать шесть букв и один пробел. Таким образом, вероятность попадания Вовы в любой заданный ключ — одна из двадцати семи.

Давайте рассмотрим фразу «to be or not to be that is the question» (мы упрощаем его от оригинала «to be or not to be: that is the question»). Фраза длиной 39 символов. Если Вова начинает печатать, вероятность того, что он напечатает первый символ правильно — равна 1 к 27. Первых два символа — 1 к 27 * 27. Следовательно, вероятность того, что Вова напишет полную фразу:

Что равно 1 к 66,555,937,033,867,822,607,895,549,241,096,482,953,017,615,834,735,226,163.

Даже если Вова — сможет печатать миллион случайных фраз в секунду, ему пришлось бы печатать в течение 9 719 096 182 010 563 073 122 (253 593 605 017 лет). (Возраст Вселенной составляет всего 13 750 000 000 лет.)

Смысл всех этих непостижимо больших чисел не в том, чтобы озадачить вас, а в том, чтобы продемонстрировать, что алгоритм грубой силы (перебор каждой случайной фразы) не является разумной стратегией для набора «to be or not to be that is the question». Нам помогут генетические алгоритмы.

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

Естественный отбор Дарвина

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

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

Вариативность (разнообразие).

Должно быть некоторое разнообразие в популяции, или что-то, что его привносит. Например, скажем, есть популяция жуков, в которой все жуки абсолютно одинаковы: одного цвета, одинакового размера, того же размаха крыльев, одинакового всего. Без какого-либо разнообразия в популяции дети всегда будут идентичны родителям и друг другу. Новые комбинации черт никогда не возникнут, и ничто не развивается.

Селекция (выборка). Должен существовать механизм, с помощью которого некоторые представители населения имеют возможность быть родителями и передавать свою генетическую информацию. Обычно это называют «выживанием наиболее приспособленных». Например, популяцию газелей, каждый день гоняют львы. Более быстрые газели с большей вероятностью избегают львов и, следовательно, с большей вероятностью живут дольше, имея возможность размножаться и передавать свои гены детям. Однако термин «наиболее подходящий» может вводить в заблуждение. Как правило, мы ассоциируем это с больше, быстрее или сильнее. В некоторых случаях, это правда, но естественный отбор основывается на том принципе, что некоторые черты лучше приспособлены к среде обитания и следовательно, от них зависит вероятность выживания и размножения. Это не имеет ничего общего с тем, что данное существо «лучше» (в конце концов, это субъективный термин) или более «физически развит». В случае печатающих обезьян более крутая обезьяна — это та, которая набрала фразу ближе к «to be or not to be».

Генетические алгоритмы — создание популяции

В рамках решения задачи о пишущих обезьянах, мы не будем создавать больше обезьян по имени Вова, одного вполне достаточно. Вместо этого, мы сформируем популяцию фраз (коллекцию строк). На этом этапе мы реализуем принцип разнообразия. Допустим наша задача получить строку cat с помощью эволюции и у нас популяция следующего вида:
hug
rid
won

Конечно, в этих трех фразах есть разнообразие, но как не миксуй, получить кошку не получится. Здесь недостаточно разнообразия, чтобы найти оптимальное решение. Однако, если бы мы имели популяцию из тысяч фраз, все полученные случайным образом, то есть вероятность, что по крайней мере один вариант в популяции будет иметь символ «c» в качестве первого символа, один будет иметь «a» в качестве второго, а один «a» в качестве третьего. Большая часть населения, скорее всего, даст нам достаточно разнообразия, чтобы сгенерировать нужную фразу (чуть позже мы введем еще один механизм для регулирования разнообразия).

Таким образом, первый шаг — создание случайной популяции.

Генотип и Фенотип

Данные которыми мы оперируем, передаем из поколения в поколение, являются генотипом. Фенотипом же является представлением этих данных.

(код цвета (генотип) и сам цвет (фенотип))

(длина (генотип) и линия(фенотип))

То каким образом записывать данные и представлять их зависит от конкретной задачи. В нашем случае, с текстом от обезьянок, особой разницы между генотипом и фенотипом нет. Разве, что мы можем записать символ в виде его ANSI кода в произвольный массив с названием genes.
Наша начальная популяция будет состоять из генерированных случайным образом генотипов — генов — ДНК. Тут уж я не биолог, +- в рамках того, что мы делаем это все одно и то же.

Генетические алгоритмы — селекция

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

В нашем случае мы можем разбить селекцию на две части.

1. Оценка пригодности

Пригодность, приспособленность, годность, соответствие. Я черпаю информацию из англ источников и там это называется fitness, от fit.

Для правильного функционирования нашего генетического алгоритма нам необходима так называемая функция пригодности (Fitness function). Функция производит числовую оценку, для определения пригодности конкретного индивидуума. В реальном мире, существа просто выживают или нет. Но в случае традиционного генетического алгоритма, где мы пытаемся выработать оптимальное решение проблемы, мы должны иметь возможность дать численную оценку.

В случае с нашей задачей, мы должны оценивать правильность слов. Например для cat наиболее подходящий вариант будет car:

2. Тиндер (пул спаривания)

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

Здесь можно использовать несколько разных подходов. Например, мы могли бы использовать так называемый элитарный метод: «Какие два члена населения набрали наибольшее количество баллов? Вы двое сделаете всех детей для следующего поколения».

Это один из самых простых подходов, но в таком случае мы потеряем разнообразие. Если два члена населения (из возможно тысяч) являются единственными доступными для размножения, у следующего поколения будет мало разнообразия, и это может замедлить эволюционный процесс. Так же мы могли бы взять половину популяции, например первые 500 из 1000. Это также очень просто сделать, но такой подход не даст оптимальных результатов. В этом случае у элементов с высокими показателями будет такой же шанс быть выбранным в качестве родителя, как и у средних. И почему обезьянка номер 500 имеет возможность воспроизведения, а номер 501 уже нет?

Лучшее решение для нашего тиндера будет использование вероятностного метода, который мы назовем «колесом фортуны» (также известным как «рулетка»). Чтобы проиллюстрировать этот метод, давайте рассмотрим простой пример, где у нас есть совокупность из пяти элементов, каждый из которых имеет оценку:

Наша рулетка будет выглядеть следующим образом:

Как мы видим, B имеет наибольший шанс. Но и самые маленькие, такие как C не лишены шанса вовсе. Частенько у элементов с низкой оценкой пригодности есть те необходимые и недостающие необходимые части. Например фраза «to be or not to be»:

A: to be or not to go
B: to be or not to pi
C: xxxxxxxxxxxxxxxxbe

А и B подходят больше всего, но C содержит необходимую концовку. Поэтому не стоит исключать такие элементы из выборки.

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

Генетические алгоритмы — репродукция

Заключительная часть генетического алгоритма которая отвечает за получение следующего поколения Вованов. Это поколение перестанет трогать кондиционер каждые 5ть минут. Так же состоит из двух этапов которые следует выделить:

1. Скрещивание (Crossover)

Скрещивание предполагает создание ребенка из генетического кода двух родителей. В случае с обезьянами, давайте предположим, что мы выбрали две фразы из пула спаривания.

Родитель A: FORK
Родитель B: PLAY

Теперь мы должны сделать из этих двоих дочернюю фразу. Возможно, самый очевидный способ (давайте назовем это методом 50/50) — это взять два первых символа из A и вторые два из B, оставив нам:

Для большего разнообразия мы можем поручить выбор середины случайности. В таком случае мы можем получить из одних и тех же родителей разные дочерние фразы:

Мы можем пойти дальше и случайным образом выбирать родителя каждого отдельно взятого символа:

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

2. Мутации

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

Мутация оценивается в процентах. Допустим мы получили FORY в результате скрещивания, если процент мутации составляет 1%, то это означает, что каждый символ в FORY имеет шанс в 1% быть изменённым другим случайным символом. Это достаточно маленький процент и в 96% случаях мутация не будет происходить. Но если вдруг, то выглядеть это будет следующим образом:

Большой процент мутации, может привести к деградации следующих популяции по отношению к нашему пониманию пригодности, мы не сможем гарантировать «похожесть» детей на родителей.

Давайте подведем итоги по нашему алгоритму и запишем его в виде псевдокода:

SETUP:

Шаг 1: Инициализация, создания случайной популяции из N элементов. Каждый элемент имеет случайную ДНК.

LOOP:

Шаг 2: Селекция, оцениваем каждый элемент популяции и формируем список потенциальных родителей.

Шаг 3: Репродукция. Повторяем N раз:

Шаг 4. Новая популяция заменяет текущую и повторяем Шаг 2.

Реализация генетического алгоритма

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

Зачастую в подобных вещах используется Python. У нас нет необходимости в специфических библиотеках, поэтому я используя привычный для себя JavaScript.

Если для вас JS не основной язык, думаю не составит труда по аналогии написать в любом другом. Для запуска мы будем использовать Node.js. В коде будет пометка о механизме адаптации, его я дописал, пока писал статью и его мы обсудим ниже. Без него все и так отлично работает 🙂

Для начала создадим основной класс DNA:

Класс DNA принимает длину фразы, которую хотим получить и набор ДНК, в том случае если это дочерний объект.

getRandomInt возвращает случайное число между 32 и 128 включительно. По факту это английский алфавит в ANSI коде.

DNA.js хранит символы в поле genes. Это своего рода генотип нашей фразы.

Класс популяции будет заниматься основной работой. Созданием популяции, селекции, скрещивания и мутации.

Инициализация популяции начинается с создания пустого массив размером в n, который мы передаем через конструктор. Далее на каждый элемент массива создается элемент популяции со своей случайной ДНК. Чуть ниже, сразу мы оцениванием всю популяцию на пригодность.

Мы пробегаем по фразе, и подбиваем среднее арифмитическое пригодности фразы. this.target хранится в виде фенотипа строкой. Конечно разумней сразу хранить в виде генотипа, но все для наглядности генетического алгоритма.

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

Скрещиваем двух родителей

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

Остается только провести мутацию:

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

Полный код класс популяции:

Прежде чем начать экспериментировать с нашим генетическим алгоритмом, необходимо обзавестись визуализацией. Обычно это не самая простая задача в машинном обучении, но в нашем случае все довольно просто. Так как это Node.js и заморачиваться с WebGL особо желания нет, пришлось поискать, что-то, что может работать со стандартным выводом — консолью.

К счастью существует такой вот инструмент blessed-contrib который позволяет создавать динамические дашборды.

Нас интересуют графики, их будет два. Один показывающий общую пригодность колонии, а второй количество верных результатов.

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

Тестирование

И так, давайте пробовать нашу поделку.

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

Данная функция создает новую популяцию и записывает статистику в массив. На основе этого массива, мы постоим графики.

sync делает необходимое количество поколений и отображает график. Асинхронный вариант может пригодиться, когда это занимает слишком много времени и хочется следить за процессом:

Результат выполнения кода выше:

Не самые удачные графики для статьи, вы их как нибудь увеличивайте в отдельной вкладке.

Как мы видим, практически сразу мы получаем 90% рост пригодности, который сохраняется на протяжении многих поколений и не подходит к 100% за счет процесса мутации.
Показатель Fintess 1, это количество 100% подходящих элементов в популяции. Есть некоторые скачки от 20 до 75 на поколение.

Давайте попробуем увеличить фразу. Hello Habr! слишком маленькая фраза и алгоритму она дается очень легко. To be or not to be:

Хороший результат, но правда первый запус дал всего один правильный ответ на 1000 поколений. Чем длинней фраза, тем возможно больше поколений необходимо для достижения правильного решения.

Увеличение количества поколений особо не влияет на результат:

Что если мы попробуем увеличить шанс мутации, с 0.1% до 1%?

При тех же остальных параметрах, результативность упала с 80% до 31-33%. Поколения слишком сильно мутируют и это не дает популяции развиваться в нужном направлении.

Адаптация

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

Если более короткие фразы дают быстре и хорошие результаты, быть может стоит бить более длинные фразы на мелкие? По мере роста процента пригодности популяции, мы будем стрессовать ее новыми данными.

И кстати это называется Адаптивные генетические алгоритмы. Полюбому стырили идею у меня.

В коде который я писал выше, уже есть возможность адаптивного подхода. Нужно лишь передать дополнительно 3 новых параметра: adaptive — использовать адаптивный подход, adaptiveThreshold — процент пригодности для удлинения фразы, cutLength — по сколько символов добавлять.

На графике отчетливо видно зубцы, это момент когда задавалась новая цель и пригодность популяции падала. В данном случае за 1000 поколений, мы не получили правильного решения. Остается только играться с параметрами, может натравить генетический алгоритм на генетический алгоритм для подбора нужных параметров?

Заключение

Мы рассмотрели самый базис генетических алгоритмов на очень простом примере. Но даже тут есть много чего улучшить. Все те места где мы делаем генерацию случайных чисел можно заменить на методы Монте Карло которые так же используются для симуляции различных сложных процессов. Изменить алгоритм выбора родителей и механизм скрещивания двух разных ДНК. Сделать плавающий процент по ипотеке мутации, ведь иногда она полезна, а иногда мешает получить 100% результат.

Генетические алгоритмы способны решать более практические задачи, оптимизации, поиска.

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

Пример с умными ракетами:

Симуляция эволюции экосистемы:

(квадратики — еда)

И конечно же обучение нейронных сетей за счет генетических алгоритмов.

Источник