UnicornGo.io
Join our telegram
Сегодня я хотел бы немного отойти в сторону от нашей основной темы и сделать этакое лирическое отступление в область генетики, математики и информатики. Так что прослушайте небольшой доклад про генетические алгоритмы. Генетические алгоритмы — это один из методов оптимизации, который позволяет найти глобальный экстремум функции в многофакторном пространстве тогда, когда входные данные можно выразить в виде «хромосомы». Впрочем, алгоритм не гарантирует точности и остановки в обозримое время. Зато он подсмотрен у природы. И потому сегодня генетические алгоритмы очень тщательно изучаются в рамках технологий Искусственного Интеллекта, особенно при рассмотрении многоагентных систем и гибридного ИИ. Так что приступим...
Генетический алгоритм состоит из следующих шагов:
Задавайте ваши вопросы. Готов отвечать.
Генетический алгоритм состоит из следующих шагов:
- Генерация начальной популяции. Это значит, что необходимо подготовить некоторое количество «начальных» значений в пространстве поиска, с которых алгоритм начнёт свою работу. Начать можно с произвольных значений, но если такие значения будут как можно более близки к целевому, то алгоритм отработает намного быстрее.
- Запуск цикличного процесса рождения новых поколений и отбора. Фактически, это и есть сам генетический алгоритм, который раз за разом запускает процесс порождения новых поколений, изучения новых особей и отбора наиболее интересных. Этот процесс состоит из следующих шагов и операций:
- Скрещивание (или перекрёст, англ. crossingover) — это операция, при которой берутся две особи текущего поколения, и их генотип перемешивается друг с другом. Чаще всего два генотипа разрезаются в одинаковом случайном месте, и после этого вторые части переставляются друг с другом. Так получаются два новых потомка. Фактически, скрещивание делается каждой особи с каждой, да ещё и по нескольку раз, чтобы разрезание генотипа происходило в разных местах. Так получается набор особей следующего поколения.
- Мутация — это операция по внесению случайных изменений в генотип потомства. С установленной частотой в каждый новый генотип после скрещивания вносятся случайные изменения. Если частота мутаций высокая, то наблюдается «подвижность» поиска, если же частота мутаций слишком низкая, то часто это приводит к «залипанию» алгоритма в локальном экстремуме, из которого он не может выбраться и, соответственно, остановиться. Величину частоты мутаций часто подбирают при помощи экспериментов для каждой конкретной задачи.
- Отбор — это операция по выбору наиболее приспособленных особей. Обычно выбирается какая-то доля (например, 10 %) тех особей нового поколения, для которых фитнесс-функция возвращает наилучшие результаты. Иногда в отобранное множество особей нового поколения добавляются наименее приспособленные особи, для которых фитнесс-функция возвращает наихудшие результаты. Это делается для получения генетического разнообразия и является инструментов борьбы с залипанием в локальных экстремумах. Также иногда в состав нового поколения включаются некоторые представители предыдущего поколения, которые в данном случае называются «элитой». Вообще, операция отбора также подбирается на основе экспериментов для каждой конкретной задачи.
- Возвращение результатов, которые привели к остановке цикла. Завершение алгоритма происходит тогда, когда фитнесс-функция для какой-либо особи находится в окрестности целевого значения с заданной точностью. Собственно, предикат проверки условия для остановки алгоритма проверяет для каждой особи значение фитнесс-функции, и если абсолютное значение разницы между ним и целевым значением меньше заданной точности, то предикат возвращает истину, и алгоритм останавливается. Необходимая точность является входным параметром алгоритма.
Задавайте ваши вопросы. Готов отвечать.
