Генетический алгоритм как метод оптимизации
Автор: Н.А. Шишкова
Источник: Прикладная математика и информатика / Московский авиационный институт, УЦ «Интеграция» - Серпухов, 2014г.
Аннотация
Н.А. Шишкова Генетический алгоритм как метод оптимизации В статье анализируется генетический алгоритм, рассматривается возможность его применения для решения оптимизационных задач.
Ключевые слова: генетический алгоритм, оптимизация, популяция.
Генетический алгоритм является эвристическим алгоритмом, довольно молодым в отношении его применения к задачам оптимизации.
Стандартный генетический алгоритм был впервые рассмотрен в работе де Джонга. Еще одним толчком для развития данного алгоритма была работа в книге Холланда. Он рассматривал использование операторов дупликации и удаления хромосомы. Последующие ученые предлагали различные модификации стандартного генетического алгоритма, а также предлагали новые генетические операторы
Принцип работы генетического алгоритма основывается на механизмах популяционной генетики. А именно на таких механизмах как случайное изменение генотипа, манипулирование хромосомным набором, естественный отбор. Рассмотрим этапы работы алгоритма (Рисунок 1).
Начальная популяция P0(x10 ... xk0).Это конечный набор допустимых решений задачи, которые можно найти произвольным образом, либо используя вероятностные методы решения задачи [1].
Все хромосомы xi имеют функцию эффективности. Вследствие этой функции хромосоме присваивается вероятность ее воспроизведения Pi.
Рисунок 1 - Этапы генетического алгоритма
При использовании полученной вероятности создается новая популяция. Воспроизведение происходит при помощи таких генетических операторов, как скрещивание и мутация. Если получено подходящий результат, то процесс завершается, в противном случае возвращаемся ко второму этапу алгоритма – воспроизводство потомков.
Особенностью генетического алгоритма это выбор родителей для последующего поколения. Для этого наиболее часто используется правило рулетки. Выбор делается на основании величины приспособленности особи по отношению к другим величинам особей. Популяции с более высокой приспособленностью будут использоваться чаще, чем с низкой.
Процедура скрещивания бывает одноточечной, когда используют одну точку скрещивания и родительские структуры делятся на два сегмента и соединяются с образованием двух потомков и многоточечной, когда используется поочередный обмен. При образовании циклов используется частично отображаемое скрещивание. Рассмотрим его подробнее, так как оно часто встречается при использовании генетического алгоритма для решения оптимизационных задач маршрутизации.
Даны две строки:
Родитель А: 5 9 8 | 4 7 6 | 2 11 10 3
Родитель В: 4 2 5 | 3 8 10 | 11 9 7 6
Вначале совершается отображение А на В, то есть 4 и 3, 7 и 8, 6 и 10 меняются местами. А затем А отображается на В, то есть заменяем 3 на 4, 8 на 7, 10 на 6. В результате получаем потомков: потомок А: 5 9 7 3 8 10 2 11 6 4, потомок В: 3 2 5 4 7 6 11 9 8 10.
Оба потомка включают в себя информацию, определяемую его родителями, однако это потомство необходимо утвердить. Для этого нужно соотнести потомство с возможными путями. Если они относятся ко всем маршрутам, то можно посчитать приспособленность потомства, иначе потомство не используется [2].
После процедуры скрещивания возможно создание дегенеративной популяции, чтобы такого не произошло, производим процедуру мутации. Методов для этого очень много, часто используется метод вставки, в котором узел помещается в случайно выбранную позицию в строке. Далее полученное поколение отправляется на процедуру подтверждения.
В генетическом алгоритме используется критерий остановки, что дает гарантию на сходимость алгоритма. Одним из критериев является отсутствие изменений в приспособленности популяций. Другим критерием является достижение заданной приспособленности.
Генетический алгоритм это итерационный процесс, который происходит до момента выполнения заданного количества поколений, либо до достижения заданного момента останова. Генетические алгоритмы будут эффективны в решении задач со сложными математическими моделями [3].