Organizer:

El - Ghazali Talbi

University of Lille

Laboratoire d'Informatique Fondamentale de Lille

Bat. M3

59655 Villeneuve d'Aseq Cedex France

Phone: 03 20 43 45 13; Fax: 03 20 43 65 66

1. An Updated Survey Of Evolutionary Multiobjective Optimization Techniques: State Of The Art And Future Trends

Carlos A. Coello Coello

Laboratorio Nacional de Informatica Avanzada (LANIA)

P.O. Box 60326-394

Houston, Texas 77205

USA

e-mail: ccoello@xalapa.lania.mx

After using evolutionary techniques for single-objective optimization during more than two decades, the incorporation of more than one objective in the fitness function has finally become a popular area of research. As a consequence, many new evolutionary-based approaches and variations of existing techniques have been recently published in the technical literature. The purpose of this paper is to provide a critical review of the existing approaches, their limitations, advantages, and degree of applicability. Finally, the future trends in this discipline and some of the most promising areas of future research will be described.

2. Multicriteria Optimization and Decision Engineering of an Extrusion Process Aided by a Diploid Genetic Algorithm

S. Massbeuf, C. Fonteix (1), L.N. Kiss (2), I. Marc, F. Pla and K. Zaras

(1) Laboratoire des Sciences du Genie Chimique - UPR CNRS 6811

ENSAIA, 2 avenue de la foret de Haye, BP 172, 54505 Vandoeuvre-les-Nancy

Cedex, France

(2) Universite Laval - Faculte des Sciences de l'Administration

Bureau 3202A/PAP, Sainte Foy G1K 7P4, Quebec, Canada

03 83 59 58 42, fax 03 83 59 58 04, perso 03 83 96 37 04

In many, if not most, optimization problems, industrials are often confronted with multiobjective decision problems. For example, in manufacturing processes, it can be necessary to optimize several criteria to take into account all the market constraints. So, the aim is to choose the best tradeoffs among all the defined and conflicting objectives. In multicriteria optimization, after the decision maker has chosen all his objectives, he has to determine the multicriteria optimal zone by using the concept of domination criterion called Pareto domination. Two points, in the research domain, are compared. If one is better for all attributes, it is a non dominated solution. All the non dominated points form the Pareto's region. Two multiobjective optimization algorithms are used to obtain the Pareto's zone. These methods are based on a diploid genetic algorithm and are compared on an industrial application : food's granulation. Some constraints are applicated to reduce the zone if some points are not interesting for the maker. In the remaining zone, the decision maker has to choose the best solution after he has made a ranking with all potential solutions.

3. Distributed Multi-Objective Optimisation for Complex Aerospace Engineering problems using Genetic Algorithms and Game Theory

B. Mantel (Dassault-Aviation), J. Periaux

(Dassault-Aviation) and M. Sefrioui (Univ. Paris 6, LIP6).

Direction de la Prospective

Computational Applied Mathematics

periaux@rascasse.inria.fr

4. Multi-objective Genetic Programming For Dynamic Systems Modelling

Katya Rodríguez-Vázquez and Peter J. Fleming

Dept. of Automatic Control and Systems Engineering

University of Sheffield, Mappin Street S1 3JD, U.K.

e-mail: katya@acse.shef.ac.uk, P. Fleming@sheffield.ac.uk

This work presents an investigation into the use of Genetic Programming (GP) applied to chaotic systems modelling. A difference equation model representation, the NARMAX (Non-Linear AutoRegressive Moving Average with eXtra inputs) model is proposed for being the basis of the hierarchical tree encoding in GP. Based upon this difference equation model representation and formulating the identification as a multiobjective optimisation problem, the well-known benchmark problem, the Chua's circuit, is studied. The formulation of the GP fitness function, multicriteria cost function based upon the definition of Pareto-optimality, generated a set of non-dominated chaotic models. This approach considered criteria related to the complexity, performance and also statistical validation of the models in the fitness evaluation. The final set of non-dominated model solutions are able to capture the dynamic characteristics of the system and reproduce the chaotic motion of the double scroll attractor.

5. Assessing the Performance of Multiobjective Genetic Algorithms for Optimisation of a Batch Process Scheduling Problem

K. J. Shaw, C. M. Fonseca [1], A. L. Nortcliffe, M. Thompson, J. Love, and P. J. Fleming.

Department of Automatic Control & Systems Engineering,

University of Sheffield, Mappin Street, S1 3JD, UK.

Fax: +44 (0) 114 273 1729 Email: shaw@acse.shef.ac.uk

[1] ADEEC/UCEH, Universidade do Algarve, Campus de Gambelas,

8000 Faro, Portugal Email: cmfonsec@ualg.pt

