Abstract
Genetic algorithm is an exploratory method inspired by Darwin's theory of natural evolution. This algorithm reflects the natural selection process in which suitable individuals are selected for reproduction to produce the offspring of the next generation. The genetic algorithm uses three main operators, namely selection, crossover, and mutation, each of which is involved in producing better strings or chromosomes. Among the three main operators, the mutation operator is one of the most important operators to achieve the optimal solution. The mutation operator is an intelligent mechanism for local search in the problem-solving search space. Mutations are therefore used to maintain population diversity and prevent premature convergence in the problem-solving process. In this study, to improve the genetic algorithm, a new type of mutation is introduced, which is called the Zigzag mutation. This mutation, by observance the zigzag pattern and making sudden and noticeable mutants in the gene compared to the existing mutations, make the local search in the problem space more efficient and helps to improve the genetic algorithm. In this paper, the proposed Zigzag mutation-based genetic algorithm is compared with six other genetic algorithms with different mutations in similar competitive conditions. The state-of-the-art mutations used in this study include Gaussian, Insertion, Inversion, Scramble, Swap, and Uniform, which are compared one by one with the proposed Zigzag mutation. In the experiments, 27 benchmark test functions are used to evaluate the performance. The evaluation results show superiority in 21 benchmark functions. According to the results, the presented method alone is better than other comparable methods in 77% of the benchmark functions. The share of the other six methods is only 23%. Also as an application, the presented improved genetic algorithm has been used in the segmentation of miscellaneous and aerial images. The results and statistical analysis show that the Zigzag mutation can improve the genetic algorithm and make it more efficient to solve the problems.
Similar content being viewed by others
References
Alkafaween EA, Hassanat AB (2020) Improving TSP Solutions Using GA with a New Hybrid Mutation Based on Knowledge and Randomness. Commun-Sci lett Univ Zilina 22(3):128–139
Ankenbrandt CA (1991) An extension to the theory of convergence and a proof of the time complexity of genetic algorithms. In: Foundations of genetic algorithms, pp. 53-68
Bhatti UA, Yuan L, Yu Z, Li J, Nawaz SA, Mehmood A, Zhang K (2021) New watermarking algorithm utilizing quaternion Fourier transform with advanced scrambling and secure encryption. Multimed Tools Appl 80(9):13367–13387
Das AK, Pratihar DK (2018) A direction-based exponential mutation operator for real-coded genetic algorithm. In: 2018 Fifth International Conference on Emerging Applications of Information Technology (EAIT), pp. 1-4
Dash S, Joshi D, Sharma A, Trivedi G (2018) A hierarchy in mutation of genetic algorithm and its application to multi-objective analog/RF circuit optimization. Analog Integ Circuit Sig Proc 94(1):27–47
Deb K, Deb D (2014) Analysing mutation schemes for real-parameter genetic algorithms. Int J Artif Int Soft Comput 4(1):1–28
Deep K, Thakur M (2007) A new mutation operator for real coded genetic algorithms. Appl Math Comput 193(1):211–230
Haghrah A, Nekoui MA, Nazari-Heris M, Mohammadi-ivatloo B (2021) An improved real-coded genetic algorithm with random walk based mutation for solving combined heat and power economic dispatch. J Ambient Int Human Comput 12(8):8561–8584
Harifi S (2022) A binary ancient-inspired Giza Pyramids Construction metaheuristic algorithm for solving 0-1 knapsack problem. Soft Comput, pp. 1–18
Harifi S, Mohammadzadeh J, Khalilian M, Ebrahimnejad S (2021) Giza Pyramids Construction: an ancient-inspired metaheuristic algorithm for optimization. Evol Int 14(4):1743–1761
Hassanat A, Almohammadi K, Alkafaween E, Abunawas E, Hammouri A, Prasath VB (2019) Choosing mutation and crossover ratios for genetic algorithms—a review with a new dynamic approach. Information 10(12):390
Hinterding R (1995) Gaussian mutation and self-adaption for numeric genetic algorithms. In: Proceedings of 1995 IEEE International Conference on Evolutionary Computation, pp. 384
Hodan D, Mrazek V, Vasicek Z (2020) Semantically-oriented mutation operator in cartesian genetic programming for evolutionary circuit design. In: Proceedings of the 2020 Genetic and Evolutionary Computation Conference, pp. 940-948
Katoch S, Chauhan SS, Kumar V (2021) A review on genetic algorithm: past, present, and future. Multimed Tools Appl 80(5):8091–8126
Mauldin ML (1984) Maintaining Diversity in Genetic Search. In AAAI, pp, pp. 247-250
Michalewicz Z (2013) Genetic algorithms+ data structures= evolution programs. Springer Science & Business Media
Michalewicz Z, Schoenauer M (1996) Evolutionary algorithms for constrained parameter optimization problems. Evolut Comput 4(1):1–32
Mirjalili S (2019) Genetic Algorithm. In: Evolutionary Algorithms and Neural Networks. Studies in Computational Intelligence, vol 780. Springer, Cham. https://doi.org/10.1007/978-3-319-93025-1_4
Neubauer A (1997) A theoretical analysis of the non-uniform mutation operator for the modified genetic algorithm. In: Proceedings of 1997 IEEE International Conference on Evolutionary Computation (ICEC'97), pp. 93-96
Qaiduzzaman KM, Khatun S, Afsa M, Sobhan S, Hossain ME, Shaharum SM, Rahman M (2020) A Mutation Triggering Method for Genetic Algorithm to Solve Traveling Salesman Problem. In Embracing Industry 4.0:159–170
Soni N, Kumar T (2014) Study of various mutation operators in genetic algorithms. Int J Comput Sci Inform Technol 5(3):4519–4521
Srinivas M, Patnaik LM (1994) Adaptive probabilities of crossover and mutation in genetic algorithms. IEEE Trans Syst, Man, Cyber 24(4):656–667
Tang PH, Tseng MH (2013) Adaptive directed mutation for real-coded genetic algorithms. Appl Soft Comput 13(1):600–614
Tsutsui S, Fujimoto Y (1993) Forking Genetic Algorithm with Blocking and Shrinking Modes (fGA). In: ICGA, pp. 206–215
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of Interest
The authors declare that they have no conflict of interest.
Additional information
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Harifi, S., Mohamaddoust, R. Zigzag mutation: a new mutation operator to improve the genetic algorithm. Multimed Tools Appl 82, 45411–45432 (2023). https://doi.org/10.1007/s11042-023-15518-3
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11042-023-15518-3