Particle Swarm Optimization (PSO)

PSO 알고리즘

 

▪PSO는 새나 물고기 무리 등의 사회적 행동양식에 대한 규칙성을 증명하는것에 착안하여 개발

▪나중에 단순화 되었고, 최적화 문제를 해결하는데 사용되어짐

 

 

참고 문헌

 

▪Adaptive Nulling Algorithm for Null Synthesis on the Moving Jammer Environment : 서종우

- PSO 알고리즘은 자기학습을 통해 최적의 해를 찾는 최적화 알고리즘

- 알고리즘이 매우 간단하고 구현이 용이하여 함수최적화, 신호처리, 자동적응제어 등의 다양한 분야에서 널리 사용되어짐

▪http://astl.snu.ac.kr/Research/mdo04.asp?tp1=025

- PSO는 군집 개체를 모방하였다는 점에서 GA(Generic Algorithm)와 유사

- PSO는 GA를 사용하였을 때와 거의 동일한 수렴 결과 값을 얻을 수 있음

- 알고리즘 특성상 설계변수가 복잡한 경우에서 수렴 시간이 단축

- 다른 탐색 알고리즘과 달리, 진화 연산처럼 방대하고 복잡한 함수에 대하여 전역적인 최적화(global optimization)할 수 있음

- 진화 연산보다 수행속도가 빠르기 때문에 최근 크게 주목받고, 기존의 알고리즘으로 해결하기 어려운 분야에 적용

 

 

▪Kennedy, James. "Particle swarm optimization." Encyclopedia of machine learning. Springer, Boston, MA

- 저자가 개발한 PSO는 매우 간단한 개념으로 구성되어있으며, 몇줄의 컴퓨터 코드로 구현 가능

- 원시적인 수학 연산만 필요하며, 메모리 요구 사항과 속도 측면에서 계산 비용이 저렴

- (비공식적으로) PSO를 이용하여 구한 가중치가 경사하강법으로 구한 가중치보다 더 성능이 좋았음

 

 

PSO 개념

 

▪PSO는 swarm이라고 불리는 particle의 bunch를 사용

▪이 particle들은 search-space를 돌아다니며 탐색

▪이 particle들은 조건에 의해 안내되는 방향으로 이동

- 관성(Inertia) - particle 자신의 이전 속도

- 인지력(Cognitive Force) - 각각 particle의 best known position으로부터의 거리

- 사회력(Social Force) - swarm best known position과의 거리

 

 

▪inertia 는 위의 관성

▪individual best는 위의 인지력

▪swarm best는 위의 사회력

 

▪각 particle은 

- 자신이 이전에 이동한 위치를 알고있고

- 자신이 지났던 위치 중에 가장 최적의 값을 갖는 위치를 기억하며

- swarm 내에서 최적의 값을 갖는 위치를 공유

 

▪위의 세가지 방향을 합하여 (벡터 연산) 새로 나아갈 position을 알 수 있음 (아래 식 이용)

  

 

 

HyperParameter Tuning 시 최적화 과정

 

▪이 과정은 2가지의 hyperparameter를 갖는 상황에서 search-space는 2가지 하이퍼파라미터 모두 -3 ~ 3 까지로 설정된 경우

▪노란색 점은 particle을 의미하며, 초기 위치는 random하게 하거나 gridsearch 방식처럼 모든 경우의 수를 사용할 수 있음

▪화살표는 위의 식을 사용하여 계산한 다음 위치를 가르킴

▪particle들이 10개일 경우 particle1~10이 한번 이동하면 1 세대(generation)이 지났다고 표현

▪particle의 수와 generation을 설정하여 함수의(ML algorithm일 수도있음) 결과값이 가장 좋을때 hyperparameter가 몇인지 알 수 있음