입자 군집 최적화란?
입자 군집 최적화는 개체 입자의 집합이 한 영역 전체를 스텝별로 이동하는 모집단 기반 알고리즘입니다. 입자라고 부르는 개체들의 집합이 한 영역 전체를 스텝별로 이동합니다. 알고리즘은 매 스텝마다 각 입자에서의 목적 함수를 평가합니다. 이 평가 후에 알고리즘은 각 입자의 새로운 속도를 결정합니다. 입자들이 이동하면 알고리즘은 입자의 목적 함수를 다시 평가합니다.
이 알고리즘은 떼 지어 다니는 새나 곤충으로부터 영감을 얻은 것입니다. 각 입자는 자신이 현재까지 찾은 최적의 위치로 향해 가고 동시에 군집의 다른 구성원이 찾은 최적의 위치로도 향하게 됩니다. 몇 번의 스텝을 거치면 모집단은 어느 한 위치를 중심으로 합쳐지거나 몇몇의 위치를 중심으로 합쳐지거나 계속해서 이동합니다.
알고리즘은 단일 현재 점이 아닌 모집단을 기반으로 합니다. 이런 점에서 particleswarm
은 유전 알고리즘과 유사합니다(유전 알고리즘이란? 참조).
알고리즘의 반복 n에서 입자는 다음 값에 따라 달라지는 속도 v(n)을 갖습니다.
발견된 최적의 목적 함수 값의 위치, s(n).
이웃 중 최적의 목적 함수 값의 위치, g(n).
이전 속도 v(n – 1).
입자의 위치 x(n)은 속도에 따라 업데이트되며,
범위 내에 유지되도록 조정됩니다.
입자의 속도는 대략 다음 수식에 따라 업데이트됩니다.
여기서 r(1)과 r(2)는 0과 1 사이의 난수 스칼라 값이고, W(n)은 반복 중에 조정되는 관성 인자입니다. 전체 알고리즘은 임의로 변화하는 이웃을 사용하고 개선된 점을 발견하면 그 상황에 맞춰 수정합니다. Particle Swarm Optimization Algorithm 항목을 참조하십시오.
다음 그림에서 보듯이, 입자의 초기 속도는 무작위처럼 보이지만 몇 번의 반복을 거치면 군집이 국소해, 심지어는 전역해로 수렴할 수 있습니다.