Controlling the tradeoff between time and quality by considering the reproductive potential of offspring

Abstract

To improve evolutionary algorithm performance, this paper proposes a strategy to aid ascent and to help avoid premature convergence. Rapid increases in population fitness may result in premature convergence and sub optimal solution. A thresholding mechanism is proposed which discards child solutions only if their fitnesses are either too bad, in which case they are discarded, nor too good, in which case they pose the danger of premature convergence. This strategy is evaluated using two combinatorial optimization problems: the classic TSP benchmark and the more constrained vehicle routing problem (VRP) benchmark. The idea offers a relatively straight forward method for adding value by improving both runtime or solution quality. We consider a stochastic hill climber and a population based heuristic (an evolutionary algorithm).