효율적인 유전 알고리즘을 활용한 요격미사일 할당 및 교전 일정계획의 최적화
An Efficient Genetic Algorithm for the Allocation and Engagement Scheduling of Interceptor Missiles
0
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
This paper considers the allocation and engagement scheduling problem of interceptor missiles, and the problem was formulated by using MIP (mixed integer programming) in the previous research. The objective of the model is the maximization of total intercept altitude instead of the more conventional objective such as the minimization of surviving target value. The concept of the time window was used to model the engagement situation and a continuous time is assumed for flying times of the both missiles. The MIP formulation of the problem is very complex due to the complexity of the real problem itself. Hence, the finding of an efficient optimal solution procedure seems to be difficult. In this paper, an efficient genetic algorithm is developed by improving a general genetic algorithm. The improvement is achieved by carefully analyzing the structure of the formulation. Specifically, the new algorithm includes an enhanced repair process and a crossover operation which utilizes the idea of the PSO (particle swarm optimization). Then, the algorithm is throughly tested on 50 randomly generated engagement scenarios, and its performance is compared with that of a commercial package and a more general genetic algorithm, respectively. The results indicate that the new algorithm consistently performs better than a general genetic algorithm. Also, the new algorithm generates much better results than those by the commercial package on several test cases when the execution time of the commercial package is limited to 8,000 seconds, which is about two hours and 13 minutes. Moreover, it obtains a solution within 0.13 ~33.34 seconds depending on the size of scenarios.
Abstract
This paper considers the allocation and engagement scheduling problem of interceptor missiles, and the problem was formulated by using MIP (mixed integer programming) in the previous research. The objective of the model is the maximization of total intercept altitude instead of the more conventional objective such as the minimization of surviving target value. The concept of the time window was used to model the engagement situation and a continuous time is assumed for flying times of the both missiles. The MIP formulation of the problem is very complex due to the complexity of the real problem itself. Hence, the finding of an efficient optimal solution procedure seems to be difficult. In this paper, an efficient genetic algorithm is developed by improving a general genetic algorithm. The improvement is achieved by carefully analyzing the structure of the formulation. Specifically, the new algorithm includes an enhanced repair process and a crossover operation which utilizes the idea of the PSO (particle swarm optimization). Then, the algorithm is throughly tested on 50 randomly generated engagement scenarios, and its performance is compared with that of a commercial package and a more general genetic algorithm, respectively. The results indicate that the new algorithm consistently performs better than a general genetic algorithm. Also, the new algorithm generates much better results than those by the commercial package on several test cases when the execution time of the commercial package is limited to 8,000 seconds, which is about two hours and 13 minutes. Moreover, it obtains a solution within 0.13 ~33.34 seconds depending on the size of scenarios.
참고문헌 (34)
- Ahner, D. K., "Optimal multi-stage allocation of weapons to targets using adaptive dynamic programming", Optimization Letters, 9(8), pp.1689~1701 (2015)
- Ahuja, R. K., "Exact and heuristic algorithms for the weapon-target assignment problem", Operations Research, 55(6), pp.1136~1146 (2007)
- Chen, H., "Particle swarm optimization based on genetic operators for sensor-weapon-target assignment", 2012 Fifth International Symposium on Computational Intelligence and Design, pp.170~173 (2012)
- Chen, J., "Evolutionary decision-makings for the dynamic weapontarget assignment problem", Science in China Series F :Information Sciences, 52(11), pp.2006~2018 (2009)
- Coello, C. A., "Theoretical and numerical constraint- handling techniques used with evolutionary algorithms : a survey of the state of the art", Computer Methods in Applied Mechanics and Engineering, 191, pp.1245~1287 (2002)
- Fu, T., "Improved genetic and ant colony optimization algorithm for regional air defense WTA problem", Proceedings of the First International Conference on Innovative Computing, Information and Control, pp.226~229 (2006)
- Geetha, S., "A hybrid particle swarm optimization with genetic operators for vehicle routing problem", Journal of Advances in Information Technology, 1(4), pp.181~188 (2010)
- Gulez, T, "Weapon-target allocation and scheduling for air defense with time varying hit probabilities", master, pp.2007
- 홍성삼, "무기할당문제에서 유전자 알고리즘의 성능을 개선하기 위한 population 초기화 방법에 관한 연구", 한국지능시스템학회 논문지, 22(5), pp.540~548 (2012), 한국지능시스템학회
- Hosein, P, "A class of dynamic nonlinear resource allocation problems", pp.1989
- 장준건, "자산기반 무기할당 문제의 선형 근사 모형", 산업경영시스템학회지, 38(3), pp.108~116 (2015), 한국산업경영시스템학회
- Julstrom, B.A., "String-and permutation-coded genetic algorithms for the static weapon-target assignment problem", Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference, pp.2553~2558 (2009)
- Jung, H.S., "Ballistic Missile Defense", Journal of the Defense Science and Technology Information, 40, pp.169~ (2013)
- Karasakal, O., "Optimal air defense strategies for a naval task group", pp.2004
- Khosla, D., "Hybrid genetic approach for the dynamic weapon-target allocation problem", Proceedings of SPIE, 4396, pp.244~259 (2001)
- Kim, M. S., "The missiles that occupy news, KAMD and Kill Chain", Geunduun, 59, pp.14~17 (2013)
- Krokhmal, P., "Recent Developments in Cooperative Control and Optimization", pp.225~243 (2004), Kluwer Academic Publishers
- 이대력, "혼합정수계획법을 이용한 요격미사일의 할당 및 교전 일정계획에 관한 연구", 경영과학, 32(4), pp.109~133 (2015), 한국경영과학회[DOI]
- Lee, J.B., "A study on real time dynamic multi-weapon multi-target assignment algorithm", pp.2009
- Lee, M. Z., "Constrained weapon-target assignment : enhanced very large scale neighborhood search algorithm", IEEE Transactions on Systems Man and Cybernetics-Part A Systems and Humans, 40(1), pp.198~204 (2010)
- Lee, Z. J., "An immunity-based ant colony optimization algorithm for solving weapon-target assignment problem", Applied Soft Computing, 2(1), pp.39~47 (2002)
- Liu, C., "An adaptive memetic algorithm solving dynamic weapon target assignment problem", IEEE International Conference on Information Engineering and Computer Science, pp.1~4 (2010)
- Liu, P., "WTA model study of air defense missile system based on particle algorithm", Proceedings of IEEE Chinese Guidance, Navigation and Control Conference, pp.1534~1538 (2014)
- Defense White Paper, "Ministry of National Defense(Republic of Korea)", 58~59 (2014)
- Moon, B.R., "Easy Learning Genetic Algorithms", pp.59~61 (2008), Hanbit Media Inc.
- Murphey, R.A., "Approximation and Complexity in Numerical Optimization : Continuous and Discrete Problems", pp.1~16 (1999), Kluwer Academic Publishers
- Song, Z., "A heuristic genetic algorithm for solving constrained weapon-target assignment problem", IEEE International Conference on Intelligent Computing and Intelligent Systems, pp.336~341 (2009)
- Teng, P., "Improved particle swarm optimization algorithm and its application in coordinated air combat missile-target assignment", Proceedings of the 7th World Congress on Intelligent Control and Automation, pp.2833~2837 (2008)
- 우병훈, "Reinforced Genetic Algorithm for Solving Reliability Optimization Design Problems", 대한설비관리학회지, 17(4), pp.17~33 (2012), 대한설비관리학회
- Xin, B., "An Estimation of Distribution Algorithm with Efficient Constructive Repair", Improvement Operator for the Dynamic Weapon-Target Assignment, 2012, 2346~2351
- Xin, B., "An efficient rule-based constructive heuristic to solve dynamic weapon-target assignment problem", IEEE Transactions on Systems, Man, and Cybernetics-Part A : Systems and Humans, 41(3), pp.598~606 (2011)
- You, H.-S., "A performance improvement study on weapon assignment of fire control system", master, pp.2014
- Zhang, J., "ACGA algorithm of solving weapon-target assignment problem", Open Journal of Applied Sciences, 2(4), pp.74~77 (2012)
- Zhu, B., "A novel approach to solving weapon-target assignment problem based on hybrid particle swarm optimization algorithm", International Conference on Electronic and Mechanical Engineering and Information Technology, pp.1385~1387 (2011)