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

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

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

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

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

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

1. сообщество (корпорация, корпоративные объекты, субъекты, окружение);
2. видовое разнообразие и распределение в экологической нише (типы распределения ресурсов, структура связей в данной корпорации);
3. экологическая ниша (сфера влияния и функционирования, эволюции на рынке, в бизнесе);
4. рождаемость и смертность (производство и разрушение);
5. изменчивость (экономической обстановки, ресурсов);
6. конкурентные взаимоотношения (рыночные отношения);
7. память (способность к циклам воспроизводства);
8. естественный отбор (штрафные и поощрительные меры);
9. наследственность (производственные циклы и их предыстория);
10. регуляция (инвестиции);
11. самоорганизация и стремление системы в процессе эволюции максимизировать контакт с окружением в целях самоорганизации, возврата на траекторию устойчивого развития и другие.

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

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

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

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

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

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

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

Важными для задач моделирования являются три значения s⁽ⁱ⁾_max, s⁽ⁱ⁾_min, s⁽ⁱ⁾_opt - максимальные, минимальные и оптимальные значения активности i-й подсистемы, а также аналогичные значения для всей системы (s_max, s_min, s_opt). В качестве показателя экономического состояния можно брать также отношение значения этого показателя к его нормированному значению, а для комплексного учета влияния параметров на состояние системы можно использовать аналоги меры информационной близости, например, по К. Шеннону.

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

ΔН=Н₀-Н₁.

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

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

H=|(F_max - F_min)/(F_max+F_min)|,F_max=max F(u_opt, s_max), F_min=min F(u_opt, s_min), t [t₀;T], s [s_min;s_max].

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

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

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

1. периодичности, цикличности, например:

( 0<T<∞, t: ⁽ⁱ⁾(s; s⁽ⁱ⁾, t)= ⁽ⁱ⁾(s; s⁽ⁱ⁾, t+T), ⁽ⁱ⁾(s; s⁽ⁱ⁾, t)= ⁽ⁱ⁾(s; s⁽ⁱ⁾, t+T));

1. затухания при снижении активности, например:

(s(x) 0 i=1, 2, ..., n) => ( ⁽ⁱ⁾ 0, ⁽ⁱ⁾ 0);

1. равновесности и стационарности: выбор (определение) функции ⁽ⁱ⁾, ⁽ⁱ⁾ осуществляется таким образом, чтобы система имела точки равновесного состояния, а s⁽ⁱ⁾_opt, s_opt достигались в стационарных точках x⁽ⁱ⁾_opt, x_opt для малых промежутков времени; в больших промежутках времени система может (в соответствии с теорией катастроф) вести себя хаотично, самопроизвольно порождая регулярные, упорядоченные, циклические взаимодействия (детерминированный хаос).

Взаимные активности ^(ij)(s; s⁽ⁱ⁾, s^(j), t) подсистем i и j мы не учитываем. В качестве функции ⁽ⁱ⁾, ⁽ⁱ⁾ могут быть эффективно использованы производственные функции типа Кобба-Дугласа:

В таких функциях важен параметр _i, отражающий степень саморегуляции, адаптации системы. Как правило, его нужно идентифицировать.

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

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

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

Пример. Пусть имеется некоторая социально-экономическая среда, которая возобновляет с коэффициентом возобновления (τ,t,x) (0<t<T, 0<x<1, 0<τ<T) свои ресурсы. Этот коэффициент зависит, в общем случае, от мощности среды (ее ресурсоемкости, ресурсообеспеченности). Рассмотрим простую гипотезу: (τ,t,x)= ₀+ ₁x, и чем больше ресурсов - тем больше темп их возобновления. Можно записать непрерывную эволюционную модель (a - коэффициент естественного прироста ресурсов, b - их убыли):

Обозначим (τ)= ₀(τ)+ ₁(τ)x(τ)>0. Тогда

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

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

Пример. Пусть u_max - максимальный уровень синтаксических ошибок в программе Р, u(t) - их оставшееся количество к моменту времени t. Исходя из простейшей эволюционной модели du/dt+λu_max=0, u(t₀)=u₀, можно заключить, что уровень ошибок убывает при λ(c-t₀) -1 (t₀<c<T) по закону: u(t) = u₀(1+ λ(c-t))/(1+λ(c-t₀)). Если задать дополнительно u(t_*)=u_*, (u_max - неизвестная величина, t_* t₀), то закон изменения уровня ошибок находится однозначно, так как: с=(u_* t₀ - u₀t_*)/(λu_* - λu₀ ) -1/λ.

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

ds/dt = ds₁/dt + ds₂/dt.

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

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

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

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

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

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

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

где v_ij - весовой коэффициент, определяющий степень влияния загрязнителя x_i на загрязнитель x_j (эффект суммирования), h_j - весовой коэффициент, учитывающий удельную интенсивность действия загрязнителя x_j или интервал τ_i, в течение которого уменьшается интенсивность (концентрация) загрязнителя. Весовые коэффициенты устанавливаются экспертно или экспериментально.

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

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

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

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

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

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

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

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

кц

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

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

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

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

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

Вопросы для самоконтроля

1. Что такое эволюционное моделирование? Каковы критерии эффективности при эволюционном моделировании? Для какого типа прогнозирования (по длительности) используется и является эффективным эволюционное моделирование?
2. Что такое генетический алгоритм?
3. Каковы основные общие и различные свойства генетических и "не генетических" алгоритмов?

Задачи и упражнения