Particle Swarm Optimization, 입자 군집 최적화

본 포스팅에서는 대표적인 휴리스틱 알고리즘 중 하나인 입자 군집 최적화에 대해 알아보겠습니다.

본 내용은 제가 쓴 책 "파이썬을 활용한 머신러닝 자동화 시스템 구축"에서 발췌했습니다.

 

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) 를 계산합니다. 여기서 각 입자의 위치와 속도는 서로 영향을 끼칩니다.

 

입자 군집 최적화는 아래 그림에 도식화된 바와 같이 초기화, 평가, 속도 계산, 위치 업데이트의 네 단계로 구성되며, 평가 단계에서 종료 조건이 만족하면 알고리즘을 종료합니다.

 

초기화

 

평가 

 

 

속도 계산

위치 업데이트

---

데이터 분석 서비스가 필요한 분은 아래 링크로! 

https://kmong.com/gig/374194 

데이터사이언스 박사의 데이터 분석 서비스 드립니다. | 150000원부터 시작 가능한 총 평점 5점의 I