А.Е. Кононюк Дискретно-непрерывная математика
51
Если оба подхода одинаково применимы на практике, почему в природе
используется только один из них? Действительно, эволюционные
стратегии в чем-то ближе к концепции не Дарвина, а Ламарка, согласно
которой совершенствуются и непосредственно наследуются
фенотипические признаки. Эта концепция неплохо работает, когда
имеется фиксированный набор фенотипических признаков,
для которых
можно определить, как их изменения сказываются на фитнесс-функции.
Но если оптимизируемые объекты комбинаторно конструируются,
перечень их внешних признаков может быть неограниченным и заранее
неизвестным. В этом случае применить поиск в пространстве
фенотипов не представляется возможным. Именно такая ситуация
имеет место в живой природе. Выше мы затрагивали вопрос о сложной
связи генов и фенотипических признаков, которые разделяют многие
уровни биохимического конструирования, способные породить
неограниченный набор внешних признаков. Но за это приходится
«платить» тем, что обратный переход от фенотипа к генотипу
становится, по крайней мере, NP-полной задачей высокой размерности.
Как
результат, наследование приобретенных признаков в стиле Ламарка
оказывается почти (но не полностью) невозможным.
При использовании генетических алгоритмов разработчик, однако,
обычно начинает с фиксированных фенотипических признаков, данных
в рамках решаемой оптимизационной задачи, и для них выдумывает
способ кодирования в геноме одновременно с обратным
преобразованием. Поскольку и в ГА фенотипы оказываются
первичными, эволюционные стратегии имеют не меньше прав на
применение.
Существует, однако, класс объектов, эволюционная оптимизация
которых затруднительна в пространстве их «фенотипических
признаков», — это алгоритмы, или программы. Не существует какого-
нибудь простого отображения между желаемым выводом программы и
ее кодом (выполнение такого отображения — это NP-полная или
алгоритмически неразрешимая, в зависимости от деталей постановки,
задача). Не удивительно, что попытки автоматического построения
программ в рамках эволюционных вычислений
выделяются в
самостоятельное направление — генетическое (эволюционное)
программирование.
А.Е. Кононюк Дискретно-непрерывная математика
52
Здесь могут применяться аналоги как генетических алгоритмов, так и
эволюционных стратегий. В обоих случаях перебираются программы, а
не совершаемые ими действия, поэтому различия между ними сводятся
к тому, в каком виде представлять код программы — в виде бинарной
строки или, скажем, в виде графа. Из-за этого и трудности у этих
методов общие, хотя и выражающиеся немного по-разному, например,
как реализовать операции скрещивания и мутации, чтобы после их
выполнения получались корректные программы (или как закодировать
программы в форме бинарной строки для достижения той же цели).
Чаще используются не программы
на каком-то обычном языке
программирования, а разрабатывается некий язык со специальным
синтаксисом, упрощающий работу в рамках эволюционных методов. На
практике этот язык зачастую не является алгоритмически полным. В
простейшем случае (исходно рассмотренном Фогелем) структура
программы фиксирована, а оптимизируются только ее параметры. В
современных методах эволюционного программирования
рассматриваются представления программ в виде деревьев. При этом в
результате скрещивания одно поддерево заменяется другим (все
родительские узлы у них должны совпадать). Пример простой (с точки
зрения представления программы), но часто встречающейся задачи, —
это подбор математического выражения под известные результаты
вычислений. На рисунке ниже представлен один из возможных
результатов скрещивания двух программ-выражений.
Такой способ поиска в пространстве программ хорошо сочетается с
А.Е. Кононюк Дискретно-непрерывная математика
53
подходом к индуктивному выводу на
основе алгоритмической
сложности. Действительно, если у нас есть некоторый набор данных,
для которого нужно построить модель, мы вполне можем применить
эволюционное (или генетическое) программирование, при котором
фитнесс-функция каждой особи-программы будет оцениваться по
критерию минимальной длины описания. Не даст ли это
универсального решения задачи индуктивного вывода? Такая
возможность, в числе прочих, исследовалась Р. Соломоновым. К
сожалению, существующие методы эволюционных вычислений не
справляются с NP-полнотой данной проблемы и позволяют получить
приемлемое решение лишь для достаточно простых случаев.
Пожалуй, в приложении к проблемам машинного обучения
наиболее
популярным оказалось применение
Do'stlaringiz bilan baham: 
