Efficient selection methods in evolutionary algorithms

Abstract

Evolutionary algorithms mimic some elements of the theory of evolution. The survival of individuals and the ability to produce offspring play significant roles in the process of natural evolution. This process is called natural selection. This mechanism is responsible for eliminating weaker members of the population and provides the opportunity for the development of stronger individuals. The evolutionary algorithm, an instance of evolution in the computer environment, also requires a selection method – a computerized version of natural selection. Widely used standard selection methods applied in evolutionary algorithms are usually derived from nature and prefer competition, randomness, and some kind of “fight” among individuals. But the computer environment is quite different from nature. Computer populations of individuals are typically small, making them susceptible to premature convergence towards local extremes. To mitigate this drawback, computer selection methods must incorporate features distinct from those of natural selection. In the computer selection methods randomness, fight, and competition should be controlled or influenced to operate to the desired extent. This work proposes several new methods of individual selection, including various forms of mixed selection, interval selection, and taboo selection. The advantages of incorporating them into the evolutionary algorithm are also demonstrated, using examples based on searching for the maximum ?-clique problem and traditional Traveling Salesman Problem (TSP) in comparison with traditionally considered highly efficient tournament selection, deemed ineffective proportional (roulette) selection, and other classical methods.