Nothing Special   »   [go: up one dir, main page]

Skip to main content

Advertisement

Log in

Zigzag mutation: a new mutation operator to improve the genetic algorithm

  • Published:
Multimedia Tools and Applications Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13

Similar content being viewed by others

References

  1. 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

    Google Scholar 

  2. 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

  3. 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

    Article  Google Scholar 

  4. 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

  5. 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

    Article  Google Scholar 

  6. Deb K, Deb D (2014) Analysing mutation schemes for real-parameter genetic algorithms. Int J Artif Int Soft Comput 4(1):1–28

    Google Scholar 

  7. Deep K, Thakur M (2007) A new mutation operator for real coded genetic algorithms. Appl Math Comput 193(1):211–230

    MathSciNet  MATH  Google Scholar 

  8. 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

    Article  Google Scholar 

  9. Harifi S (2022) A binary ancient-inspired Giza Pyramids Construction metaheuristic algorithm for solving 0-1 knapsack problem. Soft Comput, pp. 1–18

  10. 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

    Article  Google Scholar 

  11. 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

    Article  Google Scholar 

  12. Hinterding R (1995) Gaussian mutation and self-adaption for numeric genetic algorithms. In: Proceedings of 1995 IEEE International Conference on Evolutionary Computation, pp. 384

  13. 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

  14. Katoch S, Chauhan SS, Kumar V (2021) A review on genetic algorithm: past, present, and future. Multimed Tools Appl 80(5):8091–8126

    Article  Google Scholar 

  15. Mauldin ML (1984) Maintaining Diversity in Genetic Search. In AAAI, pp, pp. 247-250

  16. Michalewicz Z (2013) Genetic algorithms+ data structures= evolution programs. Springer Science & Business Media

    MATH  Google Scholar 

  17. Michalewicz Z, Schoenauer M (1996) Evolutionary algorithms for constrained parameter optimization problems. Evolut Comput 4(1):1–32

    Article  Google Scholar 

  18. 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

    Chapter  MATH  Google Scholar 

  19. 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

  20. 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

    Article  Google Scholar 

  21. Soni N, Kumar T (2014) Study of various mutation operators in genetic algorithms. Int J Comput Sci Inform Technol 5(3):4519–4521

    MathSciNet  Google Scholar 

  22. Srinivas M, Patnaik LM (1994) Adaptive probabilities of crossover and mutation in genetic algorithms. IEEE Trans Syst, Man, Cyber 24(4):656–667

    Article  Google Scholar 

  23. Tang PH, Tseng MH (2013) Adaptive directed mutation for real-coded genetic algorithms. Appl Soft Comput 13(1):600–614

    Article  Google Scholar 

  24. Tsutsui S, Fujimoto Y (1993) Forking Genetic Algorithm with Blocking and Shrinking Modes (fGA). In: ICGA, pp. 206–215

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Sasan Harifi.

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.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11042-023-15518-3

Keywords

Navigation