Эволюционное моделирование и генетические алгоритмы

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

Многие такие социально-экономические системы можно описывать с единых позиций, средствами и методами единой теории - эволюционной.

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

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

При исследовании эволюции системы необходима ее декомпозиция на подсистемы с целью обеспечения:

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

Пусть имеется некоторая система S с N подсистемами. Для каждой i-й подсистемы определим вектор x(i)=(x1(i),x2(i),:,xni(i)) основных параметров (т.е. параметров, без которых нельзя описать и изучить функционирование подсистемы в соответствии с целями и доступными ресурсами системы) и функцию s(i)=s(x(i)), которую назовем функцией активности или просто активностью этой подсистемы.

Пример. В бизнес-процессах это понятие близко к понятию деловой активности.

Для всей системы определены вектор состояния системы x и активность системы s(x), а также понятие общего потенциала системы.

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

Эти функции отражают интенсивность процессов как в подсистемах, так и в системе в целом.

Важными для задач моделирования являются три значения s(i)max, s(i)min, s(i)opt - максимальные, минимальные и оптимальные значения активности i-й подсистемы, а также аналогичные значения для всей системы (smax, smin, sopt). В качестве показателя экономического состояния можно брать также отношение значения этого показателя к его нормированному значению, а для комплексного учета влияния параметров на состояние системы можно использовать аналоги меры информационной близости, например, по К. Шеннону.

Если дана открытая экономическая система (процесс), а Н0, Н1 - энтропия системы в начальном и конечном состояниях процесса, то мера информации определяется как разность вида:

?Н=Н0-Н1.Уменьшение ?Н свидетельствует о приближении системы к состоянию статического равновесия (при доступных ресурсах), а увеличение - об удалении.

Величина ?Н - количество информации, необходимой для перехода от одного уровня организации системы к другой (при ?Н>0 - более высокой, при ?Н<0 - более низкой организации).

Возможен подход и с использованием меры по Н. Моисееву. Пусть дана некоторая управляемая система, о состояниях которой известны лишь некоторые оценки - нижняя smin и верхняя smax. Известна целевая функция управления F(s(t),u(t)), где s(t) - состояние системы в момент времени t, а u(t) - управление из некоторого множества допустимых управлений, причем считаем, что достижимо uopt - некоторое оптимальное управление из пространства U, t0<t<T, smin

smax. Мера успешности принятия решения:

H=|(Fmax - Fmin)/(Fmax+Fmin)|,Fmax=max F(uopt, smax), Fmin=min F(uopt, smin), t

[t0;T], s

[smin;smax].Увеличение Н свидетельствует об успешности управления системой (успешности принятого управляющего решения).

Активности подсистем прямо или опосредованно взаимодействуют с помощью системной активности s(x), например, по простой схеме вида

Функции j(i), y(i) должны отражать эволюционируемость системы, в частности, удовлетворять условиям:

периодичности, цикличности, например: (
0<T<?,
t:
(i)(s; s(i), t)=
(i)(s; s(i), t+T),
(i)(s; s(i), t)=
(i)(s; s(i), t+T));
затухания при снижении активности, например: (s(x)
0
i=1, 2, ..., n) => (
(i)
0,
(i)
0);
равновесности и стационарности: выбор (определение) функции
(i),
(i) осуществляется таким образом, чтобы система имела точки равновесного состояния, а s(i)opt, sopt достигались в стационарных точках x(i)opt, xopt для малых промежутков времени; в больших промежутках времени система может (в соответствии с теорией катастроф) вести себя хаотично, самопроизвольно порождая регулярные, упорядоченные, циклические взаимодействия (детерминированный хаос).

Взаимные активности

(ij)(s; s(i), s(j), t) подсистем i и j мы не учитываем. В качестве функции

(i),

(i) могут быть эффективно использованы производственные функции типа Кобба-Дугласа:

В таких функциях важен параметр

i, отражающий степень саморегуляции, адаптации системы.

Как правило, его нужно идентифицировать.

Функционирование системы удовлетворяет на каждом временном интервале (t; t+?) ограничениям вида

При этом отметим, что выполнение для ?>0 одного из двух условий

приводит к разрушению (катастрофе) системы.

Пример. Пусть имеется некоторая социально-экономическая среда, которая возобновляет с коэффициентом возобновления

