입자 군집 최적화 알고리즘

알고리즘 개요

particleswarm은 Kennedy 및 Eberhart[1]에 설명된 알고리즘을 기반으로 하며, Mezura-Montes와 Coello Coello[2] 및 Pedersen[3]에 제안된 수정 사항을 반영합니다.

입자 군집 알고리즘은 초기 입자를 만든 후 초기 속도를 할당하는 것으로 시작됩니다.

이 알고리즘은 각 입자 위치에서 목적 함수를 실행하고 최적(최소) 함수 값과 최적 위치를 결정합니다.

또한 현재 속도, 입자의 개별 최적 위치, 이웃의 최적 위치를 기반으로 새 속도를 선택합니다.

그런 다음 입자의 위치(새 위치는 이전 위치에, 입자가 경계 내에 유지되도록 수정된 속도를 더해 결정됨), 속도, 이웃을 반복적으로 업데이트합니다.

알고리즘이 중지 조건에 도달할 때까지 반복이 계속됩니다.

다음은 단계에 대한 세부 정보입니다.

초기화

기본적으로, particleswarm은 경계 내에서 균등하게 임의로 입자를 생성합니다. 비유계 성분이 있는 경우 particleswarm은 –1000과 1000 사이의 범위에서 균등분포로 입자를 임의로 생성합니다. 한쪽 경계만 있는 경우 particleswarm은 해당 경계를 끝점으로 갖고, 너비가 2000인 생성 구간으로 입자 생성을 이동합니다. 입자 i의 위치는 nvars개 요소를 가진 행 벡터 x(i)입니다. InitialSwarmSpan 옵션을 사용하여 초기 군집의 범위를 제어할 수 있습니다.

마찬가지로, particleswarm은 범위 [-r,r] 내에서 균등하게 초기 입자 속도 v를 임의로 생성합니다. 여기서 r은 초기 범위의 벡터입니다. 성분 k의 범위는 min(ub(k) - lb(k),InitialSwarmSpan(k))입니다.

particleswarm은 모든 입자에서 목적 함수를 실행합니다. 또한 각 입자 i의 현재 위치 p(i)를 기록합니다. 후속 반복에서, p(i)는 해당 입자 i가 찾은 최적 목적 함수의 위치입니다. b는 모든 입자에 대한 최적값으로, b = min(fun(p(i)))입니다. d는 b = fun(d)를 충족하는 위치입니다.

particleswarm은 이웃 크기 N을 minNeighborhoodSize = max(2,floor(SwarmSize*MinNeighborsFraction))으로 초기화합니다.

particleswarm은 관성 W = max(InertiaRange)를 초기화하며, InertiaRange가 음수인 경우 W = min(InertiaRange)를 설정합니다.

particleswarm은 정체 카운터를 c = 0으로 초기화합니다.

표기법을 간단히 하기 위해, 변수 y1 = SelfAdjustmentWeight 및 y2 = SocialAdjustmentWeight를 설정합니다. 여기서 SelfAdjustmentWeight 및 SocialAdjustmentWeight는 옵션입니다.

반복 단계

알고리즘은 다음과 같이 군집을 업데이트합니다. 즉, 위치 x(i)에 있는 입자 i에 대해 다음을 수행합니다.

  1. i 이외의 N개 입자에서 임의 서브셋 S를 선택합니다.

  2. 이웃 중 최적 목적 함수 fbest(S)와, 해당 최적 목적 함수를 가진 이웃의 위치 g(S)를 찾습니다.

  3. 길이가 nvars인 균등분포 (0,1)을 따르는 확률 벡터 u1 및 u2에 대해 속도를 업데이트합니다.

    v = W*v + y1*u1.*(p-x) + y2*u2.*(g-x).

    이 업데이트는 다음에 대한 가중합을 사용합니다.

    • 이전 속도 v

    • 현재 위치와 입자가 발견한 최적 위치의 차이 p-x

    • 현재 위치와 현재 이웃에서의 최적 위치의 차이 g-x

  4. 위치를 x = x + v로 업데이트합니다.

  5. 경계를 강제 적용합니다. x의 성분이 경계를 벗어날 경우, 해당 경계와 같도록 설정합니다. 이렇게 경계로 설정된 성분의 경우, 해당 성분의 속도 v가 경계 외부를 가리키면 해당 속도 성분을 0으로 설정합니다.

  6. 목적 함수 f = fun(x)를 실행합니다.

  7. f < fun(p)이면 p = x를 설정합니다. 이 단계를 통해 p는 해당 입자가 찾은 최적 위치를 갖게 됩니다.

  8. 알고리즘의 다음 단계는 전체 군집의 파라미터에 적용되며, 개별 입자에는 적용되지 않습니다. 군집 내의 입자 j 중 최솟값 f = min(f(j))를 고려합니다.

    f < b이면 b = f 및 d = x를 설정합니다. 이 단계를 통해 b는 군집 중 최적 목적 함수를 갖고, d는 최적 위치를 갖게 됩니다.

  9. 이전 단계에서 최적 함수 값이 낮아졌다면 flag = true를 설정합니다. 그렇지 않은 경우 flag = false를 설정합니다. flag의 값은 다음 단계에서 사용됩니다.

  10. 이웃을 업데이트합니다. flag = true인 경우 다음을 수행합니다.

    1. c = max(0,c-1)을 설정합니다.

    2. N을 minNeighborhoodSize로 설정합니다.

    3. c < 2이면 W = 2*W를 설정합니다.

    4. c > 5이면 W = W/2를 설정합니다.

    5. W가 InertiaRange 옵션의 범위 내에 있는지 확인합니다.

    flag = false인 경우 다음을 수행합니다.

    1. c = c+1을 설정합니다.

    2. N = min(N + minNeighborhoodSize,SwarmSize)를 설정합니다.

중지 기준

particleswarm은 중지 조건에 도달할 때까지 반복됩니다.

중지 옵션중지 테스트종료 플래그
MaxStallIterations 및 FunctionTolerance마지막 MaxStallIterations회의 반복에서 최적의 목적 함수 값 g의 상대 변화가 FunctionTolerance보다 작습니다.1
MaxIterations반복 횟수가 MaxIterations에 도달했습니다.0
OutputFcn 또는 PlotFcnOutputFcn 또는 PlotFcn이 반복을 중단할 수 있습니다.-1
ObjectiveLimit최적의 목적 함수 값 g가 ObjectiveLimit보다 작습니다.-3
MaxStallTime최적의 목적 함수 값 g가 마지막 MaxStallTime초 내에 변경되지 않았습니다.-4
MaxTime함수 실행 시간이 MaxTime초를 초과합니다.-5

particleswarm이 종료 플래그 1과 함께 중지된 경우, 종료 후에 선택적으로 하이브리드 함수를 호출합니다.

참고 문헌

[1] Kennedy, J., and R. Eberhart. "Particle Swarm Optimization." Proceedings of the IEEE International Conference on Neural Networks. Perth, Australia, 1995, pp. 1942–1945.

[2] Mezura-Montes, E., and C. A. Coello Coello. "Constraint-handling in nature-inspired numerical optimization: Past, present and future." Swarm and Evolutionary Computation. 2011, pp. 173–194.

[3] Pedersen, M. E. "Good Parameters for Particle Swarm Optimization." Luxembourg: Hvass Laboratories, 2010.

참고 항목

도움말 항목