데이터사이언스/최적화
Particle Swarm Optimization, 입자 군집 최적화
GIL~
2022. 12. 25. 13:07
본 포스팅에서는 대표적인 휴리스틱 알고리즘 중 하나인 입자 군집 최적화에 대해 알아보겠습니다.
본 내용은 제가 쓴 책 "파이썬을 활용한 머신러닝 자동화 시스템 구축"에서 발췌했습니다.
https://wikibook.co.kr/automl/
개요
입자 군집 최적화(particle swarm optimization; PSO)는 아래 그림과 같이 새가 무리를 이뤄 나는 것처럼 여러 개의 해가 동시에 최적해를 찾아가는 휴리스틱 해법입니다.
위 그림에서 k 는 이터레이션을 나타내며, 작은 원과 큰 원은 각각 입자와 군집을 나타냅니다. 즉, 여러 개의 입자가 하나의 군집을 이뤄 실행 가능 공간을 탐색합니다.
매 이터레이션마다 각 입자의 위치와 속도가 정의되는데, 입자의 위치는 해를 나타내며 속도는 다음 이터레이션에서 입자의 위치를 계산하는 데 사용합니다. 즉, k 번째 이터레이션에서 ii=1, 2, ⋯, n 번째 입자의 위치와 속도를 각각 xi(k) 와 vi(k) 라 하면, xi(k) 는 i 번째 입자가 현재 탐색하는 해를 나타내며 vi(k+1) 은 i 번째 입자가 다음에 탐색할 해인 xi(k+1) 를 계산합니다. 여기서 각 입자의 위치와 속도는 서로 영향을 끼칩니다.
입자 군집 최적화는 아래 그림에 도식화된 바와 같이 초기화, 평가, 속도 계산, 위치 업데이트의 네 단계로 구성되며, 평가 단계에서 종료 조건이 만족하면 알고리즘을 종료합니다.
초기화
평가
속도 계산
위치 업데이트
데이터 분석 서비스가 필요한 분은 아래 링크로!