Метод оптимизации роя частиц процедура поиска, визуализированная

Визуализированная процедура поиска с использованием метода оптимизации роя частиц

Интуиция + математика + код для практиков

Изображение, созданное DALL·E 3 на основе запроса «Нарисуйте научно-фантастическое изображение, которое изображает стаю дронов, ищущих цель в городском ландшафте»

Люди любят подражать многим вещам в природе.

Мы копируем лягушек при плавании. Мы копируем птиц, устанавливая крылья на самолеты, чтобы обеспечить подъем. Мы копируем журавля/змею/богомола в боевых искусствах. Мы подражаем термитам, чтобы строить сооружения с эффективным контролем температуры (см. Eastgate Centre).

Это распространяется и на математические алгоритмы, где вы, вероятно, слышали о искусственных роях пчел, алгоритме оптимизации муравьиной колонии, поиске замкушек и алгоритме светлячков. Ранее я также говорил о эволюционном алгоритме, который работает на основе естественного отбора.

Сегодня я расскажу о PSO — оптимизации роя частиц. В конце этой статьи у вас будет код, который позволит вам реализовать решение и сгенерировать gif-изображение для визуализации процесса поиска.

Применение

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

Высокоразмерное пространство — это не просто абстрактное математическое понятие. Представьте себе проблему снабжения. Компании нужно решить, где разместить свою производственную фабрику, склады, центры распределения и розничные магазины. Для простоты давайте предположим, что у нас есть только одно из каждого. Это уже делает наше решение 8-мерным — (x₁, y₁, x₂, y₂, x₃, y₃, x₄, y₄).

Изображение, созданное DALL·E 3 на основе запроса «Нарисуйте панорамный вид на город с четырьмя ключевыми объектами — производственной фабрикой, складом, центром распределения и розничным магазином».

Абсолютное расположение (x₁, y₁, x₂, y₂, x₃, y₃, x₄, y₄) влияет на относительные расположения между каждым объектом. И абсолютное, и относительное расположение влияют на операционные расходы, ожидаемую выручку и, следовательно, прибыль. Хотя это несовершенно, мы можем примерно сказать, что пространство поиска и влияние на целевую функцию являются непрерывными.

Формулировка проблемы

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