유전 알고리즘

1. 생물학적 모방

1. Bio-inspiration

• 자연에서 발견한 또는 생물학적 진화 등에서 영감을 받은 재료, 장치, 구조 등을 공학, 과학 등에 적용하는 것
• 로봇
  • 4족 보행 수송 로봇(견마 로봇 등)
  • 곤충 정찰 로봇(잠자리 드론 등)
• 재료
  • 홍합의 접착 물질을 이용한 의료용 접착제
  • 상어 비늘의 형태를 이용한 수영복

2. 생물학적 모방 기반 경로 계획

1. 대표적인 알고리즘

• 유전 알고리즘
• 개미 군집 알고리즘(Ant Colony Optimizaion)
• 파티클 스웜 최적화(Particle Swarm Optimization) 등

3. 유전 알고리즘

1. 진화론

• 유기체 : 수백만 년 동안의 변화를 통해 각 세대가 환경에 적응하면서 진화해온 결과
• 번식을 통해 부모 세대로부터 혼합 유전자를 가진 자식을 생산

2. 유전 알고리즘(Genetic algorithm)

유전 알고리즘은 기본적으로 여러 개의 해로 구성된 해 집단을 만들고 평가한 뒤. 좋은 해를 선별해서 새로운 해 집단을 만드는 메타휴리스틱 알고리즘이다.
유전 알고리즘의 구성 등을 살펴보기 전에 작동 과정에 대해 개략적으로 이해하고 시작하자.
아래와 같이 함수 $f(x)$가 있고, x에 따른 $f(x)$의 최소값을 찾는 문제가 있다고 하자.
설명을 위해, 이 함수를 산이라고 하고, 해를 토끼, 그리고 산의 낮은 곳일수록 더 좋은 곳이라고 하자.
유전 알고리즘은 여러 토끼를 만들고, 좋은 환경에 우연히 있던 토끼들만 살아남아서 비슷한 위치에 자식을 만드는 과정을 통해, 가장 낮은 곳, 즉 최적을 찾게 된다.

육안으로 어느 x가 가장 좋은지 알 수 있지만, 실제 문제에서는 저 그래프를 그리는 것 자체가 불가능한 경우가 대부분이다.
아래와 같이 5마리의 토끼를 만들어 임의로 배치한다. 우연히 4번과 5번에 있던 토끼는 좋은 환경에 있고, 1,2,3번은 그렇지 못하다. 즉, 4번과 5번이 적자이고, 나머지는 적자가 아니다.

이제 적자라서 살아남은 4번과 5번이 자식 a,b,c를 만든다.

이제 다시 살펴보니, 부모보다 좋은 위치에 있는 자식 b와 c도 있고, 부모랑 비슷하거나 더 나쁜위치에 있는 a도 생겼다. 그럼 이제 가장 적합한 b와 c가 살아남아 또 대를 이어 나갈 것이다.
그러다 보면 언젠가는 최저점에 있는 토끼를 만나게 될테고, 다시말해 최적해를 구할 것이다.
즉,
(1) 해를 많이 만들면, 더 좋은 해를 찾을 가능성이 높다. 물론 시간은 더 소요된다.
(2) 너무 잘난 해라면, 세대가 지나도 게속 세대를 구성하는 일원으로 남아있다.
(3) 다음 세대에서 자식을 만드는 부모의 수가 많을수록, 더 많은 해를 탐색할 수는 없다. 그렇지만 더 안정적일 것이다.
(4) 처음에 해들이 한 곳에 몰려있다면 세대를 거듭해도 좋은 해를 못 찾을 수 있다.

• 유전자로 표현된 유전체의 공간을 탐색
• 최적 솔루션을 보장하지는 않음
• 전역 최고(global best) : 탐색 가능한 최적 솔루션
• 지역 최고(local best) : 덜 최적화된 솔루션

3. 수명 주기

• 모집단 생성
  • 무작위로 잠재적 솔루션의 모집단을 생성
• 모집단 내 개체의 적합도 측정
  • 특정 솔루션의 성능 판단, 적합도 함수를 이용하여 점수를 계산하여 수행.
• 적합도에 따른 부모 선택
  • 자손을 낳을 부모 쌍을 턴색
• 부모로부터 개체 재생산
  • 유전 정보를 혼합하고 자손에 약간의 돌연변이를 적용하여 부모로부터 자손을 생산
• 다음 세대 채우기
  • 모집단에서 다음 세대까지 생존할 개체와 자손을 선택
    

3.1 초기 모집단 생성

• 무작위로 염색체를 생성 : 문제의 제약 조건을 통해 잠재적 솔루션이 유효하도록 설정
  
• 솔루션 모집단 예 : 배낭 문제
  • 솔루션 상태를 표현하는 방법이 주어지면, 각 항목이 배낭에 포함할지 여부를 무작위로 결정해서 구현
    • 단 무게 제한 제약을 충족하는 솔루션만 고려

