Хореографический интеллект в исполнении роя частиц. С аккомпанементом на Python
Метод оптимизации роя частиц (Pasrticle Swarm Optimization) возник из попыток объяснить синхронное перемещение птичьих или рыбьих стай. Был предложен психологом Джеймом Кеннеди и инженером Расселом Эберхартом, которые в 1995 году выпустили книгу «Swarm Intelligence». В основе их метода лежит эволюционный алгоритм, имитирующий социальное поведение особей стаи.
В поведение группы в целом вносит вклад каждая особь в занимаемом ею пространстве. Их взаимодействие не носит антагонистического характера, поэтому складывается своего рода кооперация, где за счет небольших неудобств для каждого вся популяция в целом выигрывает.
В методе роя частиц имитируютcя элементы живой природы, например, такие, как рой насекомых, косяки рыб, стаи птиц или группы животных, которые перемещаются в пространстве и при этом целенаправленно изменяют свою скорость таким образом, чтобы приблизиться к привлекательным для них местам, например, тем, где расположена пища. Математически это выразится в достижении целевой функцией экстремального (например, минимального) значения.
Про общие принципы методов оптимизации см. здесь ==>>
Базовые принципы оптимизации роя частиц
Метод оптимизации роя частиц работает с совокупностью возможных решений, известных как частицы. У каждой частицы есть положение и скорость в пространстве поиска, и она перемещается, основываясь на своем собственном опыте и опыте своих соседей. К основным компонентам, управляющим движением частиц, относятся:
- Личная лучшая позиция (p_best): Лучшее решение, найденное отдельной частицей.
- Глобальная лучшая позиция (g_best): Лучшее решение, найденное как среднее по всем частицам роя.
Для каждого положения частицы вычисляется значение целевой функции, в соответствии с которым в следующий момент времени частица меняет свое положение и скорость в пространстве поиска ресурсов по определенным правилам.
Наблюдения за реальными стаями птиц дали, например, следующие очень простые правила:
- Один курс: Двигаться в том же направлении, что и соседи
- Не отрываться: Держаться близко к группе (никаких одиночек!)
- Не сталкиваться: Держимся вместе, но локтями не толкаемся!
Общая схема решения задач с помощью алгоритма роя частиц
Расчет новых положений и скоростей частиц
В этом алгоритме положения частиц рассчитываются исходя из текущего положения и скоростей изменения свойств частиц.
В начале частицы либо жестко зафиксированы, либо разбросаны случайным образом по всей области поиска.
Каждая частица имеет случайный вектор скорости. В каждой точке, где побывала частица, рассчитывается значение целевой функции. При этом запоминается персональное лучшее значение целевой функции (с соответствующими параметрами) частицы.
На каждой итерации частицы корректируют свое положение и скорость (модуль и направление), чтобы быть как можно ближе как к своей лучшей точке, так и к той, которая определилась по результатам всего роя (глобальная лучшая точка, определенная по всем частицам роя).
Обновление положения частиц
В движении частиц от итерации к итерации принимаются во внимание 3 компонента.
p_new = inertia + cognitive + socialГде
p_new – новое положение частицы
inertia – Инерциальная составляющая
cognitive – Когнитивная составляющая
social – Социальная составляющая
Компоненты:
Инерционный
Инерция — сопротивление движению или изменению направления движения конкретной частицы. Складывается из величины инерции и текущей скорости частицы. Итоговое значение инерции выражается в диапазоне от 0 до 1.
inertia = inertia_koef * v_curГде
inertia – Инерциальная составляющая
inertia_koef – Коэффициент инерции
v_cur – Текущая скорость
Коэффициент инерции, близкий к 0, приводит к медленному поиску лучшего решения (больше итераций). Увеличение значения в сторону 1 приводит к более быстрому результату, с меньшим числом итераций. В последнем случае увеличивается риск ненахождения глобального минимума (для сложных функций, имеющий несколько как глобальных, так и локальных минимумов). Также увеличивается риск ненахождения решения вообще.
Когнитивный
Отражает степень принятия во внимание собственной лучшей позиции частицы.
cognitive = cognitive_acceleration * (g_best - p_best)Когнитивное ускорение:
cognitive_acceleration = cognitive_const * cognitive_rnd Где
cognitive_const – Когнитивная константа. Число большее 0 и меньшее 2. Чем значение больше, тем выше весомость собственных данных частицы.
cognitive_rnd – Когнитивное случайное число от 0 до 1.
Социальный
Отражает степень принятия во внимание лучшей позиции всех частиц роя.
social = social_acceleration * (g_best - p_best)Социальное ускорение:
social_acceleration = social_const * social_rnd Где
social_const – Социальная константа. Число большее 0 и меньшее 2. Чем выше это значение, тем весомее групповые данные всех частиц роя.
social_rnd – Социальное случайное число от 0 до 1.
Значение социальной константы также меняется от 0 до 2. Чем выше это значение, тем весомее групповые данные всех частиц роя.
Обновление скоростей частиц
Новые скорости рассчитываются аналогично расчету новых положений.
v_new = inertia + cognitive + socialРеализация алгоритма роя частиц на Python
Для реализации алгоритма была выбрана не просто самая простая n-мерная сферическая функция для оптимизации. А более того – ее простейший вариант, 2-мерная круговая плоская функция, описывающая позиции как координаты в измерениях X и Y и имеющая решение X = 0, Y = 0.
При создании роя начальная точка, которая является центром случайного распределения частиц смещена относительно решения: X = 6, Y = -3.
Код был написан на языке Python 3.11. Выполнялся во фреймворке Google Colaboratory.
Код Python скрипта
# Целевая функция
def sphere(x, bias):
total=0
for i in range(len(x)):
total+=(x[i])**2
return total#--- IMPORT DEPENDENCIES ------------------------------------------------------+
from random import random
from random import uniform
#--- MAIN ---------------------------------------------------------------------+
# КЛАСС
class Particle:
def __init__(self, x0, bias):
self.position_i=[] # Положение частиц
self.velocity_i=[] # Скорость частиц
self.pos_best_i=[] # Лучшие положения частиц
self.err_best_i=-1 # Лучшая ошибка частицы
self.err_i=-1 # Ошибка частицы
for i in range(0,num_dimensions):
self.velocity_i.append(uniform(-1,1))
self.position_i.append(uniform(-1,1))
# Расчет текущего значения целевой функции
def evaluate(self,costFunc, bias):
self.err_i=costFunc(self.position_i, bias)
# check to see if the current position is an individual best
if self.err_i<self.err_best_i or self.err_best_i==-1:
self.pos_best_i=self.position_i.copy()
self.err_best_i=self.err_i
# Расчет нового значения скорости частицы
def update_velocity(self,pos_best_g):
w=0.5 # Константа инерции относительно предыдущей скорости
c1=1 # Когнитивная константа
c2=2 # Социальная константа
for i in range(0,num_dimensions):
r1=random()
r2=random()
vel_cognitive=c1*r1*(self.pos_best_i[i]-self.position_i[i])
vel_social=c2*r2*(pos_best_g[i]-self.position_i[i])
self.velocity_i[i]=w*self.velocity_i[i]+vel_cognitive+vel_social
# Расчет нового положения частицы по новой скорости
def update_position(self,bounds):
for i in range(0,num_dimensions):
self.position_i[i]=self.position_i[i]+self.velocity_i[i]
# Коррекция выхода за пределы максимального значения позиции
if self.position_i[i]>bounds[i][1]:
self.position_i[i]=bounds[i][1]
# Коррекция выхода за пределы минимального значения позиции
if self.position_i[i]<bounds[i][0]:
self.position_i[i]=bounds[i][0]
# Главная функция с циклом обработки
def PSO(costFunc, x0, bounds, num_particles, maxiter, verbose=False, error_limit = 0.01):
global num_dimensions
num_dimensions=len(x0)
err_best_g=-1 # Лучшая ошибка роя
pos_best_g=[] # Лучшая позиция роя
# Создание роя
bias = [6.0, -3.0]
swarm=[]
for i in range(num_particles):
pos = Particle(x0, bias)
xx = pos.position_i
print(i, xx)
swarm.append(pos)
# Начало цикла оптимизации
i=0
while i<maxiter:
# Цикл по частицам роя, с расчетом целевой функции
for j in range(0,num_particles):
swarm[j].evaluate(costFunc, bias)
# Выбор текущей частицы как лучшей (глобальной) для роя
if swarm[j].err_i<err_best_g or err_best_g==-1:
pos_best_g=list(swarm[j].position_i)
err_best_g=float(swarm[j].err_i)
# Цикл обновления позиций и скоростей частиц роя
for j in range(0,num_particles):
swarm[j].update_velocity(pos_best_g)
swarm[j].update_position(bounds)
i+=1
if verbose:
print(f'Итерация: {i:>4d}, Ошибка: {err_best_g:10.6f} Координаты X, Y: {pos_best_g}')
if err_best_g < error_limit:
break
# Печать окончательного результата
if verbose:
print(f'\nРешение с ошибкой < {error_limit} найдено за {i-1} итераций')
print(f' > Ошибка: {err_best_g} Координаты X, Y: {pos_best_g}')
return err_best_g, pos_best_g
#--- END ----------------------------------------------------------------------+Выполнение скрипта
Генерируем случайные положения и скорости 300 частиц, центрированных вокруг X = 0, Y = 0 и разбросом значений от -15 до +15.
#--- RUN ----------------------------------------------------------------------+
# zero - centered initial data
initial=[5,5] # Начальная стартовая позиция [x1,x2...]
bounds=[(-15,15),(-15,15)] # Границы решения [(x1_min,x1_max),(x2_min,x2_max)...]
err_lim = 0.000001
PSO(sphere,initial,bounds,num_particles=300, maxiter=300, verbose=True, error_limit=err_lim)
#--- END -Журнал выполнения скрипта
Итерация: 1, Ошибка: 1.993344 Координаты X, Y: [1.4008788742607452, -0.17573376313227573]
Итерация: 2, Ошибка: 0.026502 Координаты X, Y: [0.11284225996849173, -0.11733988617960289]
Итерация: 3, Ошибка: 0.026502 Координаты X, Y: [0.11284225996849173, -0.11733988617960289]
Итерация: 4, Ошибка: 0.014909 Координаты X, Y: [0.053319011695837304, -0.1098451562192628]
Итерация: 5, Ошибка: 0.006643 Координаты X, Y: [-0.04374567027076404, 0.06877351440446589]
Итерация: 6, Ошибка: 0.006643 Координаты X, Y: [-0.04374567027076404, 0.06877351440446589]
Итерация: 7, Ошибка: 0.002830 Координаты X, Y: [0.027178932425718783, 0.04573069196137777]
Итерация: 8, Ошибка: 0.002685 Координаты X, Y: [-0.04987112050741349, -0.014061180193128103]
Итерация: 9, Ошибка: 0.000855 Координаты X, Y: [0.015649990082417964, 0.02469394088986021]
Итерация: 10, Ошибка: 0.000014 Координаты X, Y: [0.0023353839592563305, -0.0029006523481716062]
Итерация: 11, Ошибка: 0.000014 Координаты X, Y: [0.0023353839592563305, -0.0029006523481716062]
Итерация: 12, Ошибка: 0.000014 Координаты X, Y: [0.0023353839592563305, -0.0029006523481716062]
Итерация: 13, Ошибка: 0.000014 Координаты X, Y: [0.0023353839592563305, -0.0029006523481716062]
Итерация: 14, Ошибка: 0.000014 Координаты X, Y: [0.0023353839592563305, -0.0029006523481716062]
Итерация: 15, Ошибка: 0.000014 Координаты X, Y: [0.0023353839592563305, -0.0029006523481716062]
Итерация: 16, Ошибка: 0.000014 Координаты X, Y: [0.0023353839592563305, -0.0029006523481716062]
Итерация: 17, Ошибка: 0.000008 Координаты X, Y: [-0.0012308663100170161, -0.002517738660911684]
Итерация: 18, Ошибка: 0.000001 Координаты X, Y: [-0.0009478210682037065, 0.0004899019048626684]
Итерация: 19, Ошибка: 0.000001 Координаты X, Y: [-0.0009478210682037065, 0.0004899019048626684]
Итерация: 20, Ошибка: 0.000000 Координаты X, Y: [0.0003252710794947244, 2.0358954456239572e-05]
Решение с ошибкой < 1e-06 найдено за 19 итераций
> Ошибка: 1.0621576218221456e-07 Координаты X, Y: [0.0003252710794947244, 2.0358954456239572e-05]
(1.0621576218221456e-07, [0.0003252710794947244, 2.0358954456239572e-05])Результат выполнения
Алгоритм сходится и выполняется очень быстро.
300 точек изначально разбросанные случайным образом с нормальным распределением вокруг точки X = 6, Y = -3 стянулись к решению за 19 итераций, занявших менее 1 минуты.
Применение алгоритма роя частиц
Оптимизация роя частиц (PSO) была успешно реализована в различных реальных приложениях в различных областях. Вот несколько примечательных примеров:
- Robotic Control – Роботизированное управление: PSO используется для оптимизации параметров управления роботизированными манипуляторами, повышая их точность и оперативность в таких задачах, как сварка и обработка материалов. Было показано, что нечеткий ПИД-контроллер в сочетании с PSO значительно улучшает управление крутящим моментом в роботизированных приложениях.
- Engineering Design – Инженерное проектирование: В инженерном деле PSO применяется для оптимизации конструкций и механических систем, что позволяет эффективно использовать ресурсы и улучшать эксплуатационные характеристики.
- Neural Network Training – Обучение нейронных сетей: PSO помогает оптимизировать веса нейронных сетей, повышая эффективность их обучения и точность в таких задачах, как распознавание образов и классификация.
- Image Processing – Обработка изображений: Алгоритмы PSO используются для сегментации и улучшения изображения, эффективно группируя пиксели на основе их характеристик для улучшения качества изображения.
- Financial Forecasting – Финансовое прогнозирование: В сфере финансов PSO используется для оптимизации торговых стратегий и управления портфелем путем анализа исторических данных с целью прогнозирования будущих рыночных тенденций.
- Data Clustering – Кластеризация данных: PSO используется в алгоритмах кластеризации для эффективной группировки больших наборов данных, что упрощает выявление закономерностей и идей в данных.
- Renewable Energy Optimization – Оптимизация использования возобновляемых источников энергии: PSO оптимизирует размещение и эксплуатацию возобновляемых источников энергии, таких как ветряные турбины и солнечные батареи, для максимизации выработки энергии при минимизации затрат.
- Telecommunications – Телекоммуникации: Применяется для оптимизации сетевых конфигураций и распределения ресурсов в телекоммуникационных системах, повышения эффективности передачи данных.
- Healthcare Applications – Приложения для здравоохранения: PSO помогает в системах медицинской диагностики, оптимизируя алгоритмы выбора признаков и классификации, что приводит к повышению точности обнаружения заболеваний.
- Route Optimization – Оптимизация маршрута: PSO используется для решения задач маршрутизации транспортных средств, помогая логистическим компаниям оптимизировать маршруты доставки для снижения затрат и увеличения времени обслуживания.
- Supply Chain Management – Управление цепочками поставок: Компании используют PSO для управления запасами и оптимизации распределения, обеспечивая эффективную работу цепочки поставок.
- Manufacturing Processes – Производственные процессы: На производстве PSO оптимизирует производственные графики и работу оборудования, сокращая время простоя и увеличивая производительность.
- Environmental Monitoring – Мониторинг окружающей среды: PSO применяется для оптимизации размещения датчиков в системах мониторинга окружающей среды, обеспечивая эффективный сбор данных при минимизации затрат.
- Smart Grid Management – Интеллектуальное управление энергосистемой: Это помогает оптимизировать распределение энергии в интеллектуальных сетях, повышая надежность и эффективность систем электроснабжения.
- Agricultural Optimization – Оптимизация сельского хозяйства: PSO используется в точном земледелии для оптимизации стратегий посадки и распределения ресурсов в зависимости от условий окружающей среды и требований к урожаю.
- Game Development – Разработка игр: В играх PSO может оптимизировать поведение игрового ИИ, регулируя параметры, которые управляют движениями персонажа или процессами принятия решений.
- Structural Health Monitoring – Мониторинг состояния конструкций: PSO помогает оценить состояние конструкций за счет оптимизации сенсорных сетей, которые отслеживают вибрации и уровни нагрузки в режиме реального времени.
- Traffic Flow Optimization – Оптимизация транспортных потоков: Города используют PSO для оптимизации сигналов светофора, чтобы улучшить транспортный поток и уменьшить заторы в часы пик.
- Robust Control Systems – Надежные системы управления: В инженерии управления PSO используется для разработки надежных контроллеров, которые могут эффективно справляться с неопределенностями в динамических системах.
- Bioinformatics – Биоинформатика: PSO помогает оптимизировать процессы отбора генов для моделей классификации рака, повышая точность прогнозной аналитики в исследованиях геномики.
Эти примеры иллюстрируют универсальность оптимизации роя частиц в различных областях, демонстрируя ее эффективность при решении сложных задач оптимизации с помощью принципов коллективного разума, вдохновленных природой.
