Arnaud Liefooghe
email: liefooga@lifl.fr

Matthieu Basseur
email: basseur@lifl.fr

Laetitia Jourdan
email: jourdan@lifl.fr

El-Ghazali Talbi
email: talbi@lifl.fr

ParadisEO-MOEO: A Framework for Evolutionary Multi-objective Optimization

Keywords: object-oriented frameworks, design and code reuse, multiobjective optimization, evolutionary algorithms

This paper presents ParadisEO-MOEO, a white-box objectoriented generic framework dedicated to the flexible design of evolutionary multi-objective algorithms. This paradigm-free software embeds some features and techniques for Pareto-based resolution and aims to provide a set of classes allowing to ease and speed up the development of computationally efficient programs. It is based on a clear conceptual distinction between the solution methods and the multi-objective problems they are intended to solve. This separation confers a maximum design and code reuse. ParadisEO-MOEO provides a broad range of archive-related features (such as elitism or performance metrics) and the most common Pareto-based fitness assignment strategies (MOGA, NSGA, SPEA, IBEA and more). Furthermore, parallel and distributed models as well as hybridization mechanisms can be applied to an algorithm designed within ParadisEO-MOEO using the whole version of ParadisEO. In addition, GUIMOO, a platform-independant free software dedicated to results analysis for multi-objective problems, is briefly introduced.

Introduction

Nowadays, the usefulness of Multi-Objective Optimization (MOO) is globally established in the whole operational research community. Furthermore, evolutionary algorithms (EAs) are commonly used to solve multi-criterion problems since they naturally found a well-diversified set of good-quality solutions. EAs [START_REF] Holland | Adaptation in Natural and Artificial Systems[END_REF] are stochastic optimization processes based on an iterative improvement of a population of solutions (called individuals). As discussed later in the paper, several frameworks such as MOEA [START_REF] Tan | MOEA Toolbox for Computer Aided Multi-Objective Optimization[END_REF], MOMHLib++, Open BEAGLE [START_REF] Gagné | Genericity in Evolutionary Computation Software Tools: Principles and Case Study[END_REF], PISA [START_REF] Bleuler | PISA -A Platform and Programming Language Independent Interface for Search Algorithms[END_REF], TEA [START_REF] Emmerich | TEA -A Toolbox for the Design of Parallel Evolutionary Algorithms in C++[END_REF] (to quote only them) already attempt to simplify and accelerate the development process of evolutionary MOO applications. We here propose a new library, called ParadisEO-MOEO (MOEO for short), that aims to produce efficient programs while having a minimal programming effort and a maximum code reuse. MOEO (Multi-Objective Evolving Objects) is an extension of the Evolving Objects framework [START_REF] Keijzer | Evolving Objects: a general purpose evolutionary computation library[END_REF]. It includes a broad range of reusable features and techniques related to Pareto-based MOO such as performance metrics, elitism, fitness sharing and the most common Pareto-based fitness assignment schemes: MOGA, NSGA, NSGA-II, SPEA, SPEA2, IBEA, . . . The fine-grained components of MOEO confer a high genericity, flexibility, adaptability and extensibility. Thus, a genuine conceptual effort has been done in order to allow the user to write only the minimum problem-specific code and to incrementally adapt an algorithm rather than entirely re-implementing it. Moreover, MOEO is itself extented to compose the full ParadisEO framework which is devoted to hybridization and parallel/distributed computing. Besides, MOEO has already been used to solve various academic problems likewise real-world applications.

The remainder of the paper is organized as follows. Section 2 gives the necessary background about MOO. Sections 3 and 4 describe the aims, the implementation and the provided features of the MOEO framework. In section 5, we present ParadisEO as well as the most common parallel/distributed models and hybridization mechanisms for multi-objective problems. In section 6, we survey some existing MOEO-designed applications and we introduce a Graphical User Interface for Multi-Objective Optimization (GUIMOO). Finally, the last section concludes the paper and highlights several perspectives about this work.

Multi-objective optimization

Widely investigated since the end of the 1980's, multi-objective optimization concerns many areas of the industry (telecommunication, transport, aeronautics, etc). In this section, we briefly present some required notions about Paretobased multi-objective optimization such as the formulation of a multi-objective optimization problem (MOOP) and some concepts relating to Pareto optimality (the reader is referred to [START_REF] Coello | Evolutionary Algorithms for Solving Multi-Objective Optimization Problems[END_REF][START_REF] Deb | Multi-Objective Optimization using Evolutionary Algorithms[END_REF] for more details).

Multi-objective optimization problem.

A MOOP is defined by a decision space D, an objective space Z, and n ≥ 2 objective functions f 1 , f 2 , . . . , f n . Each objective function can be either minimized or maximized. A solution x = (x 1 , x 2 , . . . , x k ) is represented by a vector of k decision variables. To each solution x ∈ D is assigned exactly one objective vector z ∈ Z on the basis of a vector function

F : X → Z with z = F (x) = (f 1 (x), f 2 (x), . . . , f n (x)).
Pareto optimality. A multi-objective algorithm aims to approximate the set of Pareto optimal solutions according to F . A solution x a ∈ D is Pareto optimal if there exists no solution x b ∈ D that dominates x a . For a minimization problem, the Pareto dominance relation is defined as follows:

Definition 1. A solution x a ∈ D dominates a solution x b ∈ D if and only if ∀i ∈ [1..n], f i (x a ) ≤ f i (x b ) and ∃i ∈ [1..n] such as f i (x a ) < f i (x b ).
The overall goal is then to find a well-converged and well-diversified set of Pareto optimal solutions. These basic notions already emphasize the most important points to consider for the design of a library devoted to evolutionary multi-objective optimization.

The 'EO' part of MOEO stands for Evolving Objects. EO is a C++ LGPL opensource object-oriented framework for evolutionary computation1 that has been developed through an European joint work [START_REF] Keijzer | Evolving Objects: a general purpose evolutionary computation library[END_REF]. This library aims to provide a set of evolving objects dedicated to the flexible design of EAs. Furthermore, EO integrates many services including visualization facilities, on-line definition of parameters, application checkpointing, etc. MOEO is an extended version of the EO framework that includes some features related to Pareto-based multiobjective optimization. In this section, we present the goals of MOEO and we review some existing multi-objective optimization frameworks.

Goals

A framework is usually intended to be generic and could then be useful only if some important criteria are satisfied. Thence, the main goals of the MOEO framework are:

-Services. The framework must cover a wide range of features relating to Pareto-based multi-objective optimization. -Design and generic components. MOEO must provide a whole architecture design of the solution method. This objective requires a clear and maximal conceptual distinction between the method and the problem representations. Therefore, the designer might only write the minimal problem-specific code, and the development process should be done in an incremental way. -Maximum code reuse. The framework must allow the programmer to rewrite as little code as possible. Everthing that is already coded might be reusable. Then, it must be a commonplace to extend a problem from the monoobjective (and the EO framework) to the multi-objective case (and the MOEO framework), and from the classical to the parallel or the hybridizing case (and the whole version of the paradisEO framework, see section 5) without re-implementing the whole algorithm. For instance, it should not be necessary to re-code variation operators or solutions initialization. -Extensibility, flexibility and adaptability. Some new features must easily be added or modified without implicating other components. Furthermore, existing components must be adaptable, as, in practice, existing problems evolve and new ones arise. Thence, MOEO must be a white-box framework (and not a black-box one); users must have access to source-code and must use inheritance or specialization to derive new components from base or abstract classes.

Existing multi-objective optimization frameworks

Many frameworks dedicated to combinatorial optimization have been proposed. However, very few reached the whole goals stated above. A non-exhaustive comparative study between some existing multi-objective optimization frameworks is given in table 1. These frameworks are distinguished according to the following criteria: the available metaheuristic(s), the framework type (black-box or whitebox), the licence (open-source or not), the available metrics, the availability of hybridization and parallel features and the programming language.

