Введение в анализ, синтез и моделирование систем

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),   (i)(s; s(i), t)=  (i)(s; s(i), t+T));

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

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

3. равновесности и стационарности: выбор (определение) функции (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. Тогда

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

Чем выше темп - тем выше λ, чем меньше - тем ниже λ. Каким бы хорошим ни было состояние ресурсов в начальный момент, они неизменно будут истощаться, если потенциал системы меньше 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). Это очень сложная комбинаторная задача для обычных, "негенетических" алгоритмов. Генетический алгоритм может быть построен следующей укрупненной процедурой:

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

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