유전 알고리즘 genetic algorithm
- 자연에서 생물의 유전 genetics와 진화 evolution의 메카니즘을 공학적으로 모델화 하는것에의해 샐물의 적응 능력을 취급하는것
- 자연 도태의 원리를 기초로한 최적화 방법
- 탐색, 최적화 및 기계학습 도구로 많이 사용됨
유전 알고리즘의 기본 원리
- 부모로 부터 유전자에 의해 생물의 정보 전달이 행해지면 다음 세대에는 우수한, 환경 적응도가 높은 개체의 유전 정보가 우선적으로 전해짐
- 적응도가 낮은 개체는 수명이 짧고, 증식할수 없게 됨. 적응도가 낮은 종족도 자연 도태됨
- 세대를 거듭해 환경에 적응도가 높은 개체가 많아짐
=> 유전과 진화의 기본 원리
유전 알고리즘 genetic algorithm or 진화 알고리즘 evolution algorithm
- 자연 세계의 진화 과정을 컴퓨터 시뮬레이션함으로 복잡한 실제 세계 문제를 해결하고자 하는 계산 모델
유전 알고리즘 수행 방법
- 풀고자 하는 문제에 대한 가능한 해들을 정해진 형태의 자료구조로 표현
- 이들을 점차 변형하여 더 좋은 해들을 생성
-> 풀고자 하는 문제에 대해 가능한 해들을 염색체로 표현한 다음 이들을 점차 변형하여 더 좋은해들을 생성
유전 알고리즘 관련 용어
- 개체 individual, 유기체 organism : 각각 가능한 하나의 해를 유기체나 개체라고 함
- 개체군 population : 이들의 집합
- 유전 연산자 genetic operator : 하나의 개체는 보통 하나나 여러 염색체로 구성되며 염색체를 변형하는 연산자들
유전 연산자의 종류
- 기본적으로 다음 3가지 가 있음
- 선택 selection : 집단 중 적응도 분포에 따라 다음 단계로 교배를 행하는 개체의 생존 분포 결정
- 교배 crossover : 2개의 염색체 사이 유전자를 바꾸어 새 개채 발생
- 돌연변이 mutation : 유전자의 어떤 부분 값을 강제적으로 변화
유전 알고리즘의 모델
- 염색체를 표현하는 방법과 사용되는 유전 연산자 종류, 특성에 따라 여러 모델로 구분
- 진화 전략 evolution strategy : 실수 값을 취하는 유전자들로 구성된 벡터를 염색체로 사용
- 진화 프로그래밍 evolutionary programming, 유전 프로그래밍 genetic programming : 그래프와 트리를 염색체 표현에 사용
유전 알고리즘 응용 예시
- 비결정 난해 NP-hard 군에 속하는 문제들이 대표적임
- 순회 판매원 문제, 작업 공정 스캐줄링, 채널 라우팅, 자동차 스케줄링, 로드 밸런싱 등