Software & Systems

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

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

1) установка параметров эволюции;

2) инициализация начальной популяции P(0);

3) t:=0;

4) оценка решений, входящих в популяцию;

5) t:=t+1;

6) селекция артефактов (отбор родителей);

7) генерация потомков путем репликации и видоизменений;

8) оценка потомков и образование новой популяции P(t);

9) выполнение программы до тех пор, пока параметр t не достигнет заданного значения tmax либо не будут выполнены другие условия останова.

10)    вывод результатов и останов.

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

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

Проблемы компьютерного синтеза программ привлекли внимание исследователей еще в конце 50-х годов XX века. Интерес к данной проблематике резко возрос благодаря работам Дж. Коза [3], посвященным генетическому программированию (ГП) и направленным на решение задач автоматического синтеза программ с помощью обучающих данных путем индуктивного вывода.

Математические выражения, которые автоматически генерируются с помощью генетических операторов, являются компьютерными программами различной величины и сложности. Программы состоят из функций, переменных и констант. Исходная популяция P(0) артефактов в ГП образуется стохастически и состоит из программ, которые включают в себя элементы множества проблемно-ориентированных элементарных функций (function set: +, , –, *, %, sin, сos, log, or, and, for, do-until и пр., а также любая другая функция из предметной области задачи), проблемно-ориентированные переменные и константы (terminal set: ephemeral random – константы регрессионных функций с коротким временем жизни; T, Nil– булевы константы; вещественные константы). Множества function set и terminal set являются основой для эволюционного синтеза программы, способной наилучшим образом решать поставленную задачу. Одновременно устанавливаются правила выбора элементов из указанных множеств в пространстве всех потенциально синтезируемых программ, структура которых имеет древовидную форму.

Первоначально в исследованиях по ГП применялся язык LISP, обладающий всеми необходимыми свойствами для синтеза ГП-структур. В настоящее время наряду с LISP используются языки C, Smalltalk, C++.

Стартовыми условиями для ГП являются установка множеств terminal set и function set; определение подходящего вида функции соответствия (fitness-function); установка параметров эволюции; определение критерия останова моделирования эволюции и правил декодирования результатов эволюции.

Способом оценки качества функции соответствия в ГП является среднеквадратичная ошибка (чем она меньше, тем лучше программа) или критерий выигрыша, согласно которому выигрыш определяется в зависимости от степени близости к корректному значению математического выражения. Размер популяции μ в ГП обычно составляет несколько тысяч программ. Для максимального числа генераций tmax используется значение tmax=51.

Генетическая программа включает следующие модули.

1. Инициализация. На этом этапе стохастически генерируется популяция P(0), состоящая из µ древовидных программ, причем корневой вершиной дерева всегда является функция, аргументы которой выбираются случайно из множеств function set или terminal set. Концевыми вершинами дерева должны быть переменные или константы, в противном случае процесс генерации необходимо рекурсивно продолжить. Если структура дерева становится сложной, то заранее устанавливается максимальная высота дерева, равная числу ребер дерева, которое содержит самый длинный путь от корневой вершины до некоторой концевой вершины. В экспериментах обычно максимальная высота дерева колеблется от шести для популяции P(0) до 17 в более поздних популяциях P(t).

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

3. Генерация новой популяции и селекция. Основными операторами ГП являются рекомбинация (кроссинговер) и репродукция, селекция и репликация, выполняемые по схемам, аналогичным генетическим алгоритмам [4]. Если к некоторой программе применяют оператор репродукции, то эта программа копируется в новую популяцию. Для проведения кроссинговера выбираются две программы, случайным образом определяются точки кроссинговера и путем обмена образуются две программы-потомка. При программной реализации на языке LISP кроссинговер сводится к обмену списками между двумя программами при сохранении синтаксической корректности вновь получаемых программ.

4. Проверка критерия остановки. Процедура ГП является итерационной, критерии останова аналогичны критериям для генетических алгоритмов.

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

