Iterated Local Search in Combinatorial Optimization Problem

Authors

  • Mehedi Hasan  Computer Science & Engineering, Stamford University Bangladesh, Dhaka, Bangladesh

DOI:

https://doi.org//10.32628/IJSRSET196455

Keywords:

Iterated Local Search, WTA, Heuristic Solution, Combinatorial Optimization, Integer Programming

Abstract

Iterated local search (ILS) is a very powerful optimization method for continuous-valued numerical optimization. However, ILS has seldom been used to solve combinatorial integer-valued optimization problems. In this paper, the iterated local search (ILS) with random restarts algorithm is applied to solve combinatorial optimization problems, e.g., the classical weapon-target allocation (WTA) problem which arises from the military operations research. The mathematical model of the WTA problem is explained in detail. Then the idea of ILS with random restarts is explained. A comparison of the algorithm with several existing search approaches shows that the ILS outperforms its competitors on the tested WTA problem.

References

  1. A. S. Manne, A target-assignment problem, Operations Research, 6(1): 346-351, 1958.
  2. J. Chen, B. Xin, Z. H. Peng, et al, Evolutionary decision-makings for dynamic weapon-target assignment problem, Science in China Series F: Information Sciences, 52(11): 2006–2018, 2009.
  3. B. Xin, J. Chen, and Z. H. Peng, et al. An efficient rule-based constructive heuristic to solve dynamic weapon-target assignment problem, IEEE Trans. on Systems, Man, and Cybernetics, Part A: Systems and Humans, 41(3): 598-606, 2011.
  4. S. P. Lloyd and H. S. Witsenhausen, “Weapon allocation is NP-Complete”, in Proceedings of the IEEE Summer Simulation Conference, 1986: 1054-1058.
  5. R. K. Ahuja, A. Kumar, K. Jha and J. B. Orlin, Exact and heuristic methods for the weapon target assignment problem: MIT Sloan Working Paper No: 4464-03, 2003.
  6. J. M. Rosenberger and A. Yucel, “The generalized weapon target assignment problem,” 10th Int. Conf. Com. and Cont. Res. and Techn. Symp, 2005.
  7. Z-J. Lee, S-F. Su and C-Y Lee, “Efficiently solving general weapon-target assignment problem by genetic algorithms with genetic eugenics,” IEEE Trans. Syst. Man. Cybern., vol. 33, 2003.
  8. A. S. Manne, “A target-assignment problem,” Operations Research, vol. 6, pp. 346–351, 1958.
  9. R. H. Day, “Allocating weapons to target complexes by means of nonlinear programming,” Operations Research, vol. 14, no. 6, pp. 992–1013, 1966.
  10. P. A. Hosein and M. Athans, Preferential Defense Strategies. Part I: The Static Case, MIT Laboratory for Information and Decision Systems, Cambridge, Mass, USA, 1990.
  11. Z. R. Bogdanowicz, A. Tolano, K. Patel, and N. P. Coleman, “Optimization of weapon-target pairings based on kill probabilities,” IEEE Transactions on Cybernetics, vol. 43, no. 6, pp. 1835–1844, 2013.
  12.  S. Chen, J. He, and H. Liu, “Realization and simulation of parallel ant colony algorithm to solve WTA problem,” in Proceedings of the International Conference on Systems and Informatics (ICSAI ’12), May 2012.
  13. A.-G. Fei, L.-Y. Zhang, and Q.-J. Ding, “Multi-aircraft cooperative free assignment based on auction algorithm,” Systems Engineering & Electronics, vol. 34, no. 9, pp. 1829–1833, 2012.
  14. M.-Z. Lee, “Constrained weapon–target assignment: enhanced very large-scale neighborhood search algorithm,” IEEE Transactions on Systems, Man, and Cybernetics Part A: Systems and Humans, vol. 40, no. 1, pp. 198–204, 2010.
  15. D. G. Galati and M. A. Simaan, “E?ectiveness of the Nash strategies in competitive multi-team target assignment problems,” IEEE Transactions on Aerospace & Electronics System, vol. 43, no. 1, pp. 126–134, 2007.
  16. Z.-J. Lee and W.-L. Lee, “A Hybrid search algorithm of ant colony optimization and genetic algorithm applied to weapon-target assignment problems,” in Intelligent Data Engineering and Automated Learning, vol. 2690 of Lecture Notes in Computer Science, pp. 278–285, Springer, Berlin, Germany, 2003.
  17. Y. Li and Y. Dong, “Weapon-target assignment based on simulated annealing and discrete particle swarm optimization in cooperative air combat,” Acta Aeronautica et Astronautica Sinica, vol. 31, no. 3, pp. 626–631, 2010.
  18. H.-D. Chen, S.-Z. Wang, and H.-Y. Wang, “Research of firepower assignment with multi-launcher and multi-weapon based on a hybrid particle swarm optimization,” Systems Engineering & Electronics, vol. 30, no. 5, pp. 880–883, 2008.
  19. X. Liu, Z. Liu, W.-S. Hou, and J.-H. Xu, “Improved MOPSO algorithm for multi-objective programming model of weapon-target assignment,” Systems Engineering & Electronics, vol. 35, no. 2, pp. 326–330, 2013.
  20. Y. Zhang, R.-N. Yang, J.-L. Zuo, and X.-N. Jing, “Weapon-target assignment based on decomposition-based evolutionary multi-objective optimization algorithms,” Systems Engineering & Electronics, vol. 36, no. 12, pp. 2435–2441, 2014.
  21. J. Li, J. Chen, B. Xin, and L. Dou, “Solving multi-objective multistage weapon target assignment problem via adaptive NSGAII and adaptive MOEA/D: A Comparison Study,” in Proceedings of the IEEE Congress on Evolutionary Computation (CEC ’15), pp. 3132–3139, May 2015.
  22. R. Battiti, M. Brunato, and F. Mascia, “Reactive search and intelligent optimization,” Operations Research, vol. 45, no. 1, pp.
  23. R. Battiti and G. Tecchiolli, “The reactive tabu search,” ORSA Journal on Computing, vol. 6, no. 2, pp. 126–140, 1994.
  24. M. Dorigo and L. M. Gambardella, “Ant colony system: a cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, pp. 53–66, 1997.
  25. T. Stutzle and H. H. Hoos, “Max-min ant system,” ¨ Future Generation Computer Systems, vol. 16, no. 9, pp. 889–914, 1999.
  26. S. Iredi, D. Merkle, and M. Middendorf, “Bi-criterion optimization with multi colony ant algorithms,” in Evolutionary Multi-criterion Optimization: First International Conference, EMO 2001 Zurich, Switzerland, March 7–9, 2001 Proceedings, vol. 1993 of Lecture Notes in Computer Science, pp. 359–372, Springer, Berlin, Germany, 2001.
  27. D. Merkle, M. Middendorf, and H. Schmeck, “Ant colony optimization for resource-constrained project scheduling,” IEEE
  28. Transactions on Evolutionary Computation, vol. 6, no. 4, pp. 333–346, 2002.
  29. J. E. Bell and P. R. McMullen, “Ant colony optimization techniques for the vehicle routing problem,” Advanced Engineering Informatics, vol. 18, no. 1, pp. 41–48, 2004.
  30. K. Doerner, W. J. Gutjahr, R. F. Hartl, C. Strauss, and C. Stummer, “Pareto ant colony optimization: a metaheuristic approach to multi-objective portfolio selection,” Annals of Operations Research, vol. 131, pp. 79–99, 2004.
  31. P. Cardoso, M. Jesus, and A. Marquez, “MONACO-multi-objective network optimization based on an ACO,” in Proceedings of the X Encuentros de Geometr?a Computacional, vol. 1, no. 1, pp. 1–10, Seville, Spain, 2013.
  32. P. R. McMullen, “An ant colony optimization approach to addressing a JIT sequencing problem with multiple objectives,” Artificial Intelligence in Engineering, vol. 15, no. 3, pp. 309–317,
  33. T. Stutzle and M. Dorigo, “ACO algorithms for the quadratic assignment problem,” New Ideas in Optimization, vol. 3, no. 1, pp. 33–50, 2000.
  34. A. Baykasoglu, T. Dereli, and I. Sabuncu, “A multiple objective and colony ant colony optimization approach to assembly line balancing problems,” in Proceedings of the 35th International Conference on Computers and Industrial Engineering, pp. 263– 268, IEEE, Istanbul, Turkey, June 2005.
  35. S. Wei-dong, Z. Cheng-wang and H. Jun-xiu, “Improved Differential Evolution Algorithm for Solving WTA Problem,” International Conference on Computer and Automation Engineering (ICCAE 2011), IPCSIT vol. 44, 2012.

International Journal of Scientific Research in Science, Engineering and Technology

Downloads

Published

2019-08-30

Issue

Volume 6, Issue 4, July-August-2019

Section

Research Articles

License

Copyright (c) IJSRSET

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

How to Cite

[1]
Mehedi Hasan, " Iterated Local Search in Combinatorial Optimization Problem, International Journal of Scientific Research in Science, Engineering and Technology(IJSRSET), Print ISSN : 2395-1990, Online ISSN : 2394-4099, Volume 6, Issue 4, pp.405-412, July-August-2019. Available at doi : https://doi.org/10.32628/IJSRSET196455