Процесс ГА

Процесс работы ГА. Часть 2

Процесс работы ГА – совокупность характеристик оптимизационной задачи, кодирование которой выполняется в последовательность, имеющую определенную длину.Работа алгоритма прекращается в случае выполнения заранее известного количества его итераций; алгоритм может быть остановлен, если поставленная задача решена и получен удовлетворяющий исходным данным ответ.

Упорядоченный ОК. Точка «разреза» — случайная.

P1: A B C D | E F G H

P2: C A B E | C D F H

P’1: A B C D | G E F H

 

В данном случае копируется левая часть элемента P1 в P’1. Вторая часть нового элемента образуется за счет элемента P2, где позиции упорядоченные слева направо. Из второго родительского элемента в новый попадают лишь те позиции, которые не присутствуют в P’1.

 

Оператор с частичным соответствием генов. После выбора точки «разреза» выполняется тщательный анализ сегментов обоих родителей, чтобы найти соответствие между позициями с формированием «детей». Правый сегмент P2 становится правым сегментом потомка P’1, левый сегмент P1 – левым в P’1. При переносе повторяющихся позиций они заменяются не те позиции, которые отсутствуют в новом элементе, если сменяемые позиции имеют частичное сходство.

 

P1: A B C D E F | G H I J

P2: E C I A D H | J B F G

P’1: A H C D E I | J B F G

 

Таким же образом создается элемент P’2:

 

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

 

P1: A B C D E F | G H I J

P2: E C I A D H | J B F G

P’1: E C F A D B | G H I J

 

 

P1: 1 2 3 4 5 6 7 8 9 10

P2: 5 3 9 1 4 8 10 2 6 7

P’1 1 3 9 4 5 8 10 2 6 7

 

Допустим, существует популяция P из двух родительских элементов P1 и P2. Когда происходит выполнения оператора цикла, копирование в P’1 начинается с первого элемента P1. Мы знаем, что позиция 1 в P1 – это позиция 5 в P2. Так мы образовали первый циклический путь (1,5). Элемент 5 в P1 соответствует четвертому элементу в P2; это второй путь (1,5;5,4). Продолжая дальнейший поиск соответствий, мы получим цикл (1,5;5,4;4,1). Из этого видно, что пятый элементы одного родительского элемента переходит в пятый элемент другого. Также обстоят дела и с четвертым элементом. Проведем теперь работу по созданию следующего цикла. Второй элемент в «родителе» P1 соответствует третьему в «родителе» P2. Следуя данной логике, получим ряд (2,3;3,9;9,6;6,8;8,2). Третий цикл будет иметь вид (7,10;10,7). Анализируя данные циклы, можно сделать вывод, что в новой хромосоме P’1 элемент под номером 3  помещается во второй локус, 9 в 3, 6 в 9 и т.д. Данный селекционный оператор применяется при решении комбинированно-логических задач.

 

Универсальный оператор. Данный оператор применяется при работе с теорией расписаний. В процессе не происходит «разреза» хромосомы; для воспроизведения нового потомства используется маска; ее длина равна длине хромосом.

 

При сложении хромосомы P1 с существующей маской, основываясь на правиле (0+0=0;0+1=1;1+1=0), образуется первая хромосома. Вторая получается этим же методом. Гены в родителях меняются, как отображено на рисунке:

 

P1: 0 1 1 0 0 1

P2: 0 1 0 1 1 1

0 1 1 0 1 0

P’1: 0 0 0 0 1 1

P’2: 0 0 1 1 0 1

 

Двоичная маска подбирается случайным образом или задается на основании определенных параметров. Но независимо от того, как была задана маска, 0 и 1 чередуются с вероятностью 50%.

 

 

Кроме селекционных операторов во время работы используют мутационные. Обращаясь к биологии, мы можем найти интересный факт: иногда развитие популяции происходит рывками. Основываются они на точечной мутации. Мутация – важный процесс; он позволяет не терять генетический материал. Точковая мутация воздействует только на точки положения генов и не затрагивает другие параметры и характеристики. Такой селекционный оператор, влияя на изменения родительских хромосом, заставляет образовываться потомкам.

 

Мутация происходит в два этапа:

 

  1. Имеем хромосом А = (а1, а2, а3,…,a L-2,a L-1, aL). Здесь мы выбираем два элемента. Выбор не направлен, он может пасть на любой элемент. В примере: а2  и a L-1.
  2. Гены переходят на позиции друг друга, образовывается потомок вида А’ = (a1, aL.1, а3,…,аL-2, а2, aL).

 

Кратко опишем самые популярные мутационные операторы (ОМ).

 

Одноточечный оператор. Реализация данного оператора заключается в обмене случайно выбранного гена на соседний. Это перестановка позволяет получать новую хромосому. На изображении P1 – «хромосома-родитель», P’1 – потомственная хромосома.

 

P1: 0 1 1 | 0 1 1

P’1: 0 1 0 | 1 1 1

 

Двуточечный ОМ. Во время реализации данного ОМ выбирается точка «рассечения». Она может быть выбрана, либо посредством случая, либо направленно. После проведения сечения хромосомы часть генов производят взаимообмен в правом сегменте от выполненного рассечения хромосомы.

 

P: A| B C D | E F | G H

P’: A G C D  B F  E G

 

Многоточечный оператор – разновидность двуточечного. Здесь происходит обмен рядом стоящих генов.

 

Есть некоторые гены, которые не рекомендуется менять при реализации любого из операторов. Такие гены, чаще всего, это стоящие рядом два гена называются строительными блоками (СБ). Их изменение может привести к ухудшению характеристик хромосомы – потомка. СБ позволяют находит оптимальные решения ГА.

 

Если блоки находятся между линиями разреза, то обмен генами может происходить двумя разными способами. Четное количество линий рассечения хромосомы заставляет совершать обмен генами слева и справа от линий разреза.

 

P: A B | C D | E F | G H | I J

P’: A C B E D G F I H J

 

Если линий разреза нечетное число, то при работе с операторами потомственная хромосома получается за счет обмена групп генов, располагающихся между линиями разреза с четным порядком.

 

Позиционный ОМ. В данном операторе существуют две точки, в которых разрезается «родители». Отбор места рассечения происходит не направленно, а в случайном порядке. Под выполнением позиционного ОМ принимают перемещения гена второй линии разреза вперед гена первой линии.

 

P: A | B C D | E F

P’: A B E C D F

 

Операторы селекции и мутации – не единственные операторы, влияющие на успешную реализацию генетического алгоритма. Поговорим об операторе инверсии (ОИ). Данный оператор позволяет за счет инвертирования родительского гена или нескольких генов одновременно создавать потомственную хромосому. Выполнение ОИ позволяет создать одну или более линий инверсии, внутри которых происходит инвертирование генов.

 

ОИ выполняется в несколько этапов:

  1. В = b1,b2,…,b L — «хромосома-основа». Это может быть любая хромосома из имеющегося множества.
  2. Случайные числа y’1 и y’2 выполняют равенства у1 = min{y’1,y’2} и у2= max{y’1, y’2}.
  3. Потомственная хромосома получается за счет инверсии генов в правом сегменте от y’1 и в левом от y’2 «родителя».

 

Еще один оператор – транслокационный оператор (ОТ). Данный оператор за счет инвертирования и скрещивание генов «родителя» позволяет создавать две потомственных хромосомы. Если говорить иначе, ОТ – это совокупность инверсионного оператора и селекционного.

Чтобы получить новую хромосому P’1, из элемента P1 берется левый сегмент до разрыва и инвертированный правый сегмент из элемента P2 до линии разрыва. Получение хромосомы P’2 производится тем же методом, но сегменты меняются местами.

 

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

 

Оператор транспозиции. Структура, создающая новую хромосому, за счет выделения и инвентирования отдельно взятого сегмента.

 

P1: A | B C | D E F | G H

P’1: A F E D B C G H

 

В показанном на рисунке 16 примере имеется три линии рассечения хромосомы. Выбор линий разреза случаен или направлен. СБ DEF в «хромосоме-родителе» инвентируется и вставляется в линию рассечения между двумя генами. В примере это гены А и В.

 

Оператор сегрегации (ОС). Данный оператор создает потомственные хромосомы за счет отбора строительных блоков у родителя. Рассмотрим подробный пример. Перед этим стоит уточнить, что ОС выполняется только при определенном наборе хромосом. Имеем некую популяцию P:

 

Р — (Р1, Р2, Р3, Р4}: Р1 : (12345678); Р2 : (24316587); Р3 : (31425768); Р4 : (87654321)

 

Здесь P1,P2,P3,P4 – хромосомы, они будут основой для создания новых хромосом. Выделим в родителях блоки:

 

  • В P1 – 23,67
  • В P2 – 1,4
  • В P3 – 768,425
  • В P4 – 54,87

 

Теперь мы можем создавать потомственные хромосомы. Одну из хромосом можно образовать, выбрав первые СБ у родительских хромосом. В итоге потомок P’1 будет иметь вид 423176854. Это решение будет иметь практическое значение; оно реально. А вот потомок P’2 = 67442587 – нереален и не может существовать на практике.

 

Оператор удаления. Данный оператор создает новые потомственные хромосомы путем удаления СБ в структуре родительских элементов.

 

Его реализация выглядит следующим образом: выбирается точка рассечения, после чего родительская хромосома разрезается. Проводится пробное удаление генов. После удаления рассчитывается целевая функция. Гены справа от линии или между линиями удаляются. Но удаление происходит таким образом, что возможные новые решения могли существовать в реальности, а не быть лишь теоретическими выкладками.

 

Оператор вставки. Реализация подразумевает вставку отдельных генов или СБ в отдельно взятого из множества «родителя». Так получаются новые потомки.

 

На этапе выполнения отбирается хромосома-донор, откуда в будущем будут браться гены или СБ для создания потомков. На следующем этапе из множества хромосом берется одна; она будет служить основой для вставки генов и блоков. Выполняется вставка-тест, находятся реальные решения и вычисляются изменившееся значение ЦФ. Вставка происходит в правый от точки рассечения сегмент.

 

Важно знать, на размер популяции влияет удаление и вставка генов при образовании потомков. Для компенсации действий операции применяются в совокупности.

 

Репродуктивный оператор (ОР). Данный оператор позволяет уменьшать размер популяции после одного или нескольких эволюционных изменений, то есть спустя несколько поколений. Процесс уменьшения происходит за счет подробного анализа всех изменений, произошедших в этот период времени. Основная задача ОР – устранение решений, не имеющих практическое значение или являющихся неудачными. Иногда данный оператор используют в ГА (особенно в ПГА), чтобы не уменьшать и не увеличивать размер будущей популяции. Но его применение порождает одну проблему: найти компромисс между существующим разнообразием созданных хромосом и качеством найденных решений.

 

Выполнение ОР проходит в несколько этапов:

 

  1. Создают группу из существующих решений.
  2. Выбирается часть решений для образования новой популяции. Ее численность определяется по формуле: Nt+1= Нt + Нок + Ном + Н+ Нot + Нотр + Нoe + Нoy.

где Nt+1 — размер созданной популяции.

Nt — размер популяции на прошлом этапе,

Правая сторона равенства – «хромосомы-потомки», образованные при применении всех имеющихся операторов. Редукционный оператор может применяться, как после каждого шага ГА, так и в самом его конце.

 

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

 

Оператор редукции имеет ряд модификаций:

 

  • Отбор с равной степенью. Pk(s) = 1/N. В этой формуле N – размер популяции.
  • Пропорциональный отбор.

P k(s)=ЦФ(P k )/∑ ЦФ(P k )

 

Из всего выше сказанного можно подвести некоторые итоги. Редукционный оператор позволяет во время выполнения первых шагов ГА не принимать во внимание величину ЦФ. Хромосомы выбираются не направленно. В конце процесса главный критерий отбора – величины ЦФ. От нее зависит, сможет ли хромосома попасть в новую популяцию; рост значения ведет к росту вероятности. На этапе реализации ГА количество случайных операций уменьшается; в это же время растет количество операций строго направленных.

 

Оператор рекомбинации. Данный оператор определяет способ построения потомков из родительских элементов. Это подробный анализ и операции преобразования популяций во время исчезновения прошлой генерации и образования новой. Для реализации оператора есть много путей. Самый распространенный – создание потомка из родителя после применения всех операторов. Изменение месторасположения популяции каждую последующую генерацию в современности практически не применяют.

 

Для управления рекомбинационным оператором используют особый параметр W(P). Расчет количества популяций, которые способны продолжить существование в следующей генерации, рассчитываются по формуле:

 

N(l-W(P))

 

Здесь N – размер популяции. Выражение W(P) = 0 что перемещение популяции происходит без потери ее составляющих; все элементы остаются на своих местах и в новой генерации.

Предыдущая запись
Описание процесса работы ГА. Часть 1
Следующая запись
Метод PERT. Определение. Принципы. Задачи.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Заполните поле
Заполните поле
Пожалуйста, введите корректный адрес email.

*

Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.