презентация исправленная

1.

Выпускная квалификационная работа бакалавра
Разработка и исследование гибридных
алгоритмов локально-глобальной оптимизации
для многозвенных механизмов параллельной
структуры
Выполнил:
студент гр. 3822Б1ПМоп3
Дерябин Максим Сергеевич
Научный руководитель:
доцент, к.т.н.
Козинов Евгений Александрович
Направление подготовки:
«Прикладная математика и информатика»
Профиль: «общий профиль»
Нижний Новгород, 2026
1 / 13

2.

Актуальность и цель работы
Вектор
параметров q
F(q)
Расчётная модель
«чёрный ящик»
gⱼ(q),
j=1,…,m
АГП выбирает
новое испытание
1
2
3
Целевая функция и
Функции
ограничения
многоэкстремальны:
доступны
локальный метод
как «чёрный ящик»
может застрять
Конфигурация
должна
быть допустимой
и безопасной
построить и исследовать высокопроизводительную гибридную реализацию алгоритма глобального
поиска для задач позиционирования и построения траекторий многосекционного механизма.
Цель
Ключевые
идеи
1. Глобальная компонента метода идентифицирует перспективные области поиска.
2. Локальная компонента оперативно уточняет решение в пределах выделенных подобластей.
3. Индексная схема обеспечивает учёт нелинейных ограничений.
global
local
indexed
C++
поиск по всей области
уточнение решения
строгий учет ограничений
демо и
эксперименты
2 / 13

3.

Параметры, критерий и ограничения задачи
Что выбираем
обобщённые координаты q:
углы звеньев; длины секций.
θᵢᵐⁱⁿ ≤ θᵢ ≤ θᵢᵐᵃˣ
углы, i=1,…,n
Lᵢᵐⁱⁿ ≤ Lᵢ ≤ Lᵢᵐᵃˣ
длины, i=1,…,n
gᵢ(q) ≤ 0
0<i≤m
линейные/нелинейн
ые
ограничения
Что минимизируем
вычислить φ(q)
и обновить лучшее
решение
φ(y*) = min { φ(y): y ∈ Q }
F(q) = ‖P(q) − Pᵈ‖₂ → min
ν(q)=m+1
точка допустима
Как учитываем ограничения
Индексная схема: сначала проверяются ограничения,
а целевая функция вычисляется только для допустимой точки.
Преимущество перед штрафами
не подбирать
коэффициенты штрафа
сохранять первое
нарушение
раньше отбраковывать
небезопасные сегменты
3 / 13

4.

Алгоритм глобального поиска: оценка перспективных
интервалов
Для функции ψ(x) липшицева модель даёт нижнюю
оценку того, насколько «хорошим» может быть ещё не
исследованный интервал.
Rᵢ = mΔᵢ + [ψ(xᵢ) − ψ(xᵢ₋₁)]²/(mΔᵢ)
− 2[ψ(xᵢ) + ψ(xᵢ₋₁)]
На каждом шаге выбирается интервал с максимальной
характеристикой Rᵢ.
Источник рисунка: Р. Г. Стронгин, В. П. Гергель, В. А. Гришагин, К. А.
Баркалов.
«Параллельные вычисления в задачах глобальной оптимизации»,
ННГУ.
точки
испытаний
оценка
M
расчёт
Rᵢ
лучший
интервал
новое
испытание
O(log k)
выбор через
приоритетную очередь
r>1
баланс
обзор/локализация
4 / 13

5.

Многомерность и гибридизация с локальным поиском
Гибридный цикл
номер
итерации
чётный?
итерация
k
нет
Пеано/Morton-развёртка переводит многомерную
область поиска в отрезок t ∈ [0,1]. Такой переход
удобен для произвольной размерности.
• локальный поиск не заменяет глобальный критерий
• каждая локальная проба проходит индексную оценку
• улучшенная точка возвращается в интервальную
структуру
Развёртка Мортона увеличивает
эффективную константу Липшица
да
Глобальный шаг АГП
новое испытание
и индексная оценка
Локальный шаг Хук–Дживс
координатные пробы
обновление
интервалов
и очереди
возвращение лучшего
решения
в очередь
следующая итерация
общей очереди

6.

