양자화 유전자알고리즘을 이용한 무기할당
An Application of Quantum-inspired Genetic Algorithm for Weapon Target Assignment Problem
0
조회
0
다운로드
7
인용
0
참고문헌
키워드
초록
Quantum-inspired Genetic Algorithm (QGA) is a probabilistic search optimization method combined quantum computation and genetic algorithm. In QGA, the chromosomes are encoded by qubits and are updated by quantum rotation gates, which can achieve a genetic search. Asset-based weapon target assignment (WTA) problem can be described as an optimization problem in which the defenders assign the weapons to hostile targets in order to maximize the value of a group of surviving assets threatened by the targets. It has already been proven that the WTA problem is NP-complete. In this study, we propose a QGA and a hybrid-QGA to solve an asset-based WTA problem. In the proposed QGA, a set of probabilistic superposition of qubits are coded and collapsed into a target number. Q-gate updating strategy is also used for search guidance. The hybrid-QGA is generated by incorporating both the random search capability of QGA and the evolution capability of genetic algorithm (GA). To observe the performance of each algorithm, we construct three synthetic WTA problems and check how each algorithm works on them. Simulation results show that all of the algorithm have good quality of solutions. Since the difference among mean resulting value is within 2%, we run the nonparametric pairwise Wilcoxon rank sum test for testing the equality of the means among the results. The Wilcoxon test reveals that GA has better quality than the others. In contrast, the simulation results indicate that hybrid-QGA and QGA is much faster than GA for the production of the same number of generations.
Abstract
Quantum-inspired Genetic Algorithm (QGA) is a probabilistic search optimization method combined quantum computation and genetic algorithm. In QGA, the chromosomes are encoded by qubits and are updated by quantum rotation gates, which can achieve a genetic search. Asset-based weapon target assignment (WTA) problem can be described as an optimization problem in which the defenders assign the weapons to hostile targets in order to maximize the value of a group of surviving assets threatened by the targets. It has already been proven that the WTA problem is NP-complete. In this study, we propose a QGA and a hybrid-QGA to solve an asset-based WTA problem. In the proposed QGA, a set of probabilistic superposition of qubits are coded and collapsed into a target number. Q-gate updating strategy is also used for search guidance. The hybrid-QGA is generated by incorporating both the random search capability of QGA and the evolution capability of genetic algorithm (GA). To observe the performance of each algorithm, we construct three synthetic WTA problems and check how each algorithm works on them. Simulation results show that all of the algorithm have good quality of solutions. Since the difference among mean resulting value is within 2%, we run the nonparametric pairwise Wilcoxon rank sum test for testing the equality of the means among the results. The Wilcoxon test reveals that GA has better quality than the others. In contrast, the simulation results indicate that hybrid-QGA and QGA is much faster than GA for the production of the same number of generations.
참고문헌 (21)
- Bisht, S., "Hybrid Genetic-Simulated Annealing Algorithm for Optimal Weapon Allocation in Multilayer Defense Scenario", Defense Science Journal, 54(3), pp.395~405 (2004)
- Fu, T., "Improved Genetic & Ant Colony Optimization for Regional Air Defense WTA Problem", Proceedings of the 1st International Conference on Innovative Computers, Information, Control, pp.226~229 (2006)
- "On Setting the Parameters Of Quantum-inspired Evolutionary Algorithm for Practical Applications"[URL]
- Han, K.H., "Quantum-Inspired Evolutionary Algorithm for Class of Combinatorial Optimization", IEEE Transaction on Evolutionary Computation, 6(6), pp.580~593 (2002)
- 홍성삼, "무기할당문제에서 유전자 알고리즘의 성능을 개선하기 위한 population 초기화 방법에 관한 연구", 한국지능시스템학회 논문지, 22(5), pp.540~548 (2012), 한국지능시스템학회
- Some Analytical Results for the Dynamic Weapon-Target Allocation problem, "Hosein P.A.", MIT, ~, pp.MIT Technology Report LIDSP-1944 (1990)
- Preferential Defense Strategies, Part I : The Static Case, "Hosein, P.A.", MIT, ~, pp.MIT Technology Report LIPS-P-2002 (1990)
- 장준건, "자산기반 무기할당 문제의 선형 근사 모형", 산업경영시스템학회지, 38(3), pp.108~116 (2015), 한국산업경영시스템학회
- Johansson, F., "Evaluating the Performance of TEWA System", Ph.D., pp.2010
- Karasakal, O., "Air Defense Missile-Target Allocation for a Naval Task Group", Computers & Operations Research, 35, pp.1759~1770 (2008)
- 이대력, "효율적인 유전 알고리즘을 활용한 요격미사일 할당 및 교전 일정계획의 최적화", 산업경영시스템학회지, 39(2), pp.88~102 (2016), 한국산업경영시스템학회
- 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)
- Lloyd, S.P., "Weapon Allocation is NP-Complete", Proceedings of the IEEE Summer Computer Simulation Conference, pp.1054~1058 (1986)
- Lu, H., "An Improved Genetic Algorithm for Target Assignment Optimization of Naval Fleet Air Defense", Proceedings of the 6th World Congress on Intelligent Control & Automation, pp.3401~3405 (2006)
- Metler, W.A., "Solutions to a Probabilistic Resource Allocation Problem", Proceedings of the 28th IEEE Conference on Decision and Control, 2, pp.1606~1611 (1989)
- Murphey, R.A., "Target-based Weapon Target Assignment Problems, Nonlinear assignment Problems : Algorithms and Appli", pp.39~53 (2000), Kluwer Academic Publishers
- "Quantum Genetic Algorithm for Computer Scientists Computers" (2016)[URL]
- Roux, J.N., "Threat Evaluation and Weapon Assignment Decision Support : A Review of the State-of-the-Art, ORiON", Journal of ORSSA, 23(2), pp.151~187 (2007)
- Wacholder, E., "A Neural Network-based Optimization Algorithm for the Static Weapon-Target Assignment Problem", ORSA Journal of Computing, 1(4), pp.232~246 (1989)
- 임동순, "무장 할당문제에서 휴리스틱 방법 효율성 비교: 이행성 규칙이 성립하는 무장성능차이를 중심으로", 한국국방경영분석학회지, 36(3), pp.29~42 (2010), 한국국방경영분석학회
- Zeng, X., "Solving Weapon Target Assignment Problem using Discrete Particle Swarm Optimization", Proceedings of the 6th World Congress on Intelligent Control and Automation, pp.3562~3565 (2006)