Эволюционные вычисления: генетическое и эволюционное программирование

Размещено на http://www.allbest.ru/

Эволюционные вычисления: генетическое и эволюционное программирование

Курейчик В.М., Родзин С.И.

Введение

Эволюционные вычисления, синонимом которых в зарубежной литературе является термин «evolutionary computation», доказали свою эффективность как при решении трудноформализуемых задач искусственного интеллекта (распознавание образов, кластеризация, ассоциативный поиск), так и при решении трудоемких задач оптимизации, аппроксимации, интеллектуальной обработки данных. К преимуществам эволюционных вычислений относятся адаптивность, способность к обучению, параллелизм, возможность построения гибридных интеллектуальных систем на основе комбинирования с парадигмами искусственных нейросетей и нечеткой логики. Многообещающей выглядит предпосылка создания единой концепции эволюционных вычислений, включающих генетические алгоритмы, генетическое программирование (ГП), эволюционные стратегии и эволюционное программирование (ЭП). По мнению многих исследователей, эти парадигмы являются аналогами процессов, происходящих в живой природе и на практике доказавших свою непримитивность. Один из пионеров эволюционных вычислений Л.Фогель вообще видит теорию эволюции и самоорганизации как базовую концепцию для всех интеллектуальных процессов и систем, значительно расширяющую сферу применения традиционной парадигмы искусственного интеллекта. Даже если это не так, и в природе происходит реэволюция, никто не может сказать, что алгоритмы эволюционных вычислений неверны.

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

1. Достоинства и недостатки эволюционных вычислений

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

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

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

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

t:=0;

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

t:=t+1;

Селекция (отбор);

Репликация (повторение, копирование, аутосинтез);

Вариация (видоизменение);

Оценка решений-потомков;

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

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

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

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

Предпринятая в [3] попытка сравнительного анализа конкурирующих эвристических алгоритмов с точки зрения их результативности, даже при том, что NFL-теорема не учитывает время решения оптимизационной задачи, имеет два важных практических следствия:

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

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

С этой точки зрения эволюционные вычисления обладают следующими достоинствами и недостатками.

Достоинства эволюционных вычислений:

широкая область применения;

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

пригодность для поиска в сложном пространстве решений большой размерности;

отсутствие ограничений на вид целевой функции;

ясность схемы и базовых принципов эволюционных вычислений;

интегрируемость эволюционных вычислений с другими неклассическими парадигмами искусственного интеллекта, такими, как искусственные нейросети и нечеткая логика [4].

Недостатки эволюционных вычислений:

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

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

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

нерешенность вопросов самоадаптации.

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

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

2. Генетическое программирование и компьютерный синтез математических выражений

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

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

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

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

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

Рассмотрим подробнее процедуру ГП.

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

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

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

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

Проиллюстрируем рассмотренную процедуру на примере вычисления разности объемов двух параллелепипедов. Пусть два параллелепипеда задаются шестью независимыми переменными L₁,B₁,H₁,L₂,B₂,H₂ и одной зависимой переменной D. Для получения корректных значений величины D установим следующие стартовые условия:

terminal set: ={ L₁,B₁,H₁,L₂,B₂,H₂};

function set: ={+,-,*,%};

функция соответствия указывает абсолютную ошибку, определяемую разностью между корректным значением D и тем значением, которое получается программно;

выигрыш определяется числом случаев, когда сравниваемые величины D различаются менее, чем на 0.01;

м=4000;

программа останавливается, если число выигрышей равно 10, либо t_max=51.

В табл. 1 представлены 10 различных вариантов исходных значений для шести независимых переменных, а также разность объемов D= L_1*B_1*H₁-L_2*B_2*H₂.

Таблица 1 Исходные данные для вычисления разности объемов двух параллелепипедов

	L1	B1	H1	L2	B2	H2	D
1	3	4	7	2	5	3	54
2	7	10	9	10	3	1	600
3	10	9	4	8	1	6	312
4	3	9	5	1	6	4	111
5	4	3	2	7	6	1	-18
6	3	3	1	9	5	4	-171
7	5	9	9	1	7	6	363
8	1	2	9	3	9	2	-36
9	2	6	8	2	6	10	-24
10	1	10	7	5	1	45	-155

