입자군 최적화

입자 군 최적화 (PSO)는 군 지능의 일종이며 해석 방법으로 조합 최적화 문제에 사용됩니다.
입자의 속도와 위치라는 두 가지 정보의 업데이트를 반복하여 탐색을 진행하는 흐름이됩니다.
아래 그림은 입자 그룹 최적화의 이미지입니다.

알고리즘

입자 그룹 최적화 알고리즘은 다음과 같습니다.

갱신식

다음 업데이트 공식을 사용하여 입자의 속도와 위치를 업데이트하십시오.
간단히 설명하면 속도는 입자가 진화하는 방향을 나타내며 위치는 입자 자체의 매개 변수를 나타냅니다.

실험

실제로 최적화 문제를 해결합시다.
이번에는

x^2 + y^2

최소화 문제를 해결합시다.
따라서 (x, y) = (0,0)이 최적 솔루션입니다.
사용 된 코드는 다음과 같습니다.

# -*- coding: utf-8 -*-
import numpy as np
import random

# 評価関数
def evaluate(particle):
    z = 0
    for i in range(len(particle)):
        z += particle[i] ** 2
    return z

# 位置更新
def update_position(particle, velocity):
    new_particle = particle + velocity
    return new_particle

# 速度更新
def update_velocity(particle, velocity, pbest, gbest, w=0.5, max=0.15):
    new_velocity = np.array([0.0 for i in range(len(particle))])
    #new_velocity = [0.0 for i in range(len(particle))]
    r1 = random.uniform(0, max)
    r2 = random.uniform(0, max)
    for i in range(len(particle)):
        new_velocity[i] = (w * float(velocity[i]) + r1 * (float(pbest[i]) - float(particle[i])) + r2 * (float(gbest[0]) - float(particle[i])))

    return new_velocity

def main():
    N = 100 # 粒子の数
    length = 2  # 次元数
    para_max = 100  #パラメータの最大値
    # 粒子位置の初期化
    ps = [[random.uniform(-para_max, para_max) for j in range(length)] for i in range(N)]
    vs = [[0.0 for j in range(length)] for i in range(N)]
    # パーソナルベスト
    personal_best_position = ps
    # パーソナルベストの評価
    personal_best_scores = [evaluate(p) for p in ps]
    # 評価値が最も小さい粒子のインデックス
    best_particle = np.argmin(personal_best_scores)
    # グローバルベスト
    global_best_position = personal_best_position[best_particle]

    generation = 30 # 最大世代数
    # 世代数分ループ
    for t in range(generation):
        file = open("data/pso/pso" + str(t+1) + ".txt", "w")
        # 粒子数分ループ
        for n in range(N):
            # ファイル書き込み
            file.write(str(ps[n][0]) + " " + str(ps[n][1]) + "\n")
            # 粒子の速度の更新
            vs[n] = update_velocity(ps[n], vs[n], personal_best_position[n], global_best_position)
            # 粒子の位置の更新
            ps[n] = update_position(ps[n], vs[n])

            # 評価値計算をしてパーソナルベストを求める
            score = evaluate(ps[n])
            if score < personal_best_scores[n]:
                personal_best_scores[n] = score
                personal_best_position[n] = ps[n]
        # グローバルベストの更新をする
        best_particle = np.argmin(personal_best_scores)
        global_best_position = personal_best_position[best_particle]
        file.close()

    print(global_best_position)
    print(min(personal_best_scores))

if __name__ == '__main__':
    main()

실험 결과

1,10,20,30 세대의 개체를 색으로 구분하여 그림에 플롯합니다.
세대가 진행됨에 따라 입자가 (0,0)으로 수렴하는 것을 볼 수 있습니다.