X -C++ - Open EA - X - - -C++ [9] BEAGLE PISA EA X X Iǫ, Iǫ+, R2, R3, S - - - [2] TEA EA - X - - X C++ [7] ParadisEO-MOEO EA - X Iǫ+, IHD, X X C++ - (+ LS, SA, TS)
entropy, contribution

As we can see, the whole presented frameworks are open-source (only MOEA, although open-source, is based on Matlab which is not). Moreover, a large part of these frameworks are white-box frameworks, that is to say that the source-code can easily be extended or adapted in order to offer the most possible flexibility. Even so, only a thin part includes all the major metaheuristics and some metrics for performance evaluation or comparison. Also, parallel models and hybridization mechanisms are both provided at once only within ParadisEO-MOEO. Furthermore, ParadisEO is portable on distributed-memory machines and sharedmemory multi-processors, it offers a high flexibility and, to our knowledge, is the only one that is portable on grid computing.

ParadisEO-MOEO implementation and deployment

Using EO and MOEO, it is possible to build a complete multi-objective evolutionary computation application. Two major contributions of the MOEO framework refer to i) archive-related features and ii) multi-objective fitness assignment techniques. On each level of its architecture, a set of classes, devoted to the first or the second point, is provided. First, the general implementation of a multiobjective EA is shown in order to see how simple is to code a whole algorithm and to add or to change features. The implementation is conceptually divided into components so that different operators can be experimented without engendering significative modifications. A wide range of components are already provided, but new ones can easily be developed by the user with minimum code writing as MOEO is a white-box framework that tends to be flexible.

A general evolutionary algorithm implementation

Here is a general implementation of a multi-objective EA: All evolution-related objects are templatized2 regarding to the type of individuals (EOT). And, the eoEasyEA class is used to define the algorithm.

unsigned N; /*

Archive-related features

An essential point of Pareto-based optimization is the concept of archive. An archive is a secondary population that stores non-dominated solutions. Its main goal is to prevent that these solutions are not lost during the (stochastic) optimization process. As a consequence, it must be updated at each generation with newly found non-dominated individuals: moeoArchiveUpdater<EOT> updater (archive, pop); checkpoint.add (updater);

Moreover, it is possible to save the fitnesses of the archive's members at each generation into a file fileName in order to study the evolution of the non-dominated set:

moeoArchiveFitnessSavingUpdater<EOT> fitness (archive, fileName); checkpoint.add (fitness);

Performance metrics. Commonly, analyzing Pareto set approximations is done using performance metrics. The entropy [START_REF] Basseur | Design of multi-objective evolutionary algorithms: Application to the flow-shop scheduling problem[END_REF] and the contribution [START_REF] Meunier | A multiobjective genetic algorithm for radio network optimization[END_REF] are both already provided within MOEO, but other ones can easily be implemented and a few will be soon. For instance, it is possible to save the progression of the entropy measured on the archive at every generation into a file fileName: moeoEntropyMetric<EOT> entropy; moeoBinaryMetricSavingUpdater<EOT> metricUpdater (entropy, archive, fileName); checkpoint.add (metricUpdater); Elitist selection. Another major use of an archive is elitism [START_REF] Coello | Evolutionary Algorithms for Solving Multi-Objective Optimization Problems[END_REF][START_REF] Deb | Multi-Objective Optimization using Evolutionary Algorithms[END_REF]. It consists in choosing individuals in the external population as well as in the current EA population during the selection phase of the algorithm, so that non-dominated solutions also contribute to the definition of variation operators. eoSelectOne<EOT> popSelectOne; eoSelectOne<EOT> archSelectOne; selectOne = moeoSelectOneFromPopAndArch<EOT> (popSelectOne, archSelectOne, archive, ratio);

At last, MOEO aims to constantly evolve and then, if need be, to provide further archive-related features in order to reflect the advances of the literature.

Implemented multi-objective fitness assignment strategies

In EO/MOEO, the fitness of a solution is represented by a vector of real numbers for which must be specified, for each criterion, if it is to be minimized or maximized. For multi-objective problems, fitness functions must convert raw fitnesses into fitness for selection. Various Pareto-based fitness assignment schemes are already implemented in EO and MOEO (see fig. 1), but this list is not exhaustive as the framework perpetually evolves and provides all that is necessary to easily implement new ones without a significant development effort. Pareto-based fitness assignment was first proposed by Goldberg [START_REF] Goldberg | Genetic Algorithms in Search, Optimization and Machine Learning[END_REF] to solve the problems of Schaffer's approach [START_REF] Schaffer | Multiple Objective Optimization with Vector Evaluated Genetic Algorithms[END_REF]. He suggested to use the Pareto dominance relation for ranking and selection. We here present all the fitness assignment strategies provided within MOEO as well as the code that is necessary to add or to modify in order to use them.

Pareto ranking (MOGA). In [START_REF] Fonseca | Genetic Algorithms for Multiobjective Optimization: Formulation, Discussion and Generalization[END_REF], Fonseca and Fleming proposed a variation of Goldberg's fitness assignment where a solution's rank corresponds to the number of solutions in the current population by which it is dominated (see fig. 2). Then, non-dominated individuals are all assigned the same rank, while dominated ones are penalized according to the population density in the corresponding region of the trade-off surface. The algorithm proceeds, first, by sorting the population according to the ranks previously determined. Then, fitness is assigned to solutions by interpolating from the best to the worst individuals in the population. Finally, fitnesses are averaged between solutions with the same rank.

eoDominanceMap<EOT> dominanceMap; p2w = new eoParetoRanking<EOT> (dominanceMap); Pareto sharing. As Goldberg and Deb noticed in [START_REF] Goldberg | A Comparative Analysis of Selection Schemes Used in Genetic Algorithms[END_REF], a fitness assignment like the previous one tends to produce premature convergence, what does not guarantee a uniformly sampled final Pareto approximation set. To avoid that, Fonseca and Fleming [START_REF] Fonseca | Genetic Algorithms for Multiobjective Optimization: Formulation, Discussion and Generalization[END_REF] modified the strategy above by implementing fitness sharing in the objective space to distribute the population over the Pareto-optimal region. double nicheSize; p2w = new moeoParetoSharing<EOT> (nicheSize); NSGA. Srinivas and Deb [START_REF] Srinivas | Multiobjective Optimization Using Nondominated Sorting in Genetic Algorithms[END_REF] introduced another variation of Goldberg's fitness assigment in a similar way than [START_REF] Fonseca | Genetic Algorithms for Multiobjective Optimization: Formulation, Discussion and Generalization[END_REF], but based on Goldberg's version of Paretoranking. This algorithm, called Non-dominated Sorting Genetic Alorithm, classifies the solutions into several classes (or fronts). A solution that belongs to a class does not dominate another one from the same class. Then, individuals from the first front all belong to the best non-dominated set of the population; individuals from the second front all belong to the second best non-dominated set; and so on (see fig. 3). Logically, the best fitness value is assigned to solutions of the first class, because they are closest to the true Pareto-optimal front of the problem. This tends to search for solutions located in non-dominated regions. Additionally, a fitness sharing procedure helps to distribute the population over these regions. SPEA. Zitzler and Thiele [START_REF] Zitzler | Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach[END_REF] proposed an elitist algorithm called the Strength Pareto Evolutionary Algorithm. It maintains an external population (an archive) that stores a fixed number of non-dominated solutions found during the optimization process. For each member of the archive, a strength value, proportional to the number of solutions this member dominates, is computed. Then, the fitness of a solution is obtained according to the strength values of the archive's individuals that dominate it (see fig. 4). Moreover, a clustering method is used to keep diversity.

unsigned archiveSize; select = moeoSPSelect_I<EOT> (N, archiveSize);

SPEA2. An improved version of SPEA, namely SPEA2, has been introduced by Zitzler et al. [START_REF] Zitzler | SPEA2: Improving the Strength Pareto Evolutionary Algorithm[END_REF]. The three main differences of SPEA2 in comparison to its predecessor are that it incorporates: (i) a fine-grained fitness assignment strategy that takes into account the number of individuals that a solution dominates and is dominated by; (ii) a density estimation technique that leads the search process more precisely; (iii) an enhanced archive truncation method that ensures the preservation of boundary solutions.

unsigned archiveSize; select = moeoSPSelect_II<EOT> (N, archiveSize); IBEA. Introduced by Zitzler and Künzli [START_REF] Zitzler | Indicator-Based Selection in Multiobjective Search[END_REF], the Indicator-Based Evolutionary Algorithm (IBEA) has the characteristic to compute fitness values by comparing individuals on the basis of an arbitrary binary quality indicator I (also called binary performance metric). Thereby, no particular diversification mechanisms, such as fitness sharing, is necessary. The indicator, determined according to the decision maker preferences, denotes the overall goal of the optimization process. Thus, the fitness of a solution measures its usefulness according to the optimization goal. In MOEO, two binary quality indicators are proposed: the additive ǫ-indicator [START_REF] Zitzler | Performance Assessment of Multiobjective Optimizers: An Analysis and Review[END_REF] and the I HD -indicator [START_REF] Zitzler | Performance Assessment of Multiobjective Optimizers: An Analysis and Review[END_REF] that is based on the hypervolume concept [START_REF] Zitzler | Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach[END_REF] (see fig. 5). However, everything is implemented to easily develop other indicators to be used with IBEA (see [START_REF] Zitzler | Performance Assessment of Multiobjective Optimizers: An Analysis and Review[END_REF] for an overview about quality indicators).

moeoSolutionVsSolutionBM<EOT> I; double kappa;

/* scaling factor */ p2w = new moeoIBSorting<EOT> (I, kappa); New fitness assignment strategies. MOEO aims to be extensible, flexible and easily adaptable. All its components are generic in order to provide a modular architecture design that allows the user to quickly and conveniently develop a new fitness assignment scheme with a minimum code writing. The aim is to follow the new strategies coming from the litterature and, if need be, to provide any additional components required for their implementation.

