ТСМ-№4 (Лекции ТСМ)

Лекция №4

Проходы

Оператор мутации - это генетический оператор преобразования хромосомы на основе вероятностного изменения отдельного состояния отдельных генов. Для этого используется периметр - вероятность мутации.

Виды мутации

1.Однобитовая мутация

Применяется при кодировании с номером бинарного кода Грея. В хромосоме . Случайным образом выбирается число - точка мутации.

Значение бита меняется на противоположное.

2. Многобитовая мутация

Аналогична однобитовой мутации. В хромосоме выбирается несколько точек мутаций

Значения битов меняются на противоположные.

3.Одноточечная мутация

Применяется в комбинаторных и задачах на графах при кодировании вершин графа.

В хромосоме случайным образом выбирается число - точка мутации.

Гены и меняются местами:

4. Многоточечная мутация

В хромосоме случайным образом выбираются точек мутации.

Далее происходит последовательный обмен генов, расположенных правее точек мутации друг с другом в порядке их расположения. Ген, расположенный правее последней точки мутации, переходит на место 1-го.

Пример:

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

P¹: A G C D B F E H

Оператор инверсии - это генетический оператор преобразования хромосомы на основе вероятностного инвертирования ее части. Для этого вводится параметр - вероятность инверсии.

Виды инверсии

1.Одноточечная инверсия

В хромосоме случайным образом выбирается точка инверсии. Новая хромосома формируется из путем инверсии сегмента, расположенного справа от _.

2.Многоточечная инверсия

В хромосоме случайным образом выбирается точек инверсии , которые делят хромосому на сегментов. Новая хромосома формируется из путем инверсии сегментов с четными номерами.

Пример:

2-х точечный оператор инверсии

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

P¹: A B C D E F G H

Замечания:

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

{P}

кроссовер

мутация

НЕТ

Д

инверсия

А

НЕТ

ДА

{Р¹}

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

Оператор селекции включает следующие этапы:

1. Формирование функции пригодности.

2. Вычисление функции пригодности.

3. Формирование родительского массива.

Алгоритмы формирование функции пригодности

1. Задача скалярной оптимизации

Определить ; (1)

(2)

Шаг 1. В популяции размером полагаем

Шаг 2. Для всех , проверяем выполнение условия:

(3)

Обозначим - количество точек , в котором выполняется условие (3).

Шаг 3. Сформулируем функцию :

(4)

Шаг 4. Полагаем . Если i ≤ N, то переходим к шагу 2, иначе переходим к шагу 5.

Шаг 5. STOP

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

Здесь q – параметр, влияющий на скорость сходимости ГА к оптимальному решению

2. Задача многокритериальной оптимизации.

Определить , (5)

где ;

(6)

Шаг 1. В популяции размером полагаем .

Шаг 2. Для всех , проверяем выполнение условия:

, (7)

или, что то же самое:

, (8)

При этом хотя бы одно из неравенств (8) – строгое.

Обозначим - количество точек , в которых выполняется условие (7).

Шаг 3. Сформируем функцию пригодности вида:

(9)

Шаг 4. Полагаем . Если , то переходим к шагу 2, иначе переходим к шагу 5.

Шаг 5. STOP.

Свойства функции пригодности вида (4)

1. Если , то . Для задачи (1) это означает, что в точке функция достигает своего минимального значения относительно текущей популяции . Другими словами точка обладает наивысшей степенью приспособленности в популяции .

2. Если , то . Это означает, что в точке функция достигает своего максимального значения относительно текущей популяции . То есть точка обладает минимальной степенью приспособленности в популяции .

3. Если , то .

Здесь q – параметр, влияющий на скорость сходимости ГА к оптимальному решению.

Свойства функции пригодности вида (9)

1. Если , то . Для задачи (1) это означает, что векторная функция достигает оптимальность по Парето значения относительно текущей популяции , и обладает наивысшей степенью приспособленности.

2. Если , то . Точка не принадлежит Парето-области. Чем больше , тем дальше от Парето-области.

Рассмотрим пример многокритериальной задачи коммивояжера

Начальная популяция:

P ₁: a e d c b

P₂: c d b e a

P₃: e b c d a

Будем использовать алгоритм многокритериального формирования жадного кроссовера.

1. Формирование P­­₁'

Выбираем точку кроссовера на P₁.

1. P₁: (d-c); f_ч1=7; f_ч2=9.

P₂: (d-b); f_ч1=4; f_ч2=3.

P₃: (d-a); f_ч1=2; f_ч2=2.

(1)

Переходим к вершине a.

1. P₁: (a-e); f_ч1=5; f_ч2=6.

P₂: (a-c); f_ч1=1; f_ч2=2.

P₃: (a-e); f_ч1=5; f_ч2=6.

(2)

Переходим к вершине c.

1. P₁: (c-b); f_ч1=6; f_ч2=7.

P₂: (c-d) – цикл.

P₃: (c-d) – цикл.

(3)

1. Выбираем (b-e), т.к. ген у ранее не встречался. f_ч1=3; f_ч2=5.

P₁’: d a c b e

f₁ = 2 + 1 + 6 + 3 + 3 = 15

f₂ = 2 + 2 + 7 + 5 + 6 = 22

2. Формирование P₂'

Переходим к точке кроссовера в P₂.

1. P₁: (b-a); f_ч1=3; f_ч2=6.

P₂: (b-e); f_ч1=3; f_ч2=5.

P₃: (b-c); f_ч1=6; f_ч2=7.

