Методы оптимизации: семинар 14

ФКН НИУ ВШЭ

2021-2022

Маминов А.Д.

Генетические алгоритмы

Генетический алгоритм

• Генетический алгоритм (ГА) – эвристический эволюционный алгоритм, основанный на случайном переборе.
• Механизмы аналогичны естественному отбору в природе.
• Каждое возможное решение считается ’особью’.

3

Генетический алгоритм

4

Генетический алгоритм

5

Генетический алгоритм

• Шаг алгоритма:
• Генерация промежуточной�популяции (отбор из �текущего поколения);
• Скрещивание особей �промежуточной популяции;
• Мутация нового поколения.

6

Генетический алгоритм

7

Генетический алгоритм

• Скрещивание:
• Особи промежуточной популяции случайным образом разбиваются на пары и скрещиваются с некоторой вероятностью.
• В результате – либо получаются два потомка, либо в новое поколение записывается изначальная пара.
• В классическом ГА применяется одноточечный оператор кроссовера: для родительских строк случайно выбирается точка раздела; потомки получаются путем обмена отсеченными частями:

8

Генетический алгоритм

9

Генетический алгоритм

• Критерий останова:
• Заданное количество поколений;
• Схождение популяции.
• Схождение – ситуация, когда все строки популяции находятся в области некоторого экстремума и почти одинаковы. «Одинаковость» особей означает, что кроссовер почти никак не изменяет популяции, а мутирующие особи склонны вымирать, так как менее приспособлены.

10

Многокритериальная оптимизация

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

12

Парето оптимальное множество

13

Линейная свертка критериев

14

Метод изменения ограничений

15

Использование Генетических Алгоритмов

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

16

Общее описание многокритериального ГА

• Шаг 1. Начальная популяция создается случайным образом. Следующие шаги выполняются для перехода от фактической популяции (k) к следующей. (k + 1). Сначала на шагах 2–4 создается промежуточная популяция.
• Шаг 2. Процедура элитарности выбирает лучшее решение по каждому критерию, который затем помещается в промежуточную популяцию.
• Шаг 3. Равное количество решений выбирается по каждому критерию с использованием рулетки.
• Шаг 4. Промежуточная популяция дополняется особями, полученными с помощью процедуры кроссовера. Отметим, что решения, к которым применяется данная процедура, выбираются случайным образом из популяции k. Процедура кроссовера применяется с одной точкой.
• Шаг 5. Процедура мутации применяется к фиксированному числу решений, выбранных случайным образом. Единственный бит решения модифицируется, меняя свое значение с 0 на 1 или наоборот.
• Шаг 6. Новая популяция становится текущей, и шаги со 2 по 5 повторяются до тех пор пока не будет достигнуто максимальное количество популяций.
• Шаг 7. Процедура сортировки по Парето проводится для всех решений в текущем поколении. (или среди всех особей всех поколений)

17

Задача

Найти Парето-оптимальное множество:

18

Многокритериальная оптимизация. Прикладное применение к оптимизации роботов

Схема робота 2-RPR

20

Многокритериальная оптимизация робота с одним параметром

• Для робота 2-RPR были посчитаны два критерия: площадь рабочей области (W) и индекс подвижности (Global Dexterity Index) по одному параметру (d)
• Синем выделена Парето-оптимальная область
• Найдены утопическая и идеальная точки

​

21

Многокритериальная оптимизация робота с двумя параметром

22

Многокритериальная оптимизация робота с тремя параметром

23