생물학적 모방 기반 경로계획(입자 군집 최적화)

1. 입자 군집 최적화(PSO)

• 입자들의 정보를 조합하여 최적해를 탐색
• 철새는 먼 거리를 여행할 때, 무리를 지어 이동하는 경향이 있음
  • 지도자가 앞장서서 비행하면 나머지 새들은 적은 에너지로 비행 가능
  • 지도자가 지치면, 새로운 지도자가 앞장서서 비행
• 솔루션 공간의 여러 지점에 있는 개체들의 그룹을 포함하여 모두 실제 군집 개념을 사용하여 공간에서 최적 솔루션을 탐색
• 새 무리의 행동을 이해하기 위해 다음과 같은 규칙을 추출
  • 분리 : 개체들이 서로 충돌하여 그룹을 방해하지 않도록 이웃과 밀집하거나 충돌하지 않아야함
  • 정렬 : 그룹이 같은 방향으로 이동할 수 있도록 개체는 이웃하는 개체가 향하는 평균적인 방향으로 조정
  • 응집 : 그룹의 대형을 유지하기 위해, 개체는 이웃의 평균적인 위치로 이동
    

2. 최적화 문제

• 최적화 문제 예제
  
  고추 크기(x)에 따른 고추 맵기의 추세선:
  $f(x) = -(x-4)(x-0.2)(x-2)(x-3)+5$

3. 입자 군집 최적화 적용 문제

• 드론의 부품 중 성분의 비율에 따른 성능의 최적화
  • 알루미늄(x)와 플라스틱(y)의 비율에 따른 적합도 함수
    • x,y에 대한 항력과 흔들림에 따른 성능 함수
      $f(x,y) = (x+2y-7)^2 + (2x+y-5)^2$
      
  • 최적 성능을 위한 재료의 비율을 찾는 방법
    • 가장 적합한 재료 비율을 찾을 때까지 모든 값의 조합을 시도
      • 많은 계산이 필요
    • 입자 군집 최저과
      • 모든 값을 확인하지 않고, 큰 검색 공간을 검색하는 수단을 제공
        

4. 상태 표현

• 입자의 개념
  • 위치 : 모든 차원에서 입자의 위치
  • 최적 위치 : 적합도 함수를 이용해서 찾은 최적의 위치
  • 속도 : 입자가 이동하는 현재 속도

5. 입자 군집 최적화 수명 주기

5.1 알고리즘 수명 주기

• 입자 모집단 초기화
  • 사용할 입자 수 결정 및 검색 공간의 임의의 위치로 초기화
• 입자의 적합도 계산
  • 각 입자의 위치를 고려하여, 해당 위치에서 입자의 적합도를 계산
• 입자의 위치 업데이트
  • 군집 지능의 원칙을 통해 입자의 위치를 반복해서 업데이트
  • 입자는 검색 공간을 탐험한 후 좋은 솔루션으로 수렴
• 중지 기준 결정
  • 알고리즘 종료 시기 결정
    

1. 입자 모집단 초기화

• 입자 초기화의 주요 요소
• 각 입자의 시작 위치
  • 각 입자의 시작 위치는 모든 차원에서 임의 위치여야 함(균일하게 분포)
    • 입자가 특정 공간에 몰려 있으면, 다른 영역에서의 솔루션 탐색이 어려움
  • 각 입자의 시작 속도
    • 초기 속도는 0으로 설정
      

2. 각 입자의 적합도 계산

• 현재 위치에서, 각 입자의 적합도를 계산
• 입자의 적합도는 전체 군집이 위치를 변경할 때마다 계산
  
• 최적화 적용 예제: 드론 시나리오
  • 부품에 따른 항력 및 흔들림 함수 : 적합도 함수로 사용
    $f(x,y) = (x+2y-7)^2 + (2x+y-5)^2$
  • 각 입자에 대한 적합도를 계산
    $f(7,1) = (7+2-7)^2 + (14+1-5)^2 = 104\\$
    $f(-1,9) = (-1+18-7)^2 + (-1+9-5)^2 = 104$
    $f(-10,1) = (-10+2-7)^2 + (-20+1-5)^2 = 801$
    $f(-2,-5) = (-2-10-7)^2 + (-4-5-5)^2 = 557$
    

3. 각 입자의 위치 업데이트

• 입자의 속도와 위치를 업데이트

• 속도 업데이트 구성 요소

  • 관성
    • 입자의 이동 또는 방향 변화에 대한 저항: [0~1]
      • 0에 가까울수록 잠재적으로 많은 반복이 필요
      • 1에 가까울수록 더 적은 반복으로 더 많이 탐험
    • 관성 요소 : 관성 * 현재 속도
  • 인지
    • 입자의 내부인지 능력 : [0,2]
      • 가장 좋은 위치를 알고 그 위치를 통해 움직임에 영향을 미치는 입자의 감각
      • 인지 상수가 클수록 입자에 의한 활용이 더 많이 발생
    • 인지 요소 : 인지 가속 * (입자 최적 위치 - 현재 위치)
      • 인지 가속 = 인지 상수 + 무작위 인지 수
  • 사회적
    • 입자가 군집과 상호 작용하는 능력
    • 입자는 군집 내에서 가장 좋은 위치를 알고 이 정보를 이용하여 군집 이동에 영향
    • 사회적 요소: 사회적 가속 * (군집 최적 위치 - 현재 위치)
      • 사회적 가속 = 사회적 상수 * 무작위 사회적 수
      • 사회적 상수[0,2] : 클수록 더 많이 탐험

  

• 최적화 적용 문제 : 드론 시나리오
  

  • 관성 : 0.2
  • 인지 상수 : 0.35
  • 사회적 상수 : 0.45

  관성 요소 : 관성 * 현재 속도
  관성 요소 : 0.2 * 0 = 0

  인지 요소 : 인지 가속 * (입자 최적 위치 - 현재 위치)
  인지 가속 : 인지 상수 * 무작위 인지 수
  인지 가속 : 0.35 *  0.2 = 0.07
  인지 요소 :  0.07 * ([7,1] - [7,1]) = 0.07 * 0 = 0

  사회적 요소 : 사회적 가속 * (군집 최적 위치 - 현재 위치)
  사회적 가속 : 사회적 상수 * 무작위 사회적 수 
  사회적 가속 : 0.45 * 0.3 = 0.135
  사회적 요소 : 0.135 * ([-10,1] - [7,1]) = 0.135 * sqrt{(-10-7)^2 + (1-1)^2} = 0.135 * 17 = 2.295

  새로 업데이트 한 속도
  관성 요소 + 사회적 요소 + 인지 요소
  = 0 + 0 + 2.295 = 2.295

• 위치 업데이트

  • 업데이트한 속도를 이용하여 각 인자의 현재 위치를 업데이트
  • 새로운 속도로 다음 위치를 결정하고, 업데이트한 속도로 입자의 데이터 속성을 업데이트
  • 새로 구한 위치로 각 인자의 적합도를 다시 계산
  • 다음 위치 : 현재 위치 + 새로 업데이트한 속도
    • 다음 위치 : ([7, 1] + 2.295) = [9.295, 3.295]
      

  관성 요소 : 관성 * 현재 속도
  관성 요소 : 0.2 * 2.295 = 0.59

  인지 요소 : 인지 가속 * (입자 최적 위치 - 현재 위치)
  인지 가속 : 인지 상수 * 무작위 인지 수
  인지 가속 : 0.35 *  0.2 = 0.07
  인지 요소 :  0.07 * ([7,1] - [9.925,3.325]) = 0.07 * sqrt{(7-9.925)^2 + (1-3.325)^2} = 0.07 * 3.736 = 0.266

  사회적 요소 : 사회적 가속 * (군집 최적 위치 - 현재 위치)
  사회적 가속 : 사회적 상수 * 무작위 사회적 수 
  사회적 가속 : 0.45 * 0.3 = 0.135
  사회적 요소 : 0.135 * ([0.626,10] - [9.925,3.325]) = 0.135 * sqrt{(0.625-9.925)^2 + (10-3.325)^2} = 0.135 * 11.447 = 1.545

  새로 업데이트 한 속도
  관성 요소 + 사회적 요소 + 인지 요소
  = 0.59 + 0.266 + 1.545 = 2.401

• 반복을 통해 입자는 다른 위치로 이동
  

4. 중지 기준결정

• 중지 전략
  • 군집에서 최고 솔루션을 검사하고 정체 상태인지 확인
    • 정체 : 좋은 솔루션을 찾았거나, 군집이 지역적으로 최적인 솔루션에 갇혔음을 의미
      

6. 입자 군집 최적화 기반 경로 계획

• 목적 : 로봇 또는 자율주행 차량이 장애물을 피하면서 시작점에서 목표점까지의 최적의 경로를 찾는것
• 방법 : 파티클 스웜 최적화(PSO)는 집단 지성을 기반으로 하는 최적화 알고리즘
• PSO 개념
  • 파티클 : 해결책을 탐색하는 개체, 경로 계획에서는 경로를 나타냄
  • 스웜 : 모든 파티클의 집합
  • 속도 : 파티클의 경로를 변경하는 방향과 크기
• PSO 기반 경로 계획
  • 초기화
    • n개의 파티클을 생성, 각 파티클은 임의의 경로를 가짐
    • 경로는 시작점에서 목표점까지의 Waypoint로 구성됨
    • 각 파티클은 개인 최적과 전역 최적 해를 저장할 공간을 가짐
  • 평가
    • 비용 함수를 정의하여 각 경로의 성능을 평가
    • 경로의 길이, 목표까지 거리, 장애물과의 충돌 위험 등을 고려
  • 개인 및 전역 최적 해 업데이트
    • 각 파티클은 자신의 최고 성능 경로(개인 최적)를 기록
    • 모든 파티클 중 최고의 경로를 전역 최적으로 설정
  • 속도 및 위치 업데이트
    • 속도는 개인 최적 및 전역 최적 해에 대한 정보와 관성을 사용하여 업데이트
    • 속도에 기반하여 각 파티클의 경로 업데이트
    • 위치(경로)가 검색 공간을 벗어나지 않도록 조정
  • 종료 조건
    • 최대 반복 횟수 도달 또는 목표 함수의 개선이 더 이상 없을 때 종료
  • 결과
    • 가장 성능이 좋은 경로(전역 최고)를 결과로 선정
  • 비용 함수
    • 목적 : 파티클의 경로가 얼마나 좋은지 수치적으로 평가
    • 구성 요소
    • 경로의 총 거리
    • 목표 지점까지의 거리
    • 장애물과의 충돌 가능성
  • 충돌 검사
    • 경로상의 각 세그먼트를 장애물과 비교하여 충돌 검사
    • 장애물을 피하는 것은 비용 함수에 의해 크게 패널티를 받음
  • 결과 분석
    • 전역 최적 경로를 그래픽으로 시각화하여 결과 분석
    • 이상적인 경로는 장애물을 피하고, 최소 거리를 유지