×

Optimal mutation probability for genetic algorithms. (English) Zbl 0820.92017

Summary: We derive the value of the mutation probability which maximizes the probability that the genetic algorithm finds the optimum value of the objective function under simple assumptions. This value is compared with the optimum mutation probability derived in other studies. An empirical study shows that this value, when used with a larger scaling factor in linear scaling, improves the performance of the genetic algorithm. This feature is then added to a model developed by G. E. Hinton and S. J. Nowlan [Complex Syst. 1, No. 3, 495-502 (1987; Zbl 0651.92015)] which allows certain bits to be guessed in an effort to increase the probability of finding the optimum solution.

MSC:

92D15 Problems related to evolution
49N99 Miscellaneous topics in calculus of variations and optimal control
49N70 Differential games and control
49N75 Pursuit and evasion games
68U99 Computing methodologies and applications

Citations:

Zbl 0651.92015
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bramlette, M. F., Initialization, mutation and selection methods in genetic algorithms for function optimization, (Proceedings of the Fourth International Conference on Genetic Algorithms (1991), Morgan Kaufmann), 100-107
[2] DeJong, K., Analysis of the behavior of a class of genetic adaptive systems, (Ph.D. dissertation (1975), University of Michigan)
[3] Fogarty, T. C., Varying the probabilities of mutation in the genetic algorithm, (Proceedings of the Third International Conference on Genetic Algorithms (1989), Morgan Kaufmann), 104-109
[4] Grefenstette, J. J., Optimization of control parameters for Genetic Algorithms, IEEE Transactions on Systems, Man and Cybernetics, SMC-16, 122-128 (1986)
[5] Hesser, J.; Männer, R., Towards an optimal mutation probability, (Proceedings of the International Workshop Parallel Problem Solving from Nature (1990), Springer-Verlag)
[6] Nowack, M.; Schuster, P., Error thresholds of replication in finite populations mutations frequencies and the onset of Muller’s Ratchet, Journal of Theoretical Biology, 137, 375-395 (1989)
[7] Schaffer, J. D.; Caruna, R. A.; Eshelman, L. J.; Das, R., A study of control parameters affecting on line performance of genetic algorithms for function optimization, (Proceedings of the Third International Conference on Genetic Algorithms (1989), Morgan Kaufmann), 51-60
[8] Hinton, G. E.; Nowlan, S. J., How learning can guide evolution, Complex Systems, 1, 495-502 (1987) · Zbl 0651.92015
[9] Belew, R. K., When both individuals and populations search: Adding simple learning to the Genetic Algorithm, (Proceedings of the Third International Conference on Genetic Algorithms (1989), Morgan Kaufmann), 34-41
[10] Goldberg, D. E., Genetic Algorithms in Search, Optimization, and Machine Learning (1989), Addison-Wesley · Zbl 0721.68056
[11] Bäck, T.; Hoffmeister, F., Extended selection mechanisms in genetic algorithms, (Proceedings of the Fourth International Conference on Genetic Algorithms (1991), Morgan Kaufmann), 92-99
[12] Davis, L., Bit-climbing, representational bias, and test suite design, (Proceedings of the Fourth International Conference on Genetic Algorithms (1991), Morgan Kaufmann), 18-23
[13] von Laszewski, G., Intelligent structural operators for the \(κ\)-way graph partitioning problem, (Proceedings of the Fourth International Conference on Genetic Algorithms (1991), Morgan Kaufmann), 45-52
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.