Оптимизация роя частиц

Question

Я использую Particle Swarm Optimization (PSO) в Java. У меня мало знаний о том, что мы делаем. С тех пор я подаю заявку на множественное выравнивание последовательностей в биоинформатике.

Нам нужно найти положение и скорость для выравнивания этих последовательностей. Мне нужно подробное объяснение и ссылки о PSO и необходимости расчета скорости и положения в PSO. Если возможно, мне нужен простой пример, объясняющий PSO в Java. На самом деле, мне нужно понять, как это оптимизирует проблему.

public class Position {
 private double x;
 private double y;

 public Position(double x, double y) {
 this.x = x;
 this.y = y;
 }

 public double getX() {
 return x;
 }

 public void setX(double x) {
 this.x = x;
 }

 public double getY() {
 return y;
 }

 public void setY(double y) {
 this.y = y;
 }
}

Вот класс для представления положения частицы с помощью геттеров и сеттеров

Как и другие классы доступны здесь

Answer 1

Оптимизация роя частиц:

1. случайным образом инициализирует набор частиц в случайных положениях в пространство поиска;
2. оцените все позиции и обновите лучшие в мире должность и личные лучшие позиции;
3. обновить каждую скорость на основе относительного положения наилучшего глобального положения, текущая скорость частицы, личная лучшая позиция частица и некоторый случайный вектор;
4. Перейти к 2.

Answer 2

Общий обзор

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

Качество / оценка заданной позиции в пространстве поиска измеряется целевой функцией, которая является оптимизируемой функцией.

Частицы движутся через пространство поиска в поисках оптимального решения.

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

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

Уравнения обновления

На итерации t позиция данной частицы обозначается x (t) . Его новая позиция для следующей итерации рассчитывается по формуле:

x (t + 1) = x (t) + v (t + 1)

где v (t + 1) обозначает скорость частицы для следующей итерации. Обратите внимание, что каждое из приведенных значений является векторами. Длина этих векторов будет равна размерности задачи / количеству входных переменных целевой функции. (Извиняюсь за мою ужасную нотацию; у меня недостаточно репутации, чтобы опубликовать красивые уравнения). Скорость частицы рассчитывается по формуле:

v (t + 1) = w * v (t) + c1 * r1 * (pBest (t) - x (t)) + c2 * r2 * (gBest (t) - x (t) )

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

w называется весом инерции и регулирует влияние составляющей импульса. c1 и c2 являются коэффициентами когнитивного и социального ускорения и регулируют важность когнитивного и социального компонентов (соответственно). r1 и r2 - векторы случайных чисел (взятых из распределения по 0 в 1), которые используются для масштабирования каждого компонента векторов разности.

Первый вектор разности (pBest (t) - x (t)) позволяет частице двигаться в направлении своего личного лучшего / pBest - лучшего положения, с которым она столкнулась до сих пор. (Чтобы реализовать алгоритм, необходимо, чтобы частица исследовала каждую позицию, с которой сталкивалась, и сохраняла ее, если она пока лучшая).

Второй вектор разности (gBest (t) - x (t)) позволяет частице использовать информацию от других частиц в рое. В этом выражении gBest (t) обозначает лучшую позицию, найденную роем на данный момент. (Таким образом, для реализации, после каждой итерации, должны быть проверены оценки всех частиц, чтобы можно было сохранить наилучшую из них для использования в будущем).

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

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

Другие соображения

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

Кроме того, существует ряд других ловушек, таких как значения w , c1 и c2 . Хотя здесь можно делать причудливые вещи, общее правило заключается в следующем:

ш = 0,729844

c1 = c2 = 1.49618

, как предлагает http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=870279&tag=1, чтобы привести к сходящемуся поведению (то есть, чтобы все частицы в конечном итоге сходились примерно к одной и той же точке).

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

Некоторые стороны также советуют использовать фиксирование скорости (где каждый компонент скорости ограничен сверху и снизу некоторым максимальным и минимальным значением; если скорость частицы превышает это значение, она фиксируется до максимума / минимума). Обычно в этом нет необходимости, если w, c1 и c2 выбраны правильно, а gBest и pBest обновляются только в том случае, если они находятся в пределах области поиска.