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

Реклама на сайте

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


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

1)      Генетический алгоритм, предназначенный для оптимизации функции дискретных переменных и акцентирующий внимание на рекомбинациях геномов.

2)      Эволюционное программирование, ориентированное на оптимизацию непрерывных функций без использования рекомбинаций.

3)      Эволюционная стратегия, ориентированная на оптимизацию непрерывных функций с использованием рекомбинаций.

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

 

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

1)      параллельный поиск.

2)      Случайный мутации и рекомбинации уже найденных хороших решений. Они хорошо подходят как простой эвристический метод оптимизации многомерных, плохо определенных функций.

 

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

Особенность этих алгоритмов заключается в их успешном использовании при решении 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 prin I0).

Начало цикла (пока не {})

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  | флаг для завершения эволюционного процесса

НЦ пока (СТОП == 0)

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

    НЦ пока (МЕРА)  // цикл воспроизводства с критерием МЕРА (мера эффективности БС)

      РОДИТЕЛИ   // процедура выбора двух структур (филиалов), объединяемых (скрещиваемых на новом шаге)

      ОБЪЕДИНИТЬ  // процедура образования (объединение) нового банка (филиала)

      ОЦЕНКА // процедура оценки устойчивости нового банка (образования)

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

    КЦ

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

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

    ТО СТОП = 1

КЦ

End.

 

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



Методические пособия

  • Системы автоматизированного проектирования
  • Социология молодёжи
  • Общая социология
  • Криптография
  • Проектирование трансляторов
  • Компьютерная графика
  • Моделирование систем
  • Информационная безопасность
  • Теория вычислительных процессов
  • Логические основы искусственного интелекта
  • Проектирование распределённых информационных систем