<33312D312D313220C0CCC7D1C1F820BFB0C3A2BCB12E687770>

Size: px

Start display at page:

Download "<33312D312D313220C0CCC7D1C1F820BFB0C3A2BCB12E687770>"

현우 하
8 years ago
Views:

1 Journal of the Society of Korea Industrial and Systems Engineering Vol No pp March 8 Scatter Search를 이용한 신뢰성 있는 네트워크의 경제적 설계 * ** * ** Economic Design of Reliable Networks Using Scatter Search HanJin Lee* ChangSun Yum** *Division of Business Administration KyungNam University **Division of Business Administration Pukyong National University This paper considers a topological optimization of a computer network design with a reliability constraint The objective is to find the topological layout of links at minimal cost under the constraint that the network reliability is more than a given reliability To efficiently solve the problem a scatter search 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 Keywords Economic Design Reliable Network Scatter Search 서 론 Deeter and Smith998 netic algorithm ge Jan et al99 solution simulated annealing NPhard Wood 98; Cancela and Khadiri 99; Dengiz et al 99 Jan et al99 decomposition 접수일년 월 9일 수정일8년 월 9일 게재확정일8년 월 일 yumcs@pknuackr evolutionary

computer network design with a reliability constraint The objective is to find the topological layout of links at minimal cost under the constraint that the network reliability is more than a given

2 이한진 염창선 method Scatter Search Glover9 E {i j} {i j} k x = { } Cx Rx R random combination x x Glover et diversification intensification Alvarez GonzálezVelarde and De Albaa; b capacitated multicommodity GRASPgreedy randomized adaptive search procedure embedded Xu Chiu and Glover treestar tabu search al Laguna and Marti population reference set l Minimize {i j} aij {i j} {i j} Scatter Search를 위한 네트워크 설계 구조의 표현 > Scatter Search를 이용한 네트워크 설계 문제의 표현 표 > 네트워크의 노드 간의 링크 유형 기본 가정 및 표기 형식 bidirectional operational failed

procedure embedded Xu Chiu and Glover treestar tabu search al Laguna and Marti population reference set l Minimize {i j} aij {i

3 Scatter Search를 이용한 신뢰성 있는 네트워크의 경제적 설계 초기 모집단의 생성 { } > k perturbat ion solution Scatter Search를 이용한 네트워크 설계 complement Glover 9 네트워크 설계를 위한 절차 Van Slyke and Frank9 a perturbation feasible solution improvement infeasible solution p b c 초기 참조해 집단의 생성 a b b heterogeneity b diversity measure b maximin a sum of the absolute difference Laguna Marti b b b l a 반복적인 지역탐색 과정 결합해 생성 a = b a b c

feasible solution improvement infeasible solution p b c 초기 참조해 집단의 생성 a b b heterogeneity b

4 이한진 염창선 { } { } > Deeter and Smith 998 표 > 노드간 거리단위 m 결합해를 통한 참조해 집단 갱신 b + b 8 9 Laguna and Marti 다양화된 해를 통한 참조해 집단 갱신 b b = 8 = b b 제약조건 Scatter Search를 이용한 네트워크 설계 의 성능 실험 PentiumIV8GHz PC MB RAM > 신뢰도 p = b = b = = = > = % 단위거리 당 비용$ 최적해 문제 개 노드 연결 네트워크 신뢰도 imax = 표 > 링크 유형의 속성 > 비용$ 링크 유형 표 > 제약조건에 따른 최적해 enumerative / = 9% /8

MB RAM > 신뢰도 999 9998 99 998 99 99 9 9 9 9 9 8 98 8 9 8 8 8 9 p = b = b = = = 8 999 > = % 단위거리 당

5 Scatter Search를 이용한 신뢰성 있는 네트워크의 경제적 설계 표 > 문제 의 탐색 결과 제약조건 평균 탐색한 해의 수 탐색공간에 대한 탐색 해의 백분율% 최적해의 수 999 of 99 9 of 99 9 of 9 of 9 8 of 9 of 8 9 of Deeter and Smith 998 문제 개 노드 연결 Smith998 표 > Deeter and Smith998의 와 비교 m = Deeter > 표 > 노드간 거리 > = 9 최적해의 수 제약조건 Deeter and Smith998의 = 8 = = of of 99 of of 99 of of 9 of of 9 of of 9 of of 8 of of > $ 98 {} Smith998 > $ {} = 8 99 = / seconds 결 론 = = 9 8> 9> = 999 Deeter and = = = $ 98 {} 8$

= 8 999 Deeter > 표 > 노드간 거리 > = 9 최적해의 수 제약조건 Deeter and Smith998의 = 8 = = 999 8 of of 99 of of 99 of of 9 of of 9

6 이한진 염창선 표8> 초기가장우수한해의노드간링크유형 그림 > 초기 가장 우수한 해 = $ 표 9> 가장 우수한 최종해의 노드 간 링크 유형 그림 > 가장 우수한 최종해 = $ scatter search scatter search scatter search 참고문헌 [] ; Scatter Search [] ; 888 [] ; [] Alvarez A; GonzálezVelarde J L and DeAlba K; Scatter Search for Network Design Problem Annals of Operations Research 8 98 [] Alvarez A GonzálezVelarde J L and De Alba K; Grasp Embedded Scatter Search for the Multicommod

GonzálezVelarde J L and DeAlba K; Scatter Search for Network Design Problem Annals of Operations

7 Scatter Search를 이용한 신뢰성 있는 네트워크의 경제적 설계 ity Capacitated Network Design Problem Journal of Heuristics [] Xu J Chiu S and Glover F; Tabu Search and Evolutionary Scatter Search for TreeStar Network Problems with Applications to LeasedLine Network Design Telecommunications Optimization Heuristic and Adaptive Techniques John Wiley and Sons [] Deeter D L and Smith A E; Economic Design of Reliable Networks IIE Transactions 998 [8] Dengiz B Altiparmak F and Smith A E; Efficient Optimization of AllTerminal Reliable Networks Using an Evolutionary Approach IEEE Transactions on Reliability 99 [9] Glover F; Heuristics for Integer Programming Using Surrogate Constraints Decision Science 8 9 [] Glover F Laguna M and Marti M; Fundamentals of Scatter Search and Path Relinking Control and Cybernetics 9 8 [] Laguna M and Marti R; Scatter search Methodology and implementation in C Boston Kluwer Academic Publishers [] Wood R K; Factoring Algorithms for Computing KTerminal Network Reliability IEEE Transactions On Reliability [] Van Slyke R M and Frank H; Network Reliability AnalysisPart Networks 9 9

Networks IIE Transactions 998 [8] Dengiz B Altiparmak F and Smith A E; Efficient Optimization of AllTerminal Reliable Networks Using an Evolutionary Approach IEEE Transactions on Reliability 99 [9]

I

I II III (C B ) (C L ) (HL) Min c ij x ij f i y i i H j H i H s.t. y i 1, k K, i W k C B C L p (HL) x ij y i, i H, k K i, j W k x ij y i {0,1}, i, j H. K W k k H K i i f i i d ij i j r ij i j c ij r ij