PSO (Particle Swarm Optimization) Algorithm

PSO (Particle Swarm Optimization) Algorithm이란?

 

Particl Swarm Optimization을 줄여서 PSO 알고리즘은 이는 Eberhart 와 Kennedy(1995)에 의해 제안된 알고리즘으로 Swarm Intelligence Algorithm의 종류 중 하나이다. PSO는 동물이나 곤충의 집단 행동에서 영감을 받아 식량원 탐색 및 번식을 위한 최적화 문제를 해결하는 데 사용된다. PSO 알고리즘은 Swarm을 기반으로 한 탐색 과정으로, 개별 입자는 D-차원 검색 공간의 최적화된 문제의 잠재적인 솔루션으로 정의된다. 각 입자는 Swarm과 자신의 최적 위치, 그리고 속도를 기억할 수 있다. 세대마다 입자 정보가 결합하여 각 차원의 속도를 조정하고, 이를 통해 입자의 새로운 위치를 계산한다. 입자는 다차원 검색 공간에서 상태를 지속해서 변경하여 균형이나 최적 상태에 도달하거나 계산 한계를 초과할 때까지 탐색을 계속한다. PSO 알고리즘은 복잡한 문제를 최적화하는 간단하고 견고하며 효율적인 방법으로 큰 탐색 공간을 가진 최적화 작업을 처리하는데 유용하다. 그래디언트가 없는 확렬적 최적화 방법으로 PSO는 큰 검색 공간에서 기존의 그리드 탐색 방법보다 우수한 성능을 발휘한다. PSO는 다양한 분야에서 적용되며, 최적의 솔루션을 찾기 위해 입자들의 집단적 행동을 활용하는 강력한 알고리즘으로 인정받고 있다.

 

 

 

1-1) PSO 기본원리

 

PSO 알고리즘은 다음과 같은 순서로 작동한다. 

 

1 . Start : 알고리즘의 시작

 

2. Swarm initialization (Swarm 초기화): 

 ● swarm내의 각 입자는 초기 속도와 위치를 무작위로 할당받는다.

 

3. Particla fitness evaluating (입자 적합도 평가) :

 ● 각 입자의 현재 위치에서의 적합도(fitness)를 목표 함수 f(x)를 통해 계산된다. 

 ● 이건은 목표 함수를 사용하여 측정될 수 있으며, 입자가 현재 위치에서 얼마나 좋은 솔루션인지를 나타낸다. 

 

4. Calculating the individual historical optimal position(개별 최적 위치 계산) :

 ● 각 입자는 이전에 발견한 최적 위치인 pi를 업데이트한다.

 ● 현재 위치의 적합도가 이전에 기록한 최적 위치보다 좋으면 pi가 업데이트 된다. 

 

5. Calculating the wsarm historical optimal position(스웜 최적 위치 계산) :

 ● Swarm의 전체적인 최적위치인 g가 계산된다. 

 ● 각 입자가 발견한 pi 중에서 가장 좋은 것을 기반으로 한다. 

 ● pbest: 자신의 경험에서 가장 좋았던 위치로 가고자 하는 경향. (pi)

 ● gbest: 군집 전체가 가장 좋다고 판단한 위치로 가고자 하는 경향. (gi)

 

6. Updating particle velocity and position according to the velocity and position updating equation(속도 및 위치 업데이트):

 

 ● 각 입자의 속도와 위치가 속도 및 업데이트 방정식에 따라 업데이트 된다. 

 ● 속도 업데이트 방정식 :

속도 업데이트 방정식

 

7. Satisfying the ending condition(종료 조건 충족 확인) :

 

  ● 종료 조건을 확인한다. 예를 들어, 최대 반복 횟수에 도달하거나 원하는 적합도가 달성되면 종료된다. 

  ● 만약 종료 조건이 충족되면 알고리즘이 종료된다. 

 

8. End(종료) :

  알고리즘 종료

 

 

PSO 알고리즘의 Flowchart는 다음과 같다.

 

 

 

 

참고논문 

[17] Wang, Dongshu, Dapei Tan, and Lei Liu. "Particle swarm optimization algorithm: an overview." Soft computing 22 (2018): 387-408.
[18] Loshchilov, Ilya, and Frank Hutter. "CMA-ES for hyperparameter optimization of deep neural networks." arXiv preprint arXiv:1604.07269 (2016).