Метод роя частиц для задачи глобальной оптимизации

snegovick — Чт, 30/09/2010 - 17:49

Метод оптимизации с помощью роя частиц (Particle Swarm Optimization, далее PSO), базирующийся на моделировании поведения популяции частиц в пространстве параметров задачи оптимизации, был предложен в работе [1].

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

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

Описание алгоритма PSO

Алгоритм PSO использует для решения рой частиц, где каждая частица представляет собой возможное решение задачи оптимизации. Пусть s - количество агентов в рое. Каждая i-ая частица может быть представлена как объект с рядом параметров.

xi - положение частицы

vi - скорость частицы

yi - личное наилучшее положение частицы

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

t+1

if f

t+1

if f

t+1

Существует две версии базового алгоритма PSO, называемые gbest и lbest. Разница заключается в том, с какими набором частиц взаимодействует каждая частица. Обозначим символом y это взаимодействие. Определение y в случае gbest представлено в следующем выражении:

=min

Данное выражение говорит о том, что y

- лучшая позиция когда-либо посещенная кем-либо из роя.

Стохастическая составляющая алгоритма представлена двумя случайными параметрами r1

и r2

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

2] . Скорость частицы на i-м шаге расчитывается отдельно для каждого измерения j

n , таким образом vi

j обозначает j-е измерение вектора скорости i-й частицы. Расчет j-го компонента вектора скорости i-й частицы на t+1 шаге производится по формуле:

t+1

=wcvi

+c1r1

−xi

+c2r2

−xi

Таким образом, c2 управляет воздействием глобального лучшего положения, а c1 управляет воздействием личного лучшего положения на скорость каждой частицы. Для улучшения сходимости алгоритма вводится коэффициент инерции wc [2]. Положение каждой частицы в i-м измерении вычисляется по формуле

t+1

=xi

+vi

t+1

Подготовительная часть алгоритма заключается в следующем :

Присвоить координатам xij случайные значения в пределах −xmaxxmax для всех i1s и j1n,
Инициализировать векторы скоростей нулями,
Присвоить yi значения xi.

Пример решения задачи оптимизации с помощью алгоритма PSO на maxima

Пусть задана функция.

=x21+x22

Необходимо найти минимум этой функции на промежутке x1x2−1010 . Известно, чтоминимум находится в точке (0).
Решение:

f(x1,x2):= x1^2+x2^2;
 
ll: -10;
ul: 10;
numpart: 20;
numdims: 2;
wc: 0.9;
c1: 1.8;
c2: 1.9;
 
xv: ematrix(numpart,numdims,0,1,1);
vv: ematrix(numpart,numdims,0,1,1);
fitgbest: 2000;
fitlbest: ematrix(numpart,1,0,1,1);
fitlbest: fitlbest+fitgbest;
xlbest: ematrix(numpart,numdims,0,1,1);
xgbest: ematrix(1,numdims,0,1,1);
 
fitx: ematrix(numpart,1,0,1,1);
 
for i:1 step 1 thru numpart do (
    for j:1 step 1 thru numdims do (
        xv[i][j]: ll + random((ul-ll))
    )
)$
 
min: 0$
minind: 0$
display (xv);
 
globalbest : [];
 
for i:1 step 1 thru 20 do (
    for j:1 step 1 thru numpart do (
        fitx[j][1]: f(xv[j][1], xv[j][2]),
    if fitx[j][1] < fitlbest[j][1] then (
       fitlbest[j][1] = fitx[j][1],
       for k:1 step 1 thru numdims do (
           xlbest[j][k]: xv[j][k]
       )
    )  
    ),
    
   min: fitx[1][1],
   minind: 1,
   for j:1 step 1 thru numpart do (
       if fitx[j][1]<;min then (
          minind: j,
      min: fitx[j][1]
       )
   ),
 
   dispm: addcol(xv,fitx),
   display (dispm),
 
   if min<;fitgbest then (
      fitgbest: min,
      for j:1 step 1 thru numdims do (
            xgbest[1][j]: xv[minind][j]
      )
   ),
 
   display (fitgbest),
   globalbest : append(globalbest, [[i,fitgbest]]),
 
   for j:1 step 1 thru numpart do (
       for k:1 step 1 thru numdims do (
           r1: (random(1000))/1000,
           r2: (random(1000))/1000,
           vv[j][k]: wc*vv[j][k]+c1*r1*(xlbest[j][k]-xv[j][k])+c2*r2*(xgbest[1][k]-xv[j][k]),
           xv[j][k]: xv[j][k]+vv[j][k]
       )
   )
)$
 
display(globalbest);
 
plot2d([discrete, globalbest], [y,0,50], [psfile, "globalbest.eps"]);

$график $f\left( \hat{y} \right)$$

На рисунке изображена зависимость величины параметра fy от количества итераций для вариантов алгоритма
с 2, 5, 10, 20 частицами. Очевидно, что увеличение количества частиц
до определенного порога позволяет существенно увеличить скорость
получения результа.

Список литературы:

[1] J. Kennedy, R.C. Eberhart, Proceedings of IEEE International Conference on Neural
Networks,volume IV, pages 1942-1948, Perth, Australia, IEEE
Service Center, Piscataway, NJ, 1995

[2] Y. Shi, R. C. Eberhart
A modified Particle Swarm Optimizer. IEEE International
Conference of Evolutionary Computation, Anchorage, Alaska, 1998

Блог пользователя - snegovick

Отправить комментарий

Ваше имя:

E-mail:

Содержимое этого поля является приватным и не будет отображаться публично.

Домашняя страница:

Комментарий: *

Доступные HTML теги: <a> <em> <strong> <cite> <code> <ul> <ol> <li> <dl> <dt> <dd>
Syntax highlight code surrounded by the {syntaxhighlighter SPEC}...{/syntaxhighlighter} tags, where SPEC is a Syntaxhighlighter options string or "class="OPTIONS" title="the title".

Подробнее о форматировании

CAPTCHA

Этот вопрос задается для того, чтобы выяснить, являетесь ли Вы человеком или представляете из себя автоматическую спам-рассылку.

   ____   ____      _   _       ___   _____ 
  / ___| |___ \    (_) | |__   |_ _| | ____|
 | |       __) |   | | | '_ \   | |  |  _|  
 | |___   / __/    | | | |_) |  | |  | |___ 
  \____| |_____|  _/ | |_.__/  |___| |_____|
                 |__/

Введите код, указанный выше: *

Введите код, изображенный в стиле ASCII-арт.

illumium.org