평균패킷지연시간과 노드연결성이 제약된 네트워크 설계를 위한 Scatter Search 알고리즘
A Scatter Search Algorithm for Network Design with Mean Packet Delay and Node Connectivity Constraints
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
This paper considers a topological optimization of a network design with mean packet delay and node connectivity constraints. The objective is to find the topological layout of links, at minimal cost. This Problem is known to be NP-hard. To efficiently solve the problem, a scatter search algorithm is proposed. An illustrative example is used to explain and test the proposal approach. Experimental results show evidence that the proposal approach performs more efficiently for finding a good solution or near optimal solution in comparison with a genetic approach.
Abstract
This paper considers a topological optimization of a network design with mean packet delay and node connectivity constraints. The objective is to find the topological layout of links, at minimal cost. This Problem is known to be NP-hard. To efficiently solve the problem, a scatter search algorithm is proposed. An illustrative example is used to explain and test the proposal approach. Experimental results show evidence that the proposal approach performs more efficiently for finding a good solution or near optimal solution in comparison with a genetic approach.
참고문헌 (19)
- 송한식, "함수추정을 통한 시뮬레이션 최적화", 한국생산관리학회지, 17(2), pp.134~154 (2006), 한국생산관리학회
- 오동헌, "네트워크 설계를 위한 유전자 알고리즘의 성능 분석", 한국경영공학회지, 13(1), pp.147~154 (2008), 한국경영공학회
- 이한진, "Scatter Search를 이용한 신뢰성 있는 네트워크의 경제적 설계", 산업경영시스템학회지, 31(1), pp.101~107 (2008), 한국산업경영시스템학회
- 이한진, "Scatter Search를 이용한 LAN의 경제적 설계", 한국경영공학회지, 14(3), pp.13~22 (2009), 한국경영공학회
- Ahuja,R.K, "Netwok Flows : Theory, Algorithms, and Applications" (1993), Prentice Hall
- Alvarez,A.M, "Scatter Search for Network Design Problem", Annals of Operations Research, 138(1), pp.159~178 (2005)
- Alvarez,A.M, "Grasp Embedded Scatter Search for the Multicommodity Capacitated Network Design Problem", Journal of Heuristics, 11(3), pp.233~257 (2005)
- Cancela,H, "A Recursive Variance-Reduction Algorithm for Estimating Communication-Network Reliability", IEEE Transactions On Reliability, 44(4), pp.595~602 (1995)
- Dengiz,B, "Local Search Genetic Algorithm for Optimal Design of Reliable Networks", IEEE Transactions on Evolutionary Computation, 1(3), pp.179~188 (1997)
- Glover,F, "Heuristics for Integer Programming Using Surrogate Constraints", Decision Science, 8, pp.156~166 (1977)
- Glover,F, "Fundamentals of Scatter Search and Path Relinking", Control and Cybernetics, 39(3), pp.653~684 (2000)
- Konak A, "A Hybrid Genetic Algorithm Approach for Backbone Design of Communication Networks", Procedings of the 1999 Congress on Evolutionary Computation (1999), IEEE
- Laguna,M, "Scatter search. Methodology and implementation in C." (2003), Kluwer Academic Publishers
- Pierre,S, "Topological Design of Computer Communication Networks Using Simulated Annealing", Engineering Applications of Artificial Intelligence, 8(1), pp.61~69 (1995)
- Pierre,S, "A Tabu-Search Approach for Designing Computer-Network Topologies with Unreliable Components", IEEE Transactions on Reliability, 46(3), pp.350~359 (1997)
- Pierre,S, "An Evolutionary Approach for Configuring Economical Packet-switched Computer Networks", Artificial Intelligence in Engineering, 10(2), pp.127~134 (1996)
- Pierre,S, "A Genetic Algorithm for Designing Distributed Computer Network Topologies", IEEE Transactions on Systems,Man and Cybernetics, 28(2), pp.249~258 (1998)
- Wood,R.K, "Factoring Algorithms for Computing K-Terminal Network Reliability", IEEE Transactions On Reliability, 35(3), pp.269~278 (1986)
- Xu,J, "Tabu Search and Evolutionary Scatter. Search for ‘Tree-Star’ Network Problems, with Applications to Leased-Line Network Design, In Telecommunications Optimization : Heuristic and Adaptive Techniques" (2000), John and Wiley and Sons