The Rank-scaled Mutation Rate for Genetic Algorithms
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:59611", author = "Mike Sewell and Jagath Samarabandu and Ranga Rodrigo and Kenneth McIsaac", title = "The Rank-scaled Mutation Rate for Genetic Algorithms", 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.", volume = "1", number = "7", pages = "2140-5", }
