그룹 유전자 알고리즘의 성능요인 분석
Performance factor Analysis for Group Genetic Algorithm
- 주제(키워드) PDPTW , Group Genetic Algorithm
- 발행기관 아주대학교
- 지도교수 김내헌
- 발행년도 2006
- 학위수여년월 2006. 8
- 학위명 석사
- 학과 및 전공 일반대학원 산업공학과
- 본문언어 한국어
초록/요약
지난 수 십 년간 OR의 모든 분야에 있어 많은 연구가 진행되어 왔으며, 그 연구의 필요는 기업체나 또는 공공기관에 의하여 제기되었다. 그러한 분야 중 하나가 차량 경로 문제이다. 특히 공급사슬(Supply Chain Management)에서 기업간의 정보를 공유하고 협조하며 해결 가능한 일차적인 문제는 물의 흐름이다. 이러한 물류 네트웍 문제에서 중요한 부분을 차지하고 있는 문제가 차량을 이용한 수송과 배송의 문제이다. 다양한 제약 조건을 최대한 고려한 형태의 문제를 PDPTW라고 한다. 이는 일반적인 차량 경로 문제에 시간대 제약과 고객의 특성에 따른 제약까지 포함한 형태의 문제이다. 이러한 문제를 풀기 위해 많은 연구가 진행되어 왔으며 최근의 연구에서는 Group Genetic Algorithm 이라고 불리는 방법을 사용하였다. 일반적으로 유전자 알고리즘의 수행도에 영향을 미치는 요인들에 대한 연구는 많이 진행되어 왔지만, encoding 방법이 전혀 다른 Group Genetic Algorithm에 대해서는 연구가 전혀 이루어지지 않았다. 이에 유전자 알고리즘의 수행도에 영향을 미치는 요인들이 Group Genetic Algorithm에도 같은 영향을 미치는 지 알아보고자 실험하였다.
more목차
제 1장 서론∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙1
제 1절 연구 배경 및 목적∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙1
제 2절 선행 연구∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙3
제 2장 PDPTW∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙8
제1절 PDPTW 특징∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙8
제 2절 PDPTW 수리모형∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙9
제 3장 GGA for solving PDPTW∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙11
제 1절 진화 알고리즘∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙11
제 2절 Grouping Genetic Algorithm∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙13
제 3절 Group 형태의 유전자형 변환∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙15
제 4절 초기해 설정∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙17
제 5절 돌연변이 연산자와 교배 연산자∙∙∙∙∙∙∙∙∙∙∙∙∙∙20
제 6절 Selection Rule 및 개체군 생성 방법∙∙∙∙∙∙22
제 7절 실험 결과∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙22
제 4장 결론∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙31
참고 문헌∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙32
부록∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙36
목차
<표 목차>
[표 1] 시뮬레이터 사양∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙22
[표 2] 실험 군 분류∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙22
[표 3] Nanry와 Barnes 사용 문제에 대한 결과 값∙∙∙∙∙24
[표 4] 초기해 설정 비교 결과 값∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙25
[표 5] 개체군 크기에 대한 비교 값∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙27
[표 6] 개체군 생성 방법에 대한 비교 값∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙28
[표 7] 교배 연산자에 대한 비교 값∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙29
목차
<그림 목차>
[그림 1] Grouping 형태의 유전자형 변환(예) ∙∙∙∙∙∙∙∙∙∙∙16
[그림 2] 초기해 설정 플로우 차트∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙19
[그림 3] Crossover in GGA∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙21
[그림 4] 초기해 설정에 대한 비교 값∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙25
[그림 5] 개체군 크기에 대한 비교-1∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙26
[그림 6] 개체군 크기에 대한 비교-2∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙26
[그림 7] 개체군 생성 방법에 대한 비교-1∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙27
[그림 8] 개체군 생성 방법에 대한 비교-2∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙28
[그림 9] 교배 연산자에 대한 비교-1∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙29
[그림 10] 교배 연산자에 대한 비교-2∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙29
