• 생물학적 진화 원리에 기반한 Directed Search Algorithm
• NP-Hard Problem 해결 능력 좋음

구조

• 유전 진화의 원리
  • 교차 → 돌연변이 → 자연선택
• 용어 및 특징
  • 염색체
    • chromosome
    • 생명은 염색체를 통해 유전 됨
    • 유전자를 포함
  • 해집단
    • population
    • 염색체를 갖고 있는 개체들의 집단
  • 유전자
    • gene
    • 염색체의 인자
    • 문제를 푸는 요소가 됨

전형적인 구조

• N개의 임의의 해를 해집단으로 생성
  • 문제 풀이가 이루어짐
    • 성능이 좋아지도록 유전 진화를 시킴
• 해집단으로부터 선택, 교차, 변이의 단계를 거쳐 k개의 새로운 해를 생성
• K개의 해를 해집단 내의 k의 해와 대치
  • 탈락의 rule을 설정
• 임의의 정지 조건이 만족될 때까지 수행한 후 해집단에 남은 해 중 가장 좋은 해를 반환
• 해집단이 진화하기 위한 연산
  • 선택
    • 부모를 선택하는 operation & 자연 선택
  • 교차
    • 자식들을 낳기 위해 부모의 염색체를 유전 시킴
  • 변이
    • 일정 시간이 지나며 조금씩 변화 함
      • 다양성 커짐
• 일정 시간 후 population에 있는 개체들의 해가 문제를 푸는데 점점 효율 + 정확성 좋아짐

Components of a GA

• Encoding technique
  • 유전자를 어떻게 표현
• Initialization procedure
  • 초기화 문제
• Evaluation function
  • 자연 선택 등의 문제
• Selection of parents
  • 어떤 염색체 교차
• Genetic operators
  • 교차와 돌연변이
• Parameter settings
  • 파라미터 설정

Simple Genetic Algorithm