Генетический алгоритм (ГА)
Генетический алгоритм является самым известным на данный момент представителем эволюционных алгоритмов, и по своей сути является алгоритмом для нахождения глобального экстремума многоэкстремальной функции. ГА представляет собой модель размножения живых организмов.
Для начала представим себе целевую функцию от многих переменных, у которой необходимо найти глобальных максимум или минимум:
f(x1, x2, x3, …, xN)
Для того чтобы заработал ГА, нам необходимо представить независимые переменные в виде хромосом. Как это делается?
Как создать хромосомы?
Первым Вашим шагом будет преобразование независимых переменных в хромосомы, которые будут содержать всю необходимую информацию о каждой создаваемой особи. Имеется два варианта кодирования параметров:
- в двоичном формате;
- в формате с плавающей запятой.
В случае если мы используем двоичное кодирование, мы используем N бит для каждого параметра, причем N может быть различным для каждого параметра. Если параметр может изменяться между минимальным значением MIN и максимальным MAX, используем следующие формулы для преобразования:
r = g*(MAX – MIN) / (2^N – 1) + MIN.
g = (r – MIN) / (MAX – MIN) * (2^N – 1)
где g – целочисленные двоичные гены,
r – эквивалент генов в формате с плавающей запятой.
Хромосомы в формате с плавающей запятой, создаются при помощи размещения закодированных параметров один за другим.
Если сравнивать эти два способа представления, то более хорошие результаты дает вариант представления в двоичном формате (особенно, при использовании кодов Грея). Правда, в этом случае мы вынуждены мириться с постоянным кодированием/декодированием параметров.
Как работает генетический алгоритм?
В общем, генетический алгоритм работает следующим образом. В первом поколении все хромосомы генерируются случайно. Определяется их "полезность". Начиная с этой точки, ГА может начинать генерировать новую популяцию. Обычно, размер популяции постоянен.
Репродукция состоит из четырех шагов:
- селекции
и трех генетических операторов (порядок применения не важен)
- кроссовер
- мутация
- инверсия
Кроссовер является наиболее важным генетическим оператором. Он генерирует новую хромосому, объединяя генетический материал двух родительских. Существует несколько вариантов кроссовера. Наиболее простым является одноточечный. В этом варианте просто берутся две хромосомы, и перерезаются в случайно выбранной точке. Результирующая хромосома получается из начала одной и конца другой родительских хромосом.
001100101110010|11000 |
--------> |
001100101110010 11100 |
110101101101000|11100 |
00110010111001011000 |
--------> |
00110010111001111000 |
00110010111001011000 |
--------> |
11000001100101110010 |
Эволюционное (генетическое) программирование
Данные, которые закодированы в генотипе, могут представлять собой команды какой-либо виртуальной машины. В таком случае мы говорим об эволюционном или генетическом программировании. В простейшем случае, мы можем ничего не менять в генетическом алгоритме. Однако в таком случае, длина получаемой последовательности действий (программы) получается не отличающейся от той (или тех), которую мы поместили как затравку. Современные алгоритмы генетического программирования распространяют ГА для систем с переменной длиной генотипа.