Parallelism and hybridization design for multi-objective problems using the ParadisEO framework

In practice, multi-objective optimization problems are varied, they perpetually evolve (with regards to the needs, the constraints, the objectives, etc), they handle a high number of decision variables and they have to deal with instances of increasing size. Despite that, the overall goal is still to find near Pareto-optimal solutions in a tractable time. Then, classical approaches are not sufficient, and hybridization features as well as large scale parallelism must be considered to tackle this kind of problem. As shown in figure 6, in addition to parallel and distributed environments, the ParadisEO framework embeds a broad range of features, including evolutionary algorithms (as it is based on the EO framework), various local searches (as it is based on the MO framework) and multi-objective mechanisms (as it is based on the MOEO framework). Furthermore, its generic aspect allows to easily add some of its features to a MOEO-designed problem.

MO MOEO MPI

EO ParadisEO

PThreads Globus Fig. 6. ParadisEO architecture: Evolving Objects (EO) for the design of populationbased metaheuristics, Moving Objects (MO) for the design of solution-based metaheuristics and their hybridization with EAs, Multi-Objective EO (MOEO) for multiobjective optimization, and ParadisEO for parallel and distributed models. These models are portable on many execution platforms thanks to the MPI, PThreads and Globus standard libraries.

Parallel distributed evolutionary algorithms

Basically, three major parallel models can be distinguished [START_REF] Cahon | ParadisEO: A Framework for the Reusable Design of Parallel and Distributed Metaheuristics[END_REF]: the cooperative island model, the parallel population evaluation model, and the distributed single-solution evaluation model. These models are all illustrated in figure 7.

The cooperative island model. A number of EAs are simultaneously deployed to cooperate with the aim of improving the solutions's robustness. Each of them performs a search on a sub-population. Then, exchanges of genetic materials are performed in an asynchronous way to diversify the search into the target sub-populations. This allows to delay the global convergence, especially when the EAs are heterogeneous with respect to the variation operators. Individuals migrations are conducted by various parameters and are performed in a regular or irregular way. The parallel population evaluation model. The evaluation step of an EA is generally the most time-consuming. Therefore, in order to speed up the search, this centralized parallel model distributes the evaluation of the evolving population. As they require a global management of the population, the selection, the transformation and the replacement operations are applied by a master process.

At each generation, it distributes the set of newly generated solutions between different workers that evaluate and return back these solutions as well as their fitness values. A particularly efficient execution is often obtained when the ratio between communication and computation is high.

The distributed single-solution evaluation model. The fitness of each solution is evaluated in a parallel centralized way. Such a model is especially interesting when the evaluation of a solution can be itself parallelized as it requires, for instance, an access to large databases distributed among various processing nodes.

Those three parallel and distributed models are all provided within Par-adisEO [START_REF] Cahon | ParadisEO: A Framework for the Reusable Design of Parallel and Distributed Metaheuristics[END_REF]. They are implemented using MPI, PThreads and Globus standard libraries, and are thus portable on different execution platforms such as parallel computing, cluster computing, internet computing and grid computing. Moreover, their deployement is transparent as the user does not need to manage the communications and threads-based concurrency.

Hybridization

Hybridization have acquired a considerable interest in the field of optimization these last years [START_REF] Talbi | A Taxonomy of Hybrid Metaheuristics[END_REF]. A wide variety of hybrid approaches exists in the literature. And, for many academic and real-world applications, best found solutions are obtained by hybrid algorithms. In the multi-objective context, EAs are generally hybridized with local search methods in order to apply the local search algorithm on a selected individual, or to find non-dominated solutions in the neighborhood of an interesting region of the objective space. In [START_REF] Talbi | A Taxonomy of Hybrid Metaheuristics[END_REF], two levels (low and high) and two modes (relay and cooperative) of hybridization are distinguished.

The low-level hybrid algorithms address the functional composition of a single optimization method. A given function of a metaheuristic is replaced by another metaheuristic. For high-level hybridization, the different metaheuristics are selfcontained. There is no direct relationship between the internal workings of a metaheuristic. Besides, for relay hybridization, a set of metaheuristics is applied the one after another in a pipeline way, each one using the output of the previous one as its input. Contrarily, cooperative hybridization represents a teamwork optimization model in which parallel cooperating agents perform a search in a solution space and exchange solutions with the others.

The ParadisEO framework provides all these most common hybridization mechanisms [START_REF] Cahon | ParadisEO: A Framework for the Reusable Design of Parallel and Distributed Metaheuristics[END_REF] that can thus directly be applied to a MOEO-designed application in a fast and simple way. They can naturally be exploited to make cooperating metaheuristics belonging either to the same or to different families.

Applications

ParadisEO and MOEO have been applied to many areas where multi-objective optimization is required. Before presenting three examples of applications drawn from varied fields that have been implemented within MOEO, we will introduce some prerequisites concerning performance evaluation and results analysis.

Preliminaries: GUIMOO

In multi-objective optimization, a fundamental part is the performance comparison of various algorithms. Therefore, the question arises on the way of evaluating the quality of Pareto set approximations. To achieve that, let us introduce GUIMOO3 (a Graphical User Interface for Multi-Objective Optimization). This platform-independant free software is dedicated to the analysis of results for multi-objective optimization and is able to handle different input and output formats. Its main features are:

-The on-line and off-line visualization (in 2 or 3 dimensions) of Pareto set approximations. A Pareto set approximation can be characterized by its (dis)continuity, (dis)convexity, multi-modality, . . . Such an information can be useful to help an expert to build more efficient metaheuristics. -A number of metrics for quantitative and qualitative performance evaluation or comparison [START_REF] Zitzler | Performance Assessment of Multiobjective Optimizers: An Analysis and Review[END_REF] (contribution, entropy, generational distance, spacing, coverage of two sets, coverage difference, S-metric, D-metric and R-metrics).

