Rank-Based Adaptive Mutation: An Intuitive Explanation

Genetic Algorithms (GAs) have become most useful algorithm for optimization in engineering, machine learning, and operations research. GA was initially proposed by John Holland inspired by natural evolution. The algorithm uses fitness-based selection, crossover, and mutation — to evolve solutions toward optimality. But while most implementations stick with fixed probabilities for crossover and mutation operators, adaptive probabilities have emerged as an alternative to improve performance. A rank based adaptive mutation approach is explained here intuitively with comparison as an alternative to the fitness-based approach.

An Intuition for Adaptive Approach for Mutation

A fixed mutation probability must remain very low as this usually alters the best chromosomes hence affects the convergence process. Adaptive mutation probability was proposed as an alternative approach to mitigate the risk. In fitness based adaptive mutation strategies, the probability of mutation for an individual chromosome is usually calculated based on its fitness relative to the best in the population:

However, the drawback to the mentioned approach is when many chromosomes have similar fitness values close to the best, the mutation probabilities collapse toward zero for most of the population. To explain the scenario, imagine a hypothetical school of mathematics. Students are trained there to improve their skills in mathematics. The objective of the school is to improve the average score of their students as well as top score. The school takes periodic tests to evaluate the students and train them based on their performance. Students who have low scores are given more training and are assigned more tasks than students who have higher scores. This training can be considered analogous to mutation in Genetic algorithm. Assume students are evaluated in exam using percentile which represents the fitness. The reason for choosing percentile is that it is analogous to fitness in GA where the maximum possible fitness (i.e. Global optima) is unknown. The students who earned low percentile in a class test would be assigned more tasks for improvement. Below are the formulae for candidate percentile calculation.

This approach seems reasonable — poorly performing students i.e. having lower percentile would receive more assignments as part of training which is analogous to higher mutation probability based on fitness score. However, it suffers from a critical flaw. It depends on the highest mark and number of people who obtained lower marks compared to a specific candidate. Even if the highest mark is just 50% of the total mark it would be computed as a highest (99.99) percentile. There could be considerable number of students obtaining same marks i.e. same percentile. And if the highest mark is low, it is highly probable that lots of students will obtain scores very close to the highest score. In this situation the percentile distribution is mostly skewed. If the students are trained based on their percentile score, they might have received less training than required which is analogous to having lower mutation probability in Genetic algorithm eventually reducing the exploration pressure and resulting in premature convergence.

The Rank Based Approach as a Remedy

Let us design a new hypothetical ranking approach based on their percentile to overcome this. Each student would be assigned a rank where a single rank can be assigned to only a single student. Assuming total N students, the student having the maximum percentile would be assigned the highest rank i.e. N. The student who earned the lowest percentile would be assigned lowest rank i.e. 1. Rest of the students would be assigned ranks based on their earned percentile in a monotonically decreasing order. Students having same score would be assigned distinct ranks. Since this approach uses separate ranks for individuals even with same percentile it would ensure students are provided better level of trainings even after having good percentile. This would minimize the chances of converging the marks to local optima. Similarly in Genetic algorithm, since mutation probability now depends only on rank position and not on absolute fitness values, the algorithm preserves exploration pressure even when the population becomes clustered around sub-optimal solutions. The proposed formula for probability calculation is given below:

The worst ranked individual receives the highest probability of mutation, and this probability decreases linearly as rank improves, reaching near zero for the best individual. This approach ensures proper sustenance of mutation probability and good exploration pressure throughout the convergence process. This also ensures population does not converge with local optima.

References:

A Rank based Adaptive Mutation in Genetic Algorithm