В прошлый раз мы закончили со всем, что связано с машинным обучением, и теперь мы переходим к следующим методам восходящего подхода — эволюционным. Сегодня мы детально узнаем, что такое генетические алгоритмы.
В прошлых материалах при изучении квазибиологического и эволюционного подходов мы уже устремляли свой взгляд на эту тему. Пожалуйста, вспоминайте то, что мы прошли. И сегодня давайте углубим наше понимание генетических алгоритмов и всего остального, что связано с искусственной эволюцией.
Как я сказал, эволюционные алгоритмы являются явными представителями восходящей парадигмы создания Искусственного Интеллекта. Этот класс алгоритмов представляет собой отдельное направление в рамках исследований по Искусственному Интеллекту, в котором изучаются и моделируются процессы естественного и искусственного отбора. Все эволюционные алгоритмы моделируют базовые эволюционные процессы в природе — наследование, мутации и отбор.
В применении к технологиям Искусственного Интеллекта работа эволюционных алгоритмов всегда связана с взаимодействием искусственной интеллектуальной системы с какой-либо средой, а опосредованно через неё, возможно, и с другими интеллектуальными системами (как искусственными, так и естественными).
Такая среда сама может быть искусственной (виртуальный мир, «песочница»), так и представлять собой объективную реальность, с которой искусственная интеллектуальная система взаимодействует при помощи набора сенсоров и исполнительных механизмов.
На текущий момент в рамках эволюционных алгоритмов выделяются следующие направления: эволюционное программирование, генетическое программирование, эволюционные стратегии, генетические алгоритмы, дифференциальная эволюция и нейроэволюция. Давайте кратко изучим всё, что не изучали ранее. А ранее мы изучили первые два метода — эволюционное и генетическое программирование.
Эволюционная стратегия — это эвристический метод оптимизации, разработанный в 1964 году Инго Рехенбергом. Фактически, этот метод стал предтечей генетических алгоритмов, хотя в том или ином виде они прорабатывались и ранее. В эволюционной стратегии осуществляется поиск целевого вектора, который наилучшим образом подходит под решение задачи. И компонентами этого вектора являются только действительные числа.
Для поиска решения осуществляются скрещивание особей и мутации. Далее применяется функция отбора, которая принимает на вход всю когорту — и родительские особи, и множество их потомков. Отбор осуществляется детерминированным образом — оставляются самые лучшие особи, причём без повторений.
Операция мутации может быть произвольной над действительными числами, но обычно используется простое добавление нормально распределённого случайного числа к компонентам векторов. Важным дополнением эволюционной стратегии является то, что в процессе эволюции параметры нормального распределения добавляемой в рамках мутации случайной величины адаптируются под поиск решения задачи.
Перейдём к наиболее известному из методов, который является ярким представителем эволюционного подхода. Это генетические алгоритмы. Генетические алгоритмы сами по себе опять являются одним из эвристических методов оптимизации для поиска оптимального решения (или, как минимум, субоптимального).
Генетический алгоритм — это метод поиска при помощи случайного подбора по аналогии, как уже сказано, с естественным отбором живых организмов в природе. Генетический алгоритм позволяет найти оптимальное или субоптимальное решение задачи с требуемой точностью в тех случаях, когда существует возможность представить входные данные в виде вектора значений, а критерий останова выразить в виде предиката, возвращающего истину на тех входных параметрах, которые достаточны для решения. Предикат зависит от так называемой фитнесс-функции, которая возвращает степень соответствия входного вектора целевому значению. Ну и, само собой разумеется, искомое значение должно существовать, иначе алгоритм никогда не остановится.
При помощи генетического алгоритма можно отобрать подходящее значение в пространстве поиска. При этом значения, среди которых отбирается подходящее, должны быть представимы в виде вектора или списка некоторых значений, называемых «генами», а сам список называется «хромосомой».
Тип значений-генов жёстко не задан, как это сделано в эволюционных стратегиях, но главное, чтобы на нём были определены и имели смысл генетические операции, используемые в алгоритме.
Генетический алгоритм состоит из следующих шагов: генерация начальной популяции, цикличный процесс рождения новых поколений и отбора, остановка и возвращение результатов поиска.
Так, генерация начальной популяции. На этом шаге необходимо подготовить некоторое количество «начальных» значений в пространстве поиска, с которых алгоритм начнёт свою работу. Начать можно с произвольных значений, но если такие значения будут как можно более близки к целевому, то алгоритм отработает намного быстрее.
Далее — запуск цикличного процесса рождения новых поколений и отбора. Фактически, это и есть сам генетический алгоритм, который раз за разом запускает процесс порождения новых поколений, изучения новых особей и отбора наиболее интересных. В свою очередь этот процесс состоит из следующих шагов и операций: скрещивание, мутация и отбор.
Операция скрещивания или перекрёста — это операция, при которой берутся две особи текущего поколения, и их генотип перемешивается друг с другом. Чаще всего два генотипа разрезаются в одинаковом случайном месте, и после этого вторые части переставляются друг с другом. Так получаются два новых потомка. Фактически, скрещивание делается каждой особи с каждой, да ещё и по нескольку раз, чтобы разрезание генотипа происходило в разных местах. Так получается набор особей следующего поколения.
Операция мутации — это внесение случайных изменений в генотип потомства. С установленной частотой в каждый новый генотип после скрещивания вносятся случайные изменения. Если частота мутаций высокая, то наблюдается «подвижность» поиска, если же частота мутаций слишком низкая, то часто это приводит к «залипанию» алгоритма в локальном экстремуме, из которого он не может выбраться и, соответственно, остановиться. Величину частоты мутаций часто подбирают при помощи экспериментов для каждой конкретной задачи.
Операция отбора — это выбор наиболее приспособленных особей. Обычно выбирается какая-то небольшая доля (например, 10 %) тех особей нового поколения, для которых фитнесс-функция возвращает наилучшие результаты. Иногда в отобранное множество особей нового поколения добавляются наименее приспособленные особи, для которых фитнесс-функция возвращает наихудшие результаты. Это делается для получения генетического разнообразия и является инструментом борьбы с залипанием в локальных экстремумах. Также иногда в состав нового поколения включаются некоторые представители предыдущего поколения, которые в данном случае называются «элитой». Вообще, операция отбора также подбирается на основе экспериментов для каждой конкретной задачи.
И, наконец, третий шаг — возвращение результатов, которые привели к остановке цикла. Завершение алгоритма происходит тогда, когда фитнесс-функция для какой-либо особи находится в окрестности целевого значения с заданной точностью. Собственно, предикат проверки условия для остановки алгоритма проверяет для каждой особи значение фитнесс-функции, и если абсолютное значение разницы между ним и целевым значением меньше заданной точности, то предикат возвращает истину, и алгоритм останавливается. Необходимая точность является входным параметром алгоритма.
Схематически генетический алгоритм может быть изображён при помощи диаграммы, представленной на слайде. Давайте ещё раз внимательно посмотрим на эту схему и запомним её. Генетические алгоритмы — это очень мощный инструмент поиска решений в тех случаях, когда формализовать задачу затруднительно или невозможно.
Дифференциальная эволюция — это тоже метод оптимизации, который позволяет найти глобальный экстремум для недифференцируемых, нелинейных, мультимодальных функций от многих переменных. Это очень вычислительно простой и в то же очень мощный метод, позволяющий довольно быстро найти именно глобальный экстремум.
Суть его проста. Пространство поиска опять представляет собой векторы. Для каждого вектора текущего поколения случайным образом выбираются три других вектора из этого же поколения, над которыми производится операция мутации, являющаяся параметром алгоритма. Например, к первому вектору добавляется удвоенная разность между вторый и третьим вектором. Далее полученный мутантный вектор подвергается перекрёсту с изначальным вектором, причём для каждого элемента изначального вектора производится случайный выбор того, замещать ли его соответствующим элементом мутантного вектора. После перекрёста получается пробный вектор, на котором вычисляется значение фитнесс-функции. Если оно ближе к экстремуму, чем значение на изначальном векторе, то в новое поколение идёт пробный, а иначе в нём остаётся изначальный. И такой процесс осуществляется над каждым вектором текущего поколения.
И, наконец, очень интересная и важная идея — применение эволюционного подхода к нейросетям. А что если в виде хромосомы представить нейронную сеть, а потом над некоторой начальной популяцией таких нейронных сетей осуществить процедуру генетического алгоритма или дифференциальной эволюции? В этом и состоит суть нейроэволюции. И сегодня это одно из самых интересных направлений в рамках восходящего подхода. Искусственный Интеллект начинает использовать эволюцию для создания ещё более мощного Искусственного Интеллекта.
На этой животрепещущей ноте я вас покину. На досуге прошу обдумать открывающиеся возможности при применении методов эволюционного подхода ко всему, до чего мы можем дотянуться. На следующем занятии мы изучим многоагентные системы.
