Efficient noisy optimisation with the multi-sample and sliding window compact genetic algorithms
- 1 November 2017
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in 2017 IEEE Symposium Series on Computational Intelligence (SSCI)
Abstract
The compact genetic algorithm is an Estimation of Distribution Algorithm for binary optimisation problems. Unlike the standard Genetic Algorithm, no cross-over or mutation is involved. Instead, the compact Genetic Algorithm uses a virtual population represented as a probability distribution over the set of binary strings. At each optimisation iteration, exactly two individuals are generated by sampling from the distribution, and compared exactly once to determine a winner and a loser. The probability distribution is then adjusted to increase the likelihood of generating individuals similar to the winner. This paper introduces two straightforward variations of the compact Genetic Algorithm, each of which leads to a significant improvement in performance. The main idea is to make better use of each fitness evaluation, by ensuring that each evaluated individual is used in multiple win/loss comparisons. The first variation is to sample n > 2 individuals at each iteration to make n(n - l)/2 comparisons. The second variation only samples one individual at each iteration but keeps a sliding history window of previous individuals to compare with. We evaluate the methods on two noisy test problems and show that in each case they significantly outperform the compact Genetic Algorithm, while maintaining the simplicity of the algorithm.Keywords
This publication has 7 references indexed in Scilit:
- The N-Tuple bandit evolutionary algorithm for automatic game improvementPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2017
- Bandit-based Random Mutation Hill-ClimbingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2017
- The Compact Genetic Algorithm is Efficient under Extreme Gaussian NoiseIEEE Transactions on Evolutionary Computation, 2016
- Playout policy adaptation with move featuresTheoretical Computer Science, 2016
- The 2014 General Video Game Playing CompetitionIEEE Transactions on Computational Intelligence and AI in Games, 2015
- Fast Evolutionary Adaptation for Monte Carlo Tree SearchLecture Notes in Computer Science, 2014
- The compact genetic algorithmIEEE Transactions on Evolutionary Computation, 1999