SAIGA: Survival of the Fittest in Alaska

SA/GA is a genetic-algorithm-based approach to combinatorial optimization. It differs from ordinary genetic algorithms in that the acceptance of offspring is subject to the Metropolis sampling criterion [Metropolis 53] which is the basis of simulated annealing. The idea is that of a population subject to a climate that is getting colder. On one hand SA/GA can be viewed as a genetic algorithm with a crossover probability depending on the quality of the children relative to a decreasing temperature. On the other hand SA/GA can be modeled as a Markov chain with temperature-dependent transition probabilities [van Laarhoven 87]. When the population is set to one, the algorithm degenerates to a normal simulated annealing algorithm. We have tested the algorithm by applying it to a set of so- called genetic-algorithm-deceptive problems which are specially constructed to cause genetic algorithms to converge to sub-optimal results. SA/GA is not fooled by the deception and consistently finds the optimal solution. SA/GA also outperforms the pure simulated annealing algorithms while being less sensitive to parameter tuning.