A novel strategy to avoid local optimum: Army-inspired genetic algorithm (AIGA)

Abstract

Objective functions of which an analytical solution is very difficult or time-consuming are solved using stochastic optimization algorithms. Those optimization algorithms compute an approximate solution for objective functions. For a specific search space, the objective function might have one or more local optima along with the global optimum. When a comparison is made among the algorithms, one optimization algorithm could be more effective than others in finding a solution for certain objective functions. The most important factors affecting the success of optimization algorithms are the greatness of search space and the complexity of the objective function. Reaching the global optimum in huge search spaces is very difficult. In complex objective functions that have many local optima or where the differences between global optimum and local optima are very small, the probability of trapping into the local optimum is high. Existing optimization algorithms could be improved using the search space scanned more successfully to give a better performance. To achieve this aim, we present a novel algorithm, called Army-Inspired Genetic Algorithm (AIGA), which is inspired from military movement. The presented algorithm, apart from other optimization algorithms, searches global optima effectively by dividing the entire search area into territories instead of searching in one piece. Thus, the probability of getting trapped in a local optimum reduces and the probability of finding the global optimum increases. The presented algorithm was tested on well-known benchmark problems. The results shows that AIGA is more efficient algorithm in finding the global optimum than traditional algorithms.

Keywords

• Stochastic optimization
• Evolutionary algorithm
• Genetic algorithm
• Army-inspired strategy
• Local optima

References

1. Atilgan, E., & Hu, J. (2018). First-principle-based computational doping of SrTiO 3 using combinatorial genetic algorithms. Bulletin of Materials Science, 41(1), 1. https://doi.org/10.1007/s12034-017-1515-9
2. S., V. C. S., & S., A. H. (2022). Nature inspired meta heuristic algorithms for optimization problems. Computing, 104(2), 251-269. https://doi.org/10.1007/s00607-021-00955-5
3. Fister Jr, I., Yang, X. S., Fister, I., Brest, J., & Fister, D. (2013). A brief review of nature-inspired algorithms for optimization. Neural and Evolutionary Computing, 80(3), 116-122. https://doi.org/10.48550/arXiv.1307.4186
4. Darwish, A. (2018). Bio-inspired computing: Algorithms review, deep analysis, and the scope of applications. Future Computing and Informatics Journal, 3(2), 231-246. https://doi.org/10.1016/j.fcij.2018.06.001
5. Yang, X. S. (2020). Nature-inspired optimization algorithms: Challenges and open problems. Journal of Computational Science, 46, 101104. https://doi.org/10.1016/j.jocs.2020.101104
6. Stork, J., Eiben, A. E., & Bartz-Beielstein, T. (2022). A new taxonomy of global optimization algorithms. Natural Computing, 21(2), 219-242. https://doi.org/10.1007/s11047-020-09820-4
7. Mirjalili, S., Mirjalili, S. M., & Lewis, A. (2014). Grey wolf optimizer. Advances in Engineering Software, 69, 46-61. https://doi.org/10.1016/j.advengsoft.2013.12.007
8. Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. In Proceedings of ICNN'95-International Conference on Neural Networks, 4, 1942-1948. https://doi.org/10.1109/ICNN.1995.488968

9. Yang, X. S. (2010). Nature-inspired metaheuristic algorithms. Luniver press.
10. Yang, X. S., & Hossein Gandomi, A. (2012). Bat algorithm: a novel approach for global engineering optimization. Engineering Computations, 29(5), 464-483. https://doi.org/10.1108/02644401211235834
11. Askarzadeh, A. (2016). A novel metaheuristic method for solving constrained engineering optimization problems: crow search algorithm. Computers & Structures, 169, 1-12. https://doi.org/10.1016/j.compstruc.2016.03.001
12. Yang, X. S., & Deb, S. (2009). Cuckoo search via Lévy flights. In 2009 World Congress on Nature & Biologically Inspired Computing (NaBIC), 210-214. https://doi.org/10.1109/NABIC.2009.5393690
13. Chechkin, A. V., Gonchar, V. Y., Klafter, J., & Metzler, R. (2006). Fundamentals of Lévy flight processes. Fractals, Diffusion, and Relaxation in Disordered Complex Systems: Advances in Chemical Physics, Part B, 439-496.
14. Yang, X. S. (2012). Flower pollination algorithm for global optimization. In International Conference on Unconventional Computing and Natural Computation, 7445, 240-249. https://doi.org/10.1007/978-3-642-32894-7_27
15. Rocha, M., & Neves, J. (1999). Preventing premature convergence to local optima in genetic algorithms via random offspring generation. In Multiple Approaches to Intelligent Systems: 12th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems IEA/AIE-99, Cairo, Egypt, May 31-June 3, 1999. Proceedings 12, 127-136. https://doi.org/10.1007/978-3-540-48765-4_16
16. Dang, D. C., Friedrich, T., Kötzing, T., Krejca, M. S., Lehre, P. K., Oliveto, P. S., ... & Sutton, A. M. (2017). Escaping local optima using crossover with emergent diversity. IEEE Transactions on Evolutionary Computation, 22(3), 484-497. https://doi.org/10.1109/TEVC.2017.2724201
17. Doerr, B. (2020). Does comma selection help to cope with local optima?. In Proceedings of the 2020 Genetic and Evolutionary Computation Conference, 1304-1313. https://doi.org/10.1145/3377930.3389823
18. Oliveto, P. S., Paixão, T., Pérez Heredia, J., Sudholt, D., & Trubenová, B. (2018). How to escape local optima in black box optimisation: when non-elitism outperforms elitism. Algorithmica, 80, 1604-1633. https://doi.org/10.1007/s00453-017-0369-2
19. Sharma, P., & Raju, S. (2024). Metaheuristic optimization algorithms: A comprehensive overview and classification of benchmark test functions. Soft Computing, 28(4), 3123-3186. https://doi.org/10.1007/s00500-023-09276-5
20. Cheng, R., Li, M., Tian, Y., Xiang, X., Zhang, X., Yang, S., ... & Yao, X. (2018). Benchmark functions for the cec'2018 competition on many-objective optimization.
21. Deb, L. (1993). Multimodal deceptive functions. Complex Systems, 7, 131-153.
22. Kilinc, M., & Caicedo, J. M. (2019). Finding plausible optimal solutions in engineering problems using an adaptive genetic algorithm. Advances in Civil Engineering, 2019(1), 7475156. https://doi.org/10.1155/2019/7475156