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

Цели обучения

Из этой статьи вы узнаете:

  • Основы генетических алгоритмов
  • Роль кроссовера и мутации в генетических алгоритмах
  • Природа и важность фитнес-функций
  • Сила различных факторов генетического алгоритма
  • Значение функционального языка программирования в подобной проблеме
  • Аспекты работы с последовательностями в F #

Обзор серии

Это шестая и последняя статья в серии о создании генетического алгоритма на F # и .NET Core. В то время как предыдущие статьи были учебными пособиями, здесь мы сосредоточимся меньше на коде и больше на дизайне в целом.

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

Если вам интересно узнать о F # или настольном приложении .NET Core, которое я использую для моделирования этого, ознакомьтесь с предыдущими статьями этой серии:

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

Весь код находится в свободном доступе через мой репозиторий GitHub.

Обзор приложения

В приложении участвуют белка, кролик, собака, желудь и дерево.

Собака остается неподвижной и убивает кролика или белку, если они входят рядом с ней.

Кролик перемещается по карте случайным образом.

Чтобы не умереть с голоду, белка должна забрать желудь и вернуться на свое дерево.

Все это реализовано просто и происходит на небольшой квадратной игровой сетке.

Приложение размещено в пользовательском интерфейсе WPF Core C #, который позволяет перейти к следующему поколению или визуализировать любой член текущего поколения. Этот пользовательский интерфейс взаимодействует с библиотекой классов F # .NET Standard, содержащей логику приложения.

Зачем ты это сделал?

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

  • "Подождите, вы строите что?"
  • «Зачем тебе это строить?»
  • «Что с тобой не так?»
  • "Чувак! Это круто!"

Короче говоря, я изначально создал это приложение еще в 2003 году. Я жил в сельской местности, и в этом районе было много белок. Я случайно читал о генетических алгоритмах, и одно привело к другому, и… да, я придумал очень неэффективное и неуклюжее приложение в Windows Forms.

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

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

Что такое генетический алгоритм?

Итак, что такое генетический алгоритм? Хотя я определил это более подробно в моей предыдущей статье, вот определение, которое я использую:

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

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

Гены конкретной белки-кандидата называются ее хромосомой.

Хромосома белки

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

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

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

Вот образец хромосомы белки, которая работает довольно хорошо:

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

Мы можем представить эту структуру на F # с помощью следующего кода:

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

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

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

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

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

Оценка плитки

Давайте посмотрим, как эта белка видит мир, на примере сценария.

Здесь белка оценивает 8 плиток вокруг себя, а также стоит ли ждать на своем текущем месте. Он делает это путем измерения соответствующих факторов этих плиток и определения важности каждого фактора.

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

Это можно визуализировать на тепловой карте следующим образом:

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

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

Настройка популяции и моделирования

Генетические алгоритмы задействуют не только один организм. Мы структурируем генетические алгоритмы с точки зрения более широкой популяции разнообразных сущностей. Это население меняется с течением времени в виде поколений.

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

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

Я обнаружил, что эта симуляция является наиболее управляемой из 10–25 белок, но отчасти это связано с простой природой проблемы.

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

Фитнес-функции

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

Моделирование будет запускать белку через серию поворотов, имитирующих ее время жизни. Если собака съедает белку, симуляция прекращается. Точно так же, если белка доберется до дерева с желудем, симуляция также остановится.

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

Фитнес-функции - одна из самых важных частей построения генетического алгоритма.

То, что вы измеряете, и то, как вы это измеряете, в корне определяет поведение алгоритма.

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

Подумайте о проблеме, связанной с отправлением корабля из Нью-Йорка в Европу. Вы не хотите давать очки только за первый корабль, достигший Европы, иначе вы никогда не вознаграждаете за черты, которые помогают приблизиться к решению. Вместо этого вы будете вознаграждены за то, что становитесь все ближе и ближе к Европе. Вы также хотите наказать суда, которые сели на мель или попали в Африку или Южную Америку.

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

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

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

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

Вот фитнес-функция, на которой я остановился:

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

Белки-мутанты - это решение!

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

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

Случайные хромосомы просты - мы просто создаем случайное значение для каждого гена в хромосоме следующим образом:

Я должен кратко указать здесь на некоторые из синтаксиса F #.

В строке 4 мы создаем последовательность из 7 новых элементов. Затем мы определяем функцию, чтобы определить, каким будет каждое из этих значений. В этом случае он вызывает getRandomGene, чтобы построить значение от -1 до 1.

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

Хорошо, это случайная хромосома - а что насчет детей?

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

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

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

Обратите внимание на использование Array.mapi2. Это функция F #, которая принимает два массива одинакового размера и выполняет итерацию по ним, позволяя запускать из них функцию, включая индекс двух элементов. Здесь наша функция просто проверяет, достигли ли мы точки пересечения.

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

Мутация довольно проста и зависит от функции Array.map, которая принимает входное значение (значение гена) и преобразует его в новое значение.

Также обратите внимание, что мы используем max и min, чтобы ограничить результаты диапазоном от -1 до 1.

Вот цифровая белка

Хорошо, хватит обсуждения - давайте посмотрим на результаты. Как белка поживала?

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

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

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

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

Мне сказали, что будут атакующие белки

Хорошо, а что с названием? Эти белки, кажется, заинтересованы только в выживании.

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

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

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

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

Вот где меня поразили генетические алгоритмы.

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

Взглянем:

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

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

Все это стало возможным благодаря этой фитнес-функции:

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

Уроки выучены

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

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

Хотя на этот раз я знал, что такое решение возможно, комбинация вещей помешала мне получить приложение, которое могло бы прийти к этому решению:

  • Я не давал генам белки определять, рядом ли плитка с кроликом или рядом с собакой.
  • В моей логике расчета расстояния была небольшая ошибка, из-за которой белка меньше внимания уделяла близлежащим объектам.
  • Функция фитнеса чрезмерно награждала белок, которые остались живы и ждали, когда кролики случайно наткнутся на собаку.

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

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

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

Кроме того, возможность объединять функции и составлять различные функции через частичное приложение на F # помогла мне повторно использовать или адаптировать небольшие кусочки отточенной и проверенной логики.

Следующие шаги

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

Если у вас есть дополнительные вопросы, оставьте комментарий или свяжитесь со мной.

Я также рекомендую вам поискать книги и видео по генетическим алгоритмам. У меня нет современного, чтобы порекомендовать его, но есть еще много чего интересного.

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

Первоначально опубликовано на https://killalldefects.com 16 ноября 2019 г.