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



              

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


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

Идея генетических алгоритмов "подсмотрена" у систем живой природы, у систем, эволюция которых развертывается в сложных системах достаточно быстро.

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

Данные алгоритмы адаптивны, развивают решения, развиваются сами. Особенность этих алгоритмов - их успешное использование при решении 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<f(i) то f0:=f(i);
    5. обновляем популяцию (вызов процедуры ОБНОВИТЬ);
    6. k:=k+1
    кц

Указанные процедуры определяются с использованием аналогичных процедур живой природы (на том уровне знаний о них, что мы имеем). Например, процедура СЕЛЕКЦИЯ может из случайных элементов популяции выбирать элемент с наибольшим значением f(i).


Содержание  Назад  Вперед