입자 군집 최적화

입자 군집 최적화(Particle swarm optimization, PSO)는 계산과학에서 주어진 품질 측정과 관련하여 후보 솔루션을 개선하기 위해 반복적으로 노력하여 문제를 최적화하는 계산 방법이다. 여기서는 입자라고 불리는 후보 솔루션 집단을 갖고 입자의 위치와 속도에 대한 간단한 수학 공식에 따라 검색 공간에서 이러한 입자를 이동시켜 문제를 해결한다. 각 입자의 움직임은 로컬에서 가장 잘 알려진 위치의 영향을 받지만 검색 공간에서 가장 잘 알려진 위치로 안내되며 다른 입자가 더 나은 위치를 발견하면 업데이트된다. 이는 군집이 최상의 솔루션을 향해 나아갈 것으로 예상된다.

PSO는 처음에는 새 떼나 물고기 떼에서 유기체의 움직임을 양식화하여 표현함으로써 사회행동을 시뮬레이션하기 위해 고안되었다. 이 알고리즘은 단순화되었으며 최적화를 수행하는 것으로 관찰되었다. 케네디와 에버하트의 책은 PSO와 떼 지능의 많은 철학적 측면을 설명한다. PSO 애플리케이션에 대한 광범위한 조사가 폴리(Poli)에 의해 이루어졌다. 2017년에는 보냐디(Bonyadi)와 미할레비츠(Michalewicz)가 PSO에 대한 이론 및 실험 작업에 대한 종합적인 검토를 발표했다.

PSO는 최적화되는 문제에 대해 거의 또는 전혀 가정하지 않고 매우 넓은 공간의 후보 솔루션을 검색할 수 있다는 점에서 메타휴리스틱이다. 또한 PSO는 최적화되는 문제의 기울기 (벡터)를 사용하지 않는다. 즉, PSO에서는 경사 하강법 및 준뉴턴 방법과 같은 기존 최적화 방법에서 요구하는 것처럼 최적화 문제를 미분할 수 있도록 요구하지 않는다. 그러나 PSO와 같은 메타휴리스틱은 최적의 솔루션이 발견된다는 것을 보장하지 않는다.

같이 보기

• 파티클 필터
• 떼 지능

외부 링크

• Particle Swarm Central is a repository for information on PSO. Several source codes are freely available.
• A brief video of particle swarms optimizing three benchmark functions.
• Simulation of PSO convergence in a two-dimensional space (Matlab).
• Applications of PSO.
• Liu, Yang (2009). “Automatic calibration of a rainfall–runoff model using a fast and elitist multi-objective particle swarm algorithm”. 《Expert Systems with Applications》 36 (5): 9533–9538. doi:10.1016/j.eswa.2008.10.086. 
• Links to PSO source code