부하평준화 문제에서 국지적 탐색의 효율향상을 위한 이웃해 선정 기법 = A Neighbor Selection Technique for Improving Efficiency of Local Search in Load Balancing Problems

국문 초록 (Abstract)

일반적으로 국지적 탐색에서 최적해를 획득할 가능성은 가능한 많은 이웃해를 생성하면서 반복 수를 늘릴수록 높아지나 긴 탐색시간이 소요된다. 따라서 한정된 시간 내에 최적해를 효율적으로 찾기 위해서는, 적절한 수의 이웃해를 생성하되, 탐색의 질을 높일 수 있는 이웃해를 선별해서 생성하는 것이 요구된다. 본 논문에서는 국지적 탐색기법을 적용하여 부하평준화 문제를 해결할 때, 탐색의 효율을 향상시킬 수 있는 이웃해 선정 기법을 제안하고, 실세계 데이타를 대상으로 그 성능을 검증하였다. 본 논문에서 제안하는 이웃해 선정 기법은 확률적 선별에 기반한 방법으로서, 탐색의 질을 개선시킬 가능성에 대한 추정치를 기준으로 부여된 확률에 따라 이웃해를 선별하여 생성하는 기법이다. 대상 문제에 국지적 탐색기법으로 tabu 탐색과 simulated annealing를 적용한 실험에서, 무작위 또는 그리디 선별에 기반한 방법보다 우수한 성능을 보임을 확인하였다.

다국어 초록 (Multilingual Abstract)

For a local search algorithm to find a better quality solution it is required to generate and evaluate a sufficiently large number of candidate solutions as neighbors at each iteration, demanding quite an amount of CPU time. This paper presents a method of selectively generating only good-looking candidate neighbors, so that the number of neighbors can be kept low to improve the efficiency of search. In our method, a newly generated candidate solution is probabilistically selected to become a neighbor based on the quality estimation determined heuristically by a very simple evaluation of the generated candidate. Experimental results on the problem of load balancing for production scheduling have shown that our candidate selection method outperforms other random or greedy selection methods in terms of solution quality given the same amount of CPU time.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 대상문제
• 3. 탐색 알고리즘의 개요
• 4. 확률 기반의 이웃해 생성 방법
• 5. 결론 및 향후 연구
• 참고문헌
• 저자소개

참고문헌 (Reference)

1 "하이브리드 유전 알고리즘과 반복적 개선 탐색 기법에 의한 일정계획" 25 (25): 825 -835, 1998

2 "Very large-scale neighborhood search" 7 (7): 301 -317, 2000

3 "Tabu Search를 이용한 작업일정계획 및 재일정계획 수립" 376 -387, 1997

4 "Tabu Search:Part1" 1 (1): 1989pp.190∼206.

5 "Tabu Search Candidate List Strategies in Scheduling" Kluwer Academic Publishers chapter 8 : 215 -234, January1998a

6 "Tabu Search" Kluwer Academic, Publishers 1997.

7 "Optimization by simulated annealing Journal of Statistical Physics 34" 975986-, 1984

8 "Greedy Randomized Adaptive Search Procedures" 6 : 109 -133, 1995

9 "Graduate School of Business University of Colorado condensed version published in Mathematical Programming State of Art" 1994

10 "Genetic algorithms in search" 1989.