타부리스트가 결합된 유전자 알고리즘을 이용한 트리형 네트워크의 경제적 설계
- Alternative Title
- Economic Design of Tree Network Using Tabu List Coupled Genetic Algorithms
- Abstract
- 본 논문은 컴퓨터 네트워크의 한 유형인 트리형 네트워크의 경제적 설계문제를 다룬다. 이 문제는 신장 트리와 서브트리의 최대 트래픽 용량을 제약조건으로, 설치비용 최소화를 목적함수로 모형화될 수 있다.
이 문제를 해결하기 위해 기존 연구는 휴리스틱 알고리즘이나 시물레이티드 어닐링, 타부 서치, 유전자 알고리즘 등의 메타 휴리스틱 알고리즘을 이용하였다. 이 중 유전자 알고리즘이 가장 널리 사용되고 있다. 그러나 유전자 알고리즘은 지속적인 진화 연산과정 중 개체집단 내에 다수의 동일한 개체를 발생시킬 수 있다. 이는 최적해의 효율적인 탐색을 방해한다.
본 연구는 이러한 유전자 알고리즘의 단점을 해결하기 위해 타부리스트가 결합된 유전자 알고리즘(Tabu List Coupled Genetic Algorithm)을 제안한다. 이 알고리즘은 진화 연산과정 중에 개체집단 내에 동일한 개체 발생을 방지한다. 그리고 본 연구는 제안한 알고리즘을 이용한 트리형 네트워크의 경제적 설계 방법을 제시한다.
실험적 문제들을 가지고 본 연구에서 제시한 설계방법과 유전자 알고리즘을 이용한 설계방법의 성능을 비교 평가함으로써 본 연구에서 제시한 설계방법의 우수성을 입증하였다.
- Issued Date
- 2011
- Awarded Date
- 2011. 2
- Type
- Dissertation
- Publisher
- 부경대학교
- Alternative Author(s)
- Lee, Seong Hwan
- Affiliation
- 부경대학교 경영대학원
- Department
- 경영대학원 경영학과e-비지니스전공
- Advisor
- 염창선
- Table Of Contents
- Ⅰ. 서 론 1
1. 연구의 배경 및 목적 1
2. 연구의 방법 및 구성 4
Ⅱ. 네트워크, 유전자 알고리즘 및 타부서치 5
1. 네트워크 5
가. 네트워크의 종류 5
나. 네트워크의 설계 7
2. 유전자 알고리즘 9
가. 유전자 알고리즘의 개요 9
나. 염색체 12
다. 재생산 16
라. 교배(crossover) 19
마. 돌연변이(mutation) 23
3. 타부서치 25
Ⅲ. 타부리스트가 결합된 유전자 알고리즘을 이용한 트리형
네트워크 설계 26
1. 트리형 네트워크 설계 문제의 기술 26
가. 트리형 네트워크 설계에 대한 가정 및 표기 27
나. 트리형 네트워크 설계 문제 모형 28
2. 트리형 네트워크 설계의 염색체 표현방법 29
3. 트리형 네트워크 설계 31
가. 트리형 네트워크 설계를 위한 주요 절차 31
나. 초기 개체집단 생성 35
다. 교배 및 돌연변이 35
라. 서브트리 탐색 37
마. 타부리스트 39
4. 트리형 네트워크 설계를 위한 알고리즘 40
가. 노드 차수 계산 알고리즘 40
나. 서브트리 탐색 및 트래픽 계산 알고리즘 40
다. 타부리스트 관리 알고리즘 41
Ⅳ. 성능 평가 43
1. 문제 1 : 13개의 노드, 서브트리 트래픽 용량 3 44
2. 문제 2 : 13개의 노드, 서브트리 트래픽 용량 10 48
3. 문제 3 : 17개의 노드, 서브트리 트래픽 용량 5 51
4. 문제 4 : 17개의 노드, 서브트리 트래픽 용량 12 54
5. 문제 5 : 21개의 노드, 서브트리 트래픽 용량 6 57
6. 문제 6 : 21개의 노드, 서브트리 트래픽 용량 15 60
7. 노드 수의 증가에 따른 평균 설계비용의 차이 63
Ⅴ. 결 론 66
참고문헌 68
- Degree
- Master
- Appears in Collections:
- 경영대학원 > 경영학과-e비지니스전공
- Files in This Item:
-
-
Download
타부리스트가 결합된 유전자 알고리즘을 이용한 트리형 네트워크의 경제적 설계.pdf
기타 데이터 / 1.54 MB / Adobe PDF
-
Items in Repository are protected by copyright, with all rights reserved, unless otherwise indicated.