Генетические методы

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

Терминология генетических алгоритмов практически полностью заимствована из естественной генетики. Дадим несколько определений и понятий, используемых в генетических алгоритмах.

Индивидуальность - рассматриваемое решение задачи.

Популяция - набор индивидуальностей. Каждая индивидуальность состоит из одной или нескольких хромосом.

Хромосома (генотип) - закодированное каким-либо образом решение. Способ кодирования решения сильно зависит от специфики задачи.

Ген - элементарный код в хромосоме.

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

Селекция - правила, по которым выбираются индивидуальности для кроссинговера и мутации, а также индивидуальности, которые выживают в следующем поколении.

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

Мутация - применяется к одной индивидуальности и незначительно преобразует ее путем случайных перемещений составляющих внутри индивидуальности.

Локус - месторасположение гена в хромосоме

Аллели - различные значения одного и того же гена, расположенные в одинаковых локусах хромосомы.

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

Генетический алгоритм представляет собой последовательное преобразование одного конечного множества {X} промежуточных решений в другое. Обозначим i-e такое множество через {X}_i:

{X}_i= (X_1i..........X_gi ).

Тогда процесс поиска решения X* можно представить в виде последовательности:

{X}₀ —> {X}₁ —>...{X}_N —>{X}_N+1 —>...{X}* , (1)

которая сходится к множеству {X}*, одним из элементов которого является решение X. Переход к следующему множеству производится правилом алгоритма поиска:

{X}_{N + 1} =ђ({X}_N), где ђ-алгоритм поиска.

Опишем базисную структуру ГА (Рис. 1.5.). В начале работы генерируется множество решений (популяция) случайным, направленным или случайно-направленным способом. Решения представляются в виде закодированных хромосом. Способ кодирования определяется спецификой задачи. Далее для каждого решения оценивается его качество с помощью моделирующей функции. Эта функция также основана на знаниях из той области, где решается задача. Инструмент селекции выбирает индивидуальности для скрещивания (кроссинговера). Операция мутации применяется случайно с некоторой вероятностью р_м. Затем формируется новая популяция и процесс повторяется.

Генетический алгоритм должен иметь критерий остановки. Можно завершить работу после фиксированного числа генераций и взять лучшее решение из имеющихся. Можно остановиться, когда все организмы в популяции тождественны, т.е. fi=fj для всех i, j или (fi -fj)<, где -малое. Выбор критерия зависит от целей и задач, стоящих перед программистом. Теперь поясним приведенную схему, рассмотрев более подробно каждый ее блок.

При создании символьной модели задачи требуется каждое решение представить в виде хромосомы – строки символов. Необходимо отметить, что выбор символьной модели оптимизационной задачи во многом определяет эффективность и качество применяемых генетических алгоритмов. Для каждого класса комбинаторных задач должна строится своя модель, отражающая специфику и особенности решаемой задачи. Символьная модель оптимизационной задачи может быть представлена в виде множества кодовых строк-хромосом, которое соответствует конечному множеству допустимых решений. Например, в простом генетическом алгоритме генотип индивидуальностей кодируется на основе двоичного алфавита {1.0}. Каждая строка нулей и единиц является закодированной версией решения проблемы оптимизации. При любом выборе механизма кодирования существует карта каждого решения в виде единственной двоичной строки.

Создание новой генерации

Рис. Структура простого генетического алгоритма

Функция оценки годности (моделирующая функция, фитнесс, степень приспособленности) необходима для определения качества, ценности индивидуальности. Очевидно, что моделирующая функция создается с учетом специфики конкретной задачи.

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

Для воспроизводства потомков в ГА используются операторы кроссинговера и мутации. Существует огромное число модификаций оператора кроссинговера (ОК) в ГА. Его вид зависит от специфики конкретной решаемой задачи.

Самый простой оператор кроссинговера - одноточечный кроссинговер. Для двух родительских хромосом случайно определяется точка кроссинговера (скрещивания). Цепочка генов, ограниченная точкой кроссинговера, одной строки меняется местами с аналогичной частью генов второй строки.

Например, пусть родители имеют вид:

Р1

:

0

0

0

1

0

1

0

Р2

:

1

1

1

0

0

0

1

Случайным образом выберем точку оператора кроссинговера между третьим и четвертым генами.

Потомки P1' и P2' будут иметь вид:

Р1

:

0

0

0

0

0

0

1

Р2

:

1

1

1

1

0

1

0