유전 알고리즘 기반 경로 계획

1. 유전 알고리즘 기반 경로 계획

1. 주요 요소

• 유전자(Gene) : 각 이동 지점
• 염색체(Chromosome) : 유전자의 집합
• 집단(Population) : 염색체의 집합(이동 경로 후보들의 집합)

2. 적합도 평가

• 각 염색체의 적합도를 평가
  • 예) 장애물 충돌 여부, 경로 조건(비용, 시간 등) 충족 여부 등
• 평가 함수(예)

3. 교배

• 모집단에서 선택된 2개의 염색체의 유전자를 교환

4. 돌연변이(Mutation)

• 염색체의 유전자가 무작위로 변형되는 것
  • 예) 유전자 중 일부를 다른 유전자로 대체, 임의의 두 유전자를 교환

5. 객체 선택 전략

• 순위 선택
  • 룰렛 휠 선택(적합도 점수에 비례)
    • 적합도에 비례하는 만큼의 휠 부분을 해당 개체에 제공
    • 염색체 간 적합도 크기의 차이가 미미할 수 있음
  • 순위 선택(적합도 순서에 비례)
    • 개체의 적합도에 따라 순위를 매긴 다음, 각 개체의 순위를 기반으로 휠의 크기를 계산
• 토너먼트 선택
  • 모집단에서 정해진 수의 개체를 무작위로 선택해서 그룹에 배치
  • 미리 정한 수만큼의 그룹에 대해 수행
  • 각 그룹에서 적합도 점수가 가장 높은 객체를 선택
• 엘리트주의
  • 모집단에서 가장 좋은 개체를 선택
  • 우수한 개체를 유지
  • 룰렛 휠 선택, 순위 선택, 토너먼트 선택 등과 함께 사용 가능

6. 솔루션 공간 인코딩

• 용어
  • 염색체
    • 개별 후보 솔루션
    • 유전자 단위로 구성
    • 각 염색체는 항상 같은 수의 유전자로 구성
  • 유전자 : 단위의 논리적 유형
  • 대립 형질: 해당 단위의 저장된 실제 값
  • 유전자형 : 솔루션의 표현
  • 표현형 : 고유한 솔루션
  • 모집단 : 염색체 모음
• 이진 인코딩
  • 0과1로 유전자를 표현
  • 필요한 작업 메모리 감소
  • 이진 연산의 계산 속도가 빠름

7. 실숫값 인코딩

• 실숫값 인코딩
  • 잠재적 솔루션에 이진 인코딩으로 표현하기 어려운 연속 값이 포함된 경우 사용
• 산술 교차
  • 각 부모를 수식의 변수로 사용하여 계산하여 새로운 자손을 획득
• 경계 돌연변이
  • 실숫값으로 인코딩한 염색체에서 무작위로 선택한 유전자로 하한값 또는 상한값을 임의로 설정
    • 임의로 인덱스를 선택하고 그 값을 최솟값 또는 최댓값으로 설정
• 산술적 돌연변이
  • 실숫값으로 인코딩한 염색체에서 무작위로 선택한 유전자에 작은 수를 더하거나 빼는 방식으로 변경

8. 순서 인코딩

• 순서 인코딩(또는 순열 인코딩)
  • 염색체를 일련의 요소로 표현
  • 일반적으로, 모든 요소가 염색체에 있어야함
  • 적용 예) 라우팅 최적화 문제
    • 총 이동 거리를 최소화하면서, 각 목적지를 한 번 이상 방문하는 경로
• 순서 돌연변이
  • 순서 인코딩한 염색체에서 무작위로 선택한 두 유전자의 위치를 서로 바꿔서 다양성을 도입하는 동시에, 모든 항목이 염색체에 남아 있도록 함

9. 트리 인코딩

• 트리 인코딩
  • 염색체의 요소를 트리로 표현
    • 요소의 계층 구조가 필요할 때 사용
  • 적용 예) 특정 높이와 너비를 가진 화물차에 일정 수의 패키지를 적재하는 문제
    • 빈 공간을 최소화
• 트리 교차
  • 트리 구조에서 단일 지점을 선택한 다음,일부분을 교환하고 부모 개체의 복사본과 결합하여 자손 개체를 생성
  • 역과정으로 두 번째 자손을 생성
• 노드 변경 돌연변이
  • 트리 인코딩한 염색체에서 무작위로 노드를 선택하여 해당 노드를 임의의 유효하나 객체로 변경

10. 초기화

• 염색체의 초기화 집단을 구성
• 파라미터 설정
  • 모집단의 크기
  • 반복 횟수
  • 교차율
  • 돌연변이율 등

11. 염색체 선택

• 일정 기준에 따라 염색체 중 일부를 선택
• 예)
  • 적합성 평가 결과에 따라 일부 비율을 오름차순 또는 내림차순으로 선택
  • 적합성 비례 선택
    • 각 염색체의 적합성에 따라 선택 확률을 부여
  • 토너먼트 선택
    • 집단에서 정해진 개수의 염색체를 무작위로 선택하고, 가장 적합도가 높은 염색체를 선택
  • 엘리트주의 선택
    • 가장 적합성이 높은 염색체를 선택