Генетические алгоритмы

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

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

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

Данные алгоритмы адаптивны, они развивают решения и развиваются сами. Особенность этих алгоритмов - их успешное использование при решении сложных проблем.

Пример. Рассмотрим задачу безусловной целочисленной оптимизации (размещения): найти максимум функции f(i), i - набор из n нулей и единиц, например, при n = 5, i = (1, 0, 0, 1, 0). Это очень сложная комбинаторная задача для обычных, "негенетических" алгоритмов. Генетический алгоритм может быть построен на основе следующей укрупненной процедуры:

1. Генерируем начальную популяцию (набор допустимых решений задачи) - I₀ = (i₁, i₂, :, i_n), i_j {0,1} и определяем некоторый критерий достижения "хорошего" решения, критерий остановки , процедуру СЕЛЕКЦИЯ, процедуру СКРЕЩИВАНИЕ, процедуру МУТАЦИЯ и процедуру обновления популяции ОБНОВИТЬ;

2. k = 0, f₀ = max{f(i), i I₀};

3. выполнять пока не( ) :

· с помощью вероятностного оператора (селекции) выбираем два допустимых решения (родителей) i₁, i₂ из выбранной популяции (вызов процедуры СЕЛЕКЦИЯ);

· по этим родителям строим новое решение (вызов процедуры СКРЕЩИВАНИЕ) и получаем новое решение i;

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

· если f₀ < f(i) то f₀ = f(i);

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

· k = k + 1

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

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

Процедура СКРЕЩИВАНИЕ (кроссовер) может по векторам i₁, i₂ строить вектор i, присваивая с вероятностью 0.5 соответствующую координату каждого из этих векторов - родителей. Это самая простая процедура. Используют и более сложные процедуры, реализующие более полные аналоги генетических механизмов.

Процедура МУТАЦИЯ также может быть простой или сложной. Например, простая процедура с задаваемой вероятностью для каждого вектора меняет его координаты на противоположные (0 на 1, и наоборот).

Процедура ОБНОВИТЬ заключается в обновлении всех элементов популяции в соответствии с указанными процедурами.

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

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

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