Модель многосекционного механизма
Обобщённые
координаты
q = (θ₁,…,θₙ)
или q = (θ, L)
Прямая кинематика
φₙ = Σᵢ₌₁ᵏ θᵢ
xₙ = xₙ₋₁ + Lₙ cos φₙ
yₙ = yₙ₋₁ + Lₙ sin φₙ
Что даёт геометрическая модель
положение захвата
P(q)
сегменты звеньев
sᵢ(q) = [pᵢ₋₁,pᵢ]
зазор до
препятствий
безопасность
траектории
6 / 13

7.

Построение траектории и проверка безопасности
Стоимость перехода
E(Γ) = Σ [wθ‖Δθ‖² + wL‖ΔL‖² + Psafe]
Γ = (q⁰, q¹, …, qˢ)
сегмент
qᵃ → qᵇ
да
проверка
зазора
безопасен:
принять
нет
Основной
принцип
если небезопасен:
ввести mid
Переход qᵃ → qᵇ проверяется не только в концах. Если
прямой сегмент небезопасен, он делится, а две
подзадачи можно запускать параллельно через TBB.
левая
подзадача
Индексная схема прекращает расчёт полной стоимости,
если сегмент уже нарушил безопасность.
правая
подзадача
слияние
результатов
7/
13

8.

Программная реализация
Разработанная архитектура предусматривает строгое разделение
математического решателя и геометрии манипулятора.
Модель задачи
кинематика, препятствия,
функции gⱼ
Редукция
размерности
MortonND: [0,1] ↔ D
Поисковая
информация
IntervalND, локальные Mᵢ,
очередь интервалов
Локальное
ускорение
Хук-Дживс и возврат точки в
очередь
Параллелизм
Интерфейсы
O(log k)
выбор/вставка
интервала через кучу
MPI
независимые старты
с разными
ориентациями
Мортона
TBB
параллельные
рекурсивные
подзадачи
траектории
Python
скрипты сравнений и
интерфейс в стиле
Optuna
TBB-рекурсия, MPIмультистарт
Практический
результат
получена переиспользуемая C++-
Python, iOpt/Optuna для
сравнений
библиотека и демонстрационное
приложение для настройки, запуска и
визуальной проверки алгоритмов.
8 / 13

9.

Базовые проверки: операционные характеристики
Проверка корректности базовой реализации: операционные характеристики построены для
одномерной и двумерной версий алгоритма.
9 / 13

10.

Результаты: эффект локального ускорения
Постановка:
1–7
размерн.
70 000
запусков
2 метрики
100
повторов
АГП + Хук-Дживс
1,53×
0,356
относительн
ая скорость
среднее
время, мс
0,072
70k
среднее F
запусков
Интерпретация
• глобальная часть находит
перспективные области
• Хук-Дживс быстрее уточняет
найденный бассейн
• локальные пробы
возвращаются в общую
поисковую структуру
10 / 13

11.

Результаты: сравнение реализаций и MPI-мультистарт
Сравнение с
универсальными
58,2×
378×
фреймворками
iOpt
Optuna
медленнее в
этой серии
медленнее в
этой серии
0,072
1,574
среднее F у
АГП
среднее
время АГП, мс
MPI-мультистарт
• 6 процессов: F улучшилось
0,0724 → 0,0681
• по времени выигрыша нет:
задачи малы, накладные расходы
заметны
• для ускорения перспективна
схема Master-Worker с общей
очередью
11 / 13

12.

Демонстрационное приложение
Критерий: позиционирование — близость захвата к цели; траектория — линейная свёртка близости
к цели и энергетической стоимости перехода.
позиционирование восьмизвенного механизма
построение траектории: начальная сцена
промежуточная конфигурация
конечная конфигурация: безопасный обход
препятствий
12 / 13

13.

Выводы
Что сделано
• сформулирована black-box постановка
позиционирования и траекторного планирования
• реализована гибридная схема АГП + Хук-Дживс с
индексным учетом ограничений
• добавлены Morton-развёртка, локальные оценки
Липшица и очередь интервалов
• реализованы TBB-рекурсия, MPI-мультистарт и
демонстрационное
Полученный приложение
эффект
• локальное ускорение улучшило среднее значение
целевой функции и время в серии экспериментов
• индексная схема убрала зависимость от ручного
подбора штрафов
• специализированная C++-реализация оказалась
существенно быстрее универсальных фреймворков на
выбранном классе задач
1,53× в
ускорение
серии
АГП+ХукДживс
качество
MPI
выше,
скорость
требует
другой схемы
учёт
index
ограничений в
позициониров
ании и
траектории
demo
визуальная
проверка
траекторий
Спасибо за
внимание!
13 / 13