Сегодня очень популярным трендом становится искусственный интеллект. Он развивается семимильными шагами и с каждыми годом находит всё больше применений в различных сферах. Каждый день можно увидеть публикации о новых научных достижениях в области ИИ. Он проник и в потребительскую сферу - ни для кого не секрет, что почти все современные гаджеты используют его в той или иной степени. Искусственный интеллект без преувеличения меняет наш мир.
Сегодня самым популярным методом ИИ является машинное обучение. По машинному обучению (в особенности по искусственным нейронным сетям) было опубликовано уже очень много материала в сети, и эта тема освещена довольно хорошо.
В этой статье мы посмотрим на альтернативный, менее популярный, но при этом очень интересный метод создания ИИ - генетические алгоритмы. Цель данной статьи преподнести вам идею без погружения в дискретную математику и программирование.
Основы основ
Давайте начнём с определения.
В узком смысле генетический алгоритм (ГА) - это один из методов создания искусственного интеллекта и, равно как и искусственные нейронные сети, лежит в основе биологического подхода к моделированию ИИ.
Это определение неточное, но нам пока подойдёт.
Давайте рассмотрим основные характеристики ГА:
1. Генетический алгоритм является эвристическим. В сущности, это означает, что он предназначен для поиска не лучшего, а оптимального решения, которое удовлетворяет условиям поставленной задачи.
2. Генетический алгоритм - это один из видов эволюционных алгоритмов, т.е. его механизм подобен механизму естественного отбора в природе. Иными словами, главный принцип эволюционных алгоритмов - борьба за выживание.
3. Отличительной особенностью генетического алгоритма от прочих эволюционных алгоритмов является акцент на оператор скрещивания. Подробнее чуть позже.
4. Генетический алгоритм относится к классу самообучающихся алгоритмов, т.е. он обладает способностью накапливать и преобразовывать информацию, что приближает его к методам машинного обучения - ещё одному подходу к моделированию ИИ, который базируется на последовательном обучении искусственного интеллекта, предлагая ему рассмотреть готовые решения множества схожих задач, а потом потренировать свои навыки на новых задачах, решения которых он заранее не знает.
Генетический алгоритм используется для решения задач оптимизации.
Главная цель ГА - используя исходное конечное множество неоптимальных решений получить новое множество оптимальных решений путём применения определённых операторов ГА (об операторах ГА далее).
Простыми словами, ГА служит для генерации наиболее оптимальных решений задач или проблем на основе имеющейся информации.
Немножко истории
Основоположником генетических алгоритмов является Джон Холланд, который воспользовался исследованиями в области биологии и генетики, позаимствовав оттуда не только идею, но и терминологию, и адаптировал их под ЭВМ. Генетические алгоритмы получили свою популярность благодаря его книге «Адаптация в естественных и искусственных системах», которая вышла в свет в 1975 году.
Проводим аналогии и вычленяем суть
Итак, искусственная нейронная сеть (ИНС) - это модель человеческого мозга. А что же такое генетический алгоритм? Аналогично ГА - это модель естественной эволюции в природе.
Теперь давайте проведём параллели между генетикой как разделом биологии и генетическим алгоритмом в IT.
Многие понятия в теории ГА имеют аналоги в генетики:
◦ Особь - одно решение задачи.
◦ Приспособленность особи - качество/оптимальность решения.
◦ Популяция - множество решений задачи.
◦ Поколение - новая итерация (этап) цикла генетического алгоритма.
◦ Эволюция - чередование поколений, из которых каждое следующее, в идеальном случае, отличается лучшей приспособленностью по сравнению с предыдущим.
Кроме того, в теории ГА имеются операторы ГА, которым также легко найти пару в генетике:
◦ Оператор Кроссинговер (кроссовер) - скрещивание особей. Ещё ГА-синоним - рекомбинация решений.
◦ Оператор Мутация - случайное изменение признаков особи. Ещё ГА-синоним - вариация решений.
◦ Оператор Селекция - отбор особей с наилучшей приспособленностью (иными словами, отбор самых оптимальных решений).
◦ Оператор Наследование - приобретение потомком определённых признаков от родителей (родительских решений). Реализация биологического понятия "изменчивость".
По аналогии с живой природой, где выживают только сильнейшие в борьбе за природные ресурсы, в генетическом алгоритме выживают только самые оптимальные решения, и только они получают возможность воспроизводить потомство (новые решения) путём перекрёстного скрещивания двух родителей. В результате появляются новые особи (решения) с признаками обоих родителей. Слабейшие особи вымирают, сильнейшие оставляют новое потомство. Так отсеиваются худшие признаки, а лучшие распространяются по всей популяции. Иногда происходят случайные изменения, которые называются мутациями. Они тоже важны, т.к. иногда спасают популяцию от вымирания. Каждое новое поколение, в идеале, превосходит предыдущее, поскольку "молодняк" перенимает только лучшее от родителей. В конце концов, образуется популяция, приводящая к наиболее оптимальному решению задачи.
Но по какому же принципу определяется самое оптимальное решение? В природе всё понятно - кто добыл пропитание и не откинул при этом ласты, тот и победитель, бери и размножайся - а тут как?
В ГА для определения "победителей" - самых оптимальных решений - используется т.н. функция приспособленности (или попросту целевая функция) - это математическая функция, которая рассчитывает "живучесть" каждой особи (оптимальность каждого решения) и служит для определения самых лучших.
Существуют и другие термины, используемые в теории генетических алгоритмов (например, гены, хромосомы, инверсия), но в рамках вводной статьи их рассмотрение приведёт лишь к путанице, поэтому мы их опустим. Но даже используя эти термины мы можем сделать предположения о механизме работы ГА.
Как это работает?
Теперь мы готовы, поэтому плавно перетекаем к механизму работы ГА.
Генетический алгоритм состоит из пяти шагов (не путать с этапами, этап - это новый виток цикла). 2-4 шаги представляют собой цикл. Количество шагов может отличаться от приведённого здесь в зависимости от интерпретации, однако самое главное - цикл обязательно включает оператор скрещивание и/или оператор мутация и оператор селекция. Итак...
Первый шаг - создание начальной популяции. Сперва нужно случайным образом создать начальную популяцию, т.е. начальный набор решений задачи. Она может быть совершенно неконкурентоспособна (решения могут быть неоптимальными) - это не важно, главное, чтобы особи соответствовали определённому формату. В дальнейшем генетический алгоритм, вполне вероятно, приведёт популяцию в жизнеспособное состояние.
Второй шаг - скрещивание (размножение) и/или мутация.
Скрещивание (размножение). Чтобы получить потомка (новое решение задачи) требуется два родителя (т.е. два уже существующих решения), которые обычно выбираются случайным образом. Обязательным условием является то, что потомок должен унаследовать признаки обоих родителей.
Мутации. Мутации схожи с размножением. Только в отличие от размножения потомок (новое решение) изменяется некоторым необычным образом, приобретая случайные признаки, отсутствующие у обоих родителей. Мутации служат для поддержания разнообразия в популяции для возможности её дальнейшего развития и предотвращения вымирания популяции - всё как в живой природе. Вероятность мутации обычно относительно низкая.
Третий шаг - селекция (отбор). На шаге отбора из популяции выбирается та часть особей (решений), которая является наиболее жизнеприспособленной (оптимальной). На этом шаге для оценки особей используется рассмотренная ранее функция приспособленности.
Четвёртый шаг - формирование нового поколения. Этот шаг заключается в окончательном оформлении нового поколения (решений задачи), которое переходит на пятый заключительный шаг, но только в том случае, если это поколение является достаточно конкурентоспособным (решения удовлетворяют условиям задачи). В противном случае, цикл начинается заново со второго шага и повторяется до тех пор, пока не сформируется конкурентоспособное поколение. Каждый такой виток называется этапом.
Пятый шаг - получение результирующей популяции. На этот шаг популяция переходит только тогда, когда достигает решений (особей) такого качества, которое требовалось при создании алгоритма для решения задачи.
Обычно, ГА завершает работу при срабатывании одного из двух условий:
1. Превышено заданное количество итераций цикла ГА (количество итераций задаётся при создании модели)
2. Достигнуто требуемое качество решения (это означает успешное решение поставленной задачи)
Где применяются генетические алгоритмы
Следует отметить, что генетический алгоритм служит для решения многих задач IT, не только для создания ИИ. Вот несколько популярных примеров применения:
1. Оптимизация запросов в базах данных
2. Задачи на графах
3. Задачи компоновки
4. Составление расписаний
5. Игровые стратегии
6. Аппроксимация функций
и так далее.
Также ГА пересекаются с машинным обучением и иногда используются для моделирования ИНС (нейросетей).
А что насчёт практики?
Теперь, когда вам понятна суть генетических алгоритмов, имеет смысл рассмотреть пример. Дабы не растягивать статью, предлагаю ознакомиться с отличным примером по ссылке (ни в коем случае не реклама сайта, просто это самый доступный и наглядный пример использования ГА, который я видел, к тому же с разъяснениями). Для практических примеров с использованием ЯП советую поискать на Хабре - там достаточно материала для дальнейших исследований.
Заключение
Как видите, принцип работы генетического алгоритма напрямую позаимствован у Её Величества Природы, а также это результат колоссальной работы биологов и генетиков (в особенности теории эволюции Дарвина) и креативных учёных, способных проецировать идеи из одной научной сферы в другую (в нашем случае из генетики в IT). И мы можем воспользоваться всеми преимуществами такой элегантной системы в своих целях. Воодушевляет, правда?
Вот, пожалуй, и всё, что для начала следует знать о генетических алгоритмах. Мы, конечно, не посмотрели на то, что происходит "за кулисами". Как кодируются гены - "кирпичики", из которых в конечном итоге состоят все особи и которые лежат в основе их "изменчивости"? Что представляет собой хромосома? Что происходит на "молекулярном" уровне и как технически реализуется ГА? Это вопросы для углублённого изучения. Цель данной статьи - пробудить интерес к теме и дать азы.
Спасибо за внимание и удачи!
Вам понравилась статья? Если да, то не забудьте поставить лайк и подписаться. Впереди ещё много интересного!