Furthermore, GUIMOO aims to be generic. Its architecture allows to easily customize it in order to provide more functionalities to tackle specific applications (telecom, genomics, engineering design, etc).

Examples

MOEO has been experimented on different academic and industrial problems. In this section, we present three applications that show the wide range of potential of this framework as it has been applied to scheduling problems, continuous optimization and data-mining applications.

A bi-objective flow-shop scheduling problem. The flow-shop is one of the most widely investigated scheduling problem of the literature. But, the majority of studies considers it on a single-criterion form. However, other objectives than minimizing the makespan can be taken into account, like, e.g., minimizing the total tardiness.

Electromagnetic properties of conducting polymer composites in the microwave band. Due to the proliferation of electromagnetic interferences, designing protecting material for high frequencies equipments has become an important problem. In [START_REF] Legrand | Mono and Multi-objective continuous optimization for conducting polymer composites[END_REF], a new multi-objective model is proposed to design the different layers of a conducting polymer. To solve this model, a multi-objective continuous genetic algorithm is used. This algorithm offers several solutions with different physical properties and different costs.

Knowledge discovery in biological data from microarray experiments. The problem of analyzing microarray data is actually a major issue in genomics. Often used techniques are clustering and classification. In [START_REF] Khabzaoui | A Hybrid Evolutionary Algorithm for Knowledge Discovery in Microarray Experiments[END_REF], the authors propose to analyze those data through association rules. The problem is modeled as a multi-objective rule mining problem and a genetic algorithm is used to explore the large search space associated. Thence, MOGA permitted to present previously undiscovered knowledge.

Conclusion and perspectives

In this paper, we introduced ParadisEO-MOEO, a framework dedicated to the reusable design of evolutionary multi-objective optimization applications 4 . It provides the most common Pareto-based multi-objective fitness assignment shemes (MOGA, NSGA, NSGA-II, SPEA, SPEA2, IBEA, . . . ) as well as fitness sharing and a wide range of archive-related features such as non-dominated solutions storage, elitism and performance metrics computation. Moreover, the whole version of ParadisEO, a complete framework for the design of parallel/distributed and hybrid metaheuristics, and GUIMOO, a software for the analysis and the comparison of Pareto set approximations, have both been presented. These frameworks have all been applied to many type of applications, from academic to real-world problems. ParadisEO-MOEO is an open-source white-box object-oriented framework that aims to simplify and speed up the incremental implementation of a whole efficient multi-objective optimization program. In order to confer a maximum design and code reuse, it is based on a clear conceptual distinction between the metaheuristics and the problem representations. This separation is expressed at the implementation level, and the hierarchical classes that are provided allow the designer to extend the framework by inheritance or specialization. Furthermore, the fine-grained components of ParadisEO-MOEO confer a high flexibility compared to other frameworks. Modifying existing components or adding new ones can be done without impacting the whole application. Besides, ParadisEO-MOEO is a part of the ParadisEO framework that covers the most common parallel/distributed models and hybridization mechanisms. The user can thus directly include some ParadisEO features into an application designed using ParadisEO-MOEO in a fast and simple way.

In the future, ParadisEO-MOEO needs to constantly evolve in order to reflect the advances of the literature. New Pareto-based fitness assignment strategies as well as new performance metrics for Pareto set approximations should also be proposed before long. Moreover, a major extension of ParadisEO-MOEO would be to allow the design of exact methods as well as their hybridization with already provided metaheuristics. Besides, it would be interesting to introduce new specific concepts emerging from multi-criterion optimization such as the consideration of uncertainty through stochastic or fuzzy multi-objective problems.

Fig. 1 .

 1 Fig. 1. Pareto-based multi-objective fitness assignment strategies proposed in EO and MOEO: MOGA, NSGA, NSGA-II, SPEA, SPEA2, IBEA, . . .

  double nicheSize; p2w = new eoNDSorting_I<EOT> (nicheSize); NSGA-II. In [6], Deb et al. introduced a modified version of NSGA. This new algorithm, called NSGA-II, is computationnaly more efficient, uses elitism, and keeps diversity without specifying any parameters by using a crowded tournament selection operator. p2w = new eoNDSorting_II<EOT> ();

Fig. 2 .

 2 Fig. 2. The Pareto ranking fitness assignment scheme on a two-objective minimization problem.

Fig. 3 .

 3 Fig.3. The NSGA fitness assignment scheme on a two-objective minimization problem.

Fig. 4 .Fig. 5 .

 45 Fig. 4. The SPEA fitness assignment scheme on a two-objective minimization problem (the external population members are shown by circles and the EA population members are shown by crosses).

Fig. 7 .

 7 Fig. 7. Three major parallel models for multi-objective EAs.

Table 1 .

 1 Existing

		frameworks for multi-objective optimization (hybrid. stands for hy-
	bridization features, // for parallel features, lang. for programming language, ref. for
	reference, EA for Evolutionary Algorithm, LS for Local Search, SA for Simulated An-
	nealing, TS for Tabu Search, ACO for Ant Colony Optimization and PSO for Particle
	Swarm Optimization).
	name	available	black open	metrics hybrid. // lang. ref.
		metaheuristic(s) box source
	MOEA	EA	X X / -	-	-	X Matlab [20]
	for Matlab
	MOMHLib++	EA, LS, SA	-	X R, coverage,
					Ow, Os, Oc

EO is available at http://eodev.sourceforge.net

A template is a generic description of a class or a function created as an instance of the template at compile time.

GUIMOO is available at http://guimoo.gforge.inria.fr

ParadisEO-MOEO is available at http://paradiseo.gforge.inria.fr


Arnaud Liefooghe
email: liefooga@lifl.fr

Matthieu Basseur
email: basseur@lifl.fr

Laetitia Jourdan
email: jourdan@lifl.fr

El-Ghazali Talbi
email: talbi@lifl.fr

Combinatorial Optimization of Stochastic Multi-objective Problems: an Application to the Flow-Shop Scheduling Problem

Keywords: multi-objective combinatorial optimization, stochasticity, evolutionnary algorithms, flow-shop, stochastic processing times

The importance of multi-objective optimization is globably established nowadays. Furthermore, a great part of real-world problems are subject to uncertainties due to, e.g., noisy or approximated fitness function(s), varying parameters or dynamic environments. Moreover, although evolutionary algorithms are commonly used to solve multiobjective problems on the one hand and to solve stochastic problems on the other hand, very few approaches combine simultaneously these two aspects. Thus, flow-shop scheduling problems are generally studied in a single-objective deterministic way whereas they are, by nature, multiobjective and are subjected to a wide range of uncertainties. However, these two features have never been investigated at the same time.

In this paper, we present and adopt a proactive stochastic approach where processing times are represented by random variables. Then, we propose several multi-objective methods that are able to handle any type of probability distribution. Finally, we experiment these methods on a stochastic bi-objective flow-shop problem.

Introduction

