Эволюционное моделирование и генетические алгоритмы.
В общем виде эволюционный алгоритм – оптимизационный метод, базирующийся на эволюции популяции «особей». Каждая особь характеризуется приспособленностью – многомерной функцией ее генов. Задача оптимизации состоит в нахождении максимума функции приспособленности.
В процессе эволюции в результате отбора рекомбинаций и мутаций геномов особей происходит поиск особей с высокими приспособленностями. Основные эволюционные алгоритмы:
1. Генетический алгоритм, предназначенный для оптимизации функций дискретных переменных и акцентирующий внимание на рекомбинациях геномов.
2. Эволюционное программирование. Ориентировано на оптимизацию непрерывных функций без использования рекомбинаций.
3. Эволюционная стратегия. Ориентирована на оптимизацию непрерывных функций с использованием рекомбинаций.
4. Генетическое программирование, использующее эволюционный метод для оптимизации компьютерных программ.
По сравнению с обычными оптимизационными методами эволюционные алгоритмы имеют следующие особенности:
- параллельный поиск,
- случайные мутации и рекомбинации уже найденных хороших решений.
Они хорошо подходят как простой эвристический метод оптимизации многомерных, плохо определенных функций.
Генетический алгоритм – алгоритм, основанный на имитации генетических процедур развития популяции в соответствии с принципами эволюционной динамики. Часто используются для решения задач оптимизации (многокритериальной) поиска управления.
Данные алгоритмы адаптивны, развивают решение и развиваются сами.
Пример: рассмотрим задачу безусловной численной оптимизации f(i). Найти максимум f(i), где I - набор из n нулей и единиц.
При n=5 i=(1,0,0,1,0).
Эта задача является сложной для обычных, негенетических алгоритмов. Генетический алгоритм может быть построен следующей укрупненной процедурой:
1. Генерируем начальную популяцию (набор допустимых решений задачи), состоящую из элементов I0=(i1, i2, …, in). Соответственно, ij в этом наборе либо 0, либо 1. Определяем некоторый критерий достижения хорошего решения - критерий остановки, процедуру селекции, процедуру скрещивания, процедуру мутации, процедуру обновления популяции.
2. к:=0, f(0)=max {f(i), i I0}
3. Начало цикла. Пока не ()
1. С помощью вероятностного оператора (селекции) выбираем два допустимых решения (родители i1 и i2) из выбранной популяции (вызов процедуры селекция).
2. По этим родителям строим новое решение (вызов процедуры скрещивание). Получаем новое решение i.
3. Модифицируем это решение (вызов процедуры мутация).
4. Если f0 < f(i), то f0:=f(i).
5. Обновляем популяцию (вызов процедуры обновить).
6. к:=к+1;
Конец цикла.
Пример 2: работу банка можно моделировать на основе генетических алгоритмов. С их помощью можно выбирать оптимальные банковские проценты (вкладов, кредитов) некоторого банка с тем, чтобы привлечь больше клиентов (средств).
Тот банк, который сможет привлечь больше вкладов, клиентов и средств, и выработает более привлекательную стратегию поведения (эволюции), тот и выживет в условиях естественного отбора.
Филиалы такого банка (гены) будут лучше приспосабливаться и укрепляться в экономической нише, а возможно, и увеличиваться с каждым новым поколением.
Каждый филиал банка (индивид популяции) может быть оценен мерой его приспособленности. В основе таких мер могут лежать различные критерии, например, рейтинг надежности банка или соотношение привлеченных и собственных средств банка.
Такая оценка эквивалентна оценке того, насколько эффективен организм при конкуренции за ресурсы, то есть его выживаемости биологическому потенциалу.
При этом особи (филиалы) могут приводить к появлению потомства (новых банков), получаемых в результате слияния или распада, сочетающего те или иные экономические характеристики родителей.
Соответствующий генетический алгоритм (укрупненный и упрощенный) будет иметь следующий вид:
Генетический алгоритм банковской системы.
1. Ввод начальной структуры банка (начальная популяция).
2. Процедура структура – процедура оценки структуры по приспособлению.
3. Стоп:=0 – флаг для завершения эволюционного процесса.
4. Начало цикла
Пока (стоп=0)
«Селекция» – процедура нового отбора нового поколения.
Начало цикла
Пока (мера) – цикл воспроизводства с критерием «мера» в качестве эффективности банковской системы.
Процедура «родители2 – процедура выбор двух структур (филиалов), объединяемых (скрещиваемых) на новом шаге.
Процедура «объединение» – процедура образования (объединения) нового банка (филиала).
Процедура «оценка» – процедура оценки устойчивости нового банка, расчет рейтинга устойчивости.
Процедура «включение» – процедура включения (не включения) в новое поколение (в банковскую систему)
Конец цикла
Мутация – процедура эволюции (мутации) нового поколения.
Если (процесс) то стоп:=1;
Конец цикла.
Конец алгоритма.
Хотя генетические алгоритмы и могут быть использованы для решения задач, которые нельзя решить другими методами, они не гарантируют нахождение оптимального решения. Здесь более уместны критерии типа «достаточно хорошо» и «достаточно быстро».
Главное их преимущество в другом – они позволяют решать сложные задачи, для которых не разработаны пока устойчивые и приемлемые методы, особенно на этапе формализации и структурирования системы.
В когнитивных системах генетические алгоритмы эффективны в комбинации с другими классическими алгоритмами, эвристическими процедурами, а также в тех случаях, когда о множестве решений есть некоторая дополнительная информация, позволяющая настраивать параметры моделей, корректировать критерии отбора эволюции.