Другим перспективным направлением в ГП является реализация ГП на транспьютерных вычислительных системах. Существенное увеличение быстродействия ГП может быть получено и на последовательных машинах. В частности, реализация ГП на языке C увеличивает скорость ГП примерно на два порядка, а реализация ГП в машинных кодах – примерно на три порядка в сравнении с LISP-реализациями.

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

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

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

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

Рассмотрим эволюционную программу на примере задачи минимизации функции F(а1,…, аn), зависящей от n непрерывных переменных, которые представляются в виде вектора Ā=(а1,…, аn), что в ЭП соответствует отдельному артефакту. Программа состоит из следующих модулей.

1) Инициализация. На этапе инициализации случайным образом генерируется популяция Р(0), состоящая из μ артефактов Āi (i=1,2,…, μ). Рекомендуемое значение размера популяции μ≥200. Значение элемента aj для каждого артефакта Āi устанавливается случайно с помощью равномерного распределения на интервале [lj , rj ] Î R, lj < rj . Границы интервала lj , rj имеют значение лишь на этапе инициализации. В ходе дальнейшей эволюции пространство поиска в принципе является неограниченным. Стандартная форма ЭП предполагает решение оптимизационной задачи, в которой оптимальное значение равно 0, lj = – 50, rj =50.

2) Оценка решения. Каждая особь Āi определяет функцию соответствия Φ(Āi), которая зачастую равна значению целевой функции (Φ=F, хотя в общем случае они могут и не совпадать). В случае несовпадения функции соответствия и целевой функции значение Φ преобразуется с помощью некоторой случайной величины ξi. Например, если результирующее значение функции соответствия получилось отрицательным, то оно преобразуется путем скаляризации в положительное число. Таким образом, в общем случае считают, что Φ(Āi)=Ω(F(Āi), ξi).

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

3) Генерация потомков артефактов. Этот этап выполняется μ раз (i=1,2…μ) и включает в себя следующие действия.

3.1) Репликация путем копирования i-го родителя Āi=(а1,…, аn).

3.2) Мутация скопированного родителя путем сложения нормально распределенной случайной величины с нулевым математическим ожиданием и динамически изменяемым среднеквадратичным отклонением. Из родителя Āi возникает потомок Ā′i. Стандартное отклонение («ширина мутации») полученной случайной величины зависит от родительского значения функции соответствия Φ. При этом глобальный оптимум равен 0 (если это не так, то проводится соответствующее преобразование). Идея состоит в том, чтобы повысить эффективность процесса оптимизации путем сокращения «ширины мутации» при приближении к оптимуму. Значение переменной потомка определяется по формуле:

a′j = aj + sqrt(kj ∙Φ(Āi) + zj)∙Nj (0, 1),

где kj – константа скаляризации; Φ(Āi) – значение функции соответствия родителя; zj – дисперсия; Nj(0, 1) – стандартная нормально распределенная величина, определяемая для каждого j=1,2,…n. Значения kj , zj(kj, zjÎR+) являются параметрами ЭП и устанавливаются пользователем. В общем случае число этих параметров равно 2∙n. Однако на практике устанавливают kj=1, zj=0 (j=1,2,…n). Тогда квадратный корень (sqrt) в формуле для вычисления a′j упрощается, и она принимает следующий вид: a′j = aj + sqrt(Φ(Āi))∙Nj (0, 1).

3.3) Оценка потомка происходит путем определения значения его функции соответствия Φ(Ā′i)=Ω(F(Ā′i), ξi), после чего потомок добавляется в популяцию, причем Ā′i → Ā′μ+i . При окончании этапа 3 размер популяции становится равным 2∙μ.