A large part of concrete optimization problems are subject to uncertainties that have to be taken into account. Therefore, many works relate to optimization in stochastic environments (see [START_REF] Jin | Evolutionary Optimization in Uncertain Environments -A Survey[END_REF] for an overview), but very few deal with the multi-objective case where Pareto dominance is used to compare solutions. Thus, Hughes [START_REF] Hughes | Evolutionary Multi-Objective Ranking with Uncertainty and Noise[END_REF] and Teich [START_REF] Teich | Pareto-Front Exploration with Uncertain Objectives[END_REF] independently suggested to extend the concept of Pareto dominance in a stochastic way by replacing the rank of a solution by its probability of being dominated; but both studies make an assumption on probability distributions. In [START_REF] Babbar | A Modified NSGA-II to Solve Noisy Multiobjective Problems[END_REF], another ranking method, based on an average value per objective and on the variance of a set of evaluations, is presented. Likewise, Deb and Gupta [START_REF] Gupta | Searching for Robust Pareto-Optimal Solutions in Multi-Objective Optimization[END_REF] proposed to apply standard deterministic multi-objective optimizers using an average value, determined over a sample of objective vectors, for each dimension of the objective space. Finally, Basseur and Zitzler [START_REF] Basseur | Handling Uncertainty in Indicator-Based Multiobjective Optimization[END_REF] recently extended the concept of multi-objective optimization using quality indicators [START_REF] Zitzler | Indicator-Based Selection in Multiobjective Search[END_REF] to take stochasticity into account. However, even if existing methods are generally adaptable to the combinatorial case, most of them were only tested on continuous mathematical test functions. Thence, it is not obvious that the performances of these algorithms are similar for combinatorial and continuous problems. Furthermore, a large part of these algorithms exploits problem knowledge that may not be available in real-world applications.

The deterministic indicator-based approach [START_REF] Zitzler | Indicator-Based Selection in Multiobjective Search[END_REF] consists in assigning each Pareto set approximation a real value reflecting its quality, using a function I [START_REF] Zitzler | Performance Assessment of Multiobjective Optimizers: An Analysis and Review[END_REF]. The goal is then to identify a Pareto set approximation that optimizes I. As a result, I induces a total order into the set of aproximation sets in the objective space, and gives rise to a total order into the corresponding objective vectors. The interest of this perception is that no additional diversity preservation mechanisms are required, the concept of Pareto dominance not being directly used for fitness assignment. To extend this approach to the stochastic case, we must consider that every solution can be associated to an arbitrary probability distribution over the objective space.

In this paper, we propose various models to represent stochasticity for a biobjective flow-shop scheduling problem. Then, we introduce different ways to handle uncertainty, insisting on the various technical aspects. And, we apply the resulting methods to the concrete case of a flow-shop scheduling problem with stochastic processing times, that have, to our knowledge, never been investigated in a multi-objective form. Each approach has advantages and drawbacks and is adapted from indicator-based optimization.

The paper is organized as follows. In section 2, we formulate a bi-objective flow-shop scheduling problem with stochastic processing times (SFSP). In section 3, we present three different approaches dedicated to stochastic multiobjective optimization and apply them on a SFSP. Section 4 presents experimental results. And finally, the last section draws conclusion and suggests further topics in this research area.

A bi-objective flow-shop scheduling problem with stochastic processing times

The flow-shop is one of the numerous scheduling problems. It has been widely studied in the literature (see, for example, [START_REF] Dudek | The Lessons of Flowshop Scheduling Research[END_REF] for a survey). However, the majority of works dedicated to this problem considers it on a deterministic single-criterion form and mainly aims at minimizing the makespan, which is the completion time of the last job. Following the formulation of the deterministic model of a bi-objective flow-shop scheduling problem, this section presents various sources of uncertainty that have to be taken into account and introduces different probability distributions to model stochastic processing times. Note that, although this part focuses on the flow-shop, it can easily be generalizable to other types of problem.

Deterministic model

Solving the flow-shop problem consists in scheduling N jobs J 1 , J 2 , . . . , J N on M machines M 1 , M 2 , . . . , M M . Machines are critical resources, i.e. two jobs cannot be assigned to one machine simultaneously. A job J i is composed of M consecutive tasks t i1 , t i2 , . . . , t iM , where t ij is the j th task of the job J i , requiring the machine M j . A processing time p ij is associated to each task t ij and a job J i must be achieved before its due date d i . For the permutation flow-shop, the operating sequences of the jobs are identical and unidirectional on every machines.

In this study, we focus on minimizing both the makespan (C max ) and the total tardiness (T ), which are two of the most studied objectives of the literature . For each task t ij to be scheduled at the time s ij , we can compute the two considered objectives as follows:

C max = max i∈[1..N ] [s iM + p iM ] . (1)
T = N i=1 max(0, s iM + p iM -d i ) . (2)
In the Graham et al. notation [START_REF] Graham | Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey[END_REF], this problem is noted F/permu, d j /(C max , T ). Besides, the interested reader is referred to [START_REF] Silva | An Introduction to Multiobjective Metaheuristics for Scheduling and Timetabling[END_REF][START_REF] Billaut | Multicriteria Scheduling -Theory, Models and Algorithms[END_REF] for a review on multi-objective scheduling.

Sources of uncertainty

In real-world scheduling situations, uncertainty can occur from many sources such as release or due date variations, machine breakdowns, unexpected arrival or cancellation of orders, variable processing times, ... According to the literature, in the particular case of our permutation flow-shop scheduling problem, the uncertainty mainly stem from due dates and processing times. Firstly, in the deterministic model, the due date of a job J i is given by a fixed number d i . However, it looks difficult to determine it without ambiguity. So, it seems more natural to determine it using an interval [d 1 i , d 2 i ] during which the human satisfaction for the completion of the job J i decreases between d 1 i and d 2 i . Moreover, a due date d i may change dynamically since a less important job today may be of high importance tomorrow, and vice versa. Secondly, a processing time may vary from an execution to another and some unexpected events may occur during the process. So, the processing time p ij of a task t ij rarely corresponds to a constant value. To conclude, it is obvious that no parameter can be regarded as an exact and precise data and that non-classical approaches are required to solve concrete scheduling problems. Thus, we decide to adopt a proactive stochastic approach where processing time values are regarded as uncertain and are represented by random variables.

Stochastic models

Widely studied in its single-criterion form, the stochastic flow-shop scheduling problem has, to our knowledge, never been investigated in a multi-objective way. Furthermore, as soon as historic data about processing times are available, it seems quite easy to determine which probability distribution is associated to those parameters. Following an analysis, we propose four different general distributions a processing time may follow. Of course, a rigorous statistical analysis, based on real data, is imperative to determine the concrete and exact distribution associated to a certain processing time p ij of a real-world problem. Uniform distribution. A processing time p ij can uniformly be included between two values a and b. Then, p ij follows a uniform distribution over the interval [a, b] and its probability density function is:

f (x) = 1 b-a if x ∈ [a, b] 0 otherwise . ( 3
)
This kind of distribution is used to provide a simplified model of real industrial cases. For example, it has already been used by Kouvelis et al. [START_REF] Kouvelis | Robust scheduling of a two-machine flow shop with uncertain processing times[END_REF].

Exponential distribution.

A processing time p ij may follow an exponential distribution E(λ, a). Thus, its probability density function is:

f (x) = λ e -λ(x-a) if x ≥ a 0 otherwise . (4)
Exponential distributions are commonly used to model random events that may occur with uncertainty. This is typically the case when a machine is subject to unpredictable breakdowns. For example, processing times have been modeled by an exponential distribution in [START_REF] Cunningham | Scheduling jobs with exponentially distributed processing times on two machines of a flow shop[END_REF][START_REF] Ku | On Johnson's Two-Machine Flow Shop with Random Processing Times[END_REF].

Normal distribution. A processing time p ij may follow a normal distribution N (µ, σ) where µ stands for the mean and σ stands for the standard deviation, in which case its probability density function is:

f (x) = 1 σ √ 2π exp - 1 2 x -µ σ 2 . ( 5
)
This kind of distribution is especially usual when human factors are observed. A process may also depend on unknown or uncontrollable factors and some parameters can be described in a vague or ambiguous way by the analyst. Therefore, processing times vary according to a normal distribution.

Log-normal distribution. A random variable X follows a log-normal distribution with parameters µ and σ if log X follows a normal distribution N (µ, σ). Its probability density function is then:

