Эволюционные вычисления

Насколько осмысленной является идея использования законов эволюции не при имитации самой эволюции, а при решении интеллектуальных задач? На первый взгляд, идея может показаться интересной, но немного сомнительной: не происходит же у нас в голове эволюция, пусть даже виртуальная. Однако эта идея была высказана достаточно давно сразу несколькими авторами и оказалась относительно успешной. Сейчас область исследований, опирающихся на сходные идеи, называется эволюционными вычислениями. Наиболее ранним вкладом в нее в 1960-х годах стали эволюционные стратегии, предложенные Инго Рехенбергом с коллегами, и эволюционное программирование, предложенное Лоуренсом Фогелем, а также генетические алгоритмы Джона Генри Холланда (которые стали известны в 1970-х). Позднее возникла концепция генетического программирования. Все эти разновидности эволюционных вычислений являются альтернативой классическим методам поиска и оптимизации, включая эвристическое программирование.

Существующие методы эволюционных вычислений берут за основу идеи Дарвина. Одна из этих идей гласит: выживает наиболее приспособленный. В действительности, это тавтология, поскольку более приспособленный — это, по определению, тот, кто имеет больше шансов выжить. Эту тавтологичность подчеркивают и сами эволюционисты, чтобы доказать неизбежность эволюции, несмотря на отсутствие у природы каких-либо специальных целей. Не случайно идея выживания наиболее приспособленных часто называется естественным отбором. Отбор обычно подразумевает целенаправленное действие, но в природе он происходит «автоматически».

Однако неизбежность эволюции не следует лишь из логической истинности естественного отбора. Ведь для того, чтобы эволюция стала «работать», необходимо появление новых альтернатив, из которых осуществляется отбор. В связи с этим вводится дополнительная идея — идея изменчивости видов. То, что виды изменяются со временем, не самоочевидно и может быть установлено только из эмпирических данных, поскольку изменчивость должна обеспечиваться какими-то конкретными механизмами. Так, мы не можем сказать, что сейчас на уровне элементарных частиц идет естественный отбор, поскольку не происходит возникновение все новых и новых видов частиц.

Еще одна идея — это идея наследственности. Если бы виды возникали произвольно, то со временем могли бы появляться все более приспособленные виды, однако появление новых видов не зависело бы от степени приспособленности уже существующих, ведь при возникновении нового вида заранее нельзя сказать, насколько приспособленным он будет (если этот вид не конструируется сознательно). Наследственность же обеспечивает последовательное улучшение существующих решений за счет изменчивости и естественного отбора (стоит отметить, что здесь неявно присутствует предположение непрерывности: небольшое изменение вида обычно не сильно сказывается на степени его приспособленности).

Таким образом, как хорошо известно, базовые элементы дарвиновской концепции эволюции — это наследственность, изменчивость и естественный отбор. Поскольку в процессе эволюции появляются все более приспособленные виды, эволюцию можно трактовать как поиск максимума некоторой функции выживания, или фитнесс-функции. Если предположить, что в процессе эволюции в некоторый момент создан совершенный вид, то на нем эволюция прекращается, так как изменение этого вида может привести только к ухудшению его выживаемости (т. е. к уменьшению значения фитнесс-функции). Оставим на время в стороне вопрос о том, насколько биологическая эволюция соответствует такой модели, и согласимся с определенным сходством между эволюцией и поиском, которое и было замечено исследователями в области ИИ.

