The Rank-scaled Mutation Rate for Genetic Algorithms

Authors: Mike Sewell, Jagath Samarabandu, Ranga Rodrigo, Kenneth McIsaac

Abstract:

A novel method of individual level adaptive mutation rate control called the rank-scaled mutation rate for genetic algorithms is introduced. The rank-scaled mutation rate controlled genetic algorithm varies the mutation parameters based on the rank of each individual within the population. Thereby the distribution of the fitness of the papulation is taken into consideration in forming the new mutation rates. The best fit mutate at the lowest rate and the least fit mutate at the highest rate. The complexity of the algorithm is of the order of an individual adaptation scheme and is lower than that of a self-adaptation scheme. The proposed algorithm is tested on two common problems, namely, numerical optimization of a function and the traveling salesman problem. The results show that the proposed algorithm outperforms both the fixed and deterministic mutation rate schemes. It is best suited for problems with several local optimum solutions without a high demand for excessive mutation rates.

Keywords: Genetic algorithms, mutation rate control, adaptive mutation.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1075462

References:

[1] D. Whitley, "A genetic algorithm tutorial," Statistics and Computing, vol. 4, pp. 65-85, 1994.
[2] T. B¨ack, U. Hammel, and H.-P. Schwefel, "Evolutionary computation: Comments on the history and current state," IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, pp. 3-17, April 1997.
[3] X. Yao, "Evolutionary computation," in Evolutionary Optimization, R. Sarker, M. Mohammadian, and X. Yao, Eds. Kluwer Academic Publishers, 2002, ch. 2, pp. 27-53.
[4] T. B¨ack, "Optimal mutation rates in genetic search," in Proceedings of the 5th International Conference on Genetic Algorithms, S. Forrest, Ed. San Mateo, CA, USA: Morgan Kaufmann, 1993, pp. 2-8.
[5] T. B¨ack and M. Sch¨utz, "Intelligent mutation rate control in canonical genetic algorithms," in Proceedings of the Ninth International Symposium on Foundations of Intelligent Systems, ser. LNAI, Z. W. R'as and M. Michalewicz, Eds., vol. 1079. Berlin: Springer, June 1996, pp. 158-167.
[6] G. Ochoa, I. Harvey, and H. Buxton, "On recombination and optimal mutation rates," in Proceedings of the Genetic and Evolutionary Computation Conference, W. Banzhaf, J. Daida, A. E. Eiben, M. H. Garzon, V. Honavar, M. Jakiela, and R. E. Smith, Eds., vol. 1. Orlando, FL: Morgan Kaufmann, 1999, pp. 488-495.
[7] F. Zhang, Y. F. Zhang, and A. Y. C. Nee, "Using genetic algorithms in process planning for job shop machining," IEEE Transactions on Evolutionary Computation, vol. 1, no. 4, pp. 278-289, November 1997.
[8] E. Lutton and J. L. V'ehel, "H¨older functions and deception of genetic algorithms," IEEE Transactions on Evolutionary Computation, vol. 2, no. 2, pp. 56-71, July 1998.
[9] A. E. Eiben, R. Hinterding, and Z. Michalewicz, "Parameter control in evolutionary algorithms," IEEE Transactions on Evolutionary Computation, vol. 3, no. 2, pp. 124 - 141, July 1999.
[10] P. J. Angeline, "Adaptive and self-adaptive evolutionary computations," in Computational Intelligence: A Dynamic Systems Perspective, M. Palaniswami and Y. Attikiouzel, Eds. IEEE Press, 1995, pp. 152- 163.
[11] T. B¨ack, "The interaction of mutation rate, selection, and self-adaption within a genetic algorithm," in Parallel Problem Solving from Nature, 2: Proceedings of the Second Conference on Parallel Problem Solving from nature. Brussels: North-Holland, 1992, pp. 85-94.
[12] D. Thierens, "Adaptive mutation rate control schemes in genetic algorithms," in Proceedings of the 2002 Congress on Evolutionary Computation CEC -02, vol. 1. Honolulu, HI: IEEE, 2002, pp. 980-985.
[13] A. Tuson and P. Ross, "Adapting operator settings in genetic algorithms," Evolutionary Computation, vol. 6, no. 2, pp. 161-184, 1998.
[14] H. E. Aguirre and K. Tanaka, "Genetic algorithms on nk-landscapes: Effects of selection, drift, mutation, and recombination," Lecture Notes in Computer Science, vol. 2611, pp. 131-142, January 2003.
[15] S. Uyar, S. Sariel, and G. Eryigit, "A gene based adaptive mutation strategy for genetic algorithms," Lecture Notes in Computer Science, vol. 3103, pp. 271-281, January 2004.
[16] A. Acan, "Mutation multiplicity in a panmictic two-strategy genetic algorithm," Lecture Notes in Computer Science, vol. 3004, pp. 1-10, January 2004.
[17] A. B. Djurisic, A. D. Rakic, E. H. Li, M. L. Majewski, N. Bundaleski, and B. V. Stanic, "Continuous optimization using elite genetic algorithms with adaptive mutations," Lecture Notes in Computer Science, vol. 1585, pp. 365-372, January 1999.
[18] Q. Zhang, J. Sun, and E. Tsang, "An evolutionary algorithm with guided mutation for the maximum clique problem," IEEE Transactions on Evolutionary Computation, vol. 9, no. 2, pp. 192 - 200, April 2005.
[19] Z. Michalewicz and M. Schmidt, "Evolutionary algorithms and constrained optimization," in Evolutionary Optimization, R. Sarker, M. Mohammadian, and X. Yao, Eds. Kluwer Academic Publishers, 2002, ch. 3, pp. 57-86.