주요 콘텐츠

입자 군집 최적화란?

입자 군집 최적화는 개체 입자의 집합이 한 영역 전체를 스텝별로 이동하는 모집단 기반 알고리즘입니다. 입자라고 부르는 개체들의 집합이 한 영역 전체를 스텝별로 이동합니다. 알고리즘은 매 스텝마다 각 입자에서의 목적 함수를 평가합니다. 이 평가 후에 알고리즘은 각 입자의 새로운 속도를 결정합니다. 입자들이 이동하면 알고리즘은 입자의 목적 함수를 다시 평가합니다.

이 알고리즘은 떼 지어 다니는 새나 곤충으로부터 영감을 얻은 것입니다. 각 입자는 자신이 현재까지 찾은 최적의 위치로 향해 가고 동시에 군집의 다른 구성원이 찾은 최적의 위치로도 향하게 됩니다. 몇 번의 스텝을 거치면 모집단은 어느 한 위치를 중심으로 합쳐지거나 몇몇의 위치를 중심으로 합쳐지거나 계속해서 이동합니다.

알고리즘은 단일 현재 점이 아닌 모집단을 기반으로 합니다. 이런 점에서 particleswarm은 유전 알고리즘과 유사합니다(유전 알고리즘이란? 참조).

알고리즘의 반복 n에서 입자는 다음 값에 따라 달라지는 속도 v(n)을 갖습니다.

  • 발견된 최적의 목적 함수 값의 위치, s(n).

  • 이웃 중 최적의 목적 함수 값의 위치, g(n).

  • 이전 속도 v(n – 1).

입자의 위치 x(n)은 속도에 따라 업데이트되며,

x(n+1)=x(n)+v(n),

범위 내에 유지되도록 조정됩니다.

입자의 속도는 대략 다음 수식에 따라 업데이트됩니다.

v(n+1) = W(n)v(n)+r(1)(s(n)x(n))+r(2)(g(n)x(n)).

여기서 r(1)과 r(2)는 0과 1 사이의 난수 스칼라 값이고, W(n)은 반복 중에 조정되는 관성 인자입니다. 전체 알고리즘은 임의로 변화하는 이웃을 사용하고 개선된 점을 발견하면 그 상황에 맞춰 수정합니다. Particle Swarm Optimization Algorithm 항목을 참조하십시오.

다음 그림에서 보듯이, 입자의 초기 속도는 무작위처럼 보이지만 몇 번의 반복을 거치면 군집이 국소해, 심지어는 전역해로 수렴할 수 있습니다.

Six images showing a collection of particles and their velocities converging to a single location with zero velocity.

참고 항목

도움말 항목