Search Improvements via Multiple Recombination in Evolutionary Algorithms

摘要

Exploration and exploitation of solutions in the searching space are distinctive characteristics of an evolutionary algorithm (EA), which are responsible of success or failure of the search process. Extreme exploitation can lead to premature convergence and intense exploration can make the search ineffective. To find a balance between these two factors is of paramount importance for the EA performance when speed of the search and quality of results are involved. Many researchers focus this problem studying the effect of selection mechanisms, because selective pressure can adjust exploration and exploitation. Recombination has also its own contribution on this respect and depending on how it is applied can help or disrupt the searching process. A low rate for recombination can impede schema processing permitting super-individuals to cope the population and leading to premature convergence. On the other hand, a high rate can be, in some cases, too disruptive allowing good genetic material being lost, slowing the search. Two, relatively new, approaches, multiple crossovers per couple and multiparent recombination attempted to face the searching process under a new focus; multiplicity. Allowing multiple crossovers on the selected parents provided similar and better quality of solutions when contrasted against the conventional crossover (where one crossover operation is applied each time). Also an extra benefit, of saving processing time, was gained. Despite these benefits, due to a reinforcement of selective pressure, the multiple crossover method showed in some cases an undesirable premature convergence effect. To face this problem many approaches were undertaken and are explained here. Permitting multiple parents, offspring creation is based on a larger sample from the search space and therefor a larger diversity is supplied. This can help to prevent premature convergence. This paper briefly introduces both methods, discusses their motivations and describes improvements in performance on selected optimisation problems by using a new multiple crossovers on multiple parents (MCMP) method, which allows multiple crossovers between multiple parents to create multiple offspring.