Однако перечисленные выше идеи Дарвина добавляют немногое к классическим методам поиска. Чтобы показать это, достаточно переформулировать упоминавшийся при обсуждении проблем поиска метод градиентного спуска (или подъема в гору, т. е. движения в направлении наискорейшего локального возрастания или убывания функции) в эволюционных терминах. Пусть текущая точка в методе градиентного спуска — это некоторая особь. На каждом шаге градиентного спуска проверяются некоторые точки вблизи текущей (наследственность и изменчивость) и выбирается из них лучшая (отбор). Стохастический градиентный спуск из многих точек обладает еще большим сходством с дарвиновской эволюцией, если ее ограничить лишь указанными идеями. На самом деле, еще сам Дарвин называл отбор в сочетании с изменчивостью «спуском с модификацией». Таким образом, обычный градиентный спуск содержит все базовые элементы эволюции. С одной стороны, это еще раз подчеркивает сходство эволюции с поиском, но с другой стороны, ставит вопрос, что же исследователи ИИ нашли для себя нового в эволюции?

Заинтересовали их не только базовые идеи Дарвина, но и генетические механизмы передачи наследственной информации. В качестве таких механизмов чаще всего рассматриваются перекрест хромосом при скрещивании и генные мутации.

В общем виде алгоритмы эволюционных вычислений, предназначенные для поиска оптимального решения некоторой задачи, могут быть представлены следующим образом. Альтернативные решения (или оптимизируемые объекты) трактуются как особи, степень приспособленности которых, или фитнесс-функция, явно или неявно определяется условиями задачи. Эти особи «эволюционируют» — к ним применяются «генетические операторы», такие как операторы скрещивания, мутации и редукции (селекции или отбора). Такие алгоритмы обычно состоят из следующих шагов.

  1. Сгенерировать начальную популяцию (случайную совокупность неоптимальных решений).
  2. Выбрать родительские пары.
  3. Для каждой родительской пары с использованием оператора скрещивания породить потомство.
  4. К порожденным особям применить оператор мутации, внеся случайные искажения.
  5. Произвести отбор особей из популяции по значению их фитнесс-функции, применив оператор редукции.
  6. Повторять шаги 2–5, пока не выполнится критерий остановки.

Каждый шаг имеет разные реализации. Кроме того, особенности генетических операторов зависят от конкретной формы эволюционных вычислений. Так, особенностью генетических алгоритмов является то, что в них для представления решений используются битовые строки, трактуемые как генотипы (обычно состоящие из единственной хромосомы), и все генетические операторы применяются к битовым строкам. В эволюционных стратегиях операторы применяются к самим решениям, представленным в их естественной форме. Особенность же эволюционного (генетического) программирования состоит в том, что в них рассматривается оптимизация особых объектов — компьютерных программ. Рассмотрим каждый из шагов чуть подробнее на примере генетических алгоритмов (ГА).

  1. Генерация начальной популяции обычно производится равномерно по пространству генотипов. Размер популяции — установочный параметр.
  2. Выбор родительских пар может осуществляться различными способами. Обычно он включает два этапа: выбор первого родителя и формирование пары. При выборе первого родителя обычно используется один из следующих способов:
    с равной вероятностью выбирается любая особь из имеющейся популяции;
    особь выбирается случайно с вероятностью, пропорциональной значению фитнесс-функции; т. е. в этом случае значение фитнесс-функции сказывается не только на том, какие особи останутся в популяции в результате отбора, но и на том, сколько потомства они произведут.

Выбор второго родителя осуществляется по одному из следующих критериев:

  • независимо от уже выбранного родителя (т. е. второй родитель выбирается абсолютно так же, как и первый); этот вид отбора называется неселективным;
  • на основе ближнего родства;
  • на основе дальнего родства.

В последних двух случаях выбор одного родителя влияет на выбор другого родителя: с большей вероятностью формируются пары, состоящие из особей, которые больше похожи друг на друга (т. е. ближе находятся в пространстве генотипов) при использовании ближнего родства или меньше похожи при использовании дальнего родства. В генетических алгоритмах в качестве меры близости обычно используется расстояние Хемминга, которое для двух битовых строк вычисляется как число позиций, в которых в двух строках стоят несовпадающие символы (т. е. в одной строке стоит 0, а в другой — 1).

