Решение задачи упаковки кругов с помощью генетических алгоритмов

Август 1, 2022

Главная
Информатика
Решение задачи упаковки кругов с помощью генетических алгоритмов

Содержание

2. Содержательная постановка задачи об упаковке кругов Найти максимальный радиус, при котором N неперекрывающихся кругов могут быть
3. Математическая постановка задачи Пусть есть компактная область D из R². Найти такие точки S₁, … ,Sn
4. Практическая значимость задачи Укладка объектов цилиндрической формы в контейнер; Кристаллические структуры построены на основе плотнейших укладок
5. Научная значимость Теорема об упаковке кругов используется теориях конформного отображения и планарных графов.
6. Приближённое конформное отображение
7. Оптимальные упаковки Сейчас известны оптимальные упаковки (с доказательством) до n = 36; Упаковки-кандидаты – лучшие известные
8. Упаковка в единичный квадрат
9. Локальные методы Минимизация “энергии” Бильярдная симуляция Метод “тряски”
10. Минимизация “энергии” Аналогия с электростатикой; При замене x’=sin(x),y’=sin(y) получаем задачу без ограничений; Методом Ньютона получены упаковки
11. Бильярдная симуляция Аналогия с механикой; Радиус кругов увеличивается.
12. Метод тряски По очереди пытаемся двигать каждую точку в различных направлениях на величину S; Если ничего
13. Глобальные методы Метод Монте-Карло Дискретизация задачи с последующим перебором. Эволюционные методы В качестве приспособленности выступает радиус
14. Схема работы ГА Выбираем три случайные особи (A, B и С в порядке приспособленности) С вероятностью
15. Выбор кодировки Кодировать напрямую: (X1,Y1, … , Xn,Yn) Кодировать со сжатием. Цель – уменьшить число неизвестных
16. Прямая кодировка В векторе (X1,Y1, … , Xn,Yn) координаты центров кругов; Можно кодировать в (X2,Y2, …
17. Кодировка со сжатием Кодировать в A = (A[1],…,A[n-1]), B = (B[1],…,B[n-1]) B[i] – сколько кругов “создаёт”
18. Кодировка алгоритма Кодировка – пара M = { Ci | i=1…n, Ci є D} (область упаковки)
19. Роль алгоритма A M A Алгоритм A переводит множество точек M в соответствующую упаковку M A
20. Структура A Идентификатор алгоритма Кол-во итераций Вероятности Параметры, влияющие на скорость сходимости A, и т.д.
21. Пример алгоритма A Каждая точка отталкивается от ближайшей на V Каждая точка случайно сдвигается с вероятностью
22. Оператор скрещивания Множество M у потомка определяется следующим образом: Область D разбивается на подобласти D1 и
23. Наследование алгоритма Потомок наследует алгоритм A у случайного родителя; Если у родителей одинаковые схемы алгоритма, то
24. Оператор мутации Случайное подмножество M сдвигается на случайные вектора (dx,dy) = ( a, b)*(n^-½) a, b
25. Структура оптимальных упаковок начиная с 49 кругов, оптимальная упаковка n=k² кругов будет отлична от регулярной квадратной
26. Свободные круги n = 31 n = 90
27. Касания кругов в плотных упаковках n = 1,…,300
28. Использование GPU для вычислений Множество M Конечная упаковка Параметры алгоритма A GPU Алгоритм A Текстура Шейдер
29. Упаковка большого числа кругов При увеличении n появляются большие фрагменты плотнейших кладок n = 16384 r
30. Касания кругов в плотных упаковках n = 16384
31. Выводы Адаптация генетического алгоритма и его гибридизация с низкоуровневой проблемно-ориентированной эвристикой способна значительно повысить эффективность применения
33. Скачать презентацию

Слайд 2

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

N неперекрывающихся кругов могут быть помещены в область упаковки.

Слайд 3

Математическая постановка задачи
Пусть есть компактная область D из R².
Найти такие

точки S₁, … ,Sn из D, чтобы максимизировать величину min(R,r),
где
R = min{ |Si – Sj| | i≠j, i,j=1..n}
r = min{ ρ(Si, ∂D) | i=1..n }
ρ(Si, ∂D) – расстояние от точки Si до границы области D

Слайд 4

Практическая значимость задачи
Укладка объектов цилиндрической формы в контейнер;
Кристаллические структуры построены на

основе плотнейших укладок шаров.

Слайд 5

Научная значимость
Теорема об упаковке кругов используется теориях конформного отображения и планарных

графов.

Слайд 6

Приближённое конформное отображение

Слайд 7

Оптимальные упаковки
Сейчас известны оптимальные упаковки (с доказательством) до n = 36;
Упаковки-кандидаты

– лучшие известные упаковки без доказательства оптимальности (http://www.packomania.com).
Находятся эвристическими методами.

Слайд 8

Упаковка в единичный квадрат

Слайд 9

Локальные методы
Минимизация “энергии”
Бильярдная симуляция
Метод “тряски”

Слайд 10

Минимизация “энергии”
Аналогия с электростатикой;
При замене x’=sin(x),y’=sin(y) получаем задачу без ограничений;
Методом Ньютона

получены упаковки до 50 кругов.

Слайд 11

Бильярдная симуляция
Аналогия с механикой;
Радиус кругов увеличивается.

Слайд 12

Метод тряски
По очереди пытаемся двигать каждую точку в различных направлениях на

величину S;
Если ничего не передвинули – уменьшаем S.

Слайд 13

Глобальные методы
Метод Монте-Карло
Дискретизация задачи с последующим перебором.
Эволюционные методы
В качестве приспособленности выступает

радиус кругов, либо размер масштабируемой области упаковки.

Слайд 14

Схема работы ГА
Выбираем три случайные особи (A, B и С в

порядке приспособленности)
С вероятностью p особь C замещается потомком от A и B
Иначе особь B замещается потомком от A и C
C вероятностью q потомок мутирует
Если последние K итерации дали улучшения решения, то идём на шаг 2

Слайд 15

Выбор кодировки
Кодировать напрямую: (X1,Y1, … , Xn,Yn)
Кодировать со сжатием.
Цель – уменьшить

число неизвестных
Кодировать алгоритм получения плотной упаковки

Слайд 16

Прямая кодировка
В векторе (X1,Y1, … , Xn,Yn) координаты центров кругов;
Можно кодировать

в (X2,Y2, … , Xn,Yn). Тогда это координаты центров кругов радиуса 1.
Тогда область упаковки масштабируется.
Недостатки:
Много переменных
Сложная область допустимых значений
Много локальных экстремумов

Слайд 17

Кодировка со сжатием
Кодировать в
A = (A[1],…,A[n-1]), B = (B[1],…,B[n-1])
B[i] –

сколько кругов “создаёт” i-ый круг
A[i] – под каким углом “создан” (i+1)-ый круг

(1,2,1,0,1)

Слайд 18

Кодировка алгоритма
Кодировка – пара
M = { Ci | i=1…n,

Ci є D} (область упаковки)
Этими начальными условиями обладают все алгоритмы A;
A – алгоритм упаковки и начальные условия для него;

Слайд 19

Роль алгоритма A
M
A
Алгоритм A переводит множество точек M в соответствующую упаковку
M
A

Слайд 20

Структура A
Идентификатор алгоритма
Кол-во итераций
Вероятности
Параметры, влияющие на скорость сходимости A, и т.д.

Слайд 21

Пример алгоритма A
Каждая точка отталкивается от ближайшей на V
Каждая точка случайно

сдвигается с вероятностью p2
V = V*p1
Вычисляем r
Проверка принадлежности к D

Слайд 22

Оператор скрещивания
Множество M у потомка определяется следующим образом:
Область D разбивается на

подобласти D1 и D2
M = { m | (m є M1 и m є D1)или (m є M2 и m є D2) }
Если |M|Если |M|>n, то удаляем из M лишние точки

D1
D2

Слайд 23

Наследование алгоритма
Потомок наследует алгоритм A у случайного родителя;
Если у родителей одинаковые

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

Слайд 24

Оператор мутации
Случайное подмножество M сдвигается на случайные вектора
(dx,dy) = ( a,

b)*(n^-½)
a, b – числа из распределения N(0,1)

Слайд 25

Структура оптимальных упаковок
начиная с 49 кругов, оптимальная упаковка n=k² кругов будет

отлична от регулярной квадратной решётки.

Слайд 26

Свободные круги
n = 31
n = 90

Слайд 27

Касания кругов в плотных упаковках
n = 1,…,300

Слайд 28

Использование GPU для вычислений
Множество M
Конечная упаковка
Параметры алгоритма A
GPU
Алгоритм A
Текстура
Шейдер
Uniform-переменные
Графический вывод
Цель –

ускорение работы алгоритма A

Слайд 29

Упаковка большого числа кругов
При увеличении n появляются большие фрагменты плотнейших кладок
n

= 16384 r = 0.00405794

Слайд 30

Касания кругов в плотных упаковках
n = 16384

Слайд 31

Выводы
Адаптация генетического алгоритма и его гибридизация с низкоуровневой проблемно-ориентированной эвристикой способна

значительно повысить эффективность применения ГА.
Важным фактором, влияющим на эффективность применения ГА, является выбранный способ кодирования решений.

Решение задачи упаковки кругов с помощью генетических алгоритмов

Содержание

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

Математическая постановка задачи Пусть есть компактная область D из R². Найти такие

Практическая значимость задачиУкладка объектов цилиндрической формы в контейнер;Кристаллические структуры построены на

Научная значимость Теорема об упаковке кругов используется теориях конформного отображения и планарных

Приближённое конформное отображение

Оптимальные упаковкиСейчас известны оптимальные упаковки (с доказательством) до n = 36;Упаковки-кандидаты

Упаковка в единичный квадрат

Локальные методыМинимизация “энергии”Бильярдная симуляцияМетод “тряски”

Минимизация “энергии”Аналогия с электростатикой;При замене x’=sin(x),y’=sin(y) получаем задачу без ограничений;Методом Ньютона

Бильярдная симуляцияАналогия с механикой;Радиус кругов увеличивается.

Метод тряскиПо очереди пытаемся двигать каждую точку в различных направлениях на

Глобальные методыМетод Монте-КарлоДискретизация задачи с последующим перебором.Эволюционные методыВ качестве приспособленности выступает

Схема работы ГАВыбираем три случайные особи (A, B и С в

Выбор кодировкиКодировать напрямую: (X1,Y1, … , Xn,Yn)Кодировать со сжатием. Цель – уменьшить

Прямая кодировкаВ векторе (X1,Y1, … , Xn,Yn) координаты центров кругов;Можно кодировать

Кодировка со сжатиемКодировать в A = (A[1],…,A[n-1]), B = (B[1],…,B[n-1])B[i] –

Кодировка алгоритмаКодировка – пара M = { Ci | i=1…n,

Роль алгоритма AMAАлгоритм A переводит множество точек M в соответствующую упаковкуMA

Структура AИдентификатор алгоритмаКол-во итерацийВероятностиПараметры, влияющие на скорость сходимости A, и т.д.

Пример алгоритма AКаждая точка отталкивается от ближайшей на VКаждая точка случайно

Оператор скрещиванияМножество M у потомка определяется следующим образом:Область D разбивается на

Наследование алгоритмаПотомок наследует алгоритм A у случайного родителя;Если у родителей одинаковые

Оператор мутацииСлучайное подмножество M сдвигается на случайные вектора(dx,dy) = ( a,

Структура оптимальных упаковокначиная с 49 кругов, оптимальная упаковка n=k² кругов будет

Свободные кругиn = 31n = 90

Касания кругов в плотных упаковкахn = 1,…,300

Использование GPU для вычисленийМножество MКонечная упаковкаПараметры алгоритма AGPUАлгоритм AТекстураШейдерUniform-переменныеГрафический выводЦель –

Упаковка большого числа кругов При увеличении n появляются большие фрагменты плотнейших кладокn

Касания кругов в плотных упаковкахn = 16384

ВыводыАдаптация генетического алгоритма и его гибридизация с низкоуровневой проблемно-ориентированной эвристикой способна

Похожие презентации