Эволюционное программирование

Оглавление

 

История появления.

Эволюционное  программирование было изобретено доктором Лоуренсом Дж. Фогелем в Национальном Научном Фонде в 1960 году. Ему было поручено представить доклад Конгрессу США на сумму инвестиций в фундаментальные исследования. Одним из вопросов рассмотрения был искусственный интеллект.

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

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

В 1964 году Фогель получил  докторскую степень в области  электротехники в университете Калифорнии в Лос-Анджелесе. Его диссертация  «О происхождении Интеллекта», была посвящена искусственному интеллекту путем имитации эволюции. Ранние работы также привели доктора Фогеля, д-ра Аль Оуэнса, и д-ра Майкла Уолша к созданию решений для Science, Inc в 1965 году. Это была первая компания в мире, занимавшаяся исключительно коммерциализацией эволюционных алгоритмов.

В 1970, благодаря в первую очередь руководству профессора Дональда Дэрхольта в государственном университете Нью-Мехико, было опубликовано более широкое исследование вычислений для эволюционного программирования, чем для любых других форм моделируемой эволюции. Большинство этих исследований использовали эволюционные программы для распознавания образов (Root, 1970; Корнетт, 1972; Lyle, 1972; Holmes, 1973; Trellue, 1973; Монтес, 1974; Атмар, 1976; Винсент, 1976; Вильямс, 1977; Dearholt, 1976). В качестве примера для распознавания использовались главным образом рукописные символы. В эксперименты включили параметры адаптивных мутаций. Работа Атмара (1976) — один из ранних примеров имитации эволюции в обстановке искусственной жизни. Атмар (1976), возможно, первый предложил и описал, как эволюционное программирование может быть рассчитано на то, что сейчас известно как «расширенная база оборудования». Ангелине и Поллак (1993) описали, как эволюционное программирование может быть использовано для развития компьютерных программ.

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

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

Эволюционный алгоритм и его  виды.

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

Основные эволюционные алгоритмы:

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

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

Наибольшее распространение получил генетический алгоритм [2]. На его основе осуществляются: оптимизация профилей балок в строительстве, распределение инструментов в металлообрабатывающих цехах, обработка рентгеновских изображений в медицине, оптимизация работы нефтяных трубопроводов и т.д. [7]. Одна из основных областей применения генетического алгоритма – решение задач комбинаторной оптимизации (например, задача о коммивояжере).

Для иллюстрации принципов работы эволюционных алгоритмов рассмотрим подробнее  генетический алгоритм.

Генетический алгоритм

Генетический алгоритм (ГА) [2,8,9] –  это компьютерная модель эволюции популяции  искусственных "особей". Каждый особь  характеризуется своей хромосомой S_k, хромосома есть "геном" особи. Хромосома определяет приспособленность особи f(S_k); k = 1,..., n; n – численность популяции. Хромосома есть цепочка символов S_k = (S_k1, S_k2,...,S_kN), N – длина цепочки. Символы интерпретируются как "гены" особи, расположенные в хромосоме S_k . Задача алгоритма состоит в максимизации функции приспособленности f(S_k) .

Эволюция состоит из последовательности поколений. Для каждого поколения  отбираются особи с большими значениями приспособленностями. Хромосомы отобранных особей рекомбинируются и подвергаются малым мутациям. Формально, схема ГА может быть представлена следующим образом (популяция t-го поколения обозначается как {S_k(t)}):

Шаг 0 . Создать случайную начальную  популяцию {S_k(0)}.

Шаг 1. Вычислить приспособленность f(S_k) каждой особи S_k популяции {S_k(t)}.

Шаг 2. Производя отбор особей S_k в соответствии с их приспособленностями f(S_k) и применяя генетические операторы (рекомбинации и точечные мутации) к отобранным особям, сформировать популяцию следующего поколения {S_k(t+1)}.

Шаг 3. Повторить шаги 1,2 для  t = 0, 1, 2, ... , до тех пор, пока не выполнится некоторое условие окончания эволюционного поиска (прекращается рост максимальной приспособленности в популяции, число поколений t достигает заданного предела и т.п.).

Имеется ряд конкретных вариантов  генетического алгоритма, которые  отличаются по схемам отбора, рекомбинаций, по форме представления хромосом и т.д.

Наиболее традиционный вариант  генетического алгоритма базируется на следующей конкретной схеме: 1) цепочки символов в хромосомах бинарны (символы S_ki принимают значения 0 либо 1), длина цепочек постоянна (N = const), 2) метод отбора пропорционально-вероятностный (см. ниже), 3) рекомбинации производятся по схеме однократного кроссинговера.