Scheduling provides a source of many problems suitable for solution by genetic algorithms (Davis, 1985; Bagchi et, al, 1991; Cleveland and Smith, 1993; Lee et al., 1993; Shaw and Fleming, 1996; Löhl et al., 1998). The complexities, constraints and practicalities involved in the field motivate the development of genetic algorithm techniques to allow innovative and flexible scheduling solutions. Multiobjective genetic algorithms (MOGAs) extend the standard evolutionary-based optimisation genetic algorithm optimisation technique to allow individual treatment of several objectives simultaneously (Schaffer, 1985; Goldberg, 1989, Fonseca and Fleming, 1993, 1998, Horn, Nafpliotis, and Goldberg, 1994, Srivinas and Deb, 1995). This allows the user to attempt to optimise several conflicting objectives, and to explore the trade-offs, conflicts and constraints inherent in this process. The area of MOGA performance assessment and comparison is a relatively new field, as much research concentrates on applications rather than the theory behind MOGA capabilities (e.g., Fonseca and Fleming, 1996; Van Veldhuizen and Lamont, 1998; Zitzler and Thiele, 1998). However, the theoretical exploration of these issues can have tangible effects on the development of highly practical applications, such as the process plant scheduling system under development in this work (Shaw, et. al., 1999). By assessing and comparing their strengths, variations and limitations with a quantitative method, the user can develop a highly efficient MOGA to suit the application, and gain insight into behaviour the application itself. In this work, two MOGAs are implemented to solve a process scheduling optimisation problem. A quantitative comparison of their performances is conducted, and the results and implications of this comparison are then examined within the context of the problem. Finally, a discussion of how this work may be applied beyond this field, to many other types of multiobjective optimisation techniques and applications is provided. This demonstrates the utility of this study to many other MOGA users.

6. A Genetic Algorithm Approach to Multi-Objective Scheduling Problems with Earliness and Tardiness Penalties

Hisashi Tamaki, Etsuo Nishino and Shigeo Abe.

Dept. of Electrical and Electronics Engr.

Kobe University

Rokko-dai, Nada-ku, Kobe 657-8501, Japan

Tel/Fax: +81-78-803-1063

tamaki@chevrolet.eedept.kobe-u.ac.jp

This paper deals with identical parallel machine scheduling problems with two kinds of objective functions, i.e., both regular and non-regular objective functions, and proposes a genetic algorithm approach in which (a) the sequence of jobs on each machine as well as the assignment of jobs to machines are determined directly by referring to a string (genotype), and then (b) the start time of each job is fixed by solving the linear programming problem. As for (b), we newly introduce a method of representing the problem to determine the start time of each job as a linear programming problem whose objective function is formed as a weighted sum of the original multiple objective functions. This method enables to generate a lot of potential schedules. Moreover, through computational experiments by using our genetic algorithm approach, the effectiveness for generating a variety of Pareto-optimal schedules is investigated.

7. Cooperative Strategies for Solving the Bicriteria Sparse MultipleKnapsack Problem

F. S. Salman, GSIA, CMU, Pittsburgh, PA 15213,

fs2c@andrew.cmu.edu

J. Kalagnanam, S. Murthy, IBM T.J. Watson Research Center, PO Box 218,

Yorktown Hts, NY 10591

jayant@us.ibm.com, 914 945 1039

speaker: Jayant Kalagnanam

The problem of assigning a given set of orders to the production units in the inventory arises frequently in production planning and scheduling. Typically, this problem can be formulated as a variation of the multiple knapsack problem where items (orders) are packed into knapsacks (production units). In our model we consider variations such as multiple objectives and additional assignment restrictions. We consider the objectives of both maximizing total amount of assignment and minimizing total waste due to unused knapsack capacity, as well as assignment restrictions which can be represented by sparse bipartite graphs. The focus of this paper is on obtaining non-dominated solutions in reasonably short computational time. This paper studies real instances from the steel industry which proved very hard to solve using conventional integer programming techniques. A cooperative organization of heuristics was used to solve these instances with surprising effectiveness. Such an approach can generalized for use for other hard optimization problems.

8. Multi-objective design of finite word-length controllers

R.S.H. Istepanian

Dept of Electrical and Computer Engineering,

Ryerson Polytechnic University,

350 Victoria St,

Toronto M5B 2K3, Canada.

istepanr@ee.port.ac.uk

J.F. Whidborne

Division of Engineering,

Kings College London,

Strand, London WC2R 2LS, U.K.

james.whidborne@kcl.ac.uk

Feedback controller implementations with fixed-point arithmetic offer advantages of speed, memory space, cost and simplicity compared to floating-point arithmetic. Thus, to date, fixed-point processors dedicated for digital controller implementations are still the dominant architecture in many modern digital control engineering applications, particularly for automotive, consumer, military and medical applications. However, most control design methodologies assume that the designed controller will be implemented with infinite precision. Thus, when the controller is implemented, rounding errors in the controller parameters can cause a performance degradation and even instability. However, to directly design the controller with finite-precision control parameters can result in lower performance and stability robustness. Hence, there is a trade-off between the cost of the controller (in terms of word-length and memory requirements) and the performance of the system. This paper will present an approach to designing finite word-length feedback controllers by means of a multi-objective genetic algorithm. The approach provides a set of solutions that are (near) Pareto-optimal with respect to minimal word-length and memory requirements and to closed loop performance. The method is applied to the design of a finite word-length controller for the IFAC93 benchmark problem.