f (x) = 1 σ √ 2π 1 x exp(-1 2 ( log x-µ σ ) 2 ) if x > 0 0 otherwise . (6)
The log-normal distribution is often used to model the influence of uncontrolled environmental variables. In our case, a processing time p ij following a log-normal distribution takes into account simultaneously the whole observed uncertainties. For example, this modeling has already been used in [START_REF] Dauzère-Pérès | Niveau de service en ordonnancement stochastique[END_REF].

Indicator-based evolutionary methods

This section contains a brief presentation of the indicator-based approach introduced in [START_REF] Zitzler | Indicator-Based Selection in Multiobjective Search[END_REF] (the interested reader will refer to this article for more details). Then, we present its extension to the stochastic case and propose three multiobjective methods that result from this extension.

Indicator-based multi-objective optimization

Let us consider a generic multi-objective optimization problem defined by a decision space X, an objective space Z, and n objective functions f 1 , f 2 , . . . , f n . Without loss of generality, we here assume that Z ⊆ IR n and that all n objective functions are to be minimized. In the deterministic case, to each solution x ∈ X is assigned exactly one objective vector z ∈ Z on the basis of a vector function

F : X → Z with z = F (x) = f 1 (x), f 2 (x), . . . , f n (x)
. The mapping F defines the 'true' evaluation of a solution x ∈ X, and the goal of a deterministic multi-objective algorithm is to approximate the set of Pareto optimal solutions according to F1 . However, generating the entire set of Pareto optimal solutions is usually infeasible, due to, e.g., the complexity of the underlying problem or the large number of optima. Therefore, in many applications, the overall goal is to identify a good approximation of the Pareto optimal set. The entirety of all Pareto set approximations is represented by Ω.

Different interpretations of what a good Pareto set approximation is are possible, and the definition of approximation quality strongly depends on the decision maker preferences and the optimization scenario. As proposed in [START_REF] Zitzler | Indicator-Based Selection in Multiobjective Search[END_REF], we here assume that the optimization goal is given in terms of a binary quality indicator I : Ω × Ω → IR. Then, I(A, B) quantifies the difference in quality between two sets A and B ∈ Ω, according to the decision maker preferences. So, if R denotes the set of Pareto optimal solutions, the overall optimization goal can be formulated as argmin A∈Ω I(F (A), F (R)) . Binary quality indicators represent a natural extension of the Pareto dominance relation and can thus directly be used for fitness assignment. Therefore, the fitness of a solution x contained in a set of solutions can be determined using the indicator values obtained by x compared to the whole set. It measures the usefulness of x according to the optimization goal.

Handling stochasticity

In the stochastic case, the objective values are different each time a solution is evaluated. So, the vector function F does not represent a deterministic mapping from X to Z, because an infinite set of different objective vectors is now assigned to a solution x ∈ X. Note that we consider that the 'true' objective vector of a solution is absolutely unknown before the end of the optimization process.

Proposed methods

To tackle the optimization of stochastic multi-objective problems, we here propose three different adaptations inspired by a multi-objective evolutionary algorithm designed for deterministic problems and recently introduced by Zitzler and Künzli [START_REF] Zitzler | Indicator-Based Selection in Multiobjective Search[END_REF], namely IBEA (Indicator-Based Evolutionary Algorithm). For each algorithm, we will use the additive ǫ-indicator [START_REF] Zitzler | Performance Assessment of Multiobjective Optimizers: An Analysis and Review[END_REF][START_REF] Zitzler | Indicator-Based Selection in Multiobjective Search[END_REF] as the binary performance measure needed in the selection process of IBEA. This indicator seems to be efficient [START_REF] Zitzler | Indicator-Based Selection in Multiobjective Search[END_REF] and obtained significantly better results on our problem in its deterministic form than the I HD -indicator (that is based on the hypervolume concept introduced in [START_REF] Zitzler | Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach[END_REF]). The additive ǫ-indicator (I ǫ+ ) gives the minimum ǫ-value by which B can be moved in the objective space such that A is at least as good as B. For a minimization problem, it is defined as follows [START_REF] Zitzler | Performance Assessment of Multiobjective Optimizers: An Analysis and Review[END_REF][START_REF] Zitzler | Indicator-Based Selection in Multiobjective Search[END_REF]:

I ǫ+ (A, B) = inf ǫ∈IR {∀x 2 ∈ B, ∃x 1 ∈ A : f i (x 1 ) -ǫ ≤ f i (x 2 ), i ∈ {1, ..., n}} . (7)
Single evaluation-based estimate. The first method, IBEA 1 , consists in preserving the approach used in the deterministic case. A solution is evaluated only once and its fitness is estimated using this single evaluation (see fig. 1). Actually, most of the methods proceed like that since they are based on constant parameters and do not take uncertainties into account. The advantage of this method is its low computation cost, but the estimation error may be large since the evaluation used is not necessarily representative of the potential evaluation space. Average estimate. The second method, called IBEA avg , follows the idea commonly used in the single-criterion form and suggested in several multi-objective studies (such as, e.g., [START_REF] Babbar | A Modified NSGA-II to Solve Noisy Multiobjective Problems[END_REF][START_REF] Gupta | Searching for Robust Pareto-Optimal Solutions in Multi-Objective Optimization[END_REF]). It consists in doing several evaluations of the same solution, and then in calculating the average value of these evaluations on each objective function. Next, the deterministic approach is applied using those average values (see fig. 2). This method also has the advantage of having a low computation cost if the evaluation of a solution is not too expensive (what is the case for our problem). However, losses of information may occur during the average estimate, like, e.g., the potential evaluations distribution in the research space. Probabilistic estimate. The last method consists in estimating the fitness of a solution in a probabilistic way. Here, contrary to some other approaches [START_REF] Jin | Evolutionary Optimization in Uncertain Environments -A Survey[END_REF], we do not assume that there is a 'true' objective vector per solution which is blurred by noise, but we consider that a probability distribution is associated to each solution on the objective space (see fig. 3). In order to allow the comparison of potential values of solutions, this extension of IBEA, called IBEA stoch , consists in modifying the performance assessment procedure as proposed by Basseur and Zitzler in [START_REF] Basseur | Handling Uncertainty in Indicator-Based Multiobjective Optimization[END_REF]. A random variable F(x) is associated to each solution x ∈ X by the range of which is its corresponding potential evaluation space. The underlying probability distribution is usually unknown and may differ for other solutions. Thus, in practice, for a binary quality indicator I, the fitness of a solution x is computed using an estimation of expected I-values on a finite set of evaluations. Hence, for a population P = {x 1 , x 2 , . . . , x m } and a finite set of evaluation S(x), the fitness of an individual x is defined as the estimated loss of quality if x is removed from the population, i.e.:

To compute the estimated expected I ǫ+ -value between a multiset A ∈ Ω and a reference objective vector z ⋆ , we consider all pairs (x j , z k ) where x j ∈ A and z k ∈ S(x j ) and sort them in the increasing order according to the indicator values I ǫ+ ({z k }, {z ⋆ }). Suppose the resulting order is (x j1 , z k1 ), (x j2 , z k2 ), . . . , (x j l , z k l ), the estimated expected I ǫ+ -value is then:

Ê(I ǫ+ (F(A), {z * })) = I ǫ+ ({z k1 }, {z * }) × P (F({x j1 }) = {z k1 }) + I ǫ+ ({z k2 }, {z * })× P (F({x j2 }) = {z k2 }) | F({x j1 }) = {z k1 )}) + . . . I ǫ+ ({z k l }, {z * })× P (F({x j l }) = {z k l } | ∀ 1≤i<l F({x ji }) = {z ki }) . (9)
The running time complexity of an estimated expected I ǫ+ -value computation is of order O(n(N s)2 log(N s)), where N stands for the population size, n for the number of objectives and s for the number of evaluations per solution. Nevertheless, note that all l sums do not necessarily need to be computed and, thereby, the real computation time can be reduced.