Пропорционально-вероятностный отбор означает, что на шаге 2 отбор производится с вероятностями, пропорциональными приспособленностям f_k особей ( f_k = f(S_k) ) . Эту схему отбора мы уже обсуждали в лекции 2 при описании модели квазивидов. Схему можно представить, как выбор особи с помощью рулетки, относительные площади секторов которой равны q_k = f_k [S _l f_l ]^-1 ( см. Рис.1 и "прилегающий к нему" текст в  Лекции 2 ).

Эволюционная программа.

Эволюционная программа - это вероятностный алгоритм, применяемый на -й итерации к популяции особей

.

Каждая особь представляет потенциальное  решение задачи, которое в произвольной эволюционной программе может отображаться некоторой (в том числе и достаточно сложной) структурой данных . Любое решение  оценивается по значению его «приспособленности». Далее в процессе селекции на -й итерации из наиболее приспособленных особей формируется очередная популяция. Некоторые особи этой новой популяции трансформируются с помощью «генетических операторов», что позволяет получать новые решения. Существуют преобразования  (типа мутации), которые изменяют конкретные хромосомы , а также трансформации более высокого порядка  (типа скрещивания), создающие новые особи путем комбинирования фрагментов нескольких (двух или более) хромосом, т.е. . От эволюционной программы ожидается, что после смены некоторого количества поколений наилучшая особь будет представлять решение, близкое к оптимальному. Структура эволюционной программы может быть представлена в виде псевдокода [33] так, как это изображено на рис. 4.65 (рекомендуется сравнить ее с рис. 4.3).

Рис. 4.65. Представление эволюционной программы в виде псевдокода.

Рассмотрим обобщенный пример эволюционной программы [33]. Допустим, что ищется граф, который удовлетворяет определенным ограничениям (например, производится поиск топологии коммуникационной сети, оптимальной по конкретным критериям, например, по стоимости передачи и т.п.). Каждая особь в эволюционной программе представляет одно из потенциальных решений, т.е. в данном случае некоторый граф. Исходная популяция графов , формируемая случайным образом либо создаваемая при реализации какого-либо эвристического процесса, считается отправной точкой  эволюционной программы. Функция приспособленности, которая обычно задается, связана с системой ограничений решаемой задачи. Эта функция определяет «приспособленность» каждого графа путем выявления «лучших» и «худших» особей. Можно предложить несколько различных операторов мутации, предназначенных для трансформации отдельных графов, и несколько операторов скрещивания, которые будут создавать новый граф в результате рекомбинации структур двух или более графов. Очень часто такие операторы обусловливаются характером решаемой задачи. Например, если ищется граф типа «дерево», то можно предложить оператор мутации, который удаляет ветвь из одного графа и добавляет новую ветвь, объединяющую два отдельных подграфа. Другие возможности заключаются в проектировании мутации независимо от семантики задачи, но с включением в функцию приспособленности дополнительных ограничений - «штрафов» для тех графов, которые не являются деревьями.

Принципиальную разницу между  классическим генетическим алгоритмом и эволюционной программой, т.е. эволюционным алгоритмом в широком смысле, иллюстрируют рис. 4.66 и 4.67.

                                                                                   

Решение задачи с помощью классического генетического  алгоритма.

Решение задачи с помощью эволюционного алгоритма (эволюционной программы).

 

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

Эволюционные программы могут  оставить постановку задачи в неизменном виде за счет модификации хромосом, представляющих потенциальные решения (с использованием «естественных» структур данных), и применения соответствующих «генетических» операторов.

Другими словами, для решения нетривиальной  задачи можно либо преобразовать  ее к виду, требуемому для использования  генетического алгоритма (рис. 4.66), либо модифицировать генетический алгоритм так, чтобы он удовлетворял задаче (рис. 4.67). При реализации первого подхода применяется классический генетический алгоритм, а при реализации второго подхода - эволюционная программа. Таким образом, модифицированные генетические алгоритмы можно в общем случае называть эволюционными программами [33]. Однако чаще всего встречается термин эволюционные алгоритмы. Эволюционные программы также могут рассматриваться как эволюционные алгоритмы, подготовленные программистом для выполнения на компьютере. Основная задача программиста заключается при этом в выборе соответствующих структур данных и «генетических» операторов. Именно такая трактовка понятия эволюционная программа представляется наиболее обоснованной.

Применение эволюционного программирования.

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

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