3.2 개체 적합도 측정

• 모집단 내 각 개체의 적합도(fintness)를 측정
  • 적합도 : 솔루션의 성능을 정의
• 개체 적합도 측정 예
  • 각 개체에 대해서 배낭에 있는 항목의 총 가치를 측정
  • 유효하지 않은 개체의 적합도 점수는 0으로 처리

3.3 부모 선택

• 각 개체의 적합도를 계산해서, 새로운 부모가 될 확률을 결정
• 적합도에 따른 부모 선택
  • 모집단 모델
    • 모집단의 다양성을 통제하는 방법
    • 정상 상태 모델
      • 모집단의 대다수 개체를 유지하면서, 소수의 약한 개체는 제거하고 이를 새로운 자손으로 대체
      • 예) 모집단에 100개의 개체가 있는 경우, 현재 세대에서 온 80개체와 새로운 20개체
    • 세대 기반 모델
      • 모집단과 동일한 수의 자손 개체를 생성하고, 전체 모집단을 새로운 자손으로 대체
      • 예) 모집단에 100개의 개체가 있다면, 각 세대는 100개의 새로운 개체로 채움
  • 룰렛 휠 선택
    • 적합도에 비례하는 만큼의 휠 부분을 해당 개체에 제공
    • 휠을 회전시키고, 개체를 선택
    • 원하는 부모 수에 도달할때까지 반복

3.4 자손 번식

• 부모로부터 새로운 자손을 낳기 위해 번식
• 교차
  • 부모 중 부/모 및 모/부의 염색체 일부를 섞는 것
  • 부모 염색체의 반전된 혼합을 포함하는 두 개의 자손이 생성
• 부모로부터 개체 복제
  • 단일 점 교차
    • 염색체 구조의 한 지점을 선택하여 유전의 대상이 되는 부모를 참조하여, 부모 중 부의 첫 번째 부분과 모의 두번째 부분을 사용
    • 두 번째 자손을 부의 두번재 부분과, 모의 첫번째 부분을 사용하여 생성
  • 양 점 교차
    • 염색체 구조의 두 지점을 선택하여, 부모를 참조하여 하나의 자손 개체를 생성
    • 두 번째 자손은 앞서 선택하지 않은 부분을 선택해서 생성
  • 균일 교차
    • 각 부모의 어떤 유전자를 사용할지 나타내는 마스크를 이용하여 첫 번째 자손을 생성
    • 두 번째 자손은 마스크를 통해 선택하지 않은 유전자를 사용하여 생성
    • 마스크 : 자손을 생성할 때마다 무작위로 생성
• 돌연변이
  • 자손을 무작위로 변경
    • 모집단에 변화를 줌
• 모집단의 다양성을 강화하기 위해, 자손 개체를 일부 변경
• 매개변수
  • 돌연변이 비율
• 알고리즘이 지역 최고 솔루션에 갇히는 것을 방지
• 많은 돌연변이는 많은 다양성을 주지만, 너무 많은 다양성은 오히려 솔루션의 성능을 저하시킬 수 있음
• 돌연변이 생성 방법
  • 이진 인코딩을 위한 비트 문자열 돌연변이
    • 무작위로 선택한 이진 인코딩된 염색체의 유전자를 다른 유효한 값으로 변경
  • 이진 인코딩을 위한 비트 반전 돌연변이
    • 이진 인코딩된 염색체의 모든 유전자를 반대 값으로 반전

3.5 다음 세대 채우기

• 다음 세대를 위한 개체를 선택
• 새로운 개체가 유입된 만큼, 일부 개체를 제거
• 개체 적합도 측정
  • 다음 세대 중, 솔루션의 성능(적합도)측정
• 중지 조건
  • 알고리즘이 끝나는 곳에서 충족하는 조건
  • 중지 시, 그 세대의 모집단 중에 가장 적합한 개체를 최적 솔루션으로 선택

4. 유전 알고리즘 매개변수 설정

• 성능 문제
  • 문제에 대해 좋은 솔루션을 잘 찾는 것
  • 효율적으로 계산하는 것
• 주요 매개변수
  • 염색체 인코딩
    • 염색체의 구조를 정의
      • 이진 인코딩, 실숫값 인코딩 등
  • 모집단 크기
    • 모집단의 크기가 클수록
      • 솔루션의 다양성이 향상
      • 더 많은 계산이 필요
  • 모집단 초기화
    • 솔루션의 유효성은 계산의 최적성 등에 중요
  • 자손의 수
    • 각 세대에서 생성하는 자손 수
    • 자손이 많을수록 다양성이 커지지만, 좋은 솔루션이 제거될 수 있음
  • 부모 선택 방법
    • 룰렛 휠 선택, 순위 기반 선택, 토너먼트 선택, 엘리트주의 선택 등
  • 교차 방법
  • 돌연변이 비율/방법
  • 세대 선택 방법
  • 중지 조건

5. 유전 알고리즘 실습