개요

입자 그룹 최적화 방법 (PSO, Particle Swarm Optimization)은 동물 무리의 행동을 힌트로하는 그룹 지능의 일종입니다.
이 기사에서는 입자 그룹 최적화 방법의 간단한 예를 소개합니다.

포물면 공식

포물면의 공식은 다음과 같은 형태로 주어진다.

\begin{aligned}
z = x^2+y^2
\end{aligned}

당연하지만 최소값은 $ (x, y) = (0, 0) $ 일 때 $ z = 0 $입니다.
이것은 입자 그룹 최적화 방법을 사용하여 결정됩니다.

입자 군 최적화 방법의 해설

아래 기사를 참조하십시오.
입자 그룹 최적화 및 비선형 시스템

이 기사의 § 2를 구현해 보겠습니다.

소스 코드

main.py

# -*- coding: utf-8 -*-

import numpy as np
import random

#評価関数: z = x^2 + y^2
def criterion(x, y):
    z = x * x + y * y
    return z

#粒子の位置の更新を行う関数
def update_position(x, y, vx, vy):
    new_x = x + vx
    new_y = y + vy
    return new_x, new_y

#粒子の速度の更新を行う関数
def update_velocity(x, y, vx, vy, p, g, w=0.5, ro_max=0.14):
    #パラメーターroはランダムに与える
    ro1 = random.uniform(0, ro_max)
    ro2 = random.uniform(0, ro_max)
    #粒子速度の更新を行う
    new_vx = w * vx + ro1 * (p["x"] - x) + ro2 * (g["x"] - x)
    new_vy = w * vy + ro1 * (p["y"] - y) + ro2 * (g["y"] - y)
    return new_vx, new_vy


def main():
    N = 100  #粒子の数
    x_min, x_max = -5, 5
    y_min, y_max = -5, 5
    #粒子位置, 速度, パーソナルベスト, グローバルベストの初期化を行う
    ps = [{"x": random.uniform(x_min, x_max), 
        "y": random.uniform(y_min, y_max)} for i in range(N)]
    vs = [{"x": 0.0, "y": 0.0} for i in range(N)]
    personal_best_positions = list(ps)
    personal_best_scores = [criterion(p["x"], p["y"]) for p in ps]
    best_particle = np.argmin(personal_best_scores)
    global_best_position = personal_best_positions[best_particle]

    T = 30  #制限時間(ループの回数)
    for t in range(T):
        for n in range(N):
            x, y = ps[n]["x"], ps[n]["y"]
            vx, vy = vs[n]["x"], vs[n]["y"]
            p = personal_best_positions[n]
            #粒子の位置の更新を行う
            new_x, new_y = update_position(x, y, vx, vy)
            ps[n] = {"x": new_x, "y": new_y}
            #粒子の速度の更新を行う
            new_vx, new_vy = update_velocity(
                new_x, new_y, vx, vy, p, global_best_position)
            vs[n] = {"x": new_vx, "y": new_vy}
            #評価値を求め, パーソナルベストの更新を行う
            score = criterion(new_x, new_y)
            if score < personal_best_scores[n]:
                personal_best_scores[n] = score
                personal_best_positions[n] = {"x": new_x, "y": new_y}
        #グローバルベストの更新を行う
        best_particle = np.argmin(personal_best_scores)
        global_best_position = personal_best_positions[best_particle]
    #最適解
    print(global_best_position)
    print(min(personal_best_scores))

if __name__ == '__main__':
    main()

결과

결과

{'y': 0.00390598718159734, 'x': -0.0018420875049243782}
1.86500222386e-05

시각화

$ N (= 100) $ 개의 입자가 $ (x, y) = (0, 0) $에 집중되는 모습입니다.

기타

입자 수와 같은 몇 가지 매개 변수는 어떻게 결정합니까? (Trial and Error?)

문헌에 따라 위치 업데이트, 속도 업데이트, 개인 베스트, 글로벌 베스트 순서가 흩어져…
이 기사에서는 위치 업데이트 ⇒ 속도 업데이트 ⇒ 개인 베스트 업데이트 ⇒ 글로벌 베스트 업데이트로 진행됩니다.

편집 내역

(2014/11/18) 소스 코드 수정