채널배선 문제에 대한 분산 평균장 유전자 알고리즘 = Distributed Mean Field Genetic Algorithm for Channel Routing

국문 초록 (Abstract)

본 논문에서는 MPI(Message Passing Interface) 환경 하에서 채널배선 문제에 대한 분산 평균장 유전자 알고리즘(MGA, Mean field Genetic Algorithm)이라는 새로운 최적화 알고리즘을 제안한다. 분산 MGA는 평균장 어닐링(MFA, Mean Field Annealing)과 시뮬레이티드 어닐링 형태의 유전자 알고리즘(SGA, Simulated annealing-like Genetic Algorithm)을 결합한 경험적 알고리즘이다. 평균장 어닐링의 빠른 평형상태 도달과 유전자 알고리즘의 다양하고 강력한 연산자를 합성하여 최적화 문제를 효율적으로 해결하였다. 제안된 분산 MGA를 VLSI 설계에서 중요한 주제인 채널 배선문제에 적용하여 실험한 결과 기존의 GA를 단독으로 사용하였을 때보다 최적해에 빠르게 도달하였다. 또한 분산 알고리즘은 순차 알고리즘에서의 최적해 수렴 특성을 해치지 않으면서 문제의 크기에 대하여 선형적인 수행시간 단축을 나타냈다.

다국어 초록 (Multilingual Abstract)

In this paper, we introduce a novel approach to optimization algorithm which is a distributed Mean field Genetic algorithm (MGA) implemented in MPI(Message Passing Interface) environments. Distributed MGA is a hybrid algorithm of Mean Field Annealing(MFA) and Simulated annealing-like Genetic Algorithm(SGA). The proposed distributed MGA combines the benefit of rapid convergence property of MFA and the effective genetic operations of SGA. The proposed distributed MGA is applied to the channel routing problem, which is an important issue in the automatic layout design of VLSI circuits. Our experimental results show that the composition of heuristic methods improves the performance over GA alone in terms of mean execution time. It is also proved that the proposed distributed algorithm maintains the convergence properties of sequential algorithm while it achieves almost linear speedup as the problem size increases.

참고문헌 (Reference)

1 홍철의, "평균장 어닐링과 유전자 알고리즘을 결합한 부하균형기법" 한국정보과학회 33 (33): 486-494, 2006

2 Zomaya, A.Y., "Observations on Using Genetic Algorithms for Dynamic Load-Balancing" 2 (2): 899-911, 2001

3 Salleh, S., "Multiprocessor Scheduling Using Mean-Field Annealing" 288-296, 1998

4 Susmita, S., "Manhattan-diagonal routing in channels and switchboxes" 9 (9): 2004

5 Metin Ozkan, "Hierarchical oriented genetic algorithms for coverage path planning of multi-robot teams with load balancing" 2009

6 Yang, C., "Efficient routability check algorithms for segmented channel routing" 5 (5): 2000

7 Pau Bofill, "Comparison of simulated annealing and mean field annealing as applied to the generation of block designs" 16 (16): 1421-1428, 2003

8 Chen, S., "Bubble-Sort Approach to Channel Routing" 147 (147): 2000

9 W. Kim, "Asynchronous Distributed Genetic Algorithm for Optimal Channel Routing" 2004

10 Yonghuai Liu, "A mean field annealing approach to accurate free form shape matching" 40 (40): 241-82436, 2007

11 Funabiki, N., "A Parallel Algorithm for Channel Routing Problem" 11 (11): 464-474, 1992

12 Bultan, T., "A New Mapping Heuristic Based on Mean Field Annealing" 16 : 292-305, 1992

13 Ning, X., "A Neural Network Optimization Algorithm For Channel Routing" 14 (14): 2002