[스케줄링] GA를 이용한 TSP해법
- 최초 등록일
- 2002.11.11
- 최종 저작일
- 2002.11
- 24페이지/ MS 파워포인트
- 가격 1,000원
소개글
20~30분 이상 분량의 발표 자료입니다.
목차
1. TSP정의
2. 코드화 및 교차의 평가규범
3. 1점 교차
4. 치사유전자 제어를 중시한 TSP의 코드화 및 교차 – 순서표현. 부분사상교체
5. 서브투어 교환교차에 기반 한 TSP의 해법
6. 맺는 말
본문내용
1. TSP의 정의
TSP (Traveling Salesman Problem)란
- 도시 사이의 순회비용이 평면상의
유클리드 거리에 의해서 부여되는
‘순회방문 판매원 문제’이다.
- Distance의 종류
가. Chebyshef Distance
나. Rectilinear Distance
다. Euclidean Distance
도시이름 : 유전자
경로표현 : 초기지점으로 삼은 도시에서
순회하는 순서대로 도시이름을 열거한
문자열을 염색체로 표현하는 것을
코드화
1. 코드화의 평가규범
가. 완비성(completeness) - 문제 공간상에서
해의 후보는 모두 염색체로 표현 가능 할 것
나. 건전성(soundness) - GA공간상의 염색체는
모두 문제공간에서 해의 후보에 대응 될 수
있을 것
다. 비 중복성(nonredundancy) - 염색체와 해의
후보는 1 대 1로 대응될 수 있을 것
참고 자료
없음