Analysis of new niching genetic algorithms for finding multiple solutions in the job shop scheduling

摘要

In this paper the performance of the most recent multi-modal genetic algorithms (MMGAs) on the Job Shop Scheduling Problem (JSSP) is compared in term of efficacy, multi-solution based efficacy (the algorithm's capability to find multiple optima), and diversity in the final set of solutions. The capability of Genetic Algorithms (GAs) to work on a set of solutions allows us to reach different optima in only one run. Nevertheless, simple GAs are not able to maintain different solutions in the last iteration, therefore reaching only one local or global optimum. Research based on the preservation of the diversity through MMGAs has provided very promising results. These techniques, known as niching methods or MMGAs, allow not only to obtain different multiple global optima, but also to preserve useful diversity against convergence to only one solution (the usual behaviour of classical GAs). In previous works, a significant difference in the performance among methods was found, as well as the importance of a suitable parametrization. In this work classic methods are compared to the most recent MMGAs, grouped in three classes (sharing, clearing and species competition), for JSSP. Our experimental study found that those new MMGAs which have a certain type of replacement process perform much better (in terms of highest efficacy and multi-solution based efficacy) than classical MMGAs which do not have this type of process.