분야
hwpⅡ. 설계
Ⅲ. 실험결과
Ⅳ. 결과분석
Ⅴ. 결론
Ⅵ. 참고자료
Ⅰ. TSP접근-GA
1. 왜 유전자 알고리즘을 사용 하는가 ?
1-1. 유전자 알고리즘의 기본 개념 및 용어
자연계에 있는 어떤 생물의 진화과정에 있어서, 어떤 세대(generation)을 형성하는 개체(individual)들의 집합, 즉 개체군(population)중에서 환경에 대한 적합도(fitness)가 높은 개체가 높은 확률로 살아남아 재생할 수 있게 되며, 이때 교배(crossover) 및 돌연변이(mutation)로서 다음 세대의 개체군을 생성한다.
유전자 알고리즘에서 개체의 수를 개체군의 크기(population size)라고 한다. 각각의 개체는 염색체(chromosome)를 가지고 있으며 염색체는 복수개의 유전자(gene)의 집합으로 구성된다. 유전자에 의해 결정되는 개체의 형질을 표현형(phenotype)이라고 하고 이에 대응되는 염색체의 구조를 유전형(genotype)이라 한다. 표현형을 유전형으로 바꾸는 것을 코드화(coding) 그 역을 디코드화(decoding)라고 한다. 유전자 알고리즘은 이와 같이 생물의 진화과정을 인공적으로 모델링 한 알고리즘이다.
1-2. 유전자 알고리즘의 특징
* 병렬적 탐색 방법 - 다른 알고리즘의 직렬적 검색방법으로 한 번에 한 방향으로만 탐색할 수 있는 것과 달리, 유전자 알고리즘은 개체군 안의 여러 개의 개체들이 동시에 탐색공간을 다양한 방향으로 탐색할 수 있다. 즉 작은 크기의 개체군을 가지고 전체 공간을 탐색하며 개체군 안에서 최적의 값을 찾아낸다.
* 적합도가 방대한 문제를 풀기에 적합 – 적합도 지형이 방대한 문제들은 대부분 ‘비선형’적인 특성을 가지고 있다. 한 요소의 변화가 전체 시스템에 미치는 영향은 매우 적은 반면 여러 요소들이 함께 변화할 때 요소들의 조합이 전체 시스템에 주는 영향은 매우 크게 된다. 유전자 알고리즘의 병렬탐색의 특성은 방대한 적합도 지형에서 셀 수 없이 많은 요소들의 조합이 있음에도 작은 부분만을 표본 삼아 짧은 시간 안에 최적 혹은 좋은 결과를 얻을 수 있게 해준다.
* 적응도(적합도함수 값)만을 이용하기 때문에 적합도함수의 성질을 잘 알 수 없는 문제에 대해서도 적용할 수 있다.
* 결정론적인 규칙이 없고 확률적 연산자를 사용하여 수행하기 때문에 Local Minimum에 머무르지 않고 전체 해에 도달할 수 있는 가능성이 높아진다.
1-3. TSP문제에 대한 유전자 알고리즘의 적합성
그림 1. 4개 도시의 순회 경로
* 그림 1은 4개의 도시가 주어졌을 때 구할 수 있는 총 순회경로의 정보이다. (4! = ,…,) 4개의 도시가 주어졌을 때는 총 24가지 경로만을 계산하면 최소거리를 찾을 수 있지만 도시의 수가 증가할수록 이동 경로의 경우의 수는 아래 그림에서 보이는 그래프와 같이 기하급수적으로 증가하게 된다.
* 강래구, “최적의 TSP 해결을 위한 유전자 알고리즘의 새로운 집단 초기화 및 순차변환 기법 제안과 구현”, 조선대학교 박사학위 논문, 2009.8
* 김선희, “유전자 알고리즘 및 유전자-엔트로피 알고리즘을 이용한 TSP 문제 해결에 관한 연구”, 공주대학교 석사학위 논문, 2003.2
2. 관련인터넷조사
* 인터넷 블로그 – http://googleperson.blogspot.com/2012/03/blog-post_15.html
* 인터넷 블로그 - http://blog.paran.com/mudol78/3498379
