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

Украинский государственный

 

химико-технологический  университет

 

 

Реферат

 

ДИСЦИПЛИНА «Моделирование систем»

 

Эволюционное моделирование  и

генетические алгоритмы

 

 

 

 

 

 

                      Выполнил студент 3 курса, группы 3-СКС

                      Томилов Н.В.

 

 

 

 

 

 

Днепропетровск

2012 год 

 

 

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

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

Потребность в прогнозе и  адекватной оценке последствий осуществляемых

человеком мероприятий (особенно негативных) приводит к необходимости

моделирования динамики изменения  основных параметров системы, динамики

взаимодействия открытой системы  с его окружением (ресурсы, потенциал, условия,

технологии и т.д.), с которым  осуществляется обмен ресурсами  в условиях враждебных,

конкурентных, кооперативных или  же безразличных взаимоотношений.

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

Если критерии первого  типа важны, например, для кратко- и  среднесрочного

прогнозирования и тактического администрирования, то второго типа - для средне- и

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

выделить и изучить достаточно полную и информативную систему  параметров

исследуемой системы и его окружения, разработать методику введения мер

информативности и близости состояний  системы. Важно отметить, что при  этом

некоторые критерии и меры могут  часто конфликтовать друг с другом.

Многие такие социально-экономические  системы можно описывать с  единых

позиций, средствами и методами единой теории - эволюционной.

При эволюционном моделировании процесс моделирования сложной социально-

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

допустимых состояний системы, к процедуре (алгоритму) отслеживания множества

допустимых состояний (траекторий). При этом актуализируются такие  атрибуты

биологической эволюционной динамики (в скобках даны возможные социально-

экономические интерпретации этих атрибутов для эволюционного моделирования) как,

например:

 

1. сообщество (корпорация, корпоративные  объекты, субъекты, окружение);

2. видовое разнообразие  и распределение в экологической  нише (типы

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

3. экологическая ниша (сфера  влияния и функционирования, эволюции  на

рынке, в бизнесе);

4. рождаемость и смертность (производство и разрушение);

5. изменчивость (экономической  обстановки, ресурсов);

6. конкурентные взаимоотношения  (рыночные отношения);

7. память (способность к  циклам воспроизводства);

8. естественный отбор  (штрафные и поощрительные меры);

9. наследственность (производственные  циклы и их предыстория);

10. регуляция (инвестиции);

11. самоорганизация и стремление  системы в процессе эволюции

максимизировать контакт  с окружением в целях самоорганизации, возврата

на траекторию устойчивого  развития и другие.

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

с целью обеспечения:

1. эффективного взаимодействия  с окружением;

2. оптимального обмена определяющими материальными, энергетическими,

информационными, организационными ресурсами  с подсистемами;

3. эволюционируемости системы в условиях динамической смены и

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

4. управляемости системы, идентификации  управляющей подсистемы и

эффективных связей с подсистемами системы, обратной связи.

Пусть имеется некоторая система 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 s 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) должны отражать эволюционируемость системы, в

частности, удовлетворять условиям:

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

1. ( 0<T<∞, t: (i)(s; s(i), t)= (i)(s; s(i), t+T),

2. (i)(s; s(i), t)= (i)(s; s(i), t+T));

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

4. (s(x) 0 i=1, 2, ..., n) => ( (i) 0, (i) 0);

5. равновесности и стационарности: выбор (определение) функции (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)= 0+ 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, тем

быстрее (медленнее) осуществимы социо-экономические мероприятия по его