Journal of the Korean Institute of Intelligent Systems (한국지능시스템학회논문지)

Korean Institute of Intelligent Systems (한국지능시스템학회)
권호 표지
DOI QR코드

DOI QR Code

A Study of population Initialization Method to improve a Genetic Algorithm on the Weapon Target Allocation problem

무기할당문제에서 유전자 알고리즘의 성능을 개선하기 위한 population 초기화 방법에 관한 연구

  • Received : 2012.05.25
  • Accepted : 2012.09.11
  • Published : 2012.10.25
Download PDF
⟨ Previous Next ⟩

Abstract

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.

무기할당 문제(Weapon Target Allocation : WTA)는 전형적인 NP-Complete 문제로 공중에서 위협하는 표적에 대해 아군의 무기를 적절히 할당하는 문제이다. 이러한 NP-Complete 문제들은 주로 휴리스틱 알고리즘을 이용하여 최적해를 찾는다. 유전자 알고리즘은 대표적인 휴리스틱 알고리즘으로 다양한 도메인에서 우수한 성능을 보여주는 휴리스틱 알고리즘이다. 유전자 알고리즘의 단계 중에 population 초기화는 최초 염색체를 결정하는 문제로 유전자 알고리즘의 해의 질을 높일 수 있고, 탐색성능을 높일 수 있으나 많은 연구가 이루어지고 있지 않는 분야이다. 따라서 본 논문에서는 WTA 문제를 해결하기 위해 유전자 알고리즘의 성능을 향상시키기 위한 population 초기화 알고리즘을 제안하고자 한다. 제안하는 알고리즘은 초기화할 때 WTA 문제 도메인의 특성을 반영하고, 우성유전자를 상속받는다. 또한, 문제 공간에서의 탐색 공간을 넓게 선정하여 질이 좋은 해를 효율적으로 찾을 수 있도록 하였다. 본 논문에서는 제안하는 알고리즘과 다른 알고리즘과의 다양한 속성의 비교분석 및 실험을 통해 성능을 분석하여 제안하는 알고리즘의 우수성을 검증하였다. 실험 결과 제안하는 알고리즘이 WTA 문제 해결에서 다른 방법들에 비해 좋은 성능을 보였다. 특히, 제안하는 알고리즘은 문제 상황에 따라 RMI 수치를 조정하여 적응성 있게 적용할 수 있기 때문에, 문제의 상황이 다양한 WTA 문제 도메인에 적용하기 적합한 알고리즘이다.

Keywords

References

  1. Dorigo, M., Maniezzo and Colorni, A., "The ant system : an autocatalyic optimizing process," Technical Report 91-016 Revised, Dipartimento di Elettronica, Politecnico di Milano, 1991.
  2. Kirkpatrick, S, Gelatt, C. D and Vecchi, M. P, "Optimization by Simulated Annealing," Science 220, pp. 671-680, 1983. https://doi.org/10.1126/science.220.4598.671
  3. Fred Glover, "Tabu Search-Part 1," ORSA Journal on Computing, vol. 1, no. 2, pp. 190-206, 1989. https://doi.org/10.1287/ijoc.1.3.190
  4. Fred Glover, "Tabu Search-Part 2," ORSA Journal on Computing, vol. 2, no. 1, pp. 4-32, 1990. https://doi.org/10.1287/ijoc.2.1.4
  5. J. Kennedy and R. Eberhart, "Particle Swarm Optimization," IEEE International Conference Neural Network, vol. 4, pp. 1942-1948, 1995.
  6. D.E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison- Wesley Publishing Company Inc, 1989.
  7. Kyung-Youb Kwon and Joongseon Joh, "Weapon-Target Assignment Using Genetic Algorithm," Proceeding of KFIS Fall Conference, vol. 13, no. 5, 2003.
  8. Ji-Hong Yang and Myung-Mook Han, "The Intelligent Intrusion Detection Systems using Automatic Rule-Based Method," Journel of Korean Institute of Intelligent Systems, vol. 12, no. 6, pp. 531-536, 2002. https://doi.org/10.5391/JKIIS.2002.12.6.531
  9. Heikki Maaranen, Kaisa Miettinen and Antti Penttinen, "On initial populations of a genetic algorithm for continuous optimization problems," Journal of Global Optimization, vol. 37, no. 3, pp. 405-436, 2007. https://doi.org/10.1007/s10898-006-9056-6
  10. Stephane Paradis, Abder Rezak Benaskeur, Martin Oxenham, and Philip Cutler, "Threat evaluation and weapons allocation in network-centric warfare," In Proceedings of the 8th International Conference on Information Fusion, vol. 2, no. 2, 2005.
  11. George G. den Broeder, R. E. Ellison, and L. Emerling, "On optimum target assignments," Operations Research, vol. 7, no. 3, pp. 322-326, 1959. https://doi.org/10.1287/opre.7.3.322
  12. Matsumoto, M., Nishimura, T, "Mersenne twister: a 623-dimensionally equidistributed uniform pseudo- random number generator," ACM Transactions on Modeling and Computer Simulation, vol. 8, no. 1, pp. 3-30, 1998. https://doi.org/10.1145/272991.272995
  13. Diggle, P.J., Statistical Analysis of Spatial Point Patterns, Academic Press, 1983.
  14. Fredrik Johansson, Evaluating the Performance of TEWA Systems, Ph.D Thesis Orebro University, 2010.
  15. Ripley, B.D, Spatial Statistics, John Wiley & Sons, 1981.