5.3 Генетическое программирование
Генетическое программирование представляет собой метод автоматического создания программ, основанный на принципах биологической эволюции. Программы имеют древовидную структуру, которая поддается изменениям и комбинированию. В этом методе применяются три ключевых механизма: отбор программ по заданным критериям, скрещивание программ через обмен их частями и случайные изменения (мутации) в структуре. Важные аспекты метода включают защиту от избыточной сложности программ и поддержание их работоспособности при внесении изменений.
В искусственном интеллекте генетическое программирование (ГП) — автоматическое создание или изменение программ с помощью генетических алгоритмов. С помощью этой методологии «выращиваются» программы, всё лучше и лучше (в соответствии с определенной функцией приспособленности для хромосом) решающие поставленную вычислительную задачу.
Кодирование алгоритма
Выбор способа кодирования программы в генетическом алгоритме — один из основных вопросов генетического программирования. Программа должна быть закодирована в таком виде, чтобы легко было автоматически вносить случайные изменения (оператор мутации) и объединять два алгоритма в один (оператор скрещивания).
Способы кодирования можно разделить на два класса:
· Прямое кодирование — генетический алгоритм работает с программой в явном виде.
· Косвенное кодирование — генетический алгоритм работает не с самим кодом программы, а с правилами его построения. То есть генетический алгоритм работает с программой, которая генерирует нужную нам программу.
Древовидное
Функция, представленная в древовидной форме
В древовидном кодировании каждый узел дерева содержит функцию, а каждый лист -операнд.
Выражения, представленное в виде дерева может быть легко рекурсивно посчитано. Традиционное ГП легче использовать для выращивания программ, написанных на языках, естественным образом воплощающих древовидную структуру. Имеются в виду Lisp, Haskell, F# и другие функциональные языки программирования.
Недревовидные представления программ также были предложены и успешно реализованы, например линейное генетическое программирование, подходящее для традиционных императивных языков.
Оператор скрещивания
Оператор скрещивания для древовидного представления программ
В древовидном представлении оператор скрещивания реализуется обменом между двумя деревьями какими либо узлами вместе с их потомками (поддеревьями).
Пример:
individual.Children[randomChildIndex] = otherIndividual.Children[randomChildIndex];
Оператор мутации
Оператор мутации в отличие от оператора скрещивания затрагивает только одну хромосому. В древовидном представлении он может быть реализован изменением информации в узле или добавлением, удалением узла или целого поддерева. При этом, конечно, надо следить за корректностью результатов оператора.
Пример:
individual.Information = randomInformation();
или
individual = generateNewIndividual();
Генетический алгоритм производит поиск решений с помощью:
· отбора гиперплоскостей (hyperplane sampling), осуществляемого кроссовером, поскольку последний комбинирует и совмещает шаблоны родителей в их детях.
· метода hill-climbing, обеспечивающегося мутацией: особь случайным образом изменяется – неудачные варианты вымирают, полезные изменения сохраняются популяцией.
Исследования показали, что на простых задачах с малым размером популяции ГА с мутацией (и без кроссовера) находят решение быстрее. На сложных многоэкстремальных функциях лучше использовать ГА с кроссовером, поскольку этот метод более надежен, хотя и требует большего размера популяции.
С точки зрения теоремы шаблонов, мутация только вредит росту количества представителей хороших шаблонов, поскольку лишний раз их разрушает. Однако мутация просто необходима для ГА с малым размером популяции, потому что для них свойственна преждевременная сходимость (premature convergence) – ситуация, когда в некоторых позициях все особи имеют один и тот же бит, не соответствующий глобальному экстремуму.
Введём понятие, использующееся для анализа ГА. Давление отбора (selection pressure) — это мера того, насколько различаются шансы лучшей и худшей особей популяции попасть в промежуточную популяцию. Для пропорционального отбора эта величина с увеличением средней приспособленности популяции уменьшается, стремясь к 1, т.е. шансы плохой и хорошей особей создать потомство уравниваются.
При увеличении вероятностей скрещивания или мутации и при уменьшении давления отбора (например, за счет использования других стратегий отбора) размножение представителей приспособленных шаблонов замедляется, но зато происходит интенсивный поиск других шаблонов. Обратно, уменьшение вероятностей скрещивания или мутации и увеличение давления отбора ведет к интенсивному использованию найденных хороших шаблонов, но меньше внимания уделяется поиску новых.
Вывод: для эффективной работы генетического алгоритма необходимо поддерживать тонкое равновесие между исследованием и использованием.
Необходимость сбалансированной сходимости ГА:
§ быстрая сходимость может привести к схождению к неоптимальному решению
§ медленная сходимость часто приводит к потере найденной наилучшей особи.
Методология управления сходимостью классического ГА до сих пор не выработана.