Research Article
BibTex RIS Cite

Silah hedef atama problemi için uyarlanmış yerel arama ile yeni bir melez genetik algoritma

Year 2021, Volume: 11 Issue: 2, 348 - 356, 15.04.2021
https://doi.org/10.17714/gumusfenbil.691176

Abstract

Silah Hedef Atama Problemi, np-zor bir optimizasyon problemidir. Problemdeki amaç, hedeflere uygun silahların atanması ile toplam hedeflerin hayatta kalma değerini minimize etmektir. Doğrusal olmayan fonksiyonlar ve tam sayılı karar değişkenleri ile problem, çözüm açısından oldukça zor yapıdadır. Bu nedenle problem, çoğunlukla sezgisel yaklaşımlar ile çözülmeye çalışılmaktadır. Çalışmada, problemin çözümü için probleme özgü yerel arama prosedürüne sahip yeni bir Melez Genetik Algoritma önerilmiştir.
Literatürden elde edilen örnek problemlerin çözümüyle, önerilen Melez Genetik Algoritmanın etkinliği değerlendirilmiştir. Sonuçlar incelendiğinde geliştirilen yaklaşımın problemin çözümünde yüksek başarıma sahip olduğu görülmüştür.

References

  • Ahuja, R. K., Kumar, A., Jha, K. C. and Orlin, J. B. (2007). Exact and heuristic algorithms for the weapon-target assignment problem. Operations Research, 55(6), 1136-1146. https://doi.org/10.1287/opre.l070.0440.
  • Cetin, E. and Esen, S. T. (2006). A weapon–target assignment approach to media allocation. Applied Mathematics and Computation, 175(2), 1266-1275. https://doi.org/10.1016/j.amc.2005.08.041.
  • Chang, T., Kong, D., Hao, N., Xu, K. and Yang, G. (2018). Solving the dynamic weapon target assignment problem by an improved artificial bee colony algorithm with heuristic factor initialization. Applied Soft Computing, 70, 845-863. https://doi.org/10.1016/j.asoc.2018.06.014.
  • Fu, T. P., Liu, Y. S., and Chen, J. H. (2006). Improved genetic and ant colony optimization algorithm for regional air defense wta problem. First International Conference on Innovative Computing, Information and Control (ICICIC'06) (ss. 226-229). IEEE. https://doi.org/10.1109/ICICIC.2006.99.
  • Hocaoğlu, M. F. (2019). Weapon target assignment optimization for land based multi-air defense systems: A goal programming approach. Computers & Industrial Engineering, 128, 681-689. https://doi.org/10.1016/j.cie.2019.01.015.
  • Hoff, A., Løkketangen, A. and Mittet, I. (1996). Genetic algorithms for 0/1 multidimensional knapsack problems, Proceedings Norsk Informatikk Konferanse (NIK’96) (ss. 291-301). Brietvien.
  • Holland J, H. (1975). Adaptation İn Natural And Artificial Systems. (Vol 1). Ann Arbor: University of Michigan Press.
  • Hongtao, L. and Fengju, K. (2016). Adaptive chaos parallel clonal selection algorithm for objective optimization in WTA application. Optik-International Journal for Light and Electron Optics, 127(6), 3459-3465. https://doi.org/10.1016/j.ijleo.2015.12.122.
  • Hu, X., Luo, P., Zhang, X. and Wang, J. (2018). Improved ant colony optimization for weapon-target assignment. Mathematical Problems in Engineering, 2018, 1-14. https://doi.org/10.1155/2018/6481635.
  • Kline, A., Ahner, D. and Hill, R. (2019). The weapon-target assignment problem. Computers & Operations Research. 105, 226-236. https://doi.org/10.1016/j.cor.2018.10.015
  • Kutucu, H. ve Durgut, R. (2018). Silah hedef atama problemi için tavlama benzetimli bir hibrit yapay arı kolonisi algoritması. Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi, 22, Özel Sayı, 263-269. https://doi.org/10.19113/sdufbed.39561.
  • Lee, Z. J., Lee, C. and Su, S. F. (2002). An immunity-based ant colony optimization algorithm for solving weapon–target assignment problem. Applied Soft Computing, 2(1), 39-47. https://doi.org/10.1016/S1568-4946(02)00027-3
  • Lee, Z. J., Su, S. F. And Lee, C. Y. (2003). Efficiently solving general weapon-target assignment problem by genetic algorithms with greedy eugenics. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 33(1), 113-121. https://doi.org/10.1109/TSMCB.2003.808174.
  • Li, Y., Kou, Y., Li, Z., Xu, A. and Chang, Y. (2017). A modified pareto ant colony optimization approach to solve biobjective weapon-target assignment problem. International Journal of Aerospace Engineering, 2017. 1-14. https://doi.org/10.1155/2017/1746124
  • Li, X., Zhou, D., Pan, Q., Tang, Y. and Huang, J. (2018). Weapon-target assignment problem by multiobjective evolutionary algorithm based on decomposition. Complexity, 2018. 1-19. https://doi.org/10.1155/2018/8623051.
  • Lu, H., Zhang, H., Zhang, X. and Han, R. (2006). An improved genetic algorithm for target assignment, optimization of naval fleet air defense. 6th World Congress on Intelligent Control and Automation (ss. 3401-3405). IEEE. Dalian.
  • Manne, A. S., 1958. A target-assignment problem. Operations Research, 6(3), 346-351. https://doi.org/10.1287/opre.6.3.346.
  • Sonuc, E., Sen, B. and Bayır, S. (2017). A parallel simulated annealing algorithm for weapon-target assignment problem. International Journal of Advanced Computer Science and Applications, 8(4), 87-92.
  • Sonuç, E. (2020). A modified crow search algorithm for the weapon-target assignment problem. An International Journal of Optimization and Control: Theories & Applications (IJOCTA), 10(2), 188-197. https://doi.org/10.11121/ijocta.01.2020.00775.
  • Wang, C., Fu, G., Zhang, D., Wang, H. and Zhao, J. (2019). Genetic algorithm-based variable value control method for solving the ground target attacking weapon-target allocation problem. Mathematical Problems in Engineering, 2019, 1-9. https://doi.org/10.1155/2019/6761073
  • Yang, S., Yang, M., Wang, S. and Huang, K. (2016). Adaptive immune genetic algorithm for weapon system portfolio optimization in military big data environment. Cluster Computing, 19(3), 1359-1372. https://doi.org/10.1007/s10586-016-0596-3.
  • Yanxia, W., Longjun, Q., Zhi, G. and Lifeng, M. (2008). Weapon target assignment problem satisfying expected damage probabilities based on ant colony algorithm. Journal of Systems Engineering and Electronics, 19(5), 939-944. https://doi.org/10.1016/S1004-4132(08)60179-6.
  • Zeng, X., Zhu, Y., Nan, L., Hu, K., Niu, B. and He, X. (2006). Solving weapon-target assignment problem using discrete particle swarm optimization. 6th World Congress on Intelligent Control and Automation (ss. 3562-3565). IEEE. Dalian.
  • Zhou, Y., Li, X., Zhu, Y. and Wang, W. (2016). A discrete particle swarm optimization algorithm applied in constrained static weapon-target assignment problem. 12th World Congress on Intelligent Control and Automation (WCICA) (ss.3118-3123). IEEE. Guilin.

A new hybrid genetic algorithm with local search adapted for weapon target assignment problem

Year 2021, Volume: 11 Issue: 2, 348 - 356, 15.04.2021
https://doi.org/10.17714/gumusfenbil.691176

Abstract

The Weapon Target Assignment Problem is a np-hard optimization problem. The aim of the problem is to minimize the survival value of total targets by assigning appropriate weapons to the targets. With non-linear functions and integer decision variables, the problem is quite difficult in terms of solution. Therefore, the problem is mostly tried to be solved by heuristic approaches. In the study, a new Hybrid Genetic Algorithm with a problem-specific local search procedure is proposed to solve the problem. The efficiency of the proposed Hybrid Genetic Algorithm was evaluated by solving the sample problems obtained from the literature. When the results were examined, it was seen that the approach developed had high success in solving the problem.

References

  • Ahuja, R. K., Kumar, A., Jha, K. C. and Orlin, J. B. (2007). Exact and heuristic algorithms for the weapon-target assignment problem. Operations Research, 55(6), 1136-1146. https://doi.org/10.1287/opre.l070.0440.
  • Cetin, E. and Esen, S. T. (2006). A weapon–target assignment approach to media allocation. Applied Mathematics and Computation, 175(2), 1266-1275. https://doi.org/10.1016/j.amc.2005.08.041.
  • Chang, T., Kong, D., Hao, N., Xu, K. and Yang, G. (2018). Solving the dynamic weapon target assignment problem by an improved artificial bee colony algorithm with heuristic factor initialization. Applied Soft Computing, 70, 845-863. https://doi.org/10.1016/j.asoc.2018.06.014.
  • Fu, T. P., Liu, Y. S., and Chen, J. H. (2006). Improved genetic and ant colony optimization algorithm for regional air defense wta problem. First International Conference on Innovative Computing, Information and Control (ICICIC'06) (ss. 226-229). IEEE. https://doi.org/10.1109/ICICIC.2006.99.
  • Hocaoğlu, M. F. (2019). Weapon target assignment optimization for land based multi-air defense systems: A goal programming approach. Computers & Industrial Engineering, 128, 681-689. https://doi.org/10.1016/j.cie.2019.01.015.
  • Hoff, A., Løkketangen, A. and Mittet, I. (1996). Genetic algorithms for 0/1 multidimensional knapsack problems, Proceedings Norsk Informatikk Konferanse (NIK’96) (ss. 291-301). Brietvien.
  • Holland J, H. (1975). Adaptation İn Natural And Artificial Systems. (Vol 1). Ann Arbor: University of Michigan Press.
  • Hongtao, L. and Fengju, K. (2016). Adaptive chaos parallel clonal selection algorithm for objective optimization in WTA application. Optik-International Journal for Light and Electron Optics, 127(6), 3459-3465. https://doi.org/10.1016/j.ijleo.2015.12.122.
  • Hu, X., Luo, P., Zhang, X. and Wang, J. (2018). Improved ant colony optimization for weapon-target assignment. Mathematical Problems in Engineering, 2018, 1-14. https://doi.org/10.1155/2018/6481635.
  • Kline, A., Ahner, D. and Hill, R. (2019). The weapon-target assignment problem. Computers & Operations Research. 105, 226-236. https://doi.org/10.1016/j.cor.2018.10.015
  • Kutucu, H. ve Durgut, R. (2018). Silah hedef atama problemi için tavlama benzetimli bir hibrit yapay arı kolonisi algoritması. Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi, 22, Özel Sayı, 263-269. https://doi.org/10.19113/sdufbed.39561.
  • Lee, Z. J., Lee, C. and Su, S. F. (2002). An immunity-based ant colony optimization algorithm for solving weapon–target assignment problem. Applied Soft Computing, 2(1), 39-47. https://doi.org/10.1016/S1568-4946(02)00027-3
  • Lee, Z. J., Su, S. F. And Lee, C. Y. (2003). Efficiently solving general weapon-target assignment problem by genetic algorithms with greedy eugenics. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 33(1), 113-121. https://doi.org/10.1109/TSMCB.2003.808174.
  • Li, Y., Kou, Y., Li, Z., Xu, A. and Chang, Y. (2017). A modified pareto ant colony optimization approach to solve biobjective weapon-target assignment problem. International Journal of Aerospace Engineering, 2017. 1-14. https://doi.org/10.1155/2017/1746124
  • Li, X., Zhou, D., Pan, Q., Tang, Y. and Huang, J. (2018). Weapon-target assignment problem by multiobjective evolutionary algorithm based on decomposition. Complexity, 2018. 1-19. https://doi.org/10.1155/2018/8623051.
  • Lu, H., Zhang, H., Zhang, X. and Han, R. (2006). An improved genetic algorithm for target assignment, optimization of naval fleet air defense. 6th World Congress on Intelligent Control and Automation (ss. 3401-3405). IEEE. Dalian.
  • Manne, A. S., 1958. A target-assignment problem. Operations Research, 6(3), 346-351. https://doi.org/10.1287/opre.6.3.346.
  • Sonuc, E., Sen, B. and Bayır, S. (2017). A parallel simulated annealing algorithm for weapon-target assignment problem. International Journal of Advanced Computer Science and Applications, 8(4), 87-92.
  • Sonuç, E. (2020). A modified crow search algorithm for the weapon-target assignment problem. An International Journal of Optimization and Control: Theories & Applications (IJOCTA), 10(2), 188-197. https://doi.org/10.11121/ijocta.01.2020.00775.
  • Wang, C., Fu, G., Zhang, D., Wang, H. and Zhao, J. (2019). Genetic algorithm-based variable value control method for solving the ground target attacking weapon-target allocation problem. Mathematical Problems in Engineering, 2019, 1-9. https://doi.org/10.1155/2019/6761073
  • Yang, S., Yang, M., Wang, S. and Huang, K. (2016). Adaptive immune genetic algorithm for weapon system portfolio optimization in military big data environment. Cluster Computing, 19(3), 1359-1372. https://doi.org/10.1007/s10586-016-0596-3.
  • Yanxia, W., Longjun, Q., Zhi, G. and Lifeng, M. (2008). Weapon target assignment problem satisfying expected damage probabilities based on ant colony algorithm. Journal of Systems Engineering and Electronics, 19(5), 939-944. https://doi.org/10.1016/S1004-4132(08)60179-6.
  • Zeng, X., Zhu, Y., Nan, L., Hu, K., Niu, B. and He, X. (2006). Solving weapon-target assignment problem using discrete particle swarm optimization. 6th World Congress on Intelligent Control and Automation (ss. 3562-3565). IEEE. Dalian.
  • Zhou, Y., Li, X., Zhu, Y. and Wang, W. (2016). A discrete particle swarm optimization algorithm applied in constrained static weapon-target assignment problem. 12th World Congress on Intelligent Control and Automation (WCICA) (ss.3118-3123). IEEE. Guilin.
There are 24 citations in total.

Details

Primary Language Turkish
Subjects Engineering
Journal Section Articles
Authors

Osman Pala 0000-0002-2634-2653

Publication Date April 15, 2021
Submission Date February 19, 2020
Acceptance Date February 9, 2021
Published in Issue Year 2021 Volume: 11 Issue: 2

Cite

APA Pala, O. (2021). Silah hedef atama problemi için uyarlanmış yerel arama ile yeni bir melez genetik algoritma. Gümüşhane Üniversitesi Fen Bilimleri Dergisi, 11(2), 348-356. https://doi.org/10.17714/gumusfenbil.691176