수정 유전알고리듬을 사용한 최대유통문제의 치명호 결정방법 = A Method for Determining the k Most Vital Arcs Using Genetic Algorithms in Maximum Flow Problem

다국어 초록 (Multilingual Abstract)

The purpose of this study is to present a method for determining the k most vital arcs in the maximum flow problem using genetic algorithms. Generally, the problem which determine the k most vital arcs in maximum flow problem has known as NP-hard. Therefore, in this study we propose a method for determining all the k most vital arcs in maximum flow problem using a genetic algorithm and a revised genetic algorithm. First, we propose genetic algorithm to find the k most vital arcs removed at the same time then present the expression and determination method of individuals compatible with the characteristics of the problem, and specify the genetic parameter values of constitution, population size, crossover rate, mutation rate and etc. of the initial population which makes detecting efficiency better. Finally, using the proposed algorithm, we analyzed the performance of searching optimal solution through computer experiment. The proposed algorithms found all alternatives within shorter time than other heuristic methods. The method presented in this study can determine all the alternatives when there exists other alternative solutions.