유전 알고리즘을 이용한 무기표적할당 최적화 (Optimization of Weapon Target Assignment Using a Genetic Algorithm)

서지정보

· 발행기관 : 한국지능시스템학회
· 수록지 정보 : 한국지능시스템학회 논문지 / 29권 / 3호 / 176 ~ 181페이지
· 저자명 : 김혜진, 김용혁

초록

본 논문에서는 조합최적화 문제 중 하나인 무기표적할당문제(weapon target assignment problem; WTA)를 풀이하는데에 유전 알고리즘을 사용한다. 기존의 WTA에는 제약조건이 한 개였던 것에 반해, 본 논문에서는 제약조건을 하나 더추가하여 확장된 WTA를 다룬다. 본 연구에서는 제약조건이 있는 할당 문제인 WTA를 해결하기 위해 새로운 수선(repair) 메커니즘을 제안하며, 해당 연산은 제약조건과 조응하도록 2 단계로 진행하여 배치를 적격해(feasible solution)로 수정한다.
또한, 본 논문에서는 효과적인 WTA 해결을 위해 서로 다른 교차(crossover) 연산의 성능을 비교한다. 균등교차(uniform crossover)를 사용하는 유전 알고리즘과 블록균등교차(block-uniform crossover)를 사용하는 유전 알고리즘을 설계하고, 다양한 파라미터를 가지는 WTA에 적용하여 두 가지 방법에 대하여 비교한다. 결과적으로, 제안한 방법은 무작위 배치보다유의미하게 개선하여 성공적으로 WTA문제를 해결하였고, 블록 단위로 염색체를 복사하는 블록균등교차가 2차원 배치를필요로 하는 WTA 문제 풀이를 위해 더 적합한 교차 연산임을 알 수 있었다.

영어초록

In this paper, we use a genetic algorithm to solve the weapon target assignment problem (WTA), which is one of combinatorial optimization problems. In contrast to the existing WTA with one constraint, we deal with an extended WTA with an additional constraint. To solve WTA, which is a constrained assignment problem, we propose a new repair mechanism, and the repair operation the extended proceeds in the two stagesfitted onto each constraint. In addition, we compare the performance of different crossover operations for effective WTA solutions. Genetic algorithm using uniform crossover and one using block-uniform crossover are designed and applied to WTA on various instances to compare the two methods. As a results, the proposed method successfully solved the WTA problem with significant improvement over multi-start random assignment. We found that block-uniform crossover, which replicates chromosomes on block-by-block basis, is more suitable for WTA that requires two-dimensional representation.

참고자료

· 없음