NOUVEAUX ALGORITHMES HYBRIDES POUR L’OPTIMISATION GLOBALE

ALGORITHME GENETIQUE AVEC METAMODELE UTILISANT LE GRADIENT ET BASE SUR L’AGGLOMERATION (AG-MGA)

Comme SE-Meta, les deux algorithmes « l’AG-MGA » et « l’AG-MGO » utilisent aussi l’organigramme d’un AE canonique. La seule modification apportée réside dans l’étape d’évaluation des individus de la population, comme montrée sur la Figure 1.1. Figure 1.1. Organigramme d’un algorithme évolutionnaire avec Métamodèle Extraction des solutions Non Génération de la population initiale Application des opérateurs d’évolution comme sélection, croisement, mutation Test d’arrêt Population des λ enfants obtenue Population des µ parents actualisée Remplacement (Actualisation) de la population des parents Oui Évaluation exacte de tous les λ individus de la population des enfants Évaluation exacte de tous les ιindividus de la population initiale Utilisation du Métamodèle avec gradient: évaluation exacte seulement en nbpeva points Utilisation du Métamodèle avec gradient: évaluation exacte seulement en nbpeva points Do Tien Tho Page 36 CEMEF – Ecole des Mines de Paris Thèse de doctorat Optimisation de forme en forgeage 3D Chapitre II A chaque génération, au lieu d’évaluer exactement les individus de la population, l’AG-MGA et l’AG-MGO les approximent en utilisant des Méta-modèles. Ce sont ces Méta-modèles qui entraînent la différence entre ces deux algorithmes. Dans cette section, nous expliquons d’abord le fonctionnement du Méta-modèle de l’AGMGA, qui est basé sur une méthode d’agglomération et une interpolation discontinue d’ordre 1 donnée. Considérons une population qui évolue suivant un AE (cette étude utilise celui nommé Pikaïa [Charbonneau 2002]). Pour faciliter la compréhension, nous allons présenter le méta-modèle à travers l’exemple d’un problème d’optimisation à 2 paramètres (µ1, µ2).

A une génération g, supposons qu’on a une population Pg de Nind individus distribués dans l’espace de recherche comme présentés sur la Figure 1.2. Figure 1.2. Population exemplaire dans l’espace de recherche à 2 paramètres à la génération g Ce méta-modèle consiste en trois étapes principales : ª D’abord, il applique un algorithme pour regrouper la population courante en un nombre prédéfini nbpeva de sous populations (agglomérats) contenant chacune les « voisins les plus proches entre eux ». Le nombre nbpeva représente le nombre d’évaluations exactes autorisées à chaque génération. Un algorithme très simple et largement répandu pour réaliser une telle partition est celui des K-moyennes : 1) choisir nbpeva points initiaux distincts quelconques dans la population Pg comme points maîtres initiaux x P k ,…,nbpeva g k M ∈ pour = 1 2) initialiser les agglomérats (ou les sous populations) en associant à chaque point les points restants de la population qui sont Ck ⊂ Pg k Mx Do Tien Tho Page 37 CEMEF – Ecole des Mines de Paris Thèse de doctorat Optimisation de forme en forgeage 3D Chapitre II plus proches (en distance euclidienne) de lui que de tous les autres points maîtres x , j k j M ≠ 3) calculer les nouveaux barycentres de tous les agglomérats : k k c j j k k M ,nouveau c C x c k ,…,nbpeva x k où est lenombre d’individus appartenants à l’agglonérat 1 pour 1 1 ∑= = = 4) recommencer les étapes 2 et 3 jusqu’à la stationnarité.

LGORITHME GENETIQUE AVEC METAMODELE UTILISANT LE GRADIENT ET BASE SUR L’INTERPOLATION DE LISZKAORKISZ (AG-MGO)

L’algorithme AG-MGA que nous venons de décrire présente deux inconvénients: une interpolation discontinue et un méta-modèle sans mémoire. En effet, – Il utilise une interpolation discontinue d’un agglomérat à l’autre. Ainsi, un individu situé à mi-chemin entre deux points maîtres peut prendre deux valeurs très différentes. Cependant, durant la convergence de l’AE, de tels individus ont de moins en moins de chance d’exister car les individus s’agglutinent autour des barycentres. La Figure 1.5 présente cet inconvénient pour une interpolation en 1D : le problèmes est qu’il y a un saut sur l’évaluation de la fonction coût qui pourrait perturber la convergence de l’AE et donc de la méthode (en tous cas, la ralentir). Figure 1.5.

Interpolation linéaire discontinue par agglomérat : quelle valeur le point prend–t–il à mi-chemin ? Quelle valeur de Φ(X) X1 X X2 – Le second inconvénient vient du fait que l’AG-MGA ne sert pas des calculs des générations précédentes. Ces informations peuvent être précieuses pour améliorer la qualité des approximations dans le cas où la population ne déplace pas de manière importante entre chaque génération. Lorsque par exemple, d’une génération à l’autre, les agglomérats sont disjoints, les barycentres de la génération précédente (les seuls évalués exactement) ne sont plus pertinents pour une bonne évaluation P1 locale à l’intérieur des nouveaux agglomérats. Pour pallier à ces deux défauts, nous avons introduit l’approche Algorithme Génétique avec Métamodèle utilisant le Gradient basé sur l’interpolation de Liszka-Orkisz (AG-MGO) avec un méta-modèle plus proche des surfaces de réponses. Au lieu d’effacer les informations des générations précédentes, il réutilise toutes les informations disponibles pour construire une approximation plus précise et plus fiable de la valeur de la fonction coût. Do Tien Tho Page 40 CEMEF – Ecole des Mines de Paris Thèse de doctorat Optimisation de forme en forgeage 3D Chapitre II Supposons donc qu’à la génération courante, on dispose de Nbpcalc points maîtres, notés – les anciens, dont le critère et le gradient exacts ont déjà été calculés aux générations précédentes (à la génération 0, Nbpcalc = 0). A Xk Nous décidons ensuite du nombre Nbpeva d’évaluations exactes que nous nous permettons à l’étape courante. Les individus sélectionnés, selon une stratégie que nous décrirons plus loin, seront notés – les nouveaux. N X j Nous allons d’abord décrire comment utiliser les NM = Nbpeva + Nbpcalc individus maîtres pour réaliser l’interpolation, puis comment choisir un placement optimal des nouveaux points . N X j.