Influence of crossover operators in evolutionary scheduling under multirecombined schemes

Abstract

In evolutionary algorithms based on genetics, the crossover operation creates individuals by interchanging genes. On the other side selection mechanisms aim to favour reproduction of better individuals imposing a direction on the search process: copies of better ones replace worst individuals. Consequently, part of the genetic material contained in these worst individuals disappears forever. This loss of diversity can lead to a premature convergence. To prevent a premature convergence to a local optimum under the same selection mechanism and multirecombined scheme then, either a larger population size or adequate crossover and mutation operators are needed. In this work we are showing the effect on genetic diversity, quality of results and required computational effort, when applying different crossover methods to a set of very hard instances of the weighted tardiness scheduling problem in single machine environments. For these experiments we are using multirecombined approaches which allow multiple crossover operations on multiple parent each time a new individual is generated. A description of each method, experiments and preliminary results are reported.