7.126 입자 군집 최적화(PSO)

1. 기본 원리

입자 군집 최적화(Particle Swarm Optimization, PSO)는 케네디(Kennedy)와 에버하트(Eberhart)가 1995년에 제안한 모집단 기반 메타휴리스틱 최적화 방법이다. 새 떼나 물고기 떼의 집단 행동에서 착안하여, 다수의 입자(particle)가 탐색 공간을 이동하면서 개인적 경험과 집단적 정보를 공유하여 최적점을 탐색한다.

2. 알고리즘

$N$ 개의 입자로 구성된 군집에서, 각 입자 $i$ 는 위치 $\mathbf{x}_i \in \mathbb{R}^n$ 과 속도 $\mathbf{v}_i \in \mathbb{R}^n$ 을 갖는다.

초기화: 위치와 속도를 탐색 공간 내에서 무작위로 초기화한다.

갱신 규칙:

$\mathbf{v}_i^{k+1} = w\mathbf{v}_i^k + c_1 r_1 (\mathbf{p}_i - \mathbf{x}_i^k) + c_2 r_2 (\mathbf{g} - \mathbf{x}_i^k)$

$\mathbf{x}_i^{k+1} = \mathbf{x}_i^k + \mathbf{v}_i^{k+1}$

여기서:

$w$ 는 관성 가중치(inertia weight)
$c_1$ 은 인지 계수(cognitive coefficient, 개인 학습률)
$c_2$ 는 사회 계수(social coefficient, 집단 학습률)
$r_1, r_2 \sim U(0, 1)$ 은 독립 균일 난수
$\mathbf{p}_i$ 는 입자 $i$ 의 개인 최적 위치(personal best)
$\mathbf{g}$ 는 전체 군집의 전역 최적 위치(global best)

3. 매개변수의 역할

관성 가중치 $w$ : 이전 속도의 관성을 제어한다. $w$ 가 크면 탐색(exploration)이 강화되고, $w$ 가 작으면 수렴(exploitation)이 촉진된다. 통상 $w = 0.7 \sim 0.9$ 이 사용되며, 반복에 따라 점진적으로 감소시키는 스케줄이 효과적이다.

$w_k = w_{\max} - (w_{\max} - w_{\min})\frac{k}{k_{\max}}$

인지 계수 $c_1$ 과 사회 계수 $c_2$ : $c_1$ 이 크면 개인 경험에 의한 탐색이 강화되고, $c_2$ 가 크면 집단 정보에 의한 수렴이 가속된다. 통상 $c_1 = c_2 = 2.0$ 이 표준이며, $c_1 + c_2 \leq 4$ 의 조건이 안정성을 위해 권장된다.

4. 위상 구조

전역 최적 $\mathbf{g}$ 의 정의는 군집의 통신 위상(topology)에 의존한다.

전역 위상(gbest): 모든 입자가 전체 군집의 최적 위치를 공유한다. 수렴이 빠르지만 조기 수렴(premature convergence)의 위험이 있다.

국소 위상(lbest): 각 입자가 인접한 소수의 입자와만 정보를 공유한다. 수렴이 느리지만 다양성이 유지되어 전역 탐색에 유리하다.

링 위상: 각 입자가 좌우 이웃과만 통신하는 1차원 링 구조이다.

5. 수렴 분석

PSO의 수렴 거동은 속도 갱신 방정식의 동역학으로 분석된다. 난수를 기대값으로 대체한 결정론적 근사에서, 각 차원의 동역학은 다음의 2차 차분 방정식으로 기술된다.

$x_{k+1} = (1 + w - \phi)x_k - wx_{k-1} + \phi p$

여기서 $\phi = c_1 r_1 + c_2 r_2$ 의 기대값이다. 이 시스템이 안정(수렴)하기 위한 조건은 다음과 같다.

$0 < \phi < 2(1 + w), \quad \lvert w \rvert < 1$

이 조건 밖에서는 입자가 발산하여 탐색 공간 밖으로 이탈한다.

6. 변형과 개선

구속 인자(Constriction Factor): 클레르크(Clerc)와 케네디(Kennedy)가 제안한 구속 인자 $\chi$ 를 적용하여 안정적 수렴을 보장한다.

$\mathbf{v}_i^{k+1} = \chi[\mathbf{v}_i^k + c_1 r_1(\mathbf{p}_i - \mathbf{x}_i^k) + c_2 r_2(\mathbf{g} - \mathbf{x}_i^k)]$

$\chi = \frac{2}{\lvert 2 - \phi - \sqrt{\phi^2 - 4\phi} \rvert}, \quad \phi = c_1 + c_2 > 4$

속도 제한: $\lVert \mathbf{v}_i \rVert \leq v_{\max}$ 로 속도를 제한하여 탐색의 발산을 방지한다.

7. 장점과 한계

장점: 구현이 단순하고, 도함수가 불필요하며, 병렬 처리에 자연스럽게 적합하다. 매개변수 튜닝이 상대적으로 직관적이다.

한계: 고차원 문제에서 효율이 저하되며, 수렴률에 대한 이론적 보장이 약하다. 제약 처리가 직접적이지 않아 벌점법이나 수리 기법과의 결합이 필요하다.

8. 로봇 공학에서의 응용

로봇 경로 계획: 경유점의 위치를 입자의 위치로 표현하고, 경로 길이와 장애물 근접도의 가중 합을 최소화하는 PSO 기반 경로 계획이 연구되어 있다.

PID 이득 튜닝: 로봇 관절 PID 제어기의 이득 매개변수 $(K_p, K_i, K_d)$ 를 PSO로 최적화한다. 폐루프 성능 지표(정착 시간, 오버슈트 등)를 목적 함수로 설정한다.

다중 로봇 과업 할당: 다수의 로봇에 과업을 배분하는 조합 최적화 문제에 이산 PSO가 적용된다.

9. 참고 문헌

Kennedy, J., & Eberhart, R. (1995). “Particle Swarm Optimization.” Proceedings of the IEEE International Conference on Neural Networks, 4, 1942–1948.
Clerc, M., & Kennedy, J. (2002). “The Particle Swarm — Explosion, Stability, and Convergence in a Multidimensional Complex Space.” IEEE Transactions on Evolutionary Computation, 6(1), 58–73.
Shi, Y., & Eberhart, R. (1998). “A Modified Particle Swarm Optimizer.” Proceedings of the IEEE International Conference on Evolutionary Computation, 69–73.
Poli, R., Kennedy, J., & Blackwell, T. (2007). “Particle Swarm Optimization: An Overview.” Swarm Intelligence, 1(1), 33–57.

version: 1.0