TSP 문제의 해결

  • 등록일 / 수정일
  • 페이지 / 형식
  • 자료평가
  • 구매가격
  • 2013.03.29 / 2019.12.24
  • 16페이지 / fileicon hwp (아래아한글2002)
  • 평가한 분이 없습니다. (구매금액의 3%지급)
  • 1,700원
다운로드장바구니
Naver Naver로그인 Kakao Kakao로그인
최대 20페이지까지 미리보기 서비스를 제공합니다.
자료평가하면 구매금액의 3%지급!
이전큰이미지 다음큰이미지
목차
Ⅰ. 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
자료평가
    아직 평가한 내용이 없습니다.
회원 추천자료
  • [인터넷 중독] 인터넷중독의 문제점 및 해결방안
  • 방법 및 심층심리검사를 통한 상담 Psyberweb- 운영자 : 하버드의대 정신과 김주한 교수 - 인터넷중독증(webaholism)관련 정보제공- 인터넷 중독 자가진단 기준(1995, 뉴욕 정신과 전문의 Ivan K. Goldberg가 고안) 및 체크 리스트 제공 인터넷중독 온라인센터 http://psyber119.com/main.htm - 운영자 : 고려대 심리학과 권정혜 교수 푸르미 클리닉- 한국청소년문화연구소 운영 - 자가 진단법 및 상담사례 제공http://news.empas.com/show.tsp/20020927n04461/?s=888&e=1066

  • [교육] 정치교육과 선거
  • http://news.empas.com/print.tsp/20020225n005716. 참교육학부모회 자유게시판 http://www.hakbumo.or.kr/7. 전교조 열린마당 http://eduhope.net/8. 세이클럽 http://www.sayclub.com/9. 경남일보 http://www.gnnews.co.kr/print/printview.php?findex=1724110. 코리아교육신문 http://www.koreaedu.co.kr/주요뉴스/hn747.htm9. 제주도 선거관리위원회 http://www.jejuelection.go.kr/poster.htm10. 오마이뉴스 - 윤근혁 기자 검색 http://www.ohmynews.com/ ∴ 참고 인터넷 사이트에서 필요한 내용은 참고자료로 수록하였다.

  • [인적자원관리] 중앙정부의 개방형직위제도
  • 문제점과 개선방향 구분쟁점사항개선방향선발 전 관리수직적 직무분석동태적 직무분석 도입임용범위직무분석결과에 따른 직위의 재설정과 범위의 결정, 직종의 재분류보수수당대우 현실화민간과의 경쟁력 확보선발임용관리임용형태용어사상의 문제형태별 명확한 개념정의구분상의 문제직종 재분류, 고용구조 변화전문성 강조의 문제전문직위, 일반관리직위, 기업가형직위, 정치적 관리직위, 통합적 직위임용방식중앙 집권적

  • [대중문화론]주부인터넷 채팅중독을 통해본 아줌마의 모습
  • tsp/20030403n01138/?s=338&e=515http://news.empas.com/show.tsp/20030129n05072/?s=218&e=396http://news.empas.com/show.tsp/20030129n05105/?s=0&e=178http://news.empas.com/show.tsp/20000510n00293/?s=2023&e=2201http://news.empas.com/show.tsp/20030601n02076/?s=17&e=195네이버 뉴스-http://news.naver.com/newsread.php?oldid=2001121000000029055&s=13&e=253http://news.naver.com/newsread.php?oldid=200306010000461739012&s=0&e=250http://news.naver.com/newsread.php?oldid=2002102400000048015&s=1610&e=1856http://news.naver.com/newsread.php?oldid=2001040400000011054&s=248,914&e=361,1026http://ne

  • [황사문제] 황사에 대한 현재의 해결노력 현황과 문제와 개선방안
  • 문제를 해결하기 위해서는 적어도 2010년까지 지속적인 고도경제성장이 필수적이다. 중국 국가발전계획위원회 사회발전연구소 양의용(楊宜勇) 연구원은 취업문제를 해결하기 위해서는 매년 연 평균 9~10%의 고도경제성장이 필요하다고 분석했다. 이처럼 인구압력은 중국정부를 고속성장으로 내몰고 고도성장 정책은 ꡐ선오염(파괴), 후개선ꡑ노선으로 귀결되어 사막 화 등 각종 환경문제를 야기하는 구조적인 요인으로 작용하고 있는 것이다. 2) 계획

사업자등록번호 220-06-55095 대표.신현웅 주소.서울시 서초구 방배로10길 18, 402호 대표전화.02-539-9392
개인정보책임자.박정아 통신판매업신고번호 제2017-서울서초-1806호 이메일 help@reportshop.co.kr
copyright (c) 2003 reoprtshop. steel All reserved.