(?,t,x) (0<t<T, 0<x<1, 0<?<T) свои ресурсы. Этот коэффициент зависит, в общем случае, от мощности среды (ее ресурсоемкости, ресурсообеспеченности). Рассмотрим простую гипотезу:

(?,t,x)=

1x, и чем больше ресурсов - тем больше темп их возобновления. Можно записать непрерывную эволюционную модель (a - коэффициент естественного прироста ресурсов, b - их убыли):

Обозначим

(?)=

0(?)+

1(?)x(?)>0. Тогда

Задача всегда имеет решение x

0. Тогда эволюционный потенциал системы можно определить как величину:

Чем выше темп

- тем выше ?, чем меньше

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

Пример. Пусть umax - максимальный уровень синтаксических ошибок в программе Р, u(t) - их оставшееся количество к моменту времени t. Исходя из простейшей эволюционной модели du/dt+?umax=0, u(t0)=u0, можно заключить, что уровень ошибок убывает при ?(c-t0)

-1 (t0<c<T) по закону: u(t) = u0(1+ ?(c-t))/(1+?(c-t0)). Если задать дополнительно u(t*)=u*, (umax - неизвестная величина, t*

t0), то закон изменения уровня ошибок находится однозначно, так как: с=(u* t0 - u0t*)/(?u* - ?u0 ) -1/?.

Отметим, что если ds/dt - общее изменение энтропии системы при воздействии на систему, ds1/dt - изменение энтропии за счет необратимых изменений структуры, потоков внутри системы (рассматриваемой как открытая система), ds2/dt - изменение энтропии за счет усилий по улучшению обстановки (например, экономической, экологической, социальной), то справедливо уравнение И. Пригожина:

ds/dt = ds1/dt + ds2/dt.При эволюционном моделировании социально-экономических систем полезно использовать и классические математические модели, и неклассические, в частности, учитывающие пространственную структуру системы (например, клеточные автоматы и фракталы), структуру и иерархию подсистем (например, графы и структуры данных), опыт и интуицию (например, эвристические, экспертные процедуры).

Пример. Пусть дана некоторая экологическая система ?, в которой имеются точки загрязнения (выбросов загрязнителей) xi, i=1, 2, :, n. Каждый загрязнитель xi загрязняет последовательно экосистему в промежутке времени (ti-1; ti], ti=ti-ti-1. Каждый загрязнитель может оказать воздействие на активность другого загрязнителя (например, уменьшить, нейтрализовать или усилить по известному эффекту суммирования воздействия загрязнителей). Силу (меру) такого влияния можно определить через rij, R={rij: i=1,2,:, n-1; j=2,3,:, n}.

Структура задаётся графом: вершины - загрязнители, ребра - меры.

Найдём подстановку минимизирующую функционал вида:

где F - суммарное загрязнение системы с данной структурой S.

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

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

где vij - весовой коэффициент, определяющий степень влияния загрязнителя xi на загрязнитель xj (эффект суммирования), hj - весовой коэффициент, учитывающий удельную интенсивность действия загрязнителя xj или интервал ?i, в течение которого уменьшается интенсивность (концентрация) загрязнителя. Весовые коэффициенты устанавливаются экспертно или экспериментально.

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

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

Адекватным средством реализации процедур эволюционного моделирования являются генетические алгоритмы.

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

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

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

Пример. Рассмотрим задачу безусловной целочисленной оптимизации (размещения): найти максимум f(i), i - набор из n нулей и единиц, например, при n=5, i=(1,0,0,1,0). Это очень сложная комбинаторная задача для обычных, "негенетических" алгоритмов. Генетический алгоритм может быть построен следующей укрупненной процедурой:

генерируем начальную популяцию (набор допустимых решений задачи) - I0=(i1, i2, :, in), ij
{0,1} и определяем некоторый критерий достижения "хорошего" решения, критерий остановки
, процедуру СЕЛЕКЦИЯ, процедуру СКРЕЩИВАНИЕ, процедуру МУТАЦИЯ и процедуру обновления популяции ОБНОВИТЬ;
k:=0, f0:=max{f(i), i
I0};
нц пока не(
)
1. с помощью вероятностного оператора (селекции) выбираем два допустимых решения (родителей) i1, i2 из выбранной популяции (вызов процедуры СЕЛЕКЦИЯ);
2. по этим родителям строим новое решение (вызов процедуры СКРЕЩИВАНИЕ) и получаем новое решение i;
3. модифицируем это решение (вызов процедуры МУТАЦИЯ);
4. если f0<f(i) то f0:=f(i);
5. обновляем популяцию (вызов процедуры ОБНОВИТЬ);
6. k:=k+1
кц