3. Оператор скрещивания — это оператор, который определяет, как из генотипов родителей формировать генотипы их потомства. Один из интуитивно очевидных способов заключается в том, чтобы каждый бит генотипа для потомка брать от случайного родителя. Такой способ действительно используется и называется равномерным скрещиванием. Однако в природе гены внутри одной хромосомы являются сцепленными, поэтому случайным (и независимым) образом от родителей берутся целые хромосомы. Также есть механизм, который позволяет рекомбинировать и сцепленным генам. Это механизм кроссинговера, или перекреста хромосом, при котором (гомологичные) хромосомы обмениваются участками.

В ГА этот процесс моделируется так: хромосомы (а как отмечалось выше, обычно в ГА все гены особи располагаются в единственной хромосоме) делятся в некоторой случайной точке и обмениваются этими участками (т. е. все, что идет до этой точки, берется от одного родителя, а все, что после, — от другого). Это одноточечный кроссинговер. В многоточечном кроссинговере таких участков обмена больше. В ГА нередко используется такой оператор скрещивания, при котором формируются генотипы сразу двух потомков, содержащие всю генетическую информацию родителей. Варианты реализации оператора скрещивания представлены ниже на рисунке.

formula_30

Если бы в ГА геном представлялся в виде нескольких хромосом, то моделировался бы одновременно случайный выбор целых хромосом и рекомбинация генов внутри отдельных хромосом с помощью кроссинговера.

4. В бытовом понимании мутации обычно представляются как случайные искажения генов, и именно так (несмотря на то, что это крайне упрощенное представление) они реализуются в ГА. Действие оператора мутации сводится к случайной замене одного (иногда нескольких) бита генотипа. Настроечный параметр алгоритма — скорость мутации — определяет, как часто эта замена делается. Этот параметр влияет на скорость сходимости и вероятность попадания в локальный экстремум. Естественно, чем чаще мутации, тем медленнее стабилизируется генофонд популяции, но тем меньше шансов, что эволюция «застрянет» в неоптимальном решении.

5. Отбор особей в новую популяцию чаще всего осуществляется в соответствии с одной из двух стратегий:

  • пропорционального отбора, при котором вероятность того, что особь останется в следующей популяции, пропорциональна значению ее фитнесс-функции;
  • элитного отбора, при котором из популяции отбираются лучшие по значению фитнесс-функции особи, и только они переходят в следующую популяцию.

Формирование новой популяции может осуществляться как на основе потомков и родителей, так и на основе только потомков в зависимости от конкретной реализации.

6. Основные критерии остановки алгоритма базируются либо на числе сменившихся поколений (количестве выполненных итераций), либо на некотором условии стабильности популяции. Заранее сложно предсказать, сколько именно популяций потребуется для сходимости, поэтому этот критерий используется обычно как вспомогательный. Проверка стабильности популяции в общем виде, как правило, требует значительных вычислений, поэтому чаще используется проверка того, что наилучшее по популяции значение фитнесс-функции перестает заметно изменяться от поколения к поколению.

Отличие эволюционных стратегий от генетических алгоритмов заключается в том, что в первых не используются битовые представления. Вместо этого все генетические операторы реализуются в пространстве исходных объектов (или фенотипических признаков) с учетом их структуры. Рассмотрим особенности реализации генетических операторов в эволюционных стратегиях на примере объектов, описаниями которых являются двухкомпонентные векторы вида (x, y), т. е. задача заключается просто в поиске экстремума функции от двух переменных f (x, y).

  1. Генерация начальной популяции может осуществляться путем выбора случайных векторов из прямоугольной области formula_31, в которой ожидается нахождение экстремума фитнесс-функции. В случае генетических алгоритмов эта область задается неявно, и она зависит от способа отображения вектора (x, y) в битовую строку.
  2. При выборе родителей особенность эволюционных стратегий выражается в способе задания меры родства. В данном случае мерой родства двух особей (x1, y1) и (x2, y2) может служить евклидово расстояние, которое будет заметно отличаться от расстояния Хемминга, используемого в генетических алгоритмах.
  3. Результатом скрещивания двух особей в рассматриваемом случае будет являться особь, находящаяся в случайном месте отрезка (x1, y1)—(x2, y2), что, опять же, отличается от результата скрещивания в пространстве генотипов.
  4. Результатом мутации особи (x, y) будет являться особь (x + δx, y + δy), где δx, δy — случайные величины, разброс которых определяет скорость мутаций.
  5. Операторы отбора и критерии останова в эволюционных стратегиях не имеют особых отличий от тех, которые используются в генетических алгоритмах.