Implementation

To implement our algorithms, we use the EO framework [START_REF] Keijzer | Evolving Objects: A General Purpose Evolutionary Computation Library[END_REF] linked to its extension dedicated to multi-objective optimization ParadisEO-MOEO 2 . First, it was necessary to extend this framework by defining the pareto fitness notion for stochastic problems. Then, we implemented those methods in the same way as existing deterministic methods. All these new concepts are now available within the ParadisEO-MOEO framework.

The three approaches differ the one from the others by the way their fitness function is defined. The common points of the different algorithms are:

-Initialization: randomly generated individuals.

-Selection: deterministic tournament between two randomly chosen individuals. -Crossover : two-point crossover [START_REF] Ishibuchi | A Multi-Objective Genetic Local Search Algorithm and Its Application to Flowshop Scheduling[END_REF].

-Mutation: shift mutation [START_REF] Ishibuchi | A Multi-Objective Genetic Local Search Algorithm and Its Application to Flowshop Scheduling[END_REF].

-Replacement: elitist.

Simulation results

Benchmarks

To test our algorihms, we propose differents benchmark suites3 built from Taillard's instances [START_REF] Taillard | Benchmarks for Basic Scheduling Problems[END_REF]. These instances contain processing times for problems whose size varies from 20 to 500 jobs and from 5 to 20 machines.

Deterministic bi-objective benchmarks. First, we need to extend the Taillard's instances for the bi-objective deterministic case by adding a due date for every job. These dates were fixed using a random value chosen between p × M and p × (N + M -1), where N stands for the number of jobs, M for the number of machines and p for the mean of previously generated processing times. Thus, a due date d i lies between the average completion date of the first scheduled job and the average completion date of the last scheduled job. Moreover, in addition to Taillard's instances, we propose some instances with intermediate sizes. Each benchmark's name is composed on the same way: the first number represents the number of jobs to schedule, the second one the number of machines and the last one the index of the instance among the instances of same size.

Stochastic bi-objective benchmarks.

To generate stochasticity on a deterministic instance, the four probability distributions a processing time may follow can be applied over initial data using a configuration file. We choose to allow to configure this uncertainty over the machines only, by specifying, for each machine, a probability distribution and its parameters or some proportions depending on its central tendency. Thus, as in real-world problems, each time stochasticity is generated on an initial deterministic instance using the same configuration file, processing times contained in the obtained stochastic instance will be different.

Optimization runs

For the optimization runs, we generate stochasticity over the processing times of some deterministic benchmarks. Thus, for a given instance, we carry out 10 different evaluations into which processing times follow a uniform, an exponential, a normal, a log-normal or various distributions in the following way:

-uniform distribution: p ij ∼ U(a = 0.85 × p ij , b = 1.15 × p ij ); -normal distribution: p ij ∼ N (µ = p ij , σ = 0.15 × p ij ); -exponential distribution: p ij ∼ E(a = p ij , λ = 1 0.15×pij ); -log-normal distribution: p ij ∼ log-N (µ = log p ij , σ = 0.15 × log p ij );
various distributions: the distribution of the processing times differs on every machine.

The population size is set to 50. For each kind of distribution, we perform 10 runs per instance and per algorithm using 10 evaluations per solution (except for IBEA 1 where only the first evaluation is used). The different methods are tested using the same initial populations and the same number of generations. The crossover and mutation probabilities are set to 0.05 and 1.00 respectively. The scaling factor K, required in IBEA 1 [START_REF] Zitzler | Indicator-Based Selection in Multiobjective Search[END_REF], is set to 0.05.

Performance assessment

To our knowledge, no protocol fully adapted to evaluate the effectiveness of multi-objective optimization methods for stochastic problems exists by now. Consequently, we choose to revalue each final set of solutions on the reference benchmark (the one from which stochasticity was generated) and to regard this evaluation as the 'true' evaluation. Then, we only keep the non-dominated solutions (according to this 'true' evaluation) obtained by each algorithm. Therefore, we are able to apply traditional metrics, used in the deterministic case, to assess the quality of the obtained Pareto set approximations.

Here, we use two measures to compare the obtained Pareto fronts: the contribution metric [START_REF] Meunier | A multiobjective genetic algorithm for radio network optimization[END_REF] and the S metric [START_REF] Zitzler | Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach[END_REF]. The contribution metric evaluates the proportions of Pareto optimal solutions given by each front, whereas the S metric measures the size of the objective space dominated by a non-dominated set. For the contribution metric, the performance comparison is carried out using a reference set R determined by merging all the solutions found during the whole optimization runs of every algorithm into a single set and keeping only the non-dominated solutions. For the S metric, the required reference point Z is composed of the worst objective values observed on the whole optimization runs for the benchmark under consideration, multiplied by 1.1.

Computational results and discussion

To significantly compare all the algorithms, we choose to perform a Wilcoxon rank test for every instances and every kind of probability distribution. On each of the following results tables, the 'T' columns give the result of the test for a p-value lower than 5%, i.e.:

according to the metric under consideration, the results of the algorithm located at the specific row are significantly better than those of the algorithm located at the specific column (+); -according to the metric under consideration, the results of the algorithm located at the specific row are significantly worse than those of the algorithm located at the specific column (-); -according to the metric under consideration, there is no significant difference between the results of the two algorithms (≡).

Results for uniformly, exponentially, normally, log-normally and variously distributed processing times are respectively given in tables 1, 2, 3, 4 and 5.

In a general way, according to the performance metrics used, IBEA avg globally outperforms IBEA 1 and IBEA stoch for all probability distributions (except for the first benchmark whose processing times are log-normally distributed, where IBEA 1 performs significantly better according to the S metric, see table 4). However, as IBEA avg uses average values, we could have expected such results for probability distributions whose central tendency is the mean (i.e. uniform and normal distributions), but these results are more surprising for the other distributions. For uniformly and normally distributed processing times, IBEA 1 is significantly more efficient than IBEA stoch according to the S metric (see tables 1 and 3). But, according to the contribution metric, there is no significant difference between these two algorithms (except for the uniform distribution where IBEA stoch performs significantly better on the last benchmark, see table 1). For the exponential distribution, there is globally no significant difference between IBEA 1 and IBEA stoch (see table 2). Even so, according to the contribution metric, IBEA stoch is more effective on the last benchmark. And, according to the S metric, IBEA 1 is more effective on the second one. Finally, according to the contribution metric, for log-normally and variously distributed processing times, there is no significant difference between all the algorithms. On the contrary, according to the S metric, IBEA stoch generally outperforms IBEA 1 for the log-normal distribution (except for the first benchmark) whereas it outperforms IBEA 1 only on the last benchmark for variously distributed processing times (see tables 4 and 5).

The poor overall effectiveness of IBEA stoch can be partly explained by a low diversity among the Pareto set approximation obtained during the evaluation on the reference benchmark. Then, using an indicator that would increase the diversity in the decision space could give better results. Besides, the whole of the experimental results can be discussed as the evaluation protocol is not fully adapted to stochastic multi-objective problems.

Conclusion and perspectives

