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