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

нейтрализации (усилению воздействия). Чем меньше будет загрязнителей  до загрязнителя

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 - нц пока не( )

a. с помощью вероятностного оператора  (селекции) выбираем два

допустимых решения (родителей) i1, i2 из выбранной популяции

(вызов процедуры СЕЛЕКЦИЯ);

b. по этим родителям строим  новое решение (вызов процедуры

СКРЕЩИВАНИЕ) и получаем новое решение i;

c. модифицируем это решение (вызов  процедуры МУТАЦИЯ);

d. если f0<f(i) то f0:=f(i);

e. обновляем популяцию (вызов  процедуры ОБНОВИТЬ);

f. k:=k+1

4 - кц

Указанные процедуры определяются с использованием аналогичных процедур

живой природы (на том уровне знаний о них, что мы имеем). Например, процедура

СЕЛЕКЦИЯ может из случайных  элементов популяции выбирать элемент  с наибольшим

значением f(i). Процедура СКРЕЩИВАНИЕ (кроссовер) может по векторам i1, i2

строить вектор i, присваивая с вероятностью 0,5 соответствующую координату каждого

из этих векторов-родителей. Это  самая простая процедура. Используют и более сложные

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

МУТАЦИЯ также может быть простой  или сложной. Например, простая процедура  с

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

противоположные (0 на 1, и наоборот). Процедура ОБНОВИТЬ заключается  в обновлении

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

Пример. Работу банка можно моделировать на основе генетических алгоритмов. С

их помощью можно выбирать оптимальные  банковские проценты (вкладов, кредитов)

некоторого банка в условиях конкуренции с тем, чтобы привлечь больше клиентов

(средств). Тот банк, который сможет  привлечь больше вкладов, клиентов  и средств, и

выработает более привлекательную  стратегию поведения (эволюции) - тот  и выживет в

условиях естественного отбора. Филиалы такого банка (гены) будут лучше

приспосабливаться и укрепляться  в экономической нише, а, возможно, и увеличиваться с

каждым новым поколением. Каждый филиал банка (индивид популяции) может  быть

оценен мерой его приспособленности. В основе таких мер могут лежать различные

критерии, например, аналог экономического потенциала - рейтинг надежности банка  или

соотношение привлеченных и собственных  средств банка. Такая оценка эквивалентна

оценке того, насколько эффективен организм при конкуренции за ресурсы, т.е. его

выживаемости, биологическому потенциалу. При этом особи (филиалы) могут приводить

к появлению потомства (новых банков, получаемых в результате слияния  или распада),

сочетающего те или иные (экономические) характеристики родителей. Например, если

один банк имел качественную политику кредитования, а другой - эффективную

инвестиционную политику, то новый  банк может приобрести и то, и  другое. Наименее

приспособленные особи (филиалы) совсем могут исчезнуть в результате эволюции. Таким

образом, отрабатывается генетическая процедура воспроизводства новых  банков (нового

поколения), более приспособленных и способных к выживанию в процессе эволюции

банковской системы. Эта политика со временем пронизывает всю банковскую

"популяцию", обеспечивая достижение  цели - появления эффективно работающей,

надежной и устойчивой банковской системы. Приведем соответствующий генетический

алгоритм (укрупненный и упрощенный):

алг ГЕНЕТИЧЕСКИЙ_АЛГОРИТМ_БАНКОВСКОЙ_СИСТЕМЫ

ввод Начальная структура  банка (начальная популяция);

СТРУКТУРА | процедура оценки структуры по приспособлению

Стоп:=0 | флаг для завершения эволюционного процесса

нц пока (Стоп=0)

СЕЛЕКЦИЯ | процедура генетического  отбора нового поколения

нц пока (МЕРА) | цикл воспроизводства с критерием МЕРА

| мерой эффективности  банковской системы

РОДИТЕЛИ | процедура выбора двух структур (филиалов)

| объединяемых (скрещиваемых) на новом шаге

ОБЪЕДИНЕНИЕ | процедура образования (объединения)

| нового банка (филиала)

ОЦЕНКА | процедура оценки устойчивости нового банка,

| образования (рейтинга, устойчивости)

ВКЛЮЧЕНИЕ | процедура включения (не включения) в новое

| поколение (в банковскую  систему)

кц

МУТАЦИЯ | процедура эволюции (мутации) нового поколения

если (ПРОЦЕСС) | проверка функционала  завершаемости эволюции

то Стоп:=1

кц

кон.

Мы не конкретизируем структуру  процедур СЕЛЕКЦИЯ, МЕРА, РОДИТЕЛИ,

ОБЪЕДИНЕНИЕ, ОЦЕНКА, ВКЛЮЧЕНИЕ, МУТАЦИЯ, ПРОЦЕСС, хотя даже на

интуитивном уровне ясно, что  в этом алгоритме они играют решающую роль для

эволюционного процесса. Не менее важен и правильный (эффективный) выбор структуры,

а также представления (описания) этой структуры. Часто ее выбирают по аналогии со

структурой хромосом, например, в виде битовых строк. Каждая строка (хромосома)

представляет собой конкатенацию ряда подстрок (генная комбинация). Гены

располагаются в различных  позициях строки (локусах хромосомы). Они могут принимать

некоторые значения (аллели), например, для битового представления - 0 и 1. Структура

данных в генетическом алгоритме (генотип) отражает генетическую модель особи.

Окружающая среда, окружение  определяется вектором в пространстве параметров и

соответствует термину "фенотип". Мера качества (процедура МЕРА) структуры  часто

определяется целевой  функцией (приспособленности). Для каждого  нового поколения

генетический  алгоритм осуществляет отбор пропорционально приспособленности

(процедура ОТБОР), модификацию  (процедуры РОДИТЕЛИ, ОБЪЕДИНЕНИЕ,

ВКЛЮЧЕНИЕ) и мутацию (процедура  МУТАЦИЯ). Например, в процедуре ОТБОР

каждой структуре ставится в соответствие отношение ее приспособленности  к суммарной

приспособленности популяции  и затем происходит отбор (с замещением) всех особей для

дальнейшей генетической обработки в соответствии с этой величиной. Размер отбираемой

комбинации можно брать  пропорциональным приспосабливаемости, и поэтому особи

(кластеры) с более высокой  приспособленностью с большей  вероятностью будут чаще

выбираться, чем особи  с низкой приспособленностью. После  отбора выбранные особи

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

может применяться кроссовер. Неизмененные особи переходят к стадии мутации. Если

кроссовер происходит, полученные потомки заменяют собой родителей и переходят к

мутации.

Хотя генетические алгоритмы и могут быть использованы для решения задач,

которые, видимо, нельзя решать другими методами, они не гарантируют  нахождение

оптимального решения (по крайней мере, - за приемлемое время; полиномиальные оценки

здесь часто неприменимы). Здесь более уместны критерии типа "достаточно хорошо и

достаточно быстро". Главное  же преимущество в другом: они позволяют решать сложные

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

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

алгоритмы эффективны в комбинации с другими классическими алгоритмами,

эвристическими процедурами, а также в тех случаях, когда  о множестве решений есть

некоторая дополнительная информация, позволяющая настраивать параметры  модели,

корректировать критерии отбора, эволюции.