Metaheuristics for Multiobjective Optimisation

Multiple, often conflicting objectives arise naturally in most real-world optimization scenarios. As evolutionary algorithms possess several characteristics that are desirable for this type of problem, this class of search strategies has been used for multiobjective optimization for more than a decade. Meanwhile evolutionary multiobjective optimization has become established as a separate subdiscipline combining the fields of evolutionary computation and classical multiple criteria decision making.

This paper gives an overview of evolutionary multiobjective optimization with the focus on methods and theory. On the one hand, basic principles of multiobjective optimization and evolutionary algorithms are presented, and various algorithmic concepts such as fitness assignment, diversity preservation, and elitism are discussed. On the other hand, the tutorial includes some recent theoretical results on the performance of multiobjective evolutionary algorithms and addresses the question of how to simplify the exchange of methods and applications by means of a standardized interface.

We consider algorithms for the sequential storage, or ‘archiving’, of solutions discovered during a Pareto optimization procedure. We focus particularly on the case when an a priori hard bound, N,is placed on the capacity of the archive of solutions. We show that for general sequences of points, no algorithm that respects the bound can maintain an ideal minimumnumber of points in the archive. One consequence of this, for example, is that a strictly bounded archive cannot be expected in general to contain the Pareto front of the points generated so far (where this set is smaller than the archive bound). Using the notion of an ideal ε-approximation set—the subset (of size ≤ N)of a whole sequence of points which minimizes ε—we also show that no archiving algorithm can attain this ideal for general sequences. This means that in general no archiving algorithm can be expected to maintain an ‘optimal’ representation of the Pareto front when the size of that set is larger than the archive bound. Furthermore, if the ranges of the PF of the sequence are not known a priori, no algorithm that certifies (using its own internal epsilon parameter ε _arc ) that it maintains an epsilon-approximate set of the sequence, can maintain ε _arc )within any fixed multiple of the minimal (ideal) ε value. In a case study we go on to demonstrate several scenarios where e-based archiving algorithms proposed by Laumanns et al. — which perform well when the archive’s capacity is nota priori bounded—perform poorly when ε is adapted ‘on the fly’ in order to respect a capacity constraint. For each scenario we demonstrate that the performance of an adaptive grid archiving (AGA) algorithm (which does notassure a formally guaranteed approximation level) performs comparatively well, in practice.

The paper describes techniques for the evaluation of multiple objective metaheuristics, i.e. methods that aim at generating a set of approximately Pareto- optimal solutions in a single run. We focus on aspects specific to the multiple objective case, i.e. the evaluation of sets of solutions being outcomes of multiple objective metaheuristics and on the comparison of computational efficiency of the methods with respect to their single objective counterparts.

In many real-world scheduling problems (eg. machine scheduling, educational timetabling, personnel scheduling, etc.) several criteria must be considered simultaneously when evaluating the quality of the solution or schedule. Among these criteria there are: length of the schedule, utilisation of resources, satisfaction of people’s preferences and compliance with regulations. Traditionally, these problems have been tackled as single-objective optimization problems after combining the multiple criteria into a single scalar value. A number of multiobjective metaheuristics have been proposed in recent years to obtain sets of compromise solutions for multiobjective optimization problems in a single run and without the need to convert the problem to a single-objective one. Most of these techniques have been successfully tested in both benchmark and real-world multiobjective problems. However, the number of reported applications of these techniques to scheduling problems is still relatively scarce. This paper presents an introduction to the application of multiobjective metaheuristics to some multicriteria scheduling problems.

A particular vehicle routing problem is considered: a customer asks to load a quantity at one place and to tran sport it to another one. The aim is to determine the daily routes of a fleet of trucks satisfying the requests of a set of customers. Several constraints must be considered: maximal duration of the daily routes; time-windows at the loading points; request of a particular type of trucks.

Several objectives are taken into account. A Multiobjective Simulated Annealing approach is applied to generate an approximation of the set of efficient solutions.

In this paper we extend the dynasearch approach proposed by Congram, Potts and van de Velde [4, 17] in the context of multicriteria optimization for the bicriteria traveling salesman problem. The idea is to use local search with an exponential sized neighborhood which can be searched in polynomial time using dynamic programming and a rounding technique. Experimental results are presented to verify the quality of the proposed approach to obtain approximate Pareto curves for the bicriteria traveling salesman problem.

In this article, we study Pareto local optimum sets for the biobjective Traveling Salesman Problem applying straightforward extensions of local search algorithms for the single objective case. The performance of the local search algorithms is illustrated by experimental results obtained for well known benchmark instances and comparisons to methods from literature. In fact, a 3-opt local search is able to compete with the best performing metaheuristics in terms of solution quality. Finally, we also present an empirical study of the features of the solutions found by 3-opt on a set of randomly generated instances. The results indicate the existence of several clusters of near-optimal solutions that are separated by only a few edges.

This paper focuses on Multiobjective job-shop scheduling with Genetic Algorithms (GAs). The efficiency of G As for combinatorial problems largely depends on how the solutions are represented. We introduce a new kind of representation, which combines the advantages of two well-known encodings and allows the use of standard recombination operators without losing solution feasibility. Our solution alternation model efficiently guides the search towards promising regions of the search space. This approach tested in a single objective context aiming at the optimization of the makespan of classical benchmarks instances performs excellently compared to state-of-the-art GAs. The usefulness of the proposed method for Multiobjective scheduling is finally shown by tackling four job-shop scheduling problems introduced by Bagchi with the goal of minimizing the makespan, the mean flow-time and the mean tardiness simultaneously.

In this paper a Multiobjective Optimization Genetic Algorithm, denoted as Reduced Pareto Set Genetic Algorithm with Elitism (RPSGAe), is presented and its performance is assessed. The algorithm is compared with other Evolutionary Multiobjective Algorithms — EMOAs (SPEA2, PAES and NSGA-II) using problems from the literature and statistical comparison techniques. The results obtained showed that the RPSGAe algorithm has good overall performance. Finally, the RPSGAe algorithm was applied to the optimization of the polymer extrusion process. The aim is to implement an automatic optimization scheme capable of defining the values of important process parameters, such as operating conditions and screw geometry, yielding the best performance in terms of prescribed attributes. The results obtained for specific case studies have physical meaning and correspond to a successful process optimization.