Design of Multi-Objective Evolutionary Algorithms: Application to the Flow-Shop Scheduling Problem

Abstract : Multi-objective optimization using evolutionary algorithms has been extensively studied in the literature. We propose formal methods to solve problems appearing frequently in the design of such algorithms. To evaluate the effectiveness of the introduced mechanisms, we apply them to the flow-shop scheduling problem. We propose a dynamic mutation Pareto genetic algorithm (GA) in which different genetic operators are used simultaneously in an adaptive manner, taking into account the history of the search. We present a diversification mechanism which combines sharing in the objective space as well as in the decision space, in which the size of the niche is automatically calculated. We also propose a hybrid approach which combines the Pareto GA with local search. Finally, we propose two performance indicators to evaluate the effectiveness of the introduced mechanisms.