[스케줄링] GA를 이용한 TSP해법

등록일 2002.11.11 MS 파워포인트 (ppt) | 24페이지 | 가격 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로 대응될 수 있을 것
*원하는 자료를 검색 해 보세요.
  • TSP를 위한 유전자 알고리즘 (A Genetic Algorithm for the Traveling Salesman Problem) 8페이지
    본 연구에서는 N 개의 도시를 방문하는 TSP 문제의 최단 경로를 찾기 위하여 유전자 알고리즘을 적용하였다. 유전자 알고리즘에서는 새로운 경로를 만들어 내기 위하여 교차 연산자, 돌연변이 연산자 및 전위 연산자가 자주 도입된다. 최근 전치(前値) 행렬을 이용한 교차 연..
  • 순수 유전 알고리즘을 이용한 외판원순회문제 (TSP) 실험 6페이지
    Travel Salesman Problem(TSP)은 거리가 주어진 각 도시들에서 그들을 모두 연결하는 가장 짧은 경로를 찾는 문제이며, 계산 시간이 도시수의 지수로 증가하는 전형적인 NP-hard 문제이다. 적당한 시간 내에 근사 최적해(near-optimal sol..
  • TSP 경로탐색을 위한 S-MINE 알고리즘 (S-MINE Algorithm for the TSP) 10페이지
    메타 휴리스틱 알고리즘을 이용해 TSP (Traveling Salesman Problem) 문제를 풀고자 하는 많은 시도가 이루어지고 있다. TSP 문제는 대표적인 NP_Hard 문제로 탐색 알고리즘이나 최적화 알고리즘을 실험하는데 많이 사용되고 있으며, 복잡한 사회의..
  • [프로그램 소스, TSP, 세일즈맨, 주먹구구]TSP - 주먹구구 알고리즘으로 구현 0페이지
    #include #include #include #include using namespace std;#define MAX 999999999 // 4294967294 - 행렬 값들의 합typedef unsi..
  • TSP(Travel sales problem) 판매원 경로문제 0페이지
    휴리스틱을 통해 입력 받은 위치에서 가장 가까운 거리가 가까운 경로를 통해서 전 모든 경로를 순환한다. 하지만 휴리스틱 해법은 유일하지 않고, 얻어진 해가 최적도 아니기 때문에 만족할만한 결과를 얻지 못할 수도 있다. 판매원 구조체를 만들어서 구현 하였다.struct..
  • [프로그램 소스, TSP, 세일즈맨]TSP - 분기한정법 알고리즘 이용하여 구현 0페이지
    #include #include "PriorityQueue.h"#include "time.h"#define MAX 9999 //999999999 // 4294967294 - 행렬 값들의 합UINT nodeCnt;UINT edgeCnt;UINT minLength = M..
  • MS TSP와 G1 TSP 구조 비교 0페이지
    국내 중소기업이 일체형 베젤리스(Bezelless) 터치스크린패널(TSP)를 조만간 양산한다. 최근 TSP 업계가 베젤을 극도로 줄인 내로 베젤 개발에 한창인 가운데 일체형 베젤리스 TSP 양산은 세계 처음이다. 특히 TSP 업계의 가장 큰 숙제인 투명전극필름(ITO)..
더보기
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      최근 본 자료더보기