# PICPA : un nouvel algorithme évolutionnaire pour les problèmes continus multi-objectifs sous contraintes

Vincent Barichard, Jin-Kao Hao

<figure><img src="image_1.png" /></figure>

To cite this version:

Vincent Barichard, Jin-Kao Hao. PICPA : un nouvel algorithme évolutionnaire pour les problèmes continus multi-objectifs sous contraintes. 5ème Congrès de la Société Française de recherche Opérationnelle et d'Aide à la Décision (ROADEF'03), Feb 2003, Avignon, France. pp.44-45. hal-04031250

HAL Id: hal-04031250

https://univ-angers.hal.science/hal-04031250

Submitted on 15 Mar 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# PICPA : un nouvel algorithme évolutionnaire pour les problèmes continus multi-objectifs sous contraintes

Vincent Barichard et Jin-Kao Hao

LERIA - Université d'Angers, 2, Bd Lavoisier, 49045 Angers cedex 01
(vincent.barichard, jin-kao.hao)@info.univ-angers.fr

**Mots-clefs** : optimisation combinatoire, multi-critères, algorithmes évolutionnaires, calcul par intervalles

## 1 Introduction

Le modèle d'optimisation continu multi-objectifs sous contraintes permet de formaliser de nombreux problèmes pratiques. Un tel problème est défini formellement comme suit :

$$ \begin{cases} \min & f_i(\vec{x}) & i = 1, \dots, o \\ \text{s.c.} & C_l(\vec{x}) \ge 0 & l = 1, \dots, m \\ & \vec{x} \in \mathbb{R}^n \end{cases} $$

où $n$ est le nombre de variables, $\vec{x}$ un vecteur de l'espace de décision, $o$ le nombre d'objectifs et $m$ le nombre de contraintes du problème.

La résolution d'un tel problème nécessite la détermination d'un ensemble de points réalisables de l'espace de décision, représentant des compromis selon les différents objectifs du problème.

Récemment, plusieurs approches évolutionnaires ont été adaptées avec succès pour traiter certains problèmes multi-critères [3,6,7]. Ces travaux ont démontré l'intérêt d'utiliser un algorithme gérant une population de solutions.

Malheureusement, lorsque les contraintes du problème considéré deviennent trop difficiles à satisfaire ou quand l'espace objectif est non connexe, les algorithmes évolutionnaires multi-objectifs convergent difficilement vers le front Pareto optimal. De plus, ces algorithmes ne déterminent aucune borne du front Pareto optimal du problème.

## 2 Population and Interval Constraint Propagation Algorithm (PICPA)

Nous présentons ici PICPA, un nouvel algorithme à base de population traitant des problèmes continus multi-objectifs sous contraintes [1]. Cet algorithme combine des techniques de propagation de contraintes sur intervalles [2,4] à un mécanisme de sélection fondé sur la notion de PS-dominance.

PICPA réduit les domaines des variables représentés par des intervalles et propage ces réductions vers les autres variables et objectifs du problème. Ensuite, grâce à des mécanismes couvrant utilisés dans le domaine de l'optimisation multi-objectives (la dominance), elle éague certaines zones de l'espace des objectifs avant de réitérer son processus de réduction des domaines. Pour appliquer la dominance, PICPA instancie des points réalisables. Donc PICPA utilise à la fois des points et des intervalles pendant la recherche.

A la différence des autres algorithmes évolutionnaires qui ne donnent que des solutions heuristiques, PICPA est capable de déterminer efficacement des bornes du front Pareto optimal tout en produisant des solutions de très bonne qualité.
Les bornes ainsi déterminées encadrent le front Pareto optimal du problème. C'est un atout très important pour une méthode heuristique, car elles permettent d'évaluer la qualité des solutions trouvées sans aucune connaissance particulière du problème traité, en mesurant simplement la distance du point aux bornes.

# 3 Expérimentations et Conclusions

Nous avons évalué PICPA sur de nombreux benchmarks connus et comparé les résultats obtenus à ceux de NSGA-IIc [5], un des meilleurs algorithmes évolutionnaires connus à ce jour pour optimiser des problèmes continus multi-objectifs sous contraintes.

Les résultats de ces expérimentations mettent en évidence l'excellent comportement de PICPA sur tous les problèmes testés. Les bornes déterminées encadrent de manière très précise le font Pareto optimal (calculé de manière analytique). Les solutions heuristiques trouvées par PICPA sont de qualité égale voir supérieure sur certains problèmes à celles trouvées par NSGA-IIc.

PICPA utilise des mécanismes plus rationnels que les autres algorithmes évolutionnaires. La plupart de ces mécanismes sont déterministes et ont besoin de peu de paramètres. Ainsi, PICPA nécessite seulement deux paramètres (taille de la population et effort de recherche) alors que la plupart des algorithmes évolutionnaires en demandent au moins quatre.

PICPA est une méthode hybride héritant des atouts des différents méthodes qui la composent. Ainsi, PICPA est un algorithme garanti, efficace, nécessitant peu de paramétrages, calculant des bornes et des solutions heuristiques en une seule exécution.

# Références

[1] V. Barichard and J.K. Hao (2003). A Population and interval constraint propagation algorithm. A paraître dans *Lecture Notes in Computer Science, Proceedings of the 2nd International Conference on Evolutionary Multi-criterion Optimization (EMO'03)*, Faro, Portugal, April 2003.

[2] J.G. Cleary (1987). Logical arithmetic. *Future Computing Systems*, 2(2):125-149.

[3] D.W. Corne and J.D. Knowles (2000). M-paes : a memetic algorithm for multiobjective optimization. In *Proceedings of the 2000 congres on evolutionary computation*, 325-332

[4] E. Davis (1987). Constraint propagation with interval labels. *Artificial Intelligence*, 32(3):281-331.

[5] K. Deb and T. Goel (2001). Controlled elitist non-dominated sorting genetic algorithms for better convergence. In *Proceedings of Evolutionary Multi-criterion Optimization*, 67-81.

[6] N. Srinivas and K. Deb (1994). Multiobjective optimization using non dominated sorting in genetic algorithms. *Evolutionary Computation*, 2(3):221-248.

[7] E. Zitzler and L. Thiele (1999). Multiobjective evolutionary algorithms : a comparative case study and the strength pareto approach. *IEEE Transactions on Evolutionary Computation*, 3:257-271.