4) Случайная селекция. Селекция выполняется по соревновательному принципу, согласно которому каждый родитель или потомок попарно сравнивается с h противниками, причем hÎN (h≥1) является параметром ЭП, устанавливается пользователем и обычно принимает значения от h=0.05μ до h=0.1μ. Противники выбираются случайно с помощью закона равномерного распределения. Победитель определяется путем попарного сравнения функций соответствия. Артефакт побеждает в соревновании, если ее функция соответствия по меньшей мере не хуже, чем у ее противника. Для представленной выше задачи минимизации число побед Wi i-го артефакта (i=1,2,…2∙μ) определяется как Wi =∑{1, если Φ(Āi)≤Φ(Ād)}, причем суммирование ведется для d=1,2,…h, и d≠i является целочисленным значением равномерно распределенной в интервале [1, 2∙μ] случайной величины, которое для каждого d определяется заново. После этого все артефакты сортируются по убыванию числа побед (а не по значению функций соответствия). Лучшие артефакты образуют новую родительскую популяцию размером μ. При одинаковом числе побед преимущество получает артефакт с лучшим значением функции соответствия. Очевидно, что при таком механизме селекции «слабые» артефакты имеют некоторую отличную от нуля вероятность репродукции. С ростом значения параметра h селекция начинает принимать дискриминационный элитарный характер.

5) Критерий останова. В качестве критерия останова могут быть следующие заданные пользователем события:

-   достижение в ходе эволюции заданного числа поколений tmax ;

-   достижение заданного уровня качества, когда, например, значение функций соответствия всех артефактов в популяции превысило некоторое пороговое значение;

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

Параметры ЭП выбираются таким образом, чтобы обеспечить скорость работы алгоритма и поиск наилучшего решения.

Одним из перспективных направлений практического развития идей ЭП является преодоление следующих недостатков: если пользователь не обладает информацией о глобальном оптимуме, то согласование и подбор функции скаляризации становится затруднительным; необходимость установки 2∙n значений параметров эволюции выдвигает перед пользователем дополнительные оптимизационные трудности, даже если он использует стандартную установку (kj =1, zj =0).

Преодоление этих недостатков эволюционной программы требует ее модификации с целью повышения адаптивных свойств ЭП, в частности, изменения процедур генерации потомков и селекции [5]. Например, на этапе генерации потомков из популяции с помощью закона равномерного распределения в интервале [1, μ] случайно выбирается родитель, из которого путем мутации получают потомка, добавляют его в популяцию, размер которой становится равным (μ+1), после чего производится детерминированная селекция путем исключения из популяции слабого артефакта.

Роль ЭП в моделировании интеллектуального поведения программных агентов может оказаться весьма плодотворной. Одним из наиболее объективных средств тестирования эволюционных алгоритмов для подобного рода проблем является классическая задача теории игр, называемая «дилеммой узников» [6].

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

Ясно, что наиболее выгодным для них является молчание. Однако простое рассуждение показывает, что, не имея никаких контактов между собой и к тому же не очень доверяя друг другу, каждый из узников, поразмыслив, придет к выводу, что нужно сознаваться.

Задачей ЭП является поиск такой игровой стратегии, которая позволит минимизировать средние потери при многократном повторении игровой ситуации. Можно представить каждую совместную игровую стратегию одним из состояний конечного автомата. Эксперименты с автоматами показали, что примерно в течение первых 20 ходов преобладает стратегия молчания, хотя уже после 5-10 ходов начинает встречаться стратегия кооперативного поведения, которая в дальнейшем однозначно становится доминирующей.

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

Список литературы

1.   Курейчик В.М., Родзин С.И. Эволюционные алгоритмы: генетическое программирование. Обзор. - Изв. РАН. ТиСУ. - 2002. - №1. - С. 127-137.

2.   Rodzin S.I. Schemes of Evolution Strategies // Proc. of 2002 IEEE Int. Conf. on AI' Systems (ICAIS, sept. 2002). IEEE Comp. Society: Los Alamos, California. P. 375-380.

3.   Koza J.R. Genetic Programming. Cambridge: MA: MIT Press, 1992, 1994.

4.   Курейчик В.М. Генетические алгоритмы. Состояние. Проблемы. Перспективы. - Изв. РАН. ТиСУ. - 1999. - №1. - С. 144-160.

5.   Holland J.H. Adaptation in natural and artificial systems. An Arbor: the Uni of Michigan press, 1975.

6.   Родзин С.И. Гибридные интеллектуальные системы на основе алгоритмов эволюционного программирования // Новости искусственного интеллекта. - 2000. - №3. - С. 159-170.