TSP 문제의 해결
- 등록일 / 수정일
- 페이지 / 형식
- 자료평가
- 구매가격
- 2013.03.29 / 2019.12.24
- 16페이지 / hwp (아래아한글2002)
- 평가한 분이 없습니다. (구매금액의 3%지급)
- 1,700원
최대 20페이지까지 미리보기 서비스를 제공합니다.
자료평가하면 구매금액의 3%지급!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
추천 연관자료
- 목차
-
Ⅰ. TSP접근-GA
Ⅱ. 설계
Ⅲ. 실험결과
Ⅳ. 결과분석
Ⅴ. 결론
Ⅵ. 참고자료
- 본문내용
-
Ⅰ. 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가지 경로만을 계산하면 최소거리를 찾을 수 있지만 도시의 수가 증가할수록 이동 경로의 경우의 수는 아래 그림에서 보이는 그래프와 같이 기하급수적으로 증가하게 된다.
- 참고문헌
-
1. 논문
* 강래구, “최적의 TSP 해결을 위한 유전자 알고리즘의 새로운 집단 초기화 및 순차변환 기법 제안과 구현”, 조선대학교 박사학위 논문, 2009.8
* 김선희, “유전자 알고리즘 및 유전자-엔트로피 알고리즘을 이용한 TSP 문제 해결에 관한 연구”, 공주대학교 석사학위 논문, 2003.2
2. 관련인터넷조사
* 인터넷 블로그 – http://googleperson.blogspot.com/2012/03/blog-post_15.html
* 인터넷 블로그 - http://blog.paran.com/mudol78/3498379
자료평가
-
아직 평가한 내용이 없습니다.
오늘 본 자료
더보기
최근 판매 자료
- [일반화학실험] [일반화학실험] 탄산염의 분석
- [식음료 관리] 메뉴 코스별 서비스-전채요리 & 수프
- 기계공학실험 - 관수로, 열전달 실험
- 미니멀리즘 건축의 사례 ; 미니멀리즘 건축의 특징과 발전과정 분석
- [화학공학설계] Aspen을 이용하여 바이오디젤로부터 글리세롤 정제 공정 설계
- 미래사회와 정보기술 - 인공지능에 관한 조사
- 일반물리실험 - 길이의 측정 실험 보고서
- 영상제작실무 / 유튜브기획안 (영상제작예산안, 영상구성안, 촬영스케줄표, 유튜브구성)
- 실험보고서 - 산, 염기 적정을 통해 적정곡선을 얻어 해석하는 방법, 이온화 상수 결정
- pH측정 및 아세트산의 이온화상수의 결정
저작권 관련 사항 정보 및 게시물 내용의 진실성에 대하여 레포트샵은 보증하지 아니하며, 해당 정보 및 게시물의 저작권과 기타 법적 책임은 자료 등록자에게 있습니다. 위 정보 및 게시물 내용의 불법적 이용, 무단 전재·배포는 금지됩니다. 저작권침해, 명예훼손 등 분쟁요소 발견시 고객센터에 신고해 주시기 바랍니다.