무장 할당문제에서 휴리스틱 방법 효율성 비교: 이행성 규칙이 성립하는 무장성능차이를 중심으로 = Performance Comparison of Heuristics for Weapon-Target Assignment Problem with Transitivity Rules in Weapon's Kill Probability

다국어 초록 (Multilingual Abstract)

In this study, the weapon-target assignment problem arising in military application of operations research is considered. We reformulated the problem in order to simplify the solution methods based on genetic algorithms and heuristics. Since the problem is well known as NP-complete and cannot be solved in polynomial time, such solution methods have been widely used to obtain good solutions. Two chromosome representations--target number representation and permutation representation--in genetic algorithm are compared. In addition, a construction heuristic and three improving heuristics are developed. Several experiments under the condition of transitivity rules in weapon's kill probability have been accomplished. It shows that the construction heuristic and exchange-based improving heuristic guarantees good solutions within a second and the performance of construction heuristic is sensitive to transitivity rules.

참고문헌 (Reference)

1 Lloyd, S. P., "Weapon Allocation is NP-complete" 1054-1058, 1986

2 Murphey, R. A., "Target-based weapon target assignment problems. in: Nonlinear Assignment Problems: Algorithms and Applications" Kluwer Academic Publishers 39-53, 1999

3 Jones, D. R., "Proceedings of the Fourth International Conference on Genetic Algorithms" Morgan Kaufmann Publishers 442-449, 1991

4 Goldberg, D. E., "Proceedings of the First International Conference on Genetic Algorithms, Lawrence Erlbaum Associates" Hillsdale 154-159, 1985

5 Harhalakis, G., "Manufacturing cell design using simulated annealing: An industrial application" Journal of Intelligent Manufacturing 185-191, 1990

6 Michaelwicz, Z., "Genetic Algorithms + Data Structures = Evolution Programs" Springer-Verlag 1992

7 Ahuja, R. K., "Exact and Heuristic Algorithms for the Weapon-Target Assignment Problem" 55 (55): 1136-1140, 2007

8 Lee, Z. J., "Efficiently Solving General Weapon-Target Assignment Problem by Genetic Algorithms With Greedy Eugenics" 33 (33): 113-121, 2003

9 Davis, L., "Applying Adaptive Algorithms to Epistatic Domains" 162-164, 1985

10 Oliver, I. M., "A Study of Permutation Crossover Operators on the traveling Salesman Problem" Lawrence Erlbaum Associates 224-230, 1987