Лекция 19 мин.
В искусственном интеллекте генетическое программирование (ГП) — автоматическое создание или изменение программ с помощью генетических алгоритмов. С помощью этой методологии «выращиваются» программы, все лучше и лучше (в соответствии с определенной функцией приспособленности для хромосом) решающие поставленную вычислительную задачу.
Генетические алгоритмы и генетическое программирование относятся к классу эволюционных методов искусственного интеллекта. Их идея основана на механизмах естественной эволюции: отборе, наследовании, мутациях и скрещивании.
В природе более приспособленные организмы имеют больше шансов выжить и передать свои признаки потомкам. В вычислительных задачах похожий принцип используется для поиска хороших решений: создается множество вариантов решений, они оцениваются, лучшие варианты «размножаются», изменяются и постепенно улучшаются.
Эти методы особенно полезны там, где трудно вывести точную формулу решения, где пространство возможных решений очень большое, а классические алгоритмы работают слишком медленно или требуют слишком много ручной настройки.
Генетический алгоритм — это метод оптимизации, который ищет лучшее или достаточно хорошее решение задачи с помощью имитации эволюции.
Простая схема работы генетического алгоритма:
Например, если нужно подобрать оптимальные параметры для игровой стратегии, каждое решение может быть набором чисел: скорость персонажа, сила атаки, дистанция атаки, шанс уклонения и так далее. Алгоритм будет создавать разные комбинации параметров, проверять их качество и постепенно находить более удачные варианты.
Генетическое программирование — это разновидность эволюционных алгоритмов, где эволюционируют не просто числа или параметры, а целые программы, выражения или алгоритмы.
Если в генетическом алгоритме решением может быть массив чисел:
[4, 7, 2, 9]
то в генетическом программировании решением может быть программа:
if x > 10:
return x * 2
else:
return x + 5
или математическое выражение:
(x + 3) * sin(y)
Главная идея генетического программирования: компьютер сам пытается создавать программы, которые решают заданную задачу.
Генетический алгоритм обычно оптимизирует параметры или структуры данных.
Генетическое программирование оптимизирует сами программы или формулы.
Таблица Отличие генетического алгоритма от генетического программирования
| Критерий | Генетический алгоритм | Генетическое программирование |
|---|---|---|
| Что эволюционирует | Решения, параметры, комбинации | Программы, формулы, деревья выражений |
| Пример особи | [1.2, 5.5, 9.0] | x * sin(y) + 3 |
| Основная цель | Найти лучшее решение | Найти программу, которая решает задачу |
| Представление | Строка, массив, бинарный код | Дерево, код, выражение |
| Сложность | Обычно ниже | Обычно выше |
создать начальную популяцию
пока не выполнено условие остановки:
оценить приспособленность каждой особи
выбрать лучших родителей
создать потомков с помощью скрещивания
применить мутации
сформировать новое поколение
вернуть лучшее найденное решение
создать случайную популяцию программ
пока не выполнено условие остановки:
запустить каждую программу на тестовых данных
вычислить ошибку или качество программы
выбрать лучшие программы
скрестить части программ
мутировать случайные узлы программ
сформировать новое поколение
вернуть лучшую найденную программу
Первое упоминание о предложении эволюционировать программы, вероятно, относится к 1950 году и принадлежит Алану Тьюрингу, который опубликовал работу « Вычислительные машины и интеллект ». Прошло 25 лет, прежде чем была опубликована работа Джона Холланда «Адаптация в естественных и искусственных системах», заложившая теоретические и эмпирические основы этой науки. В 1981 году Ричард Форсайт продемонстрировал успешную эволюцию небольших программ, представленных в виде деревьев, для классификации улик с места преступления для Министерства внутренних дел Великобритании.
Хотя идея эволюционирующих программ, первоначально на языке программирования Lisp , была популярна среди учеников Джона Холланда , только после того, как они организовали первую конференцию по генетическим алгоритмам (ГА) в Питтсбурге, Ничел Крамер опубликовал эволюционировавшие программы на двух специально разработанных языках, которые включали первое описание современного «древовидного» генетического программирования (то есть процедурных языков, организованных в древовидные структуры и обрабатываемых соответствующим образом определенными ГА-операторами). В 1988 году Джон Коза (также аспирант Джона Холланда) запатентовал свое изобретение ГА для эволюции программ . За этим последовала публикация на Международной объединенной конференции по искусственному интеллекту IJCAI-89 .
Затем Коза опубликовал 205 работ по «генетическому программированию», термину, введенному Дэвидом Голдбергом, также аспирантом Джона Холланда. Однако именно серия из 4 книг Козы, начиная с 1992 года с сопровождающими видеороликами , действительно утвердила генетическое программирование. Впоследствии произошло огромное расширение числа публикаций в Библиографии по генетическому программированию, превысившей 10 000 записей. В 2010 году Коза перечислил 77 результатов, где генетическое программирование было конкурентоспособным по отношению к человеческому.
Отход GP от жестких представлений фиксированной длины, характерных для ранних моделей GA, не был совершенно беспрецедентным. Ранние работы по представлениям переменной длины заложили основу. Одним из примечательных примеров являются сложные генетические алгоритмы, которые ввели нерегулярные хромосомы переменной длины для решения проблемы нарушения строительных блоков и позиционной предвзятости в стандартных GA. Другим предшественником было программирование траекторий роботов, где представления генома кодировали инструкции программы для движений роботов — структуры, по своей природе имеющие переменную длину. Еще раньше представления нефиксированной длины были предложены в докторской диссертации Кавиччио, который исследовал адаптивный поиск с использованием имитации эволюции. Его работа заложила основы для гибких структур программ.
В 1996 году Коза начал проводить ежегодную конференцию по генетическому программированию , за которой в 1998 году последовала ежегодная конференция EuroGP и первая книга из серии по генетическому программированию, отредактированная Козой. В 1998 году также вышел первый учебник по генетическому программированию . Генетическое программирование продолжало процветать, что привело к появлению первого специализированного журнала по генетическому программированию , а три года спустя (2003) Рик Риоло основал ежегодный семинар по теории и практике генетического программирования (GPTP) . Статьи по генетическому программированию продолжают публиковаться на различных конференциях и в связанных с ними журналах. Сегодня существует девятнадцать книг по генетическому программированию, включая несколько для студентов .
| Год | Описание | Ссылка |
|---|---|---|
| 1992 | Внедрение генетического программирования в виде генетически выведенных популяций компьютерных программ. | |
| 2000 | Декартово генетическое программирование | |
| 2000 | Грамматически-ориентированное гауссовское программирование – динамическое отсечение грамматики применяется при инициализации. | |
| 2001 | Программирование экспрессии генов | |
| 2012 | Многогенный GP – сочетание классического метода оценки параметров и выбора структуры. | |
| 2012 | Геометрический семантический ГП – прямой поиск в пространстве базовой семантики программ. | |
| 2015 | Замещающий врач общей практики | |
| 2015 | Меметическая семантическая ГП | |
| 2017 | Статистическое генетическое программирование — статистическая информация, используемая для построения хорошо структурированных поддеревьев. | |
| 2018 | Многомерное генетическое программирование – новый подход к представлению программ для многомерных признаков. |
Ранние работы, заложившие основу для современных исследований и приложений генетического программирования, разнообразны и включают в себя синтез и исправление программного обеспечения, предиктивное моделирование, интеллектуальный анализ данных , финансовое моделирование , программные датчики , проектирование и обработку изображений . Приложения в некоторых областях, таких как проектирование, часто используют промежуточные представления , например, клеточное кодирование Фреда Груау . Промышленное внедрение было значительным в нескольких областях, включая финансы, химическую промышленность, биоинформатику и сталелитейную промышленность
Популяция — это набор возможных решений задачи.
Например, если мы ищем лучший маршрут доставки, то популяция может состоять из разных вариантов маршрутов.
Каждый элемент популяции называется особью или индивидом.
Хромосома — это закодированное решение задачи.
В биологии хромосома содержит наследственную информацию. В генетическом алгоритме хромосома содержит информацию о варианте решения.
Примеры хромосом:
1011010010
или
[3.5, 8.2, 0.7, 12.0]
или
[A, D, C, B, E]
Форма хромосомы зависит от задачи.
Ген — это отдельная часть хромосомы.
Например, в хромосоме:
[10, 25, 5]
каждое число можно считать геном. Один ген может отвечать за скорость, другой — за силу, третий — за радиус действия.
Функция приспособленности показывает, насколько хорошим является решение.
Ее также называют fitness function.
Например:
fitness = прибыль - расходы
или
fitness = количество выигранных игр
или
fitness = 1 / ошибка модели
Чем выше значение функции приспособленности, тем лучше решение.
Функция приспособленности — один из самых важных элементов генетического алгоритма. Если она плохо задана, алгоритм может оптимизировать не то, что действительно нужно.
Большая популяция дает больше разнообразия, но требует больше вычислений.
Маленькая популяция быстрее считается, но может быстрее застрять в локальном оптимуме.
Мутация помогает находить новые варианты.
Но слишком высокая мутация превращает поиск почти в случайный перебор.
Скрещивание помогает комбинировать хорошие части решений.
Но если скрещивание плохо подходит к структуре задачи, оно может разрушать удачные решения.
Чем больше поколений, тем больше времени у алгоритма на поиск хорошего решения.
Но после некоторого момента улучшения могут стать очень маленькими.
Элитизм
Элитизм — это сохранение нескольких лучших особей без изменений в следующее поколение.
Это помогает не потерять уже найденное хорошее решение.
Например:
лучшие 5% популяции переходят в новое поколение без изменений
Локальный оптимум — это решение, которое лучше соседних вариантов, но не является лучшим в целом.
Примерно это можно представить как горный ландшафт:
маленькая гора — локальный максимум самая высокая гора — глобальный максимум
Алгоритм может подняться на маленькую гору и «решить», что это лучшее место, если не будет механизмов для дальнейшего поиска.
Мутации, разнообразие популяции и случайность помогают выходить из локальных оптимумов.
Выбор способа кодирования программы в генетическом алгоритме — один из основных вопросов генетического программирования. Программа должна быть закодирована в таком виде, чтобы легко было автоматически вносить случайные изменения (оператор мутации) и объединять два алгоритма в один (оператор скрещивания).
Способы кодирования можно разделить на два класса:
В древовидном кодировании каждый узел дерева содержит функцию, а каждый лист — операнд. Выражение, представленное в виде дерева, может быть легко рекурсивно посчитано. Традиционное ГП легче использовать для выращивания программ, написанных на языках, естественным образом воплощающих древовидную структуру: Lisp, Haskell, F# и других функциональных языках программирования.
Недревовидные представления программ также были предложены и успешно реализованы, например, линейное генетическое программирование, подходящее для традиционных императивных языков.
В древовидном представлении оператор скрещивания реализуется обменом между двумя деревьями какими-либо узлами вместе с их потомками (поддеревьями).
Пример:
individual.Children[randomChildIndex] = otherIndividual.Children[randomChildIndex];
В отличие от оператора скрещивания, оператор мутации затрагивает только одну хромосому. В древовидном представлении он может быть реализован изменением информации в узле или добавлением / удалением узла или целого поддерева. При этом надо следить за корректностью результатов оператора.
Пример:
individual.Information = randomInformation();
или
individual = generateNewIndividual();
На первом этапе создается множество случайных решений.
Например:
Особь 1: [2, 5, 8] Особь 2: [7, 1, 4] Особь 3: [3, 9, 6] Особь 4: [8, 2, 1]
Эти решения еще не обязательно хорошие. Их задача — дать алгоритму стартовое разнообразие.
Каждая особь проверяется с помощью функции приспособленности.
Например:
Особь 1: fitness = 15 Особь 2: fitness = 12 Особь 3: fitness = 20 Особь 4: fitness = 8
В этом примере лучшей является особь 3.
Отбор — это выбор лучших особей для создания следующего поколения.
Есть разные способы отбора.
Выбираются несколько особей с самым высоким fitness.
Преимущество: просто и быстро.
Недостаток: алгоритм может слишком рано потерять разнообразие.
Турнирный отбор
Случайно выбирается несколько особей, и среди них побеждает лучшая.
Например:
Турнир: особь 1, особь 3, особь 4 Победитель: особь 3
Турнирный отбор часто используется, потому что он прост и хорошо работает на практике.
Рулеточный отбор
Вероятность выбора особи зависит от ее приспособленности.
Чем лучше особь, тем выше шанс быть выбранной. Но слабые особи тоже иногда могут попасть в следующее поколение, что помогает сохранять разнообразие.
Скрещивание, или crossover, создает новое решение из двух родительских решений.
Например:
Родитель 1: [1, 2, 3, 4, 5] Родитель 2: [9, 8, 7, 6, 5]
После скрещивания:
Потомок: [1, 2, 3, 6, 5]
Смысл скрещивания в том, чтобы объединить удачные части разных решений.
Мутация — это случайное изменение части решения.
Например:
До мутации: [1, 2, 3, 4, 5] После мутации: [1, 2, 9, 4, 5]
Мутации нужны для появления новых вариантов решений. Без мутаций алгоритм может застрять в локальном оптимуме.
После отбора, скрещивания и мутации создается новое поколение решений.
Затем процесс повторяется:
поколение 1 → поколение 2 → поколение 3 → ... → поколение N
Обычно алгоритм останавливается, когда:
найдено достаточно хорошее решение
или
достигнуто максимальное число поколений
или
улучшение прекратилось
Представим задачу: нужно найти число x, при котором функция имеет максимум:
f(x) = x²
Допустим, x может быть от 0 до 31.
Каждое число можно представить в двоичном виде:
0 = 00000 7 = 00111 15 = 01111 31 = 11111
Начальная популяция:
00101 = 5, fitness = 25 01010 = 10, fitness = 100 10100 = 20, fitness = 400 11100 = 28, fitness = 784
Лучшие особи имеют большие значения x, потому что x² растет при увеличении x.
Через несколько поколений алгоритм с большой вероятностью найдет:
11111 = 31 fitness = 961
Это и будет лучшим решением в заданном диапазоне.
Часто программы представляются в виде дерева.
Например выражение:
(x + 3) * y
можно представить как дерево:
*
/ \
+ y
/ \
x 3
В таком дереве:
* и + — функции или операции x, y, 3 — терминалы
Операции могут быть разными:
+, -, *, /, sin, cos, if, and, or
Терминалы — это входные переменные или константы:
x, y, 1, 2, 3.14
Метагенетическое программирование — это ГП, в котором изменяется и, тем самым, «выращивается» не только заданная компьютерная программа, но и сами применяемые операторы скрещивания и мутации.
Генетические алгоритмы применяются в задачах оптимизации.
Примеры:
Например, в игре генетический алгоритм можно использовать для подбора баланса:
Алгоритм может искать такую комбинацию параметров, при которой игра будет достаточно сложной, но не слишком несправедливой.
Генетическое программирование применяется там, где нужно автоматически создать формулу, правило или программу.
Примеры:
Один из известных примеров — символьная регрессия. Это задача, где нужно найти формулу, которая объясняет данные.
Например, по набору точек алгоритм может найти формулу:
y = x² + 2x + 1
Главные преимущества:
Генетические алгоритмы не обязательно гарантируют идеальное решение, но часто находят достаточно хорошее решение там, где полный перебор невозможен.
Основные недостатки:
Например, если мутаций слишком мало, алгоритм может быстро застрять. Если мутаций слишком много, хорошие решения будут разрушаться слишком часто.
Если fitness function измеряет не то, что нужно, алгоритм будет улучшать неправильный показатель.
Например, если в игре награждать ИИ только за скорость прохождения уровня, он может найти странную стратегию: использовать баги, избегать целей или ломать игровую механику.
Алгоритм быстро теряет разнообразие и застревает.
Хорошие решения постоянно разрушаются.
Алгоритм плохо исследует новые области поиска.
Лучшее найденное решение может случайно исчезнуть в следующем поколении.
Алгоритм может не успеть найти хорошее решение.
| Метод | Особенность |
|---|---|
| Полный перебор | Проверяет все варианты, но часто слишком медленный |
| Жадный алгоритм | Быстрый, но может давать плохое решение |
| Градиентный спуск | Хорош для дифференцируемых задач |
| Генетический алгоритм | Хорош для сложных, дискретных, плохо формализуемых задач |
| Генетическое программирование | Может искать не только параметры, но и сами формулы/программы |
Комментарии