Генетический алгоритм: описание

Генетический алгоритм работает с представленными в конечном алфавите строками S конечной длины l, которые используются для кодировки исходного множества альтернатив W. Строки представляют собой упорядоченные наборы из l элементов: S=(s₁, s₂, ..., s_l), каждый из которых может быть задан в своём собственном алфавите V_i, , т.е. s_iО V_i, , где алфавит V_i является множеством из r_i символов: . Для решения конкретной задачи требуется однозначно отобразить конечное множество альтернатив W на множество строк подходящей длины (очевидно, что длина строк зависит от алфавитов, используемых для их задания).

Для работы алгоритма необходимо на множестве строк задать неотрицательную функцию F(S), определяющую показатель качества, “ценность” строки SО . Алгоритм производит поиск строки, для которой

Если на множестве W задана целевая функция f(w), то функцию F(S) на множестве строк можем определить следующим образом: F(S)=f(w), если элемент w при отображении исходного множества W на множество строк был сопоставлен строке S.

Генетический алгоритм за один шаг производит обработку некоторой популяции строк. Популяция G(t) на шаге t представляет собой конечный набор строк: , , , где N -- размер популяции, причём строки в популяции могут повторяться.

Анализ работы алгоритма удобно производить, используя аппарат схем. Схемой в генетическом алгоритме называют описание некоторого подмножества строк. Схема H=(h₁, h₂, ..., h_m  ) может рассматриваться как строка, алфавиты для элементов которой дополнены специальным символом “#”: ,. Если в некоторой позиции r схемы H присутствует символ “#”, то такая позиция называется свободной, а сам символ “#” интерпретируется как произвольный символ из алфавита V_r. Позиция q схемы H называется фиксированной, если в этой позиции присутствует один из символов алфавита V_q. Схема H, в которой определены фиксированные и свободные позиции, описывает подмножество , содержащее такие строки, у которых элементы, соответствующие фиксированным позициям схемы, совпадают с символами схемы, а элементы, соответствующие свободным позициям схемы, являются произвольно заданными в соответствующих алфавитах: где I_{[1, m]} - множество целых чисел отрезка [1, m].

Например, для множества строк , где V_i= {0, 1}, , схема H₁ ="1###0" задаёт такое множество строк, у которых первым элементом является символ "1", пятым - "0", а остальные - либо "0", либо "1". Строки "10010", "11110" являются примерами строк, принадлежащих множеству .

Часть популяции , строки которой удовлетворяют схеме H, обозначают , где n(H, t) - число строк схемы H в популяции G(t) и называют подпопуляцией, соответствующей схеме H.

Суть генетического алгоритма заключается в следующем.

Пусть на шаге t имеется популяция G(t), состоящая из N строк. Для популяции вводится понятие средней ценности популяции F_ср (G(t)):

Аналогично для подпопуляции G_H(t), удовлетворяющей схеме H, вводится понятие средней ценности подпопуляции F_ср (G_H(t)): .

Генетический алгоритм осуществляет переход от популяции G(t) к популяции G(t+1) таким образом, чтобы средняя ценность составляющих её строк увеличивалась, причём количество новых строк в популяции равно KЧ N, где K - коэффициент новизны. Если K<1, то популяция будет перекрывающейся, т.е. в новой популяции сохраняются некоторые строки из старой, а если K=1, то она будет неперекрывающейся, т.е. подвергнется полному обновлению.

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