S L Avila

L Krähenbühl

B Sareni
email: bruno.sareni@leei.enseeiht.fr

A Multi-Niching Multi-Objective Genetic Algorithm for Solving Complex Multimodal Problems

Keywords: Multi-objective Optimization, Evolutionary Algorithms, Niching and Clearing Methods, Multimodal Problems

In this work, a Multi-Niching Multi-Objective Genetic Algorithm is presented for solving multimodal optimization problems. The originality of this algorithm resides in its niching procedure, which maintains population diversity in both objective and design variable spaces. In particular, the clearing of non-dominated individuals in the archive update is carried out using a global density estimator computed from distances between individuals in objective and design variable spaces. The efficiency of this algorithm is shown on mathematical test functions with multiple equivalent Pareto-optimal fronts and on electromagnetic design problems.

I. INTRODUCTION

Because of their inherent parallelism, Evolutionary Algorithms (EA) have the potential to find several efficient solutions (typically Pareto-optimal solutions in case of a multi-objective optimization problem) during only one iteration. However, on complex applications, it is not always possible to obtain the optimal solutions or the complete Pareto-optimal set ('optimal' is an idealization in the majority of real problems) [START_REF] Collette | Multi-objective Optimization: Principles and Case Studies (Decision Engineering[END_REF]. Consequently, the main goals of multi-objective optimization problems can be reformulated and generalized, constituting three premises:

• The distance between the non-dominated front found and the Pareto-optimal set must be minimized;

• A sparse and uniform distribution of the detected solutions is desirable;

• Finally, the extent of the non-dominated front must be maximized. In other words, the extreme values for each objective must be reached.

Beyond these three principles, when we apply an EA for solving a multi-objective optimization problem, it is important to pay attention to:

• How to treat the information about the merits of each individual, on the selection process, for guiding the search toward the Pareto-optimal set. • How to preserve the population diversity in order to prevent a premature convergence, and maximize the probabilities to find the Pareto-optimal set.

To take these considerations into account, complementary Darwinian operators must be applied in conjunction with other traditional procedures (selection, crossover, and mutation):

• Niching to preserve diversity and to explore distinct areas simultaneously, by discovering local and/or global optima;

• Clearing to avoid an excessive concentration of non-dominated individuals in some regions of the search space.

Most of recent EAs use both niching and clearing methods especially multi-objective EAs. However, niching and clearing procedures depends on distances between individuals computed in a single space (typically the design variable space or the objective space). The diversity is then preserved in the corresponding space. In this paper, we suggest a Multi-Niching Multi-Objective Genetic Algorithm capable of maintaining equivalent solutions in both spaces, by simultaneously niching in the objective and in the design variable spaces. The results obtained on mathematical and electromagnetic test problems ensure the effectiveness of the proposed algorithm.

II. THE CLEARING PROCEDURE

In certain problems, the Pareto-optimal set can be extremely vast or includes an infinite number of solutions (especially for problems with continuous variables). As a reason of a limited population size in standard EAs, it is advisable to maintain diversity to reduce genetic drift towards certain regions of the search space.

The clearing procedure consists in eliminating specific configurations in the most populated regions of the search space to avoid premature convergence and genetic drift. For example, to improve the individual distribution on the Pareto front, a minimal distance (D min ) between non-dominated individuals can be computed. In [START_REF] Deb | A fast and elitist multi-objective genetic algorithm: NSGA-II[END_REF], this procedure is called "Diversity Preservation" and the evaluation of D min is carried out only in the objective space (several other references employ the same methodology [START_REF] Zitzler | SPEA2: Improving the strength Pareto evolutionary algorithm[END_REF]). This approach works well on problems with unimodal Pareto-optimal front. In complex multimodal problems with equivalent Pareto fronts, as shown in Fig. 1a, we recommend to also consider the distance between individuals in the parameter space to prevent the clearing of solutions having similar objectives but dissimilar design variables. Therefore, the clearing of the non-dominated solutions should be associated with a niching method which computes niching indexes in relation to global density information established in both spaces.

III. THE NICHING TECHNIQUE

The procedure for detection of multiple niches in multi-objective problems is based on adapted concepts niching methods for mono-criterion genetic algorithms [START_REF] Sareni | Niching genetic algorithms for optimization in electromagnetic: I. fundamentals[END_REF]. These techniques allow an exploration of distinct areas, which constitute local optima.

In practice, the detection of different solutions gives to the engineer more degrees of freedom for decision making by considering the objectives but also the facility to design the optimized solution for example. We compute niche indexes (i.e. similarity between individuals) in the objective and parameter spaces to take into account the configuration diversity in both spaces. These indexes are calculated from the distances between individuals sorted in order of their objective value. The process makes up in two stages: first of all, for each objective k, the population is sorted in ascending (or decreasing) order according to the analyzed objective f k and distances between the individuals are computed in both spaces. Two indexes Nobj k and Npar k are then obtained according [START_REF] Collette | Multi-objective Optimization: Principles and Case Studies (Decision Engineering[END_REF].

() ( ) ( )

11
11 k i i i ii Npar x x x x x -+ = -+- r r r rr (1)
where i x r is a population member. Note that configurations having heterogeneous design variables (and/or heterogeneous objectives) must be scaled in relation to the maximum variation of their design variable (and objectives) in the population using for example a sigmoid function. Both indexes are merged into a global density estimator (2) :

Index k = Nobj k + Npar k (2)
Finally, this estimator is used in association with the clearing procedure to remove from the population, individuals of the most populated regions of each space.

IV. RESULTS

The efficiency of the proposed algorithm is characterized on a modified Himmenblau test function with multimodal and equivalent Pareto-optimal fronts [START_REF] Deb | Multi-objective genetic algorithm: problem difficulties and construction of test functions[END_REF].

  Fig 1.b shows the existence of four niches in the parameters space which results in four equivalent Pareto-optimal fronts in the objective spaces. The detection of well spread and uniformly distributed results in both spaces shows the interest of the proposed Multi-Niching Multi-Objective Genetic Algorithm. Other analytical and electromagnetic design problems will be solved in the final version of the paper.

Fig. 1 -

 1 Fig. 1 -Illustration of the Multi-Niching Multi-Objective GA