Как видно, реализация генетических операторов на уровне фенотипов допускает более гибкую их настройку, что может оказать помощь в повышении эффективности поиска, но при этом требуются дополнительные усилия со стороны разработчика. При использовании ГА реализация операторов может быть одинаковой для разных задач, для которых нужны только процедуры перевода объектов в битовые строки и обратно. Однако неудачный способ перевода может привести к низкой эффективности ГА.

Оба этих подхода могут применяться при решении самых разнообразных задач — от поиска экстремума функций вещественных переменных до решения изобретательских задач по разработке конструкций технических систем (известны случаи даже патентования и коммерческого использования решений, найденных методами эволюционных вычислений). Они позволяют приближенно решать некоторые NP-полные задачи не хуже, чем методы эвристического программирования, и требуют при этом меньших усилий от разработчика.

Если оба подхода одинаково применимы на практике, почему в природе используется только один из них? Действительно, эволюционные стратегии в чем-то ближе к концепции не Дарвина, а Ламарка, согласно которой совершенствуются и непосредственно наследуются фенотипические признаки. Эта концепция неплохо работает, когда имеется фиксированный набор фенотипических признаков, для которых можно определить, как их изменения сказываются на фитнесс-функции. Но если оптимизируемые объекты комбинаторно конструируются, перечень их внешних признаков может быть неограниченным и заранее неизвестным. В этом случае применить поиск в пространстве фенотипов не представляется возможным. Именно такая ситуация имеет место в живой природе. Выше мы затрагивали вопрос о сложной связи генов и фенотипических признаков, которые разделяют многие уровни биохимического конструирования, способные породить неограниченный набор внешних признаков. Но за это приходится «платить» тем, что обратный переход от фенотипа к генотипу становится, по крайней мере, NP-полной задачей высокой размерности. Как результат, наследование приобретенных признаков в стиле Ламарка оказывается почти (но не полностью) невозможным.

При использовании генетических алгоритмов разработчик, однако, обычно начинает с фиксированных фенотипических признаков, данных в рамках решаемой оптимизационной задачи, и для них выдумывает способ кодирования в геноме одновременно с обратным преобразованием. Поскольку и в ГА фенотипы оказываются первичными, эволюционные стратегии имеют не меньше прав на применение.

Существует, однако, класс объектов, эволюционная оптимизация которых затруднительна в пространстве их «фенотипических признаков», — это алгоритмы, или программы. Не существует какого-нибудь простого отображения между желаемым выводом программы и ее кодом (выполнение такого отображения — это NP-полная или алгоритмически неразрешимая, в зависимости от деталей постановки, задача). Не удивительно, что попытки автоматического построения программ в рамках эволюционных вычислений выделяются в самостоятельное направление — генетическое (эволюционное) программирование.

Здесь могут применяться аналоги как генетических алгоритмов, так и эволюционных стратегий. В обоих случаях перебираются программы, а не совершаемые ими действия, поэтому различия между ними сводятся к тому, в каком виде представлять код программы — в виде бинарной строки или, скажем, в виде графа. Из-за этого и трудности у этих методов общие, хотя и выражающиеся немного по-разному, например, как реализовать операции скрещивания и мутации, чтобы после их выполнения получались корректные программы (или как закодировать программы в форме бинарной строки для достижения той же цели).