В результате моделирования эволюции для популяции P(0) лучшее значение D=783, что соответствовало следующему выражению:

(*(Ї(ЇB₁L₂)(ЇB₂H₁))(+(ЇH₁H₁)(*H₁L₁))) или H₁L₁(B₁+H₁ЇB₂ЇL₂).

Видно, что в данном математическом выражении отсутствует переменная H₂ и оно мало похоже на корректное решение. Далее, лучшие значения D в популяциях P(1)-P(6) имели значения 778, 510, 138, 117, 53, 51 соответственно. Лучшая программа на восьмом этапе эволюции дала значение D, равное 4.44, что соответствовало LISP-выражению следующего вида: программирование генетический компьютерный

(Ї(Ї(*(*B₁H₁)L₁)(*(*L₂H₂)B₂))(%(+B₁L₁)(Ї(ЇL₁B₂)(+(+B₂L₂)(*L₂B₂)))))

или B₁H₁L₁ЇB₂H₂L₂Ї(B₁+L₁)/(L₁Ї2B₂ЇL₂ЇL₂B₂).

Видно, что, за исключением последнего ошибочного терма, данное выражение соответствует корректному решению. Наконец, на 11-м шаге эволюции была получена правильная программа вида:

(Ї(*(*B₁H₁)L₁)(*(*L₂H₂)B₂)) или L₁B₁H₁ЇL₂B₂H₂.

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

Эксперименты с использованием ADF для ранее рассмотренной задачи о параллелепипедах показали что с точки зрения вычислительной трудоемкости и структурной сложности преимущество за ГП без ADF.

Однако имеется целый ряд задач, свидетельствующих об обратном. Рассмотрим одну из них, связанную с проверкой на четность. Пусть булева функция, зависящая от пяти аргументов (D₀,D₁,D₂,D₃,D₄), принимает значение T, если четное число аргументов принимают значение «истина», в противном случае, булева функция принимает значение Nil (константа, обозначающая список, в котором нет ни одного элемента); 32 возможных комбинации аргументов служат основой для оценки ГП с ADF и без ADF.

Для ГП без ADF и с ADF устанавливаются одинаковые стартовые условия и параметры эволюции: функция соответствия определяется числом совпадений значений исходной функции со значениями, выдаваемыми ГП; м=16000; программа останавливается, если число совпадений равно 32.

Результаты моделирования однозначно свидетельствуют о преимуществе ГП с ADF как по структурной сложности решений, так и по вычислительной трудоемкости.

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

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

Обозначим через С_е(а_i) эффективную сложность программы a_i (i=1,2,…м), через С_a (a_i) абсолютную сложность программы а_i, через p_c - вероятность применения кроссинговера, а через p_d -вероятность того, что применение кроссинговера приведет к деструктивному эффекту, причем p_d=0, если кроссинговер проводится с интроном. Пусть Ф(a_i) - значение функции соответствия программы a_i; Ц(a_i)- среднее значение функций соответствия всех программ в популяции P(t). Если применяется пропорциональная селекция, то нижняя оценка A_i(t+1) «доли» программы a_i в популяции P(t+1) примерно равна

A_i(t+1) ? A_i(t)·Ц(a_i)/[Ц(t)]·(1Їp_c·С_е(а_i)·p_di/ С_a (a_i)) = A_i(t)·? Ц(a_i)Їp_c·Ц(a_i) С_е(а_i)·p_di/ С_a (a_i) ?,

где выражение в скобках представляет собой функцию Ц_e(a_i) эффективной сложности программы:

Ц_e(a_i) = Ц(a_i)Їp_c·Ц(a_i) С_е(а_i)·p_di/ С_a (a_i),

которая соответствует вкладу программы a_i в следующую популяцию P(t+1). Отсюда следует, что репродуктивные шансы некоторой программы a_i тем выше, чем меньше отношение между эффективной и абсолютной сложностью программы. Достигнуть этого можно двумя путями.

Первый заключается в увеличении абсолютной сложности путем добавления интронов, второй - в поиске простых решений. Эмпирические данные [1], подтверждают приведенные выше соображения:

на ранних этапах эволюции среднее значение целевой функции от популяции к популяции изменяется очень сильно, в то время как Ф_e изменяется относительно медленно;

несколько позднее темп изменения функции уменьшается, однако начинает расти соотношение между эффективной и абсолютной сложностью, «компрессионное давление» также возрастает, и Ф_e уменьшается;

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

Теоретически обоснованное и эмпирически наблюдаемое явление «компрессии» таит в себе опасность преждевременной сходимости ГП к субоптимальным решениям.

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

3. Эволюционное программирование и взаимодействие агентов

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

3.1 Концепция и направления развития эволюционного программирования

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

Рассмотрим стандартную форму ЭП-алгоритма. Пусть стоит задача минимизации функции F(а₁,…, а_n), зависящей от n непрерывных переменных: F: Rⁿ > R.

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

1) Инициализация. На этапе инициализации случайным образом генерируется популяция Р(0), состоящая из м особей В_i (i=1,2,…, м). Рекомендуемое значение размера популяции м?200. Значение элемента a_j для каждой особи В_i устанавливается случайно с помощьюравномерного распределения на интервале [l_j , r_j ] Є R, l_j < r_j . Границы интервала l_j , r_j имеют значение лишь на этапе инициализации. В ходе дальнейшей эволюции пространство поиска в принципе является неограниченным. Стандартная форма ЭП предполагает решение оптимизационной задачи, в которой оптимальное значение равно 0, l_j =Ї50, r_j =50.

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

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

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

3.1) Репликация путем копирования i-го родителя В_i=(а₁,…, а_n).

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

a?_j = a_j + sqrt(k_j •Ц(В_i) + z_j)•N_j (0, 1),

k_j -константа скалирования, Ц(В_i) -значение функции соответствия родителя, z_j -дисперсия, N_j (0, 1) -стандартная нормально распределенная величина, определяемая для каждого j=1,2,…n. Значения k_j , z_j (k_j, z_j ЄR₊) являются параметрами ЭП и устанавливаются пользователем. В общем случае, число этих параметров равно 2•n. Однако на практике устанавливают k_j=1, z_j=0 (j=1,2,…n). Тогда квадратный корень (sqrt) в формуле для вычисления a?_j упрощается и она принимает следующий вид:

a?_j = a_j + sqrt(Ц(В_i))•N_j (0, 1).

3.3) Оценка потомка происходит путем определения значения его функции соответствия Ц(В?_i)=Щ(F(В?_i), о_i.), после чего потомок добавляется в популяцию, причем В?_i > В?_м+i . При окончании этапа 3 размер популяции становится равным 2•м.

4) Случайная селекция. Селекция выполняется по соревновательному принципу, согласно которому каждый родитель или потомок попарно сравнивается с h противниками, причем hЄN (h?1) является параметром ЭП, устанавливается пользователем и обычно принимает значения от h=0.05м до h=0.1м. Противники выбираются случайно с помощью закона равномерного распределения. Победитель определяется путем попарного сравнения функций соответствия. Особь побеждает в соревновании, если ее функция соответствия по меньшей мере не хуже, чем у ее противника. Для представленной выше задачи минимизации число побед W_i i-ой особи (i=1,2,…2•м) определяется как W_i =?{1, если Ц(В_i)? Ц(В_d)}, причем суммирование ведется для d=1,2,…h и d?i является целочисленным значением равномерно распределенной в интервале [1, 2•м] случайной величины, которое для каждого d определяется заново. После этого все особи сортируются по убыванию числа побед (а не по значению функций соответствия). Лучшие особи образуют новую родительскую популяцию размером м. При одинаковом числе побед преимущество получает особь с лучшим значением функции соответствия. Очевидно, что при таком механизме селекции «слабые» особи имеют некоторую отличную от нуля вероятность репродукции. С ростом значения параметра h селекция начинает принимать дискриминационный элитарный характер.

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

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

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

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

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

В отличие от генетических алгоритмов, ЭП является относительно малоисследованной парадигмой моделирования эволюции. Из теоретических результатов внимания заслуживает доказательство асимптотической сходимости рассмотренной выше стандартной формы ЭП [10], основанное на теории марковских цепей. Доказательство приводится для случая, когда параметры k_j , z_j принимают значение 1 и 0 соответственно, а также справедливо Ц(В_i)=F(В_i)>0. Представляется, что математический аппарат марковских цепей как модель описания стохастических процессов вполне подходит в качестве одной из фундаментальных основ для формирования единой концепции эволюционных вычислений. С помощью марковских цепей можно обосновать эффективность эволюционного процесса.

Одним из перспективных направлений практического развития идей ЭП является преодоление следующих проблем:

(1) Если глобальный оптимум функции соответствия отличается от 0, то это негативно влияет на устойчивость ЭП;

(2) Если значения функции соответствия являются очень большими, то поиск становится квазислучайным;

(3) Если пользователь не обладает информацией о глобальном оптимуме, то согласование и подбор функции скаляризации Щ становится затруднительным;

(4) Необходимость установки 2•n значений параметров эволюции k_j и z_j выдвигает перед пользователем дополнительные оптимизационные трудности, даже если он использует стандартную установку (k_j =1, z_j =0).

Преодоление этих недостатков стандартной формы ЭП требует ее модификации с целью повышения адаптивных свойств ЭП. Рассмотрим возможные модификации ЭП в этом направлении.

Пусть популяция составляется не из векторов В_i (i=1,2,…, м), а из векторов З_i = (В_i , ы_i ), где ы_i - вектор среднеквадратичного отклонения, элементы которого u_j Є R₊ (j=1,2,…n). Тогда речь может идти о следующих отличиях модифицированной ЭП от рассмотренных ранее этапов стандартной формы ЭП.

На этапе инициализации для каждого вектора В_i дополнительно образуется вектор ы_i на основе равномерного распределения в интервале [0, в], где в>0 является параметром эволюции (рекомендуемое значение в=25), который требует адаптации к каждому конкретному классу задач. На этапе генерации потомков отличие состоит в операторе мутации. В частности, потомок З'_i = (В'_i , ы'_i ), где u'_j = u_j + u_jбN_j (0,1), a'_j = a_j + u'_jN_j (0,1). Отметим, что, если коэффициент б выбрать слишком большим, то величина u'_j может стать отрицательной и тогда она заменяется на некоторое малое е>0, что несколько противоречит идее адаптации. Если б выбрать слишком малым, то проявляется тенденция замедления эволюции. Рекомендуемое значение б=1/6 [Fog92a]. Заслуживает внимания и другая идея. Речь идет о программируемой мутации путем с использованием ковариационной матрицы, составленной из коэффициентов корреляции и подробно рассмотренной в [11] применительно к другой парадигме моделирования эволюции - эволюционным стратегиям.

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

3.2 Прикладные аспекты эволюционного программирования

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

В частности, одним из наиболее объективных средств тестирования эволюционных алгоритмов для NP-полных комбинаторных проблем является задача о коммивояжере [7]. Приведем результаты тестирования ЭП для задачи о коммивояжере, предусматривающей обход 100 городов.

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

1 -- (длина цикла особи/сумма длин циклов оцениваемой особи и контрагента).

Это означает, что у слабой особи имеется некоторый шанс победить в соревновании. Затем популяция из 100 особей сокращалась до 50 особей, имевших наибольшее число побед, после чего цикл эволюции повторялся вновь до останова. Сравнение полученных результатов с генетическим алгоритмом на основе PMX-операторов [10] о некотором преимуществе ЭП.

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

Эта задача служит неплохой моделью конфликтной ситуации, в которой интересы игроков (агентов) хотя и различны, но не являются антагонистическими. Игроками считаются два узника, находящиеся в предварительном заключении по подозрению в совершении преступления. При отсутствии прямых улик возможность их осуждения в значительной степени зависит от того, заговорят они или будут молчать. Если оба будут молчать, наказанием будет лишь срок предварительного заключения (потери каждого из узников составят 1 год). Если оба сознаются, то получат срок, учитывающий признание как смягчающее обстоятельство (потери каждого из узников в этом случае составят 3 года). Если же заговорит только один из узников, а другой будет молчать, то заговоривший будет выпущен на свободу (его потери равны 0), а сохранивший молчание получит максимально возможное наказание (его потери будут равны 5 лет). Эта конфликтная ситуация приводит к игре, в которой каждый из игроков имеет по две стратегии -- молчать (М) или говорить (Г). Потери игроков описываются матрицей следующего вида:

Таблица 2

	М	Г
М	(1,1)	(5,0)
Г	(0,5)	(3,3)

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

Задачей ЭП является поиск такой игровой стратегии, которая позволит минимизировать средние потери при многократном повторении игровой ситуации. Следуя [Fog66], можно представить каждую совместную игровую стратегию одним из состояний конечного автомата. Множество возможных входных сигналов автомата при символьном представлении равно {(м/м), (м/г), (г/м), (г/г)}. Множеством выходов автомата являются символы {м, г}.

В ходе эксперимента размер исходной популяции м=50, число ходов в игре -- не менее 150, число состояний, переходы состояний, первый ход, а также выход автомата устанавливаются случайно. Каждый автомат копировался, над ним производилась мутация на базе равномерного распределения. В дальнейшем каждый автомат попарно сравнивался с 99 другими, причем в качестве функции соответствия выбирались ожидаемые средние потери. Хотя в игре возможна стохастическая селекция, предпочтительнее применять детерминированный отбор, согласно которому из 100 автоматов выбирались 50 лучших. Критерием останова в данной задаче являлось значение t_max =200. В табл. 2 в качестве иллюстрации приводится список возможных автоматных состояний и переходов между состояниями, полученный в ходе работы ЭП-алгоритма для задачи «дилемма узника».

Таблица 3 Переходы состояний автомата для задачи «дилемма узника»

Состояние	S0	S1	S2	S3	S4	S5	S6	S7
Переходы состояний	г,г/г,S0 м,г/г,S1 м,м/м,S3 г,м/г,S6	м,г/м,S1 г,м/г,S3 г,г/м,S3 м,м/г,S4	м,м/г,S1 м,г/г,S1 г,г/м,S3 м,м/м,S4	м,г/г,S2 м,м/м,S2 г,г/г,S5 г,м/м,S6	м,г/г,S1 г,г/м,S1 м,м/м,S2 г,м/м,S7	м,м/г,S2 г,м/м,S3 м,г/г,S5 г,г/г,S5	г,г/г,S5 м,м/г,S6 г,м/м,S7	м,м/г,S1 г,м/м,S3 г,г/м,S6 м,г/м,S8

Здесь S₀ - это стартовое состояние, входом которого являлось решение узника говорить («г»), а, например, запись в столбце S₄ (г,г/м, S₂ ) означает, что узник на очередном ходе принял решение говорить, на предыдущем ходе использовалась стратегия г/м, автомат из состояния S₄ переходит в состояние S₂. Эксперименты с автоматами показали, что примерно в течение первых 20 ходов преобладает стратегия молчания, хотя уже после 5-10 ходов начинает встречаться стратегия кооперативного поведения, которая в дальнейшем однозначно становится доминирующей.

Литература

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

2. Nissen V. Einfьhrung in evolutionдre algorithmen. -- Braunschweig: Vieweg, 1997.

3. Wolpert D.H., Macready W.G. No free lunch theorems for search // Operations research: Santa Fe Institute, 1995.

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

5. Родзин С.И. Параллельные нейроэволюционные вычисления // Известия НАН Украины. Искусственный интеллект. --Донецк: Наука i ocвiта, 2003. №4. С. 485-492.

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

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

8. Nordin P., Banzhaf W. Evolving turing-complete programs for a register machine with self-modifying code// Proc. of the sixth inter. conf. on genetic Programming. San Francisko: Morgan Kaufmann, 1995.

9. Fogel L.J., Owens A.J., Walsh M.J. Artificial Intelligence through simulated evolution. N.Y.: J.Wiley&Sons, 1966.

10. Fogel D.B. Evolutionary Computation. Toward a New Philosophy of Machine Intelligence. -- N.Y.: IEEE Press, 1995.

11. 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.

Размещено на Allbest.ru

...