The canonical PSO algorithm is a robust stochastic evolutionary computation technique based on the information exchange between the particles. The Potential and Dynamics-based PSO algorithm is inspired by the canonical PSO and it is based on the motion dynamics.
This thesis proposes a novel PSO algorithm, based on the potential field and the motion dynamics model. It is assumed that particles form potential fields and each particle has its own mass. The potential filed and mass are modeled by the particles’ fitness value. By using these fitness based models, the proposed algorithm performs well, in particular, in avoiding the local minima compare to the original PSO.
Although the PDPSO algorithm is designed to have more exploration capability compare to the canonical algorithm. The algorithm shows more exploration power, but the exploitation capability was weakened. To solve the problem, an updated version of PDPSO which have more exploitation capability is proposed while the exploration power is kept in the updated algorithm.
In addition, the relationship between swarm divergence and parameters of PDPSO is discussed.
입자 군집 최적화 알고리즘 (PSO, Particle Swarm Optimization algorithm)은 J. Kennedy와 R. c. Eberhart에 의해 1995년에 제안된 집단 지능(swarm intelligence)에 기반한 최적화 알고리즘이다. 각각의 후보 해(candidate solution)은 탐색 공간(search space)내에서 움직이는 하나의 입자(particle)로 묘사된다. 각각의 입자들은 다른 입자와 서로의 적합도(fitness)와 위치 정보를 주고받으며, 이 정보들을 바탕으로 각 입자의 위치 및 속도를 지속적으로 수정하여 주어진 문제의 최적 해를 찾아내는 알고리즘이다. 본 논문에서는 Kennedy와 Eberhart의 PSO 알고리즘을 Canonical PSO라는 이름으로 참조한다.
Canonical PSO는 국부 최적값으로 수렴하는 경우가 잦다는 널리 알려진 문제가 존재한다. Canonical PSO에서 각 입자의 위치와 속도를 계산함에 있어 하나의 최적 입자만을 참조하기 때문에 발생하는 문제이다. 이 문제를 개선하기 위한 대부분의 연구 주제는 보다 복잡한 참조 모델 - 군집화(clustering) 등 -을 사용하는 방법을 사용한다. 본 논문에서는 보다 확실한 물리적 모델에 기반한 PSO의 개선된 알고리즘을 제안한다.
각각의 입자는 탐색 공간 내에서 고유의 질량을 갖는 것으로 묘사된다. 초기 단계에서 각 입자는 임의의 위치에 정지한 상태로 분포한다. 각각의 입자는 자신의 적합도에 따라 위치에너지 장(potential field)를 생성한다. 하나의 입자는 다른 입자들이 생성한 위치에너지 장에 의해 받는 힘이 결정되고, 이로부터 가속도와 속도, 위치가 결정된다. 힘과 가속도의 관계는 뉴턴의 제 2법칙을 이용하여 계산하고, 가속도와 속도, 위치는 일반적인 동역학 모델을 사용하여 계산한다.
다른 입자들의 위치에너지 장을 이용한 업데이트 방식은 수렴 속도가 떨어진다는 문제점이 존재한다. 따라서 각 입자는 자신이 지금까지 지나왔던 궤적 중 가장 적합도가 높았던 위치를 참조하여 자신의 위치를 결정하도록 제안하는 알고리즘을 개선하였다. 참조 방식은 다른 입자로부터의 참조 방식과 마찬가지로 위치에너지 장을 형성하여 자신의 운동을 결정하게 된다. 여기에 더하여 보다 빠른 연산 시간을 위하여 3계층 구조(3-Tier)를 갖는 시뮬레이터 모델을 제안하였다.
제안한 알고리즘의 효율성을 입증하기 위하여 5개의 시험 함수(benchmark function)을 이용하여 Canonical PSO와 PDPSO알고리즘의 성능을 분석하였다. 비교 결과 기존의 알고리즘에 비하여 PDPSO 알고리즘은 국부 최소값(local minima)을 회피하는 능력이 개선되었음을 확인할 수 있었다. 제안하는 알고리즘이 시험 함수가 간단하거나 저차원의 탐색 공간에서 시험하는 경우에는 약간 낮은 수렴 속도를 보였지만, 복잡한 시험 함수 또는 고차원의 탐색 공간에서는 월등한 탐색 성능을 갖는 것을 확인하였다.