타부 리스트가 결합된 유전자 알고리즘을 이용한 트리형 네트워크의 경제적 설계
Economic Design of Tree Network Using Tabu List Coupled Genetic Algorithms
2
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
This paper considers an economic design problem of a tree-based network which is a kind of computer network. This problem can be modeling to be an objective function to minimize installation costs, on the constraints of spanning tree and maximum traffic capacity of sub tree. This problem is known to be NP-hard. To efficiently solve the problem, a tabu list coupled genetic algorithm approach is proposed. Two illustrative examples are used to explain and test the proposed approach. Experimental results show evidence that the proposed approach performs more efficiently for finding a good solution or near optimal solution in comparison with a genetic algorithm approach.
Abstract
This paper considers an economic design problem of a tree-based network which is a kind of computer network. This problem can be modeling to be an objective function to minimize installation costs, on the constraints of spanning tree and maximum traffic capacity of sub tree. This problem is known to be NP-hard. To efficiently solve the problem, a tabu list coupled genetic algorithm approach is proposed. Two illustrative examples are used to explain and test the proposed approach. Experimental results show evidence that the proposed approach performs more efficiently for finding a good solution or near optimal solution in comparison with a genetic algorithm approach.
참고문헌 (8)
- 김여근, "메타 휴리스틱, 유전알고리듬" (1997), 영지문화사
- Ersoy, C., "Topological Design of Interconnected LAN-MAN Networks", INFOCOM ‘92. Eleventh Annual Joint Conference of the IEEE Computer and Communications Societies, 3, pp.2260~2269 (1992), IEEE
- Gamvros, I., "The Multilevel Capacitated Minimum Spanning Tree Problem", Journal on Computing, 18(3), pp.348~365 (2006)
- Papadimitriou, C. H., "The Complexity of the Capacitated Tree Problem", Networks, 8, pp.217~230 (1978)
- Sharaiha, Y. M., "A Tabu Search Algorithm for the Capacitated Shortest Spanning Tree Problem", Networks, 29(3), pp.161~171 (1997)
- Tate, D. M., "A Genetic Approach to the Quadratic Assignment Problem", Computers and Operations Research, 22(1), pp.73~83 (1995)
- Torres-Jiménez, J., "A Simulated Annealing Approach for the Capacitated minimum Spanning Tree Problem", iccima, Third International Conference on Computational Intelligence and Multimedia Applications (ICCIMA‘99), pp.432~ (1999)
- Zhou, G., "A Genetic Algorithm Approach on Capacitated Minimum Spanning Tree Problem", Computational Intelligence and Security, 2006 International Conference on, pp.215~218 (2006)