입자 군집 최적화(PSO)는 인공 지능 및 계산 과학 분야에서 주어진 품질 척도에 대해 후보 해의 집단을 반복적으로 개선하여 문제를 최적화하는 계산 방법입니다. 이는 입자라고 불리는 후보 해 집단 간의 상호 작용을 통해 문제를 해결하며, 각 입자의 위치와 속도를 조정하는 간단한 수학 공식에 따라 탐색 공간 내에서 입자들을 이동시킵니다. 각 입자의 움직임은 자신이 지금까지 발견한 최적 위치와 위상적 이웃 내에서 발견된 최적 위치에 의해 영향을 받으며, 지정된 경우 전체 집단이 포함될 수 있습니다. 더 나은 위치가 발견되면 벡터가 업데이트되며, 이를 통해 군집이 좋은 해로 이동할 것으로 기대됩니다.
PSO는 최적화 대상 문제에 대해 거의 또는 전혀 가정을 하지 않고 매우 넓은 후보 해 공간을 탐색할 수 있기 때문에 메타휴리스틱입니다. 이는 문제의 기울기를 사용하지 않으므로 경사 하강법이나 준뉴턴 방법과 같은 고전적 방법과 달리 최적화 문제가 미분 가능할 필요가 없습니다. 그러나 PSO와 같은 메타휴리스틱은 최적 해가 반드시 발견될 것이라는 보장은 하지 않습니다.
기원 및 발전
PSO는 원래 Kennedy와 Eberhart에 의해 처음 제안되었으며, 그들은 새 떼나 물고기 떼의 유기체 이동 또는 인간 집단의 태도 진화를 양식화된 표현으로 사회적 행동을 시뮬레이션하기 위한 목적으로 도입했습니다. 사회적 행동 원리의 시뮬레이션이 어려운 수학적 문제를 해결할 수 있다는 것이 관찰되었습니다. Kennedy와 Eberhart의 저서는 PSO와 군집 지능의 많은 철학적 측면을 설명합니다. PSO 응용에 대한 광범위한 조사는 Poli에 의해 수행되었으며, 2017년에는 Bonyadi와 Michalewicz가 PSO에 대한 이론적 및 실험적 연구에 대한 포괄적인 검토를 발표했습니다.
알고리즘
기본 변형 PSO 알고리즘은 후보 해(입자라고 함)의 연결된 집단(군집이라고 함)으로 초기화됩니다. 후보 해는 탐색 공간의 한 점의 좌표로 간주할 수 있는 숫자 값의 벡터이며, 반복적으로 이동하는 점으로 개념화할 수 있습니다. 입자는 몇 가지 간단한 공식에 따라 탐색 공간에서 이동합니다. 각 입자는 연결된 이웃을 가지며, 이 이웃은 일부 또는 모든 다른 집단 구성원일 수 있습니다. 입자의 다음 위치는 탐색 공간에서 자신의 지금까지 최적 위치와 입자의 최적 이웃의 지금까지 최적 위치에 의해 확률적으로 결정됩니다. 개선된 위치, 즉 목적 함수에서 더 나은 결과를 생성하는 위치가 발견되면 입자의 지금까지 최적 위치가 업데이트됩니다. 이 과정이 반복되며, 이를 통해 만족스러운 해가 결국 발견될 것으로 기대되지만 보장되지는 않습니다.
공식적으로, \( f: \mathbb{R}^n \to \mathbb{R} \)를 최소화할 비용 함수라고 합시다. 이 함수는 실수 벡터 형태의 후보 해를 인수로 받아 목적 함수 값을 나타내는 실수를 출력합니다. \( f \)의 기울기는 알려져 있지 않습니다. 목표는 탐색 공간의 모든 \( b \)에 대해 \( f(a) \le f(b) \)를 만족하는 해 \( a \)를 찾는 것이며, 이는 \( a \)가 전역 최소값임을 의미합니다.
\( S \)를 군집의 입자 수라고 하고, 각 입자는 위치 \( x_i \in \mathbb{R}^n \)와 속도 \( v_i \in \mathbb{R}^n \)를 가집니다. \( p_i \)를 입자 \( i \)의 지금까지 최적 위치라고 하고, \( g \)를 입자의 이웃에서 지금까지 최적 위치라고 합시다. 비용 함수를 최소화하는 기본 PSO 알고리즘은 다음과 같습니다:
- 각 입자 \( i = 1, \dots, S \)에 대해:
- 입자의 위치를 균일 분포된 무작위 벡터로 초기화합니다: \( x_i \sim U(b_{lo}, b_{up}) \).
- 입자의 지금까지 최적 위치를 초기 위치로 설정합니다: \( p_i \leftarrow x_i \).
- \( f(p_i) < f(g) \)이면 군집의 지금까지 최적 위치를 업데이트합니다: \( g \leftarrow p_i \).
- 입자의 속도를 초기화합니다: \( v_i \sim U(-|b_{up}-b_{lo}|, |b_{up}-b_{lo}|) \).
- 종료 기준이 충족될 때까지:
- 각 입자 \( i = 1, \dots, S \)에 대해:
- 각 차원 \( d = 1, \dots, n \)에 대해:
- 무작위 수 \( r_p, r_g \sim U(0,1) \)를 선택합니다.
- 입자의 속도를 업데이트합니다: \( v_{i,d} \leftarrow w v_{i,d} + \phi_p r_p (p_{i,d} - x_{i,d}) + \phi_g r_g (g_d - x_{i,d}) \).
- 입자의 위치를 업데이트합니다: \( x_i \leftarrow x_i + v_i \).
- \( f(x_i) < f(p_i) \)이면 입자의 지금까지 최적 위치를 업데이트합니다: \( p_i \leftarrow x_i \).
- \( f(p_i) < f(g) \)이면 군집의 지금까지 최적 위치를 업데이트합니다: \( g \leftarrow p_i \).
값 \( b_{lo} \)와 \( b_{up} \)는 탐색 공간의 하한 및 상한 경계를 나타냅니다. 매개변수 \( w \)는 관성 가중치입니다. 매개변수 \( \phi_p \)와 \( \phi_g \)는 종종 인지 계수와 사회 계수라고 불립니다. 종료 기준은 수행된 반복 횟수 또는 적절한 목적 함수 값이 발견된 해일 수 있습니다. 매개변수 \( w \), \( \phi_p \), \( \phi_g \)는 실무자가 선택하며 PSO 방법의 동작과 효율성을 제어합니다.
매개변수 선택
PSO 매개변수의 선택은 최적화 성능에 큰 영향을 미칠 수 있습니다. 좋은 성능을 제공하는 매개변수를 선택하는 것은 많은 연구의 주제였습니다. 발산("폭발")을 방지하려면 관성 가중치가 1보다 작아야 합니다. 다른 두 매개변수는 수축 접근법을 사용하여 유도하거나 자유롭게 선택할 수 있지만, 분석에 따르면 수렴 영역으로 제한해야 합니다. 일반적인 값은 [1, 3] 범위에 있습니다. PSO 매개변수는 메타 최적화라는 개념인 다른 상위 최적화기를 사용하여 조정하거나, 예를 들어 퍼지 논리를 통해 최적화 중에 미세 조정할 수도 있습니다. 매개변수는 다양한 최적화 시나리오에 맞게 조정되었습니다.
이웃 및 토폴로지
군집의 토폴로지는 각 입자가 정보를 교환할 수 있는 입자의 하위 집합을 정의합니다. 기본 버전의 알고리즘은 전역 토폴로지를 군집 통신 구조로 사용합니다. 이 토폴로지는 모든 입자가 다른 모든 입자와 통신할 수 있도록 하므로 전체 군집이 단일 입자의 최적 위치 \( g \)를 공유합니다. 그러나 이 접근법은 군집이 지역 최소값에 갇힐 수 있으므로, 입자 간 정보 흐름을 제어하기 위해 다양한 토폴로지가 사용되었습니다. 예를 들어, 지역 토폴로지에서 입자는 입자의 하위 집합과만 정보를 공유합니다. 이 하위 집합은 기하학적, 예를 들어 "가장 가까운 m개 입자"일 수 있으며, 더 자주는 사회적, 즉 거리에 의존하지 않는 입자 집합일 수 있습니다. 이러한 경우 PSO 변형은 기본 PSO의 전역 최적과 대비하여 지역 최적이라고 합니다. 일반적으로 사용되는 군집 토폴로지는 각 입자가 두 개의 이웃만 가지는 링이지만, 다른 많은 토폴로지가 있습니다. 토폴로지는 반드시 정적일 필요는 없으며 최적화 과정 중에 변경될 수 있습니다.
응용 및 관련 방법
PSO는 공학, 경제학, 기계 학습과 같은 분야의 다양한 최적화 문제에 적용되었습니다. 특히 탐색 공간이 크고 목적 함수가 미분 불가능하거나 잡음이 있는 경우에 유용합니다. PSO는 유전 알고리즘 및 개미 군집 최적화와 같은 다른 집단 기반 메타휴리스틱과 유사점을 공유하지만, 사회적 행동에서 영감을 받은 속도 업데이트 메커니즘으로 구별됩니다. 기계 학습의 맥락에서 PSO는 하이퍼파라미터 튜닝이나 신경망 훈련에 사용될 수 있지만, 종종 경사 기반 방법과 비교됩니다. 확률적 특성과 기울기 요구 사항이 없다는 점은 인공 지능의 더 넓은 분야에서 다재다능한 도구로 만듭니다.