  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 lead 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-1)/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 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.
