1 of 22

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

ФКН НИУ ВШЭ

2023-2024

Маминов А.Д.

2 of 22

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

3 of 22

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

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

3

4 of 22

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

  •  

4

5 of 22

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

  •  

5

6 of 22

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

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

6

7 of 22

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

  •  

7

8 of 22

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

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

8

9 of 22

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

  •  

9

10 of 22

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

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

10

11 of 22

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

12 of 22

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

  •  

12

13 of 22

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

  •  

13

14 of 22

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

  •  

14

15 of 22

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

  •  

15

16 of 22

Задача

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

16

17 of 22

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

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

17

18 of 22

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

19 of 22

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

  •  

19

20 of 22

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

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

​

20

21 of 22

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

21

22 of 22

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

22