In this paper, we investigated a bi-objective flow-shop scheduling problem with stochastic processing times as well as general combinatorial optimization algorithms applied to its resolution. First, we saw that, in real-world situations, none of the parameters related to this kind of problem is deprived of uncertainty. Thus, non-deterministic models are required to take this uncertainty into account. To this end, a proactive approach, where processing times are represented by random variables, have been taken and several general stochastic models have been proposed. Next, we introduced three different indicator-based methods for stochastic multi-objective problems that are able to handle any type of uncertainty. The first method, called IBEA 1 , consists in preserving the deterministic approach by computing the fitness of a solution on a single evaluation. The second method, namely IBEA avg , is based on average objective values. At last, the IBEA stoch method consists in estimating the quality of a solution in a probabilistic way. The latter, already investigated in [START_REF] Basseur | Handling Uncertainty in Indicator-Based Multiobjective Optimization[END_REF] on continuous problems, has never been applied neither to the combinatorial case nor to the stochastic models proposed here. All these algorithms and the fitness concept for multiobjective stochastic problems are now available within the ParadisEO-MOEO framework; new methods can thus easily be implemented in order to compare their effectiveness with those presented in this paper. To test these algorithms on our stochastic flow-shop problem, we initially had to build benchmark suites, first for the deterministic bi-objective case, then for the stochastic case. According to the experimental protocol we formulated, we concluded that IBEA avg was overall more efficient than IBEA 1 and IBEA stoch . Even so, from a purely theoretical point of view, IBEA stoch seems to be more representative of the quality associated to a solution than the two other methods. In spite of that, the results it obtained are a little disappointing in comparison with the continuous case [START_REF] Basseur | Handling Uncertainty in Indicator-Based Multiobjective Optimization[END_REF]; even if, in that last case, its effectiveness is especially significant for more than two objectives. This can be explained by the fact that the final solutions found by this algorithm are relatively close the ones from the others in the decision space, which generally implies, for our problem, that they are also close in the objective space. As a result, this method cannot contest the others in term of diversity. However, all these results should be moderated. No experimental protocol fully adapted to the combinatorial optimization of stochastic multi-objective problems exists up to now. The one we proposed, although simple and fast, is not really natural and is imperfectly adapted to this kind of problem. Moreover, considering the evaluation on the deterministic benchmark as the 'true' evaluation advantages a lot IBEA avg , especially for probability distributions whose central tendency is the mean.

Different perspectives emerge from this work. First of all, other sources of uncertainty that processing times could be taken into account for the flow-shop problem. Furthermore, a reactive approach could be linked to our proactive approach in order to largely improve the effectiveness of all the algorithms. Additionally, as all the results obtained during our experiments reveal a weakness of convergence, hybridizing our evolutionary algorithms with local searches could be beneficial, especially to accelerate the exploration near potentially interesting solutions. Moreover, even if most of quality indicators to be used with IBEA take diversity into account, they only deal with diversity on the objective space, and not on the decision space. Then, to fill the low-level of diversity of IBEA stoch , it could be interesting to create an indicator that would allow the decision maker to obtain diversified solutions in the decision space and that would not be completely focused on the Pareto dominance relation. Also, perhaps IBEA stoch is simply to fine-grained compared to IBEA avg , and so presents a landscape with a complex structure whereas IBEA avg provides a reasonable guidance and uses stochasticity to pass over such a structure. Studying the lanscape more precisely could then be helpful. Besides, the population size as well as the number of evaluations per solution are two parameters that influence a lot the effectiveness of all the algorithms. Studying more finely the way of determining them and analyzing how to make them evolve in a more efficient way during the optimization process could be profitable. Lastly, working out an experimental protocol adapted to the combinatorial optimization of stochastic multi-objective problems proves to be essential to evaluate the results in a more rigorous way. As well, this study could be extended in order to consider problems with more than two ojectives.

Fig. 1 .

 1 Fig. 1. IBEA1: a single evaluation is used to approximate the fitness of a solution.

Fig. 2 .

 2 Fig. 2. IBEAavg: the average evaluation values are used to approximate the fitness of a solution.

Fig. 3 .

 3 Fig. 3. IBEA stoch : the fitness of a solution is estimated in a probabilistic way, a quality indicator being associated to each evaluation.

Fitness

  (x) = Ê(I(F(P \ {x}), F(P )) = Ê(I(F(P \ {x}), F({x})) = 1 |S(x)| z∈S(x) Ê(I(F(P \ {x}, {z}))) .

Table 5 .

 5 p-value T p-value T p-value T p-value T 20 5 01 IBEAavg > 5 % ≡ 0.002 + IBEA stoch > 5 % ≡ > 5 % ≡ 0.021 -0.001 -20 5 02 IBEAavg > 5 % ≡ 0.001 + IBEA stoch > 5 % ≡ > 5 % ≡ 0.002 -0.001 -20 10 01 IBEAavg 0.004 + 0.002 + IBEA stoch > 5 % ≡ 0.004 + 0.001 -0.001 -Table 4. Comparison of the quality assessment values obtained by IBEA1, IBEAavg and IBEA stoch for log-normally distributed processing times using the Wilcoxon rank test. contribution metric S metric IBEA1 IBEAavg IBEA1 IBEAavg p-value T p-value T p-value T p-value T 20 5 01 IBEAavg > 5 % ≡ 0.032 -IBEA stoch > 5 % ≡ > 5 % ≡ 0.001 -0.001 -20 5 02 IBEAavg > 5 % ≡ 0.001 + IBEA stoch > 5 % ≡ > 5 % ≡ 0.001 + 0.001 -20 10 01 IBEAavg > 5 % ≡ 0.001 + IBEA stoch > 5 % ≡ > 5 % ≡ 0.001 + 0.020 -Comparison of the quality assessment values obtained by IBEA1, IBEAavg and IBEA stoch for variously distributed processing times using the Wilcoxon rank test. contribution metric S metric IBEA1 IBEAavg IBEA1 IBEAavg p-value T p-value T p-value T p-value T 20 5 01 IBEAavg > 5 % ≡ 0.001 + IBEA stoch > 5 % ≡ > 5 % ≡ 0.019 -0.001 -20 5 02 IBEAavg > 5 % ≡ 0.014 + IBEA stoch > 5 % ≡ > 5 % ≡ > 5 % ≡ 0.010 -20 10 01 IBEAavg > 5 % ≡ 0.001 + IBEA stoch > 5 % ≡ > 5 % ≡ 0.003 + > 5 % ≡

Table 1 .

 1 Comparison of the quality assessment values obtained by IBEA1, IBEAavg and IBEA stoch for uniformly distributed processing times using the Wilcoxon rank test.

	contribution metric	S metric
	IBEA1 IBEAavg IBEA1 IBEAavg
	p-value T p-value T p-value T p-value T
	20 5 01 IBEAavg > 5 % ≡	0.002 +
	IBEA stoch > 5 % ≡ 0.009 -0.002 -0.001 -
	20 5 02 IBEAavg 0.013 +	0.002 +
	IBEA stoch > 5 % ≡ 0.006 -0.005 -0.001 -
	20 10 01 IBEAavg 0.002 +	0.001 +
	IBEA stoch 0.005 + 0.002 -0.001 -0.001 -

Table 2 .

 2 Comparison of the quality assessment values obtained by IBEA1, IBEAavg and IBEA stoch for exponentially distributed processing times using the Wilcoxon rank test.

	contribution metric	S metric
	IBEA1 IBEAavg IBEA1 IBEAavg
	p-value T p-value T p-value T p-value T
	20 5 01 IBEAavg > 5 % ≡	0.001 +
	IBEA stoch > 5 % ≡ > 5 % ≡ > 5 % ≡ 0.033 -
	20 5 02 IBEAavg > 5 % ≡	> 5 % ≡
	IBEA stoch > 5 % ≡ > 5 % ≡ 0.002 -0.001 -
	20 10 01 IBEAavg 0.045 +	0.001 +
	IBEA stoch 0.036 + > 5 % ≡ > 5 % ≡ 0.005 -

Table 3 .

 3 Comparison of the quality assessment values obtained by IBEA1, IBEAavg and IBEA stoch for normally distributed processing times using the Wilcoxon rank test.

A solution x1 ∈ X is Pareto optimal if and only if there exists no x2 ∈ X such that (i) F (x2) is component-wise smaller than or equal to F (x1) and (ii) F (x2) = F (x1).

ParadisEO-MOEO is available at http://paradiseo.gforge.inria.fr.

All benchmarks are available at http://www.lifl.fr/∼liefooga/benchmarks/.