Указанные процедуры определяются с использованием аналогичных процедур живой природы (на том уровне знаний о них, что мы имеем). Например, процедура СЕЛЕКЦИЯ может из случайных элементов популяции выбирать элемент с наибольшим значением f(i).

Процедура СКРЕЩИВАНИЕ (кроссовер) может по векторам i1, i2 строить вектор i, присваивая с вероятностью 0,5 соответствующую координату каждого из этих векторов-родителей. Это самая простая процедура. Используют и более сложные процедуры, реализующие более полные аналоги генетических механизмов. Процедура МУТАЦИЯ также может быть простой или сложной. Например, простая процедура с задаваемой вероятностью для каждого вектора меняет его координаты на противоположные (0 на 1, и наоборот). Процедура ОБНОВИТЬ заключается в обновлении всех элементов популяции в соответствии с указанными процедурами.

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

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

алг ГЕНЕТИЧЕСКИЙ_АЛГОРИТМ_БАНКОВСКОЙ_СИСТЕМЫ ввод Начальная структура банка (начальная популяция); СТРУКТУРА | процедура оценки структуры по приспособлению Стоп:=0 | флаг для завершения эволюционного процесса нц пока (Стоп=0) СЕЛЕКЦИЯ | процедура генетического отбора нового поколения нц пока (МЕРА) | цикл воспроизводства с критерием МЕРА | мерой эффективности банковской системы РОДИТЕЛИ | процедура выбора двух структур (филиалов) | объединяемых (скрещиваемых) на новом шаге ОБЪЕДИНЕНИЕ | процедура образования (объединения) | нового банка (филиала) ОЦЕНКА | процедура оценки устойчивости нового банка, | образования (рейтинга, устойчивости) ВКЛЮЧЕНИЕ | процедура включения (не включения) в новое | поколение (в банковскую систему) кц МУТАЦИЯ | процедура эволюции (мутации) нового поколения если (ПРОЦЕСС) | проверка функционала завершаемости эволюции то Стоп:=1 кц кон.Мы не конкретизируем структуру процедур СЕЛЕКЦИЯ, МЕРА, РОДИТЕЛИ, ОБЪЕДИНЕНИЕ, ОЦЕНКА, ВКЛЮЧЕНИЕ, МУТАЦИЯ, ПРОЦЕСС, хотя даже на интуитивном уровне ясно, что в этом алгоритме они играют решающую роль для эволюционного процесса. Не менее важен и правильный (эффективный) выбор структуры, а также представления (описания) этой структуры. Часто ее выбирают по аналогии со структурой хромосом, например, в виде битовых строк. Каждая строка (хромосома) представляет собой конкатенацию ряда подстрок (генная комбинация). Гены располагаются в различных позициях строки (локусах хромосомы). Они могут принимать некоторые значения (аллели), например, для битового представления - 0 и 1. Структура данных в генетическом алгоритме (генотип) отражает генетическую модель особи.

Окружающая среда, окружение определяется вектором в пространстве параметров и соответствует термину "фенотип". Мера качества (процедура МЕРА) структуры часто определяется целевой функцией (приспособленности). Для каждого нового поколения генетический алгоритм осуществляет отбор пропорционально приспособленности (процедура ОТБОР), модификацию (процедуры РОДИТЕЛИ, ОБЪЕДИНЕНИЕ, ВКЛЮЧЕНИЕ) и мутацию (процедура МУТАЦИЯ). Например, в процедуре ОТБОР каждой структуре ставится в соответствие отношение ее приспособленности к суммарной приспособленности популяции и затем происходит отбор (с замещением) всех особей для дальнейшей генетической обработки в соответствии с этой величиной. Размер отбираемой комбинации можно брать пропорциональным приспосабливаемости, и поэтому особи (кластеры) с более высокой приспособленностью с большей вероятностью будут чаще выбираться, чем особи с низкой приспособленностью. После отбора выбранные особи подвергаются кроссоверу (рекомбинации), т.е. разбиваются на пары. Для каждой пары может применяться кроссовер. Неизмененные особи переходят к стадии мутации. Если кроссовер происходит, полученные потомки заменяют собой родителей и переходят к мутации.

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

Содержание раздела