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

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

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

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

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

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

  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.

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

Вероятен подход и с внедрением меры по Н. Моисееву. Пусть дана некая управляемая система, о состояниях которой известны только некие оценки - нижняя smin и Лекция: Эволюционное моделирование и генетические алгоритмы верхняя smax. Известна мотивированная функция управления F(s(t),u(t)), где s(t) - состояние системы в момент времени t, а u(t) - управление из некого огромного количества допустимых управлений, при этом считаем, что достижимо uopt - некое наилучшее управление из места U, t0 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
  • затухания при понижении активности, к примеру:
  • (s(x) 0 i Лекция: Эволюционное моделирование и генетические алгоритмы=1, 2, ..., n) => ( (i) 0, (i) 0);
    1. равновесности и стационарности: выбор (определение) функции (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 1-го из 2-ух критерий

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

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

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

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

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

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

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

    кц

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

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

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

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

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

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

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

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


    lekciya-9-povedenie-firmi-v-usloviyah-oligopolii.html
    lekciya-9-pyatij-period-evolyucii-ot-ravnih-prav-k-ravnim-vozmozhnostyam-ot-institucializacii-k-integracii.html
    lekciya-9-socialnaya-politika-gosudarstva.html