(1)

1. P₁: (e-d); f_ч1=3; f_ч2=6.

P₂: (e-a); f_ч1=5; f_ч2=6.

P₃: (e-b) – цикл.

(2)

1. P₁: (d-c); f_ч1=7; f_ч2=9.

P₂: (d-b) – цикл.

P₃: (d-a); f_ч1=2; f_ч2=2.

(3)

1. Выбираем (a-c), т.к. ген с ранее не встречался. f_ч1=1; f_ч2=2.

P₂’: b e d a c

f₁ = 3 + 3 + 2 + 1 + 6 = 15

f₂ = 5 + 6 + 2 + 2 + 7 = 22

3. Формирование P­­₃'

Переходим к точке кроссовера в P₃.

1. P₁: (c-b); f_ч1=6; f_ч2=7.

P₂: (c-d); f_ч1=7; f_ч2=9.

P₃: (c-d); f_ч1=7; f_ч2=9.

(1)

1. P₁: (b-a); f_ч1=3; f_ч2=6.

P₂: (b-e); f_ч1=3; f_ч2=5.

P₃: (b-c) – цикл.

(2)

1. P₁: (e-d); f_ч1=3; f_ч2=6.

P₂: (e-a); f_ч1=5; f_ч2=6.

P₃: (e-b) – цикл.

(3)

1. Выбираем (d-a), т.к. ген a ранее не встречался. f₂₁=2; f₂₂=2.

P₃’: c b e d a

f₁ = 6 + 3 + 3 + 2 + 1 = 15

f₂ = 7 + 5 + 6 + 2 + 2 = 22

Таким образом, после кроссовера получим:

P ₁’: d a c b <=> e

P₂’: b e d a <=> c

P₃’: c b e d <=> a

Осуществляем оператор мутации:

Пусть k=a – случайное число.

В P₁’ меняем местами b <=> e

В P₂’ меняем местами a <=> c

В P₃’ меняем местами d <=> a

Получим:

P₁”: d a c e b

P₂”: b e d c a

P₃”: c b e a d

Предположим, что на данном этапе инверсия не осуществляется.

Таким образом, получим популяцию 2-го поколения:

P ₁: d a c e b

P₂: b e d c a

P₃: c b e a d

II. Формирование популяции 3-го поколения

1. Формирование P₁'

Выбираем точку кроссовера на P₁.

1. P₁: (a-c); f_ч1=1; f_ч2=2.

P₂: (a-b); f_ч1=3; f_ч2=6.

P₃: (a-d); f_ч1=2; f_ч2=2.

(1)

1. P₁: (c-e); f_ч1=2; f_ч2=1.

P₂: (c-a) – цикл.

P₃: (c-b); f_ч1=6; f_ч2=7.

(2)

1. P₁: (e-b); f_ч1=3; f_ч2=5.

P₂: (e-d); f_ч1=3; f_ч2=6.

P₃: (e-a) – цикл.

(3)

1. Выбираем (b-d), т.к. ген d ранее не встречался. f₂₁=4; f₂₂=3.

P₁’: a c e b d

f₁ = 1 + 2 + 3 + 4 + 2 = 12

f₂ = 2 + 1 + 5 + 3 + 2 = 13

2. Формирование P₂'

Переходим к точке кроссовера в P₂.

1. P₁: (e-b); f_ч1=3; f_ч2=5.

P₂: (e-d); f_ч1=3; f_ч2=6.

P₃: (e-a); f_ч1=5; f_ч2=6.

(1)

1. P₁: (b-d); f_ч1=4; f_ч2=3.

P₂: (b-e) – цикл.

P₃: (b-e) – цикл.

(2)

1. P₁: (d-a); f_ч1=2; f_ч2=2.

P₂: (d-c); f_ч1=7; f_ч2=9.

P₃: (d-c); f_ч1=7; f_ч2=9.

(3)

1. Выбираем (a-c), т.к. ген c ранее не встречался. f_ч1=1; f_ч2=2.

P₂’: e b d a c

f₁ = 3 + 4 + 2 + 1 + 2 = 12

f₂ = 5 + 3 + 2 + 2 + 1 = 13

3. Формирование P₃'

Переходим к точке кроссовера в P₃.

1. P₁: (b-d); f_ч1=4; f_ч2=3.

P₂: (b-e); f_ч1=3; f_ч2=5.

P₃: (b-e); f_ч1=3; f_ч2=5.

Выбираем из и . Механизм выбора может быть:

• случайным

• по сумме (f₂₁ + f₂₂) -> min;

выбираем (4)

1. P₁: (d-a); f_ч1=2; f_ч2=2.

P₂: (d-c); f_ч1=7; f_ч2=9.

P₃: (d-c); f_ч1=7; f_ч2=9.

(2)

1. P₁: (a-c); f_ч1=1; f_ч2=2.

P₂: (a-b) – цикл.

P₃: (a-d) – цикл.

(3)

1. Выбираем (c-e), т.к. ген d ранее не встречался. f_ч1=2; f_ч2=1.

P₃’: b d a c e

f₁ = 4 + 2 + 1 + 2 + 3 = 12

f₂ = 3 + 2 + 2 + 1 + 5 = 13

Получим:

P₁’: a c e b d

P₂’: e b d a c

P₃’: b d a c e

P₁’, P₂’, P₃’ – реализуют один и тот же оптимальный маршрут. Популяция выродилась в одно оптимальное решение по Парето.