Transactions on Machine Intelligence

Transactions on Machine Intelligence

A Niching Ring Topology Genetic Algorithm for Multimodal Optimization

Document Type : Original Article

Author
Department of Computer Engineering, Esfarayen University of Technology, Esfarayen, North Khorasan, Iran
Abstract
Multimodal optimization represents a significant and ongoing challenge within the broader field of optimization, particularly due to the presence of multiple global and local optima within a complex search space. Unlike unimodal problems that focus on a single optimal solution, multimodal problems require algorithms to locate and maintain a diverse set of high-quality solutions across various regions of the landscape. This characteristic reflects many real-world scenarios, such as engineering design, robotics, and bioinformatics, where multiple viable solutions can coexist. Traditional optimization algorithms often struggle in such settings, as they tend to converge prematurely to a single optimum and lack mechanisms for diversity preservation. In this paper, we propose a novel niching-based Genetic Algorithm (GA) tailored specifically for multimodal optimization problems. The proposed algorithm dynamically forms niches based on the spatial distribution of individuals in the population, enabling the preservation and evolution of multiple optima simultaneously. To ensure that niches are maintained effectively, the genetic operators are strategically modified to minimize disruption to niche structure during crossover and mutation. Extensive experiments conducted on standard multimodal benchmark functions demonstrate that our approach consistently outperforms existing methods in both convergence speed and solution diversity. The results validate the algorithm’s robustness and its practical potential in solving complex multimodal problems.
Keywords

  • [1] Zhang, Y., Li, X., & Yang, S. (2022). Advancements in Evolutionary Multimodal Optimization: A Comprehensive Review. IEEE Transactions on Evolutionary Computation, 26(1), 78-92.
  • [2] Gupta, A., Sinha, A., & Deb, K. (2021). A Hybrid Swarm Intelligence Approach for Multimodal Optimization. Expert Systems with Applications, 176, 114787.
  • [3] Wang, Z., Zheng, Q., & Zhang, W. (2020). Machine Learning Approaches for Multimodal Optimization: A Comparative Study. Information Sciences, 514, 84-101.
  • [4] Li, J., Gong, W., & Zhang, Q. (2022). Dynamic Multimodal Optimization: Challenges and Opportunities. Soft Computing, 26(5), 3769-3786.
  • [5] Li, X. (2010). Niching without niching parameters: particle swarm optimization using a ring topology. IEEE Transactions on Evolutionary Computation, 14(1), 150-169. https://doi.org/10.1109/TEVC.2009.2026270
  • [6] De Jong, K. A. (1975). Analysis of the behavior of a class of genetic adaptive systems.
  • [7] Qu, B. Y., Suganthan, P. N., & Liang, J. J. (2012). Differential evolution with neighborhood mutation for multimodal optimization. IEEE transactions on evolutionary computation, 16(5), 601-614. https://doi.org/10.1109/TEVC.2011.2161873
  • [8] Mahfoud, S. W. (1995). Niching methods for genetic algorithms. Urbana, 51(95001), 62-94.
  • [9] Wong, K. C., Wu, C. H., Mok, R. K., Peng, C., & Zhang, Z. (2012). Evolutionary multimodal optimization using the principle of locality. Information Sciences, 194, 138-170. https://doi.org/10.1016/j.ins.2011.12.016
  • Harik, G. R. (1995). Finding Multimodal Solutions Using Restricted Tournament Selection. In ICGA (pp. 24-31).
  • Yazdani, S., Nezamabadi-pour, H., & Kamyab, S. (2014). A gravitational search algorithm for multimodal optimization. Swarm and Evolutionary Computation, 14, 1-14. https://doi.org/10.1016/j.swevo.2013.08.001
  • Li, X. (2007). A multimodal particle swarm optimizer based on fitness Euclidean-distance ratio. In Proceedings of the 9th annual conference on Genetic and evolutionary computation (pp. 78-85). ACM. https://doi.org/10.1145/1276958.1276970
  • Liang, J. J., Qu, B. Y., Mao, X. B., Niu, B., & Wang, D. Y. (2014). Differential evolution based on fitness Euclidean-distance ratio for multimodal optimization. Neurocomputing, 137, 252-260. https://doi.org/10.1016/j.neucom.2013.03.069
  • Das, S., Maity, S., Qu, B. Y., & Suganthan, P. N. (2011). Real-parameter evolutionary multimodal optimization-A survey of the state-of-the-art. Swarm and Evolutionary Computation, 1(2), 71-88. https://doi.org/10.1016/j.swevo.2011.05.005
  • Li, J. P., Balazs, M. E., Parks, G. T., & Clarkson, P. J. (2002). A species conserving genetic algorithm for multimodal function optimization. Evolutionary computation, 10(3), 207-234. https://doi.org/10.1162/106365602760234081
  • Li, X. (2004). Adaptively choosing neighborhood bests using species in a particle swarm optimizer for multimodal function optimization. In Genetic and Evolutionary Computation Conference (pp. 105-116). Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24854-5_10
  • Parrott, D., & Li, X. (2006). Locating and tracking multiple dynamic optima by a particle swarm model using speciation. IEEE Transactions on Evolutionary Computation, 10(4), 440-458. https://doi.org/10.1109/TEVC.2005.859468
  • Li, L., & Tang, K. (2015). History-based topological speciation for multimodal optimization. IEEE Transactions on Evolutionary Computation, 19(1), 136-150. https://doi.org/10.1109/TEVC.2014.2306677
  • Wang, H., Wang, W., & Wu, Z. (2013). Particle swarm optimization with adaptive mutation for multimodal optimization. Applied Mathematics and Computation, 221, 296-305. https://doi.org/10.1016/j.amc.2013.06.074
  • Qu, B. Y., Suganthan, P. N., & Das, S. (2013). A distance-based locally informed particle swarm model for multimodal optimization. IEEE Transactions on Evolutionary Computation : A Publication of the IEEE Neural Networks Council, 17(3), 387–402. doi:10.1109/tevc.2012.2203138
  • Li, S., Tan, M., Tsang, I. W., & Kwok, J. T. Y. (2011). A hybrid PSO-BFGS strategy for global optimization of multimodal functions. IEEE Transactions on Systems, Man, and Cybernetics, 41(4), 1003–1014.
  • Vitela, J. E., & Castaños, O. (2012). A sequential niching memetic algorithm for continuous multimodal function optimization. Applied Mathematics and Computation, 218(17), 8242–8259. doi:10.1016/j.amc.2011.05.051
Volume 5, Issue 2
Spring 2022
Pages 115-121

  • Receive Date 17 March 2022
  • Revise Date 26 May 2022
  • Accept Date 23 June 2022