무기할당 문제(Weapon Target Allocation : WTA)는 전형적인 NP-Complete 문제로 공중에서 위협하는 표적에 대해 아군의 무기를 적절히 할당하는 문제이다. 이러한 NP-Complete 문제들은 주로 휴리스틱 알고리즘을 이용하여 최적해를 찾는다. 유전자 알고리즘은 대표적인 휴리스틱 알고리즘으로 다양한 도메인에서 우수한 성능을 보여주는 휴리스틱 알고리즘이다. 유전자 알고리즘의 단계 중에 population 초기화는 최초 염색체를 결정하는 문제로 유전자 알고리즘의 해의 질을 높일 수 있고, 탐색성능을 높일 수 있으나 많은 연구가 이루어지고 있지 않는 분야이다. 따라서 본 논문에서는 WTA 문제를 해결하기 위해 유전자 알고리즘의 성능을 향상시키기 위한 population 초기화 알고리즘을 제안하고자 한다. 제안하는 알고리즘은 초기화할 때 WTA 문제 도메인의 특성을 반영하고, 우성유전자를 상속받는다. 또한, 문제 공간에서의 탐색 공간을 넓게 선정하여 질이 좋은 해를 효율적으로 찾을 수 있도록 하였다. 본 논문에서는 제안하는 알고리즘과 다른 알고리즘과의 다양한 속성의 비교분석 및 실험을 통해 성능을 분석하여 제안하는 알고리즘의 우수성을 검증하였다. 실험 결과 제안하는 알고리즘이 WTA 문제 해결에서 다른 방법들에 비해 좋은 성능을 보였다. 특히, 제안하는 알고리즘은 문제 상황에 따라 RMI 수치를 조정하여 적응성 있게 적용할 수 있기 때문에, 문제의 상황이 다양한 WTA 문제 도메인에 적용하기 적합한 알고리즘이다.
The Weapon Target Allocation(WTA) problem is the NP-Complete problem. The WTA problem is that the threatful air targets are assigned by weapon of allies for killing the targets. A good solution of NP-complete problem is heuristic algorithms. Genetic algorithms are commonly used heuristic for global optimization, and it is good solution on the diverse problem domain. But there has been very little research done on the generation of their initial population. The initialization of population is one of the GA step, and it decide to initial value of individuals. In this paper, we propose to the population initialization method to improve a Genetic Algorithm. When it initializes population, the proposed algorithm reflects the characteristics of the WTA problem domain, and inherits the dominant gene. In addition, the search space widely spread in the problem space to find efficiently the good quality solution. In this paper, the proposed algorithm to verify performance examine that an analysis of various properties and the experimental results by analyzing the performance compare to other algorithms. The proposed algorithm compared to the other initialization methods and a general genetic algorithm. As a result, the proposed algorithm showed better performance in WTA problem than the other algorithms. In particular, the proposed algorithm is a good way to apply to the variety of situation WTA problem domain, because the proposed algorithm can be applied flexibly to WTA problem by the adjustment of RMI.