Чаще используются не программы на каком-то обычном языке программирования, а разрабатывается некий язык со специальным синтаксисом, упрощающий работу в рамках эволюционных методов. На практике этот язык зачастую не является алгоритмически полным. В простейшем случае (исходно рассмотренном Фогелем) структура программы фиксирована, а оптимизируются только ее параметры. В современных методах эволюционного программирования рассматриваются представления программ в виде деревьев. При этом в результате скрещивания одно поддерево заменяется другим (все родительские узлы у них должны совпадать). Пример простой (с точки зрения представления программы), но часто встречающейся задачи, — это подбор математического выражения под известные результаты вычислений. На рисунке ниже представлен один из возможных результатов скрещивания двух программ-выражений.

formula_33

Такой способ поиска в пространстве программ хорошо сочетается с подходом к индуктивному выводу на основе алгоритмической сложности. Действительно, если у нас есть некоторый набор данных, для которого нужно построить модель, мы вполне можем применить эволюционное (или генетическое) программирование, при котором фитнесс-функция каждой особи-программы будет оцениваться по критерию минимальной длины описания. Не даст ли это универсального решения задачи индуктивного вывода? Такая возможность, в числе прочих, исследовалась Р. Соломоновым. К сожалению, существующие методы эволюционных вычислений не справляются с NP-полнотой данной проблемы и позволяют получить приемлемое решение лишь для достаточно простых случаев.

Пожалуй, в приложении к проблемам машинного обучения наиболее популярным оказалось применение эволюционного программирования при обучении нейронных сетей, что в большей степени используется не в индуктивном выводе, а при синтезе систем управления, в том числе в «Искусственной жизни» и «Адаптивном поведении». Наиболее простым в реализации является случай, когда структура нейронной сети фиксирована и требуется лишь настроить веса ее связей. В геноме тогда кодируются только веса связей, так что длина генотипов оказывается одинаковой у всех особей и не возникает опасности порождения некорректного генетического кода в результате применения генетических операторов. Это, однако, приводит к сильному ограничению пространства поиска. Поиск на менее ограниченном множестве программ является все еще плохо изученной проблемой.

Одна из причин, почему разработчики пытаются ограничиться геномом фиксированного размера, заключается в том, что в противном случае не вполне ясно, как реализовывать оператор скрещивания. Стоит отметить, что фиксированная структура генома приводит к тому, что в эволюционных вычислениях обычно скрещиваются все особи, т. е. эволюционирует один вид. Возможность изменения структуры генома в ходе эволюционных вычислений с соответствующим расщеплением видов практически не исследована.

Порождение ИНС методами эволюционных вычислений лишь заменяет традиционные методы их обучения. В этой связи гораздо больший интерес может представлять порождение нейроглиальных сетей, ведь в применении к ИНГС эволюционные вычисления превращаются в метаобучение — автоматическое построение самих алгоритмов обучения. Пока, однако, в этом направлении сделаны лишь первые шаги.

Альтернативой эволюционного синтеза нейросетевых систем управления является порождение управляющих конечных автоматов (как классических, так и на основе теории нечетких множеств), где также достигнуты определенные успехи.

Итак, эволюционные вычисления неплохо себя зарекомендовали в качестве методов поиска как при решении задач классического ИИ (т. е. при решении корректно поставленных NP-полных задач), так и при решении задач машинного обучения, хотя и не дали их полного решения.

Почему же методы эволюционных вычислений оказываются достаточно успешными для решения проблем поиска? Эволюционные стратегии в применении к поиску экстремума функции от вещественных переменных очень похожи на стохастический градиентный спуск за исключением того, что в них происходит «скрещивание» решений. С генетическими алгоритмами ситуация чуть сложнее, так как в них небольшие мутации генов могут привести к значительному изменению «фенотипа» (примером может служить изменение старшего бита в двоичной записи числа). Но и в ГА основной особенностью является скрещивание, благодаря которому новые решения строятся как фрагменты имеющихся решений. Если задача разбивается на подзадачи и решению каждой подзадачи соответствует отдельный участок генома, то за счет скрещивания подзадачи могут решаться независимо. Действительно, если решение какой-то подзадачи улучшает общее решение независимо от других подзадач, то в генофонде популяции соответствующий участок генома быстро стабилизируется (его вариативность сильно уменьшится). Еще в большей степени этому будет способствовать использование не равномерного скрещивания, а кроссинговера, при котором потомкам передаются длинные фрагменты генотипов родителей. Кроссинговер будет работать хорошо, только если решения отдельных подзадач локализованы в геноме.

Итак, мы видим, что ГА дополнены одним, но очень мощным приемом, благодаря которому решаемая задача «мягко» (но не адаптивно) разбивается на подзадачи. Следует, однако, иметь в виду, что этот прием не вполне универсален. Если участки генома не соответствуют фрагментам решений почти независимых подзадач (в силу особенностей решаемой NP-полной задачи или в силу неудачного выбора способа кодирования решения в геноме), то ГА будут смесью полного перебора и градиентного спуска, причем реализованного не самым эффективным образом. Отдельные участки генома не будут стабилизироваться независимо друг от друга, и найти решение удастся, только если все гены одновременно рекомбинируют нужным образом, вероятность чего будет очень низка.

Прием, который позволяет эффективно сокращать перебор для многих задач, но в общем случае не гарантирует нахождения оптимального решения, принято называть метаэвристикой. В отличие от простой эвристики метаэвристика не является предметно-специфичной, что делает ее широко применимой, но во многих случаях недостаточной. К примеру, сами по себе ГА не могут использоваться при выборе хода в шахматах, для которых классическое эвристическое программирование пока остается хоть и весьма трудоемким, но практически единственным подходящим средством. Если же в какой-то NP-полной задаче части решения являются почти независимыми (как, например, в задаче коммивояжера), то единственная метаэвристика, заложенная в ГА, может оказаться достаточной для получения приемлемого решения, благодаря чему не нужно будет разрабатывать индивидуальный (под данную задачу) алгоритм обхода дерева варианта со сложными предметно-специфичными эвристиками.

Часто говорят, что эволюционные вычисления весьма эффективны, поскольку они заимствуют основные идеи из естественной эволюции. Но зададимся наивным вопросом: почему генетическое программирование не позволяет создать ИИ? Выше мы не напрасно останавливались на вопросах устройства генов: теперь мы видим, что ГА и аналогичные им методы столь же проще реальных генетических механизмов, сколь и ИНС проще биологических нейронов. Вместе с тем ГА, как и методы обучения ИНС, недостаточны для работы в алгоритмически полном пространстве.

Несмотря на некоторые положительные свойства, методы эволюционных вычислений оказываются вовсе не универсальными. В связи с этим, если мы рассмотрим эволюционные вычисления как методы поиска в пространстве решений, то становится понятным, почему с их помощью не так просто автоматически получить ИИ. По сути, эти методы сами будут составлять интеллектуальную систему, перед которой ставится задача поиска программы ИИ. Нет ли здесь противоречия? Не получается ли так, что нам уже нужно иметь ИИ, чтобы компьютер смог сам его придумать? Принципиального противоречия здесь нет: более «глупая» программа может вывести более «умную» посредством «грубой силы», т. е. используя очень интенсивный перебор. Конечно, чем глупее эволюционная программа, тем больше грубой силы ей придется приложить. Полным перебором задачу построения ИИ или даже игры в шахматы на практике не решить. Естественно, недостаточно и нескольких простых метаэвристик. Такой взгляд показывает наивность попыток с помощью простой искусственной эволюции вывести интеллектуальные программы. Но как это удалось сделать естественной эволюции?