Генетический алгоритм представляет собой поисковый алгоритм, основанный на природных механизмах селекции и генетики. Он работает с кодами безотносительно их смысловой интерпретации. Каждый код представляет, по сути, точку пространства поиска. С целью максимально приблизиться к биологическим терминам, экземпляр кода называют хромосомой или особью. В обозначении строки кода будем использовать термин «особь». На каждом шаге работы генетический алгоритм использует несколько точек поиска одновременно. Совокупность этих точек в пространстве поиска является набором особей или популяцией. Количество особей в популяции называют размером популяции. Размер популяции является фиксированным и представляет одну из характеристик генетического алгоритма. Формирование исходной популяции происходит с использованием какого-либо случайного закона, на основе которого выбирается нужное количество точек поискового пространства. В процессе работы алгоритма генерация новых особей происходит на основе моделирования процесса размножения. При этом, естественно, порождающие особи называются родителями, а порожденные соответственно - потомками. Родительская пара, как правило, порождает пару потомков. Непосредственная генерация новых кодовых строк из двух выбранных происходит за счет работы оператора скрещивания, который также называют кроссинговером Вероятность применения оператора скрещивания обычно выбирается в пределах от 0,9 до 1, чтобы обеспечить появление новых особей, расширяющих пространство поиска. При значении вероятности меньше единицы часто используют особую стратегию - элитизм, которая предполагает переход в популяцию следующего поколения элиты, то есть лучших особей текущей популяции, без всяких изменений. Применение элитизма способствует сохранению общего качества популяции на высоком уровне. При этом элитные особи участвуют еще и в процессе отбора родителей для последующего скрещивания. Количество элитных особей определяется по формуле
,
где К – количество элитных особей,
Р – вероятность применения оператора скрещивания,
N – размер популяции.
В случае использования элитизма все выбранные родительские пары подвергаются скрещиванию, несмотря на то, что вероятность применения оператора скрещивания меньше единицы, что позволяет сохранить прежний размер популяции.
Моделирование процесса мутации новых особей осуществляется за счет работы оператора мутации. Основным параметром оператора мутации также является вероятность мутации. Поскольку размер популяции фиксирован, то порождение потомков должно сопровождаться уничтожением других особей. Выбор пар родителей из популяции для порождения потомков производит оператор отбора, а выбор особей для уничтожения - оператор редукции. Основным параметром их работы является, как правило, качество особи, которое определяется значением целевой функции в точке пространства поиска, описываемой этой особью. В основе оператора отбора лежит принцип «выживает сильнейший». Выбор особи для размножения производится случайно. Вероятность участия особи в процессе размножения определяется по формуле
,
где i – номер особи,
- вероятность участия особи в процессе размножения,
- значение целевой функции для i -ой особи.
Очевидно, что одна особь может быть задействована в нескольких родительских парах.
Таким образом, можно перечислить основные понятия и термины, используемые в области генетических алгоритмов:
- генотип и фенотип;
- особь и качество особи;
- популяция и размер популяции;
- поколение;
- родители и потомки.
К характеристикам генетического алгоритма относятся: размер популяции; оператор скрещивания и вероятность его использования; оператор мутации и вероятность мутации; оператор отбора; оператор редукции; критерий останова.
Операторы отбора, скрещивания, мутации и редукции называют еще генетическими операторами.
Критерием останова работы генетического алгоритма может быть одно из трех событий:
- формирование заданного пользователем числа поколений;
- достижение популяции заданного пользователем качества;
- достижение уровня сходимости, при котором дальнейшее улучшение особей в популяции происходит чрезвычайно медленно.
Характеристики генетического алгоритма определяются путем подбора, обеспечивающего поиск лучшего решения задачи за малое время работы. Рассмотрим примеры применения генетических алгоритмов при решении оптимизационных задач.
