Skip to content
Назад к результатам поиска

Оптимизация роем частиц (PSO)

Год
1995
Тип
Population-based metaheuristic / swarm intelligence

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

Оптимизация роем частиц (PSO) — это метаэвристический алгоритм, основанный на популяции, представленный Кеннеди и Эберхартом в 1995 году, который был вдохновлен коллективным движением стай птиц и косяков рыб.

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

Интуиция метода

Представьте стаю птиц, ищущую в большом поле самый богатый источник пищи. Ни одна птица не имеет карты, но каждая помнит лучшее место, которое она лично посетила, и осведомлена о лучшем месте, найденном любой птицей поблизости. Каждая птица направляет свой полет частично к своему собственному запомненному лучшему местоположению и частично к коллективному лучшему местоположению стаи, соответствующим образом корректируя скорость. После многих таких корректировок вся стая сходится к самому богатому району. PSO работает именно так: каждая частица — это кандидатное решение, ее положение — это само решение, а рой коллективно движется к оптимуму, объединяя индивидуальную и социальную память.

История

PSO был представлен Джеймсом Кеннеди и Расселом Эберхартом на Международной конференции по нейронным сетям IEEE в 1995 году, опираясь непосредственно на имитационные модели социального поведения стай птиц и косяков рыб. Фундаментальная статья 1995 года установила уравнения обновления скорости и положения, которые остаются центральными для алгоритма. В 1998 году Ши и Эберхарт ввели параметр веса инерции в обновление скорости, что значительно улучшило контроль сходимости и стало стандартной модификацией, принятой последующими исследованиями. PSO быстро завоевал популярность как практичная альтернатива генетическим алгоритмам для непрерывной оптимизации благодаря своей простоте и конкурентоспособной скорости сходимости, и с тех пор применяется в инженерии, настройке гиперпараметров машинного обучения, обработке сигналов и научном моделировании.

Когда применять

PSO подходит для задач непрерывной оптимизации, где функция приспособленности может быть оценена в любой точке пространства поиска, но может быть недифференцируемой, мультимодальной или дорогостоящей для аналитического вычисления. Он не требует предположения о нормальности и минимального размера выборки, что делает его применимым в различных областях. Метод лучше всего работает, когда границы пространства поиска известны заранее, когда вес инерции и коэффициенты ускорения тщательно настроены, и когда выделено достаточное количество итераций. Если количество итераций слишком мало (менее нескольких сотен для нетривиальных задач), вероятна преждевременная сходимость, и байесовская оптимизация может быть более безопасной альтернативой.

Ограничения и замечания

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

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Быстрая сходимость в непрерывных пространствах поиска по сравнению со многими методами, основанными на популяциях.
  • Очень мало параметров для настройки — в основном вес инерции и два коэффициента ускорения.
  • Не требует информации о градиенте или производной, что делает его применимым к недифференцируемым функциям приспособленности типа «черный ящик».
  • Естественно масштабируется для непрерывных задач высокой размерности.
  • Концептуально прост и легок в реализации.

Применение

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

Как это работает

Как это работает

1

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

2

Функция приспособленности вычисляется для каждой частицы в ее текущем положении. Это единственный специфичный для задачи шаг: PSO не налагает никаких ограничений на форму функции приспособленности, кроме требования, чтобы она могла быть оценена в любой точке непрерывного пространства поиска. Личное лучшее положение каждой частицы и глобальное лучшее положение роя обновляются всякий раз, когда новое положение дает лучшее значение приспособленности.

3

Скорость каждой частицы обновляется с использованием трех компонентов: инерционного члена (масштабированная предыдущая скорость, способствующая инерции), когнитивного члена (притяжение к личному лучшему положению частицы) и социального члена (притяжение к глобальному лучшему положению роя). Затем новое положение вычисляется путем добавления обновленной скорости к текущему положению. Вес инерции контролирует компромисс между исследованием и эксплуатацией: более высокое значение способствует широкому исследованию, в то время как более низкое значение способствует тонкой эксплуатации известных хороших областей.

4

Шаги оценки и обновления повторяются предписанное количество итераций. Рой постепенно сужает свой поиск вокруг наиболее перспективного региона. Выполнение завершается, когда достигается предельное количество итераций, после чего глобальное лучшее положение сообщается как решение. Достаточное количество итераций — обычно не менее нескольких сотен или тысячи для нетривиальных задач — необходимо, чтобы рой мог сойтись; слишком раннее прекращение рискует привести к субоптимальному результату.

Частые ошибки

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

Часто задаваемые вопросы

Чем PSO отличается от генетического алгоритма?

Оба являются метаэвристиками, основанными на популяциях, для оптимизации, но они различаются по механизму. Генетический алгоритм развивает популяцию через операторы отбора, скрещивания и мутации, вдохновленные биологической эволюцией. PSO вместо этого перемещает частицы в непрерывном пространстве, обновляя скорости на основе индивидуальной и социальной памяти — нет скрещивания или мутации. PSO обычно имеет меньше параметров для настройки и часто сходится быстрее на непрерывных задачах, в то время как генетические алгоритмы могут быть более естественно адаптированы к дискретным или комбинаторным пространствам.

Каковы ключевые параметры и как их следует устанавливать?

Три основных параметра: вес инерции (w), который контролирует, какая часть предыдущей скорости сохраняется; когнитивный коэффициент (c1), который масштабирует притяжение к личному лучшему положению частицы; и социальный коэффициент (c2), который масштабирует притяжение к глобальному лучшему положению. Распространенной отправной точкой из литературы является w около 0.7–0.9, c1 и c2 около 1.5–2.0. Вес инерции часто линейно уменьшается в течение итераций, чтобы сместить рой от исследования в начале к эксплуатации позже.

Может ли PSO обрабатывать дискретные или комбинаторные задачи?

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

Как узнать, что рой преждевременно сошелся?

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

Похожие методы

Источники

  1. Kennedy, J. & Eberhart, R. (1995). Particle Swarm Optimization. IEEE International Conference on Neural Networks (ICNN), 1942-1948.

    Открыть ссылку DOI
    Скопировано.
  2. Shi, Y. & Eberhart, R. (1998). A Modified Particle Swarm Optimizer. IEEE Congress on Evolutionary Computation (CEC).

    Открыть ссылку на публикацию
    Скопировано.