Tuesday 28
Multi-objective optimization
P. Delisle
› 17:20 - 17:40 (20min)
Implementation of the GISMOO algorithm in the ParadisEO framework
Florian Mazière  1, 2, *@  , Caroline Gagné  2, *@  , Pierre Delisle  1, *@  , Arnaud Zinflou  3, *@  , Michaël Krajecki  1, *@  
1 : Centre de Recherche en Sciences et Technologies de l'Information et de la Communication  (CRESTIC)  -  Website
Université de Reims - Champagne Ardenne
UFR Sciences Exactes et Naturelles Moulin de la Housse BP 1039 51687 Reims CEDEX 2 FRANCE -  France
2 : Département d'informatique et de mathématique  (DIM UQAC)  -  Website
555, boulevard de l'Université Chicoutimi, QC G7H 2B1 Canada -  Canada
3 : Institut de Recherche d'Hydro-Québec  (IREQ)
1800, Lionel-Boulet, Varennes, QC, Canada J3X 1S1 -  Canada
* : Corresponding author

Most industrial problems tend to optimize several objectives at once. This kind of problem does not usually have a single optimal solution, but rather a set of best trade-offs. To solve these problems, the resolution algorithms, such as metaheuristics, have to adjust their way of doing things in order to find a number of solutions : the Pareto-optimal set. In some recent work a new evolutionary algorithm which allows solving multiobjective problems was proposed : the GISMOO algorithm. This algorithm looks like a genetic algorithm with an elitist replacement, but its main distinctive feature is that it contains an immune phase, whereby half of the offspring population is generated by methods coming from clonal selection algorithms. This immune phase allow us to obtain a set of solutions which are better distributed on the Pareto front. Moreover, it is important to note that GISMOO, unlike other evolutionary algorithms, requires few parameters to calibrate. Thus, it is easy and fast to readjust this algorithm to different problems. Finally, whether the problems are continuous or combinatorial, GISMOO outperforms the reference algorithm NSGA-II. Indeed, the classical metrics used during the set of experiments show a better convergence toward the Pareto front and an ability to find more diversified solutions.

In order to make GISMOO accessible to as many people as possible and to get a version which is easily adaptable to any kind of problem, the use of a framework seems to be the suitable solution. The framework that has been chosen is ParadisEO, a white-box object-oriented framework for the design of metaheuristics on different platforms. These metaheuristics can be either based on a single solution or several solutions such as evolutionary algorithms. In addition, this framework contains a module for solving multiobjective problems and another to exploit parallel architectures in order to implement parallel and distributed metaheuristics. In its basic version, ParadisEO proposes the MOGA, NSGA-II and SPEA-II algorithms but not yet the GISMOO algorithm, although the latter was proved more efficient. This is why it is interesting to propose an implementation of GISMOO in Paradiseo, whereby users could quickly optimize their own problems by the GISMOO algorithm. To do this, users only have to define the problem in the framework, especially determining its objective functions. Furthermore, they could use the crossover operator and mutations operators already defined in ParadisEO or create new operators more specific to their problem.

To exemplify the efficiency of the GISMOO implementation in ParadisEO, the quadratic assignation problem (MQAP) has been chosen. Schematically, a set of facilities have to be assigned to various locations. For each pair of facilities, there are different kinds of flow, and the flow cost depends on the distance between the two facilities. The aim of this problem is to minimize the total cost of each flow. In this way, each kind of flow corresponds to a specific objective function of the problem. Like its uniobjective version, this problem is NP-hard and so requires the use of approximate methods to optimize problem instances with many facilities and locations. Moreover, the MQAP is a well-known multiobjective problem, and some test instances are freely available. The true Pareto front is available for some test instances which allow us to validate the quality of the solutions obtained by the implemented algorithm. During the set of experiments, GISMOO was directly compared with algorithms already defined in ParadisEO, such as NSGA-II or SPEA-II. Since this is multiobjective optimization, several elements have to be evaluated. Thus, three metrics have been used. The first metric, called the convergence metric, allows us to assess the convergence of a solution set toward the Pareto front or its approximation. The second metric compares the convergence of two sets of solutions obtained. More specifically, it indicates the proportion of solutions dominated by another solution set. The last metric, the diversity metric, allows us to evaluate the spread of solutions contained in a set. The results obtained on twenty test instances confirm that the GISMOO algorithm outperforms the others according to all three metrics computed. Indeed, the first two metrics show a better convergence of the algorithm toward the Pareto front. In addition, according to the last metric, the solutions obtained by GISMOO are better distributed than those obtained by competing algorithms. This spread is an important consideration in offering a wide range of choices to the decision maker. More details on the set of experiments and results will be provided in an extended article.

 


Online user: 2 RSS Feed