ГЛАВА 5. ПРОГНОЗ МАКРОСОСТОЯНИЙ: ЭВОЛЮЦИОННОЕ МОДЕЛИРОВАНИЕ

Дальше

Назад

Начало

Конец

Список

5.2. ЭВОЛЮЦИОННОЕ МОДЕЛИРОВАНИЕ
Смысла нет перед будущим дверь запирать,
Смысла нет между злом и добром выбирать.
Небо мечет вслепую игральные кости.
Все, что выпало, надо успеть проиграть.

Омар Хайям

Эволюционное моделирование (Фогель и др., 1969; Букатова, 1979; Розенберг, 1984; Брусиловский, 1987) представляет собой существенно машинный (т.е. ориентированный на использование ЭВМ), универсальный способ построения прогнозов макросостояний системы в условиях, когда полностью отсутствует апостериорная информация, а априорные данные задают лишь предысторию этих состояний. Одним из первых на возможность применения эволюционного моделирования для целей экологического прогнозирования указал В.Ф.Крапивин (1978, с.98-99). В дальнейшем, эти подходы использовались для прогнозирования величины прироста деревьев (Розенберг, 1984) и состояний байкальского планктона (Брусиловский, 1987).

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

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

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

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

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

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

Конкретное функционирование автомата по этой предыстории выглядит следующим образом:

предъявляем первый символ 0 предыстории начальному состоянию А, при этом автомат по дуге 0/0 переходит в состояние С, синтезируя на выходе символ 0;

второй символ предыстории 0 предъявляется уже состоянию С, в результате чего по дуге 0/0 осуществляется переход в состояние В и генерация символа 0;

третий символ предыстории 1 оставляет автомат в состоянии В и генерирует символ 0.

Продолжая предъявлять символы предыстории, получаем последовательность выходных символов (см.табл. 5.1).

Таблица 5.1

Результаты функционирования автомата, представленного на рис. 5.1а, по предъявленной предыстории

П а р а м е т р ы	Этапы работы автомата
Последовательность состояний	А	С	В	В	В	В	В	В	С	А	А
Предыстория (входной символ)	0	0	1	1	1	1	1	0	1	1
Последовательность выходных символов		0	0	0	0	0	0	0	1	1	1
Ошибка предсказания		0	1	1	1	1	1	0	0	0

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

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

Интенсивность каждого режима мутации задается некоторым распределением его вероятности. При этом, в классическом варианте эволюционного моделирования распределение вероятностей остается неизменным. А.Г.Ивахненко с соавторами (1976, с.92) отмечают, что "...поиск структуры механизма мутаций является чисто случайным, нецеленаправленным. Это, естественно, приводит к затягиванию процесса эволюционного развития по сравнению с процессом адаптации (целенаправленного обучения)". Этот недостаток легко исправляется путем применения, например, алгоритмов случайного поиска с адаптацией (Лбов,1965), когда возрастает вероятность "удачных" мутаций (автомат-потомок лучше автомата-родителя) и, соответственно, уменьшается вероятность "неудачных".

Эволюционный процесс может быть остановлен, например, по выполнению одного из трех условий:

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

Была предложена модификация процесса построения эволюционной модели (Брусиловский, Розенберг, 1981; Брусиловский, 1987), которая имеет одно существенное отличие от традиционных процедур эволюционного моделирования. В ней использован принцип внешнего дополнения в том же виде, в каком он используется в алгоритмах МГУА. Исходная информация делится на две части - обучающую и проверочную последовательности. По первой из них строится конечный автомат эволюционного моделирования, и после каждой мутации, если результаты прогноза обучающей последовательности не ухудшились, качество автомата-потомка оценивается на проверочной последовательности. Естественно, что поиск "лучшего" автомата при этом несколько удлиняется, однако достигается более высокая точность прогнозирования.

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

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

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

Таблица 5.2

Cимвол обучающей последователь-ности (состояние А)	Прогноз коллектива автоматов ("атомы прогноза")
Cимвол обучающей последователь-ности (состояние А)	000	001	010	011	100	101	110	111
0	p ₀₀₀	p ₀₀₁	p ₀₁₀	p ₀₁₁	p ₁₀₀	p ₁₀₁	p ₁₁₀	p ₁₁₁
1	q ₀₀₀	q ₀₀₁	q ₀₁₀	q ₀₁₁	q ₁₀₀	q ₁₀₁	q ₁₁₀	q ₁₁₁

Тогда для выборок малого объёма байесовская оценка вероятности получить фактический символ обучающей последовательности (А) в случае реализации одного из "атомов прогноза" (ijk) будет (Брусиловский, 1987, с.37):

Р(А/ijk) = (p_ijk+ 1)/( p_ijk + q_ijk + 2),

где p и q - число испытаний, в котором наступило событие А при реализации "атома" (ijk). На этапе эксплуатации алгоритма предсказывается состояние А очередного макросостояния, если значение Р(А/ijk) > 0,5.

Дальше

Назад

Начало

Конец

Список