Self-adaptation of mutation operator and probability for permutation representations in genetic algorithms.

Area of Science:

• Computational Intelligence
• Evolutionary Computation
• Optimization Algorithms

Background:

• The selection of mutation rate and operators is crucial for genetic algorithm (GA) performance, especially for permutation representations.
• Optimal mutation strategies are problem-dependent and dynamic, posing a challenge for GA users.
• Previous success of self-adaptation in continuous domains and binary encodings suggests potential for permutation problems.

Purpose of the Study:

• To investigate the efficacy of self-adaptation in automatically managing mutation operator choice and rate for permutation-based genetic algorithms.
• To reduce the burden on users by automating non-trivial parameter tuning.
• To assess if self-adaptation can improve performance compared to static, pre-tuned operators.

Main Methods:

• Examined one method for runtime adaptation of mutation operator selection.
• Investigated several methods for adapting the mutation rate during evolution.
• Evaluated adaptive genetic algorithms on benchmark Traveling Salesperson Problem (TSP) instances, a common permutation encoding problem.

Main Results:

• Self-adaptive genetic algorithms achieved solutions with costs comparable to or lower than extensively pre-tuned static algorithms.
• Adaptive methods demonstrated robustness across various host algorithms, population models, and operator choices.
• While adaptive GAs required longer runtimes, the time saved in manual tuning was significant.

Conclusions:

• Self-adaptation is a viable and beneficial approach for managing mutation operators and rates in permutation-based genetic algorithms.
• The robustness of the presented methods suggests broad applicability in solving complex optimization problems.
• Automating mutation strategy selection via self-adaptation offers a practical advantage over manual tuning, leading to competitive or superior performance.