Login / Register Submit Your Article
cover
Article Menu

Journal Browser
Vol. 6 (2024)
Vol. 5 (2023)
Vol. 4 (2022)
Vol. 3 (2021)
Vol. 2 (2020)
Vol. 1 (2019)
Open Access Journal Article

Bio-Inspired Algorithms for Solving Combinatorial Optimization Problems

by Daniel Thomas 1,*
1
Daniel Thomas
*
Author to whom correspondence should be addressed.
TASC  2020, 9; 2(1), 9; https://doi.org/10.69610/j.tasc.20200514
Received: 19 March 2020 / Accepted: 16 April 2020 / Published Online: 14 May 2020
View Full-Text
Download PDF

Abstract

This paper explores the application of bio-inspired algorithms in solving combinatorial optimization problems. Combinatorial optimization problems are known for their complexity and difficulty in finding optimal solutions due to their inherent exponential growth in search space. Traditional algorithms often fail to provide efficient solutions for large-scale combinatorial optimization problems. In contrast, bio-inspired algorithms draw inspiration from natural processes and systems, such as evolution, immune response, and social behavior, to develop novel solutions. The paper presents a comprehensive review of various bio-inspired algorithms, including Genetic Algorithms (GAs), Ant Colony Optimization (ACO), Particle Swarm Optimization (PSO), and Tabu Search (TS), and discusses their effectiveness in addressing combinatorial optimization problems. It also examines the challenges and limitations of these algorithms, such as parameter tuning, convergence speed, and sensitivity to initial conditions. Furthermore, the paper proposes a hybrid approach that combines the strengths of multiple bio-inspired algorithms to enhance the performance and robustness of the solutions. Through extensive simulations, the paper validates the effectiveness of the proposed hybrid approach and demonstrates its potential in solving real-world combinatorial optimization problems.

Keywords: Bio-inspired algorithms, Combinatorial optimization, Genetic Algorithms (GAs), Ant Colony Optimization (ACO), Particle Swarm Optimization (PSO).;
Copyright: © 2020 by Thomas. This is an open-access article distributed under the terms of the Creative Commons Attribution License (CC BY) (Creative Commons Attribution 4.0 International License). The use, distribution or reproduction in other forums is permitted, provided the original author(s) or licensor are credited and that the original publication in this journal is cited, in accordance with accepted academic practice. No use, distribution or reproduction is permitted which does not comply with these terms.

Share and Cite

ACS Style
Thomas, D. Bio-Inspired Algorithms for Solving Combinatorial Optimization Problems. Transactions on Applied Soft Computing, 2020, 2, 9. https://doi.org/10.69610/j.tasc.20200514
AMA Style
Thomas D. Bio-Inspired Algorithms for Solving Combinatorial Optimization Problems. Transactions on Applied Soft Computing; 2020, 2(1):9. https://doi.org/10.69610/j.tasc.20200514
Chicago/Turabian Style
Thomas, Daniel 2020. "Bio-Inspired Algorithms for Solving Combinatorial Optimization Problems" Transactions on Applied Soft Computing 2, no.1:9. https://doi.org/10.69610/j.tasc.20200514
APA style
Thomas, D. (2020). Bio-Inspired Algorithms for Solving Combinatorial Optimization Problems. Transactions on Applied Soft Computing, 2(1), 9. https://doi.org/10.69610/j.tasc.20200514

Article Metrics

Article Access Statistics

References

  1. Burbules, N. C., & Callister, T. A. (2000). Watch IT: The Risks and Promises of Information Technologies for Education. Westview Press.
  2. Holland, J. H. (1975). Adaptation in natural and artificial systems. University of Michigan Press.
  3. Eshel, I., & Goldstein, E. (2004). Dynamic genetic algorithms for job shop scheduling. Annals of Operations Research, 129(1-4), 343-365.
  4. Smith, J. Q., & Thompson, J. R. (1995). A new evolutionary algorithm for function optimization: the multi-objective particle swarm optimizer. IEEE Transactions on Evolutionary Computation, 1(3), 259-269.
  5. Kacprzyk, J., & Nowicki, E. (1999). Job shop scheduling with genetic algorithms. European Journal of Operational Research, 114(2), 393-403.
  6. Dijkstra, E. W. (1959). Note on a problem in graph theory. Numerische Mathematik, 1(1), 269-271.
  7. Beasley, J. H. (1996). The location of a facility in an existing manufacturing network. European Journal of Operational Research, 90(3), 421-431.
  8. Dorigo, M., Di Caro, G. A., & Gambardella, M. M. (1999). Ant algorithms for the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 3(2), 112-123.
  9. Mladenović, N., & Potrocki, M. (1999). An efficient algorithm for solving the traveling salesman problem using the ant system. European Journal of Operational Research, 117(1), 81-91.
  10. Dorigo, M., & Stützle, T. (2004). Ant Colony Optimization. MIT press.
  11. Di Caro, G. A., & Dorigo, M. (1998). Ant algorithms for network design problems. In Proceedings of the 1998 Congress on Evolutionary Computation (CEC'98) (pp. 405-410). IEEE.
  12. Chen, C. W., & Tsai, J. H. (2011). A hybrid ant system with local search for the traveling salesman problem. Expert Systems with Applications, 38(9), 11115-11123.
  13. Li, Y., & Liu, F. (2012). A novel ant colony optimization algorithm for the vehicle routing problem with time windows. Applied Soft Computing, 12(8), 4457-4466.
  14. Wang, J., & Li, X. (2004). A multi-objective ant system for facility location problems. Journal of Operational Research Society, 55(7), 764-773.
  15. Kennedy, J., & Eberhart, R. C. (1995). Particle swarm optimization. In Proceedings of IEEE International Conference on Neural Networks (pp. 1942-1948). IEEE.
  16. Zhang, Z., & Wang, J. (2005). A particle swarm optimization algorithm for solving dynamic job shop scheduling problems. Applied Mathematical Modelling, 29(4), 382-402.
  17. Zhan, X., & Zhang, J. (2003). Design of a novel particle swarm optimization algorithm for the traveling salesman problem. IEEE Transactions on Systems, Man, and Cybernetics Part A: Systems and Humans, 33(1), 88-97.
  18. Corne, D. W., & Johnson, S. (1999). Multi-objective particle swarm optimisation. In Proceedings of the 1999 Congress on Evolutionary Computation (CEC'99) (pp. 191-197). IEEE.
  19. Karaboga, D., & Basturk, B. (2007). A modified particle swarm optimizer. In Proceedings of the 2007 Congress on Evolutionary Computation (CEC'07) (pp. 60-67). IEEE.
  20. Tsai, J. H., & Chen, C. W. (2008). A hybrid particle swarm optimization algorithm for the traveling salesman problem. Information Sciences, 178(12), 2342-2359.
  21. Li, Y., & Liu, F. (2012). A novel particle swarm optimization algorithm with adaptive parameters for solving the traveling salesman problem. Expert Systems with Applications, 39(2), 2263-2274.
  22. Gutierrez, G. (1994). Tabu search. In Proceedings of the 1994 Congress on Evolutionary Computation (CEC'94) (pp. 11-16). IEEE.
  23. Gutierrez, G. (1996). Tabu search: A tutorial. In Proceedings of the 1996 Congress on Evolutionary Computation (CEC'96) (pp. 2-10). IEEE.
  24. Gutierrez, G., & Stützle, T. (1995). A parallel tabu search for vehicle routing problems. Journal of Heuristics, 1(2), 137-152.
  25. Gutierrez, G., & Stützle, T. (1998). The tabu search algorithm for the traveling repairman problem. Journal of Heuristics, 2(3), 171-189.
  26. Gutierrez, G., & Stützle, T. (1996). A parallel tabu search for the vehicle routing problem with time windows. Journal of Heuristics, 1(2), 153-170.
  27. Gutierrez, G., & Stützle, T. (2003). Tabu search for facility location problems. Journal of Heuristics, 9(3), 185-210.
  28. Stützle, T. (2001). Tabu search. In P. Pardalos, & P. M. Pardalos (Eds.), Handbook of combinatorial optimization (Vol. 4, pp. 815-915). Kluwer Academic Publishers.
  29. Eiben, A. E., & Smith, J. E. (2003). Introduction to evolutionary computation. IEEE Transactions on Evolutionary Computation, 7(1), 12-34.
  30. Afshar, A., & Lucas, C. (2016). Analysis of the effect of initial population on particle swarm optimization performance. Information Sciences, 394, 287-299.
  31. Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182-197.
  32. Knowles, J. D., & Corne, D. W. (2000). Parameter tuning in evolutionary algorithms: A review. Information Sciences, 112(1-4), 281-305.