Un chemin en optimisation globale

Com. Conf. Optimisation de Forme, 1999 au C.I.R.M.

B. Rousselet^{∗}

juin 1999

Table des matières

1 Introduction 4 1.1 Orientation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Un exemple en optimisation de structures . . . . . . . . . . . . . 4 1.3 Deux familles d’algorithmes . . . . . . . . . . . . . . . . . . . . . 5 1.4 Quelques algorithmes déterministes: . . . . . . . . . . . . . . . . 6 1.5 Quelques algorithmes stochastiques: . . . . . . . . . . . . . . . . 6 1.6 Le recuit simulé . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.7 Application aux autodirecteurs de torpilles . . . . . . . . . . . . . 9 1.8 Les algorithmes génétiques . . . . . . . . . . . . . . . . . . . . . 10 1.9 Conclusions d’études d’optimisation en acoustique . . . . . . . . . 11

2 Equation differentielle stochastique avec recuit 13 2.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Equation differentielle stochastique . . . . . . . . . . . . . . . . . 13 2.3 Méthode du recuit . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3 Autres approches 16 3.1 Diagnostics et remèdes . . . . . . . . . . . . . . . . . . . . . . . . 16 3.2 Algorithme d’élimination de domaines . . . . . . . . . . . . . . . . 16 3.3 Nouveaux algorithmes . . . . . . . . . . . . . . . . . . . . . . . . 18

∗Laboratoire J.A. Dieudonné U.M.R. C.N.R.S. 6621, Parc Valrose, F 06108 Nice, Cédex 2, email : br@math.unice.fr

3.3.1 Recuit simulé et élimination de domaines . . . . . . . . . . 18 3.3.2 Recuit -evolutionnaire avec élimination de domaines …. 19

4 Conclusion 19 3

1 Introduction

1.1 Orientation

L’optimisation globale a pour but de determiner un optimum (maximum ou minimum) global (ou absolu) d’une fonction; les algorithmes les plus classiques de programmation mathématique ne trouvent que des minimums locaux sauf si le problème est convexe (dans ce cas, tout minimum local est global) ce qui est rarement le cas dans la pratique industrielle! Le problème de l’optimisation globale est un defi tant du point de vue mathématique que numérique; par exemple on ne dispose pas de caractérisation pratique d’un optimum global de f dans X_{ad} ⊂ R^{n} analogue aux conditions d’optimalité de Karush-kuhn-Tucker pour un minimum local en programmation mathématique. De très nombreux algorithmes existent et ceci depuis les années 50 ; ils sont devenus particulièrement intéressants avec le développment de la puisance des ordinateurs. De nombreux articles sont publiés, citons parmi d’autres: [?, ?, ?]. En optimisation de structures des travaux sont régulièrement publiées depuis 5 ans dans J. of Structural Optimisation (Springer). Un article de synthèse y est publié en 1995 (Arora, Elwakeil, Chahande, Hsieh) [?] auquel on pourra se référer. Les algorithmes d’optimisation globale peuvent se répartir en deux classes,

– les algorithmes déterministes

– les algorithmes stochastiques.

1.2 Un exemple en optimisation de structures

Dans [?], les auteurs proposent une situation typique, l’optimisation de treillis de poutres pour illustrer la problématique de l’optimisation globale. Les variables de conception peuvent être l’inertie de la section ou des paramètres géométriques qui caratérisent la géométrie de la section. L’objectif est de minimiser le poids avec des contraintes d’optimisation sur:

– contraintes mécaniques;

– déplacements;

– fréquences de vibration; – flambement local;

– variables de conception. Les exemples proposés comprennent de 8 à 225 degrés de liberté et de 4 à 116 variables de conception et différentes combinaisons des contraintes d’optimisation. Les calculs à l’aide des 2 algorithmes qu’ils proposent mettent en évidence de nombreux cas avec une dizaine de minimum locaux avec 2 situations: en ces points, soit les valeurs de la fonctionnelle sont égales (le minimum global est alors atteint en plusieurs points) soit la fonctionnelle prend des valeurs très différentes.

1.3 Deux familles d’algorithmes

Les algorithmes déterministes doivent en principe faire une recherche exhaustive dans tout le domaine admissible; ceci demande un énorme effort de calcul et est bien sur impossible dans le cas de variables continues (dans R^{n}) où on doit se contenter d’un minimum global approché. une hypothèse très répandue : continuité à la Lipschitz; c’est à dire qu’il existe une constante L > 0 telle que

∀x ∈ X_{ad} ∀y ∈ X_{ad} |f(x) − f(y)| ≤ L||x − y||  (1)

Dans les algorithmes déterministes on peut distinguer les algorithmes exacts pour lesquels on est sûr de trouver le minimum global en un nombre fini d’étapes ( ils demandent naturellement un très gros effort de calcul) et les algorithmes heuristiques pour lesquels la convergence n’est qu’empirique. Les algorithmes stochastiques développés à partir de l’algorithme de recherche purement aléatoire (on calcule f(x) en N points de distribution aléatoire uniforme sûr X_{ad}); convergence "presque sure " au sens probabiliste. L’efficacité d’un algorithme peut être estimé à l’aide des 2 propriétés partiellement contradictoire: la convergence asymtotique vers un minimum global; après un temps de calcul raisonable il doit donner une bonne aproximation du minimum global.

1.4 Quelques algorithmes déterministes:

– Recouvrement du domaine admissible à l’aide d’une grille à pas variable; le pas de cette grille est estimé á l’aide de la valeur courante de f(x) de la plus petite valeur trouvée précédemment et de la constante de Lipschitz L de la fonction; (par exemple Evtushensko, 1971, 1985).

– Méthode du zoom (Arora [?]); on cherche un minimum local x_{loc}(par un algorithme de programmation mathématique) puis on rajoute aux contraintes f(x) ≤ γf(x_{loc}) avec 0 ≤ γ ≤ 1 et on itère le processus.

– Les méthodes de descente généralisée (concept introduit par Griewank [?] en 1981) mais l’utilisation d’équations différentielles du second ordre remonte au moins à 1964: méthode du golf de Inomata et Cumada [?]. Actulluement, cette approche fait l’objet de développements mathématiques nouveaux présentés à la même conférence (Optimisation de Forme, 1999 au C.I.R.M.) [?] .

– Méthode du tunnelier (Levy and Gomez, 1985): après une recherche locale on trouve x_{loc} on cherche alors un autre point x ≠ x_{loc} pour lequel f(x) − f(x_{loc}) = 0 en résolvant cette équation modifiée.

– Utilisation de dérivées d’ordre supérieur (Massat-Roques-Rossel [?])

1.5 Quelques algorithmes stochastiques:

– L’algorithme purement aléatoire décrit plus haut peut être complété par une seule utilisation d’une recherche locale.

– Algorithme de recherche aléatoire avec recherche locale à partir de chaque point aléatoire trouvé; Rinnooy and Timmer (1987).

– Les méthodes de voisinages: elles consistent à ne faire de recherche locale que dans chaque région d’attraction; plusieurs méthodes : Boender et al, 1982; Rinnooy and Timmer (1987); Jain, 1989.

– Mentionnons l’algorithme du tabou (voir par exemple Glover, 1989) qui utilise un historique des solutions admissibles déjà calculées et où l’on ne doit plus aller (la liste des tabous).

– Deux nouveaux algorithmes stochatiques sont présentés dans Elwakeil et Arora [?, ?] avec des tests d’optimisation de structures élastiques: la méthode d’élimination de domaines et une nouvelle version stochastique de l’algorithme du zoom dont une version déterministe était indiquée plus haut.

– Recherche aléatoire controlée (Price, 1987): on utilise des tirages aléatoires que l’on manipule pour les diriger vers le minimum global.

– Le recuit simulé : voir section suivante.

– Equations différentielles stochastiques et recuit: voir plus loin.

– Les algorithmes génétiques et évolutionaires: voir plus loin.

1.6 Le recuit simulé

est une méthode basée sur les idées de la mécanique statistique (Jaynes, 1951, [?]). L’algorithme du recuit simulé est par exemple utilisé en traitement d’images (Azencott, 1986, [?]). En voici une présentation algorithmique (c.f. Michalewicz, 1996, [?]).

début Procédure Recuit simulé j = 0 initialiser température T choisir au hasard un point initial x^{0} faire jusqu’à ce que critère d’arret satisfait

faire jusqu’à ce que condition de changement de température satisfaite

choisir au hasard un nouveau point x au voisinage de x^{0}; Si f(x) ≤ f(x^{0}) alors x^{0} = x sinon si random[0 , 1] < exp((f(x^{0}) − f(x))/T)alors x^{0} = x fin si fin faire T = g(T, j); j = j + 1 fin faire fin de procédure

Les difficultés dans la mise en oeuvre de cet algorithme sont dans le choix de la condition du changement de température et de la fonction g de mise à jour de la température. Principe (Duflo exo 1.4.3): pour E fini, densité de Gibbs:

g_{f,τ}(x) = \frac{exp(−\frac{f(x)}{τ})}{c_{τ}}

c_{τ} est choisi pour que g_{f,τ} soit une densité de probabilté. si on remplace f par f − m alors g conservé; quand τ → 0 alors g tend vers proba unifome sur Argminf simulation d’observations indépendantes de loi g_{f,τ} couteuse, d’où idée du recuit: la distribution de Gibbs est invariante pour le processus du recuit et moins couteuse à simuler. Dessin à réaliser a l’aide de Maple: plotsetup(ps,plotoutput=‘plot.ps‘); plot(exp(−(100 ∗ sin(x)^{2} + (x − 1)^{2})), x = −10..10); plotsetup(ps,plotoutput=‘plot1.ps‘); plot[ps](((100 ∗ sin(x)^{2} + (x − 1)^{2})), x = −10..10);

1.7 Application aux autodirecteurs de torpilles

Dans le cadre d’une convention entre l’Université de Nice Sophia-Antipolis et Thomson Marconi sonars (J. Audet), E. Dubois a étudié dans son mémoire de thèse [?, ?, ?] avec l’aide de C. Vaissade de l’UTC et B. Rousselet des méthodes d’optimisation globale en acoustique sous-marine; elle a considéré d’une part l’optimisation

– de signaux acoustiques temporels de revêtements multicouches élastiques ou piezo-élastiques;

– d’autodirecteurs de torpilles en terme de directivité d’antennes acoustiques. Nous donnons quelques indications sur ce dernier cas; l’antenne est constituée d’un assemblage d’antennes élémentaires constituées de transducteurs. Chaque transducteur de numéro i a une directivié élémentaire:

D_{I}(θ, ϕ) = |\frac{p(θ, ϕ, r)}{p_{max}(r)}|^{2}  (2)

où θ, ϕ, r sont les coordonnées sphériques du point où l’on évalue la directivité et p est la pression acoustique. Comme l’on ne considère cette directivité pour r grand (en champ lointain), on dispose d’une formule explicite pour la directivité de l’antenne:

D(θ, ϕ) = \frac{|∑_{I} D_{I}(θ, ϕ)A_{I}e^{i(kR_{I}+ϕ_{I})}|^{2}}{max_{θ,ϕ} |∑_{I} D_{I}(θ, ϕ)A_{I}e^{i(kR_{I}+ϕ_{I})}|^{2}}  (3)

Avec A_{I}, ϕ_{I} amplitude et phase du signal électrique appliqué au transducteur I. La directivité élémentaire est calculée a priori (par exemple avec des éléments finis); c’est une quantité délicate à quantifier car il faut tenir compte de l’environement fluide et solide (peau qui isole le transducteur de l’élément fluide).

Les variables de conception sont ici les amplitudes A_{I}. La fonction objectif à minimiser:

J_{1} = \frac{∫_{−90^{0}}^{+90^{0}} ∫_{−90^{0}}^{+90^{0}} D(θ, ϕ)dθdϕ}{∫_{−θ_{3}}^{+θ_{3}} ∫_{−θ_{3}}^{+θ_{3}} D(θ, ϕ)dθdϕ}  (4)

avec des contraintes pour éviter la remontée des lobes secondaires; par exemple D(θ, ϕ) ≤ Rej. pour

θ_{3} ≤ |θ| ≤ θ_{c}  (5)
θ_{3} ≤ |ϕ| ≤ θ_{c}  (6)

(7)

Quelques paramètres retenus pour la résolution efective:

– nombre de transducteurs: 76

– ’température initiale’: T = 10^{4}

– nombre d’ évaluations de fonctions: 10^{5}

– nombre de possibilités pour les variables de conception discrétisées 10^{23} Le nombre d’évaluation de fonctions est raisonnable pour une fonction explicite comme celle considérée ici mais serait prohibitif pour une fonction côuteuse obtenue à travers la solution d’une EDP.

1.8 Les algorithmes génétiques

s’inspirent du phénomène biologique de l’évolution au cours de la reproduction (Holland 1975); cet algorithme travaille non pas avec une suite de valeurs des paramètres mais avec une suite d’ ensembles de valeurs, appelé populations; c’est dans cette population que s’effectuent diverses opérations d’inspiration biologique (mutation, croisement et sélection); Les difficultés sont dans la représentation des données du problème, l’adaptation des opérateurs biologiques au problème posé, le traitement des contraintes; les variantes de cet algorithme sont nombreuses et peuvent être vues comme des cas particuliers de programmes d’évolution dont voici une présentation algorithmique de principe.

Procédure d’évolution

i = 0

initialiser la population P(i)

évaluer P(i)

faire jusqu’à la condition d’arrêt i = i + 1 sélectionner P(i) dans P(i-1) modifier P(i) (opérateurs génétiques) évaluer P(i) fin faire fin de procédure

1.9 Conclusions d’études d’optimisation en acoustique

Des études détaillées de la thèse d’Evelyne Dubois [?], nous relevons quelques remarques générales. Nous avons considéré l’utilisation de 2 algorithmes qui commencent à se dégager: le recuit simulé et un algorithme génétique. Une abondante littérature existe. Selon livre de Michalewicz [?], il semble néanmoins que l’adaptation d’un algorithme génétique (hybrider cet algorithme ) à une classe restrainte de problèmes d’optimisation (il convient de les appeler alors programmes d’évolution) semble une voie prometteuse pour obtenir un algorithme efficace. C’est ainsi que l’abandon de la représentation et de la manipulation des variables comme chaines de bits au profit de la manipulation de nombres flotants semble être un choix bien adapté pour le cas de variables continues, X_{ad} ⊂ R^{n}; choix suggéré par C. Vaissade; l’opération de croisement de x, y est alors λx + (1 − λ)y avec λ = random[0, 1]. Le livre de Goldberg (1989) a été un guide utile pour la compréhension et la mise en oeuvre de l’algorthme génétique. Le choix des deux algorithmes retenus semble bien adapté à des critéres qui ne sont pas nécessairement différentiables et/ou définis à l’aide de variables discrètes. Dans le cas où un gradient est accessible l’utilisation d’une équation différentielle stochastique parait préférable (Suza de Cursi, [?]); ou version hybride de l’algorithme génétique [?]. Pour l’optimisation de signaux acoustiques temporels de revêtements multicouches élastiques ou piezo-élastiques, une analyse precise et efficace était a mettre en place pour la resolution du phénomène mécanique. Une approche naturelle aurait consisté à discrétiser par différences finies (ou éléments finis) les variables d’espace et par différences finies le temps; cette approche très répandue en dynamique des structures a dû être abandonnée car elle aurait donné des coûts de calcul prohibitifs; l’utilisation d’algorithmes stochatiques pour optimiser demande de l’analyser un très grand nombre de fois. Compte tenu de la forme simple du dispositif, ceci nous a amené à considerer une utilisation numérique de la transformée de Fourier ou de Laplace pour l’analyse du systeme mécanique; cette méthode très répandue en électronique et automatique nous semble innovante dans ce cadre (c.f. Dautray Lions (1985), tome 3 chapitres 14 à 20) et bien adaptée à la situation d’optimisation du système. Ceci illustre l’importance de l’interaction entre l’analyse et l’optimisation d’un système L’étude de la stabilité des solutions obtenues est important en pratique compte tenu des inévitables dispersions de réalisation industrielle. Cette stabilité n’a semble t-il pas été considérée; elle a été mise en évidence avec la nature par-

ticulière des algorithmes; pour le recuit simulé on a proposé de tenir compte de la fréquence d’apparition des niveaux de solution; pour l’algorithme génétique on a proposé d’exploiter le fait qu’à chaque itération on utilse une population et donc d’utiliser des opérateurs de moyenne; dans certaines situations un calcul approché du Hessien inspiré des algorithmes de quasi-Newton pourait permettre une réalisation complémentaire.

Il va de soi que ces travaux ne constituent qu’une première approche; d’autres algorithmes parmi ceux cités ci dessus méritent d’être comparés aux 2 algorithmes plus particulièrement considérés. L’étude de systèmes couplés dans l’analyse permettrait une prise ne compte plus fidèle de la réalité expérimentale. Du point de vue de la formulation, l’optimisation multicritère peut être une alternative intéressante dans des cas ou le choix du critère à optimiser n’est pas clair. Du point de vue de la mise en oeuvre l’utilisation du parallélisme parait particulièrement adapté aux algorithmes génétiques et pourait etre une réponse à l’important temps ce calcul nécessaire pour l’optimisation globale. Enfin l’hybridisation d’un algorithme génétique avec une classe de problèmes ou mieux le point de vue de programmes d’évolution est une voie qui reste à exploiter pour l’optimisation de systèmes complexes; voir une possibilité à la fin.

2 Equation differentielle stochastique avec recuit

2.1 Introduction.

Cette méthode s’inspire encore de la mécanique statistique; une présentation de ces méthodes peut se trouver dans Brown et Batholomew-Biggs (1989); cette méthode s’appuie sur des algorithmes de recherche locale; si l’on s’appuie sur l’algorithme du gradient, on intègre l’équation différentielle stochastique:

dX = −∇f(X)dt + ϵ(t)dw X(0) = x^{0}  (8)

où w(t) processus de Wiener. Il est bien connu en mécanique statistique que pour ϵ constant et pour t → +∞ la densité de probbilité de x(t) tend vers

cexp[−2f(x)/ϵ]  (9)

cette densité est donc concentrée autour du minimum global de f, pour ϵ petit (voir un dessin au paragraphe du recuit simulé). Dans la mise en oeuvre il convient donc de faire décroitre ϵ quand t → +∞.

2.2 Equation differentielle stochastique

On considére l’EDS:

dX_{t}^{ϵ} = −grad f(X_{t}^{ϵ}) + ϵdw_{t}  (10)
X_{0} = x_{0}  (11)

où w est un mouvement brownien standard dans ℝ^{d}. Avec des hypothèses sur f, la probabilité de transition de X_{t}^{ϵ} a une densité de probabilités p^{ϵ}(0, x_{0}, t, x) qui est solution de l’équation de Fokker-Planck:

\frac{∂}{∂t}p = \frac{1}{2}ϵ^{2}Δp + div(p gradf)  (12)

avec:

lim_{t→0} p^{ϵ}(0, x_{0}, t, x) = δ_{x_{0}}  (13)

quand t ⟼ ∞ cette densité de probabilité tend vers une densité de probabilité dite de Gibbs:

p_{∞}^{ϵ}(0, x_{0}, x) = \frac{exp[−2\frac{f(x)}{ϵ^{2}}]}{∫_{ℝ} exp[−2\frac{f(x)}{ϵ^{2}}]dx}  (14)

C’est la loi d’une variable aléatoire X_{infini}^{ϵ} On a un résultat précis (M. Duflo chapitre 7 par. 2),

Hypothèses 1 1. La fonction f est C^{2} et tend vers l’infini à l’infini; 2. Pour A, B, D, b constantes positives:

Bf − b ≤ ∥gradf∥ ≤ A(1 + f)  (15)
Δf ≤ D(∥gradf∥^{2} + 1)  (16)

3. gradf est lipschitzienne

Proposition 0.1 La diffusion solution de l’EDS a une probabilité invariante P_{∞}^{ϵ} et

∥p^{ϵ}(0, x_{0}, t, x) − P_{∞}^{ϵ}∥_{variation} ≤ ρ^{t}|1 + f(x)|  (17)

avec 0 < ρ < 1

Maintenant si l’on fait tendre ϵ vers zero, on voit facilement dans le cas d’ un seul minimum x^{∗} que cette probabilité tend vers cδ_{x^{∗}}. En fait on dispose d’un résultat précis; avec des hypothèses sur f Hwang, (1980) a montré que quand ϵ_{→0}, P_{∞}^{ϵ} tend faiblement vers P^{0} ≡ P_{∞}^{0}; cette probabilité vérifie:

P^{0}(x : f(x) = inf_{y}F (y)) = 1

. Si par exemple f a un nombre fini de points, P^{0} est concentrée sur les minima locaux et

P^{0} = ∑ c_{y}δ_{y}

avec

c_{y} = (detD^{2}f(y))^{− \frac{1}{2}} (∑(detD^{2}f(z))^{\frac{1}{2}} )^{−1}

Première idée: fixer ϵ très petit, intégrer numériquement l’EDS; [?] indique que le temps nécessaire pour approcher de l’équilibre croit exponentiellement avec 1/ϵ

2.3 Méthode du recuit

Deuxième idée (dite du recuit): on prend ϵ fonction de t avec ϵ(t) → 0 quand t → ∞; la difficulté: comment faire tendre ϵ(t) → 0 pour que la solution converge étroitement vers P^{0}? Des réponses: on trouve dans [?, ?] des réponses sous l’hypothèse principale: Si P_{∞}^{ϵ} converge étroitement vers P^{0} quand ϵ → 0 et (malheureusement)

ϵ^{2}(t) = \frac{c}{log(2 + t)}

avec c assez grand; alors:

P^{ϵ} → P_{0}

Exemple Si t = 10^{4} alors ϵ ≈ \frac{\sqrt{c}}{2} complètement imprécis! Pour des calculs numériques il faut de plus discrétiser:

X_{k+1} − X_{k} = Δt_{k}gradf(X_{k}) + ϵ(t_{k})(w_{k+1} − w_{k})

pour la stabilité on doit prendre Δt_{k} petit; l’algorithme est donc beaucoup trop lent! C’est pourquoi [?] proposent:

1. faire

2. calcul de N chemins (par exemple N = 7) avec ϵ fixé;

3. on calcule f , on supprime le plus mauvais et on dédouble un des chemins;

4. on diminue ϵ sauf si on est dans un minimum local (augmenter)

5. fin faire Ils proposent de nombreux exemples de fonctions de quelques variables avec plusieurs minimum locaux; le minimum global est trouvé après des milliers ou dizaines de milliers d’itérations.

3 Autres approches

3.1 Diagnostics et remèdes

L’approche avec cette EDS repose sur l’idée de rajouter une perturbation gaussienne à l’algorithme du gradient; or dans le cas de fonctions convexes, cet algorithme est déjà trop lent! De plus la recherche 1D est importante; ici absente. De plus il mélange deux méthodes: Explorer l’espace pour se mettre dans le bassin d’attraction du minimum global; Calculer avec précision ce minimum global; Informations sur les minumums locaux. D’où l’idée d’un algorithme conceptuel:

– Utiliser des tirages aléatoires pour explorer où se trouvent les bassins d’attraction des minima locaux.

– Utiliser un algorithme efficace de programmation mathématique pour préciser les minima locaux et leur bassin d’attraction.

3.2 Algorithme d’élimination de domaines

Voici un algorithme présenté dans [?, ?]; Le principe est le suivant:

– Explorer l’espace à l’aide de tirages aléatores suivant une loi uniforme;

– On élimine le point engendré si il est proche d’un minimum local, d’un autre point de départ ou d’un point déjà rejeté.

– Si le point n’est pas rejeté on fait une recherche locale avec un bon algo-

rithme de programmation mathematique. Notations:

– X_{∗} minimum locaux trouvés;

– X_{0} points de départ admissible sutilisés;

– X_{r} points rejetés.

E 1: Initialiser X_{∗}, X_{0}, X_{r}; c_{i} = 0 pour i = 1, ..., 4 Iterations globales: Faire pour i=1,iterglobalmax E 2: Si critère d’arrêt est satisfait alors arrêt sinon tirage aléatoire de x^{e} ∈ X_{b} fin si

E 3:Si x^{e} proche de X_{∗} ou X_{0} alors mettre x^{e} ∈ X_{r}; c_{1} = c_{1} + 1 ; reprendre Iterations globales sinon si x^{e} proche de X_{r}, alors c_{2} = c_{2} + 1 reprendre Iterations globales sinon si x^{e} proche d’une trajectoire, alors ajouter x^{e} ∈ X_{r}; c_{1} = c_{1} + 1 ; reprendre Iterations globales sinon ajouter x^{e} ∈ X_{0}; c_{3} = c_{3} + 1 poser x^{0} = x^{e} fin si

E4:Iterations locales:

Faire M itérations locales  a partir de x^{0}, on obtient x^{M};

E5:Si x^{M} est un minimum local alors noter x^{∗} = x^{M} le rajouter à X_{∗}; c_{4} = c_{4} + 1; noter combien de fois x^{∗} est obtenu; reprendre itérations globales sinon Si x^{M} proche de X_{0}: alors rajouter à X_{r}; c1 = c_{1} + 1 reprendre itérations globales sinon si x^{M} proche de X_{r} alors c_{2} = c_{2} + 1 et reprendre itérations globales sinon si x^{M} proche de trajectoire alors rajouter x^{M} ∈ X_{r}; c_{1} = c_{1} + 1 reprendre itérations globales sinon reprendre itérations locales fin si

fin faire Iterations locales fin faire Iterations globales

3.3 Nouveaux algorithmes

Objectifs: algorithmes adaptés à des problèmes de grandes tailles avec contraintes dans ℝ^{d} avec une version parallèle.

3.3.1 Recuit simulé et élimination de domaines

début Procédure Recuit simulé et élimination de domaines j = 0 initialiser température T choisir au hasard un point initial x^{0} faire jusqu’à ce que critère d’arret satisfait

faire jusqu’à ce que condition de changement de température satisfaite

choisir au hasard un nouveau point x au voisinage de x^{0};

si x proche de X_{∗}, X_{0}, X_{r} alors Eliminer ce point mettre dans X_{r} fin si Si f(x^{0}) ≤ f(x) alors x^{0} = x appeler procedure minimisation locale(x^{0})

sinon si random[0 , 1] < exp((f(x) − f(x^{0}))/T)alors x^{0} = x appeler procedure minimisation locale(x^{0}) fin si fin si fin faire T = g(T, j); j = j + 1 fin faire fin de procédure

procedure minimisation locale(x^{0}) Faire min. locale; on trouve x^{M} fin faire si x^{M} proche de X_{∗}, X_{0}, X_{r} alors Eliminer ce point mettre dans X_{r} sinon x^{0} = x^{M} fin si

3.3.2 Recuit -evolutionnaire avec élimination de domaines

Le cadre de principe est celui d’un algorithme d’évolution dans lequel les algorithmes génétiques comprennent une mutation particulière effectuée sur une partie de la population: procédure mutation recuit avec élimination de domaines(P op, P op_{mute}, p_{m}) Faire pour chaque x ∈ P op Si random[0, 1] ≥ p_{m} alors appeler procédure recuit avec élimination de domaines avec x fin si fin faire Inconvénient: place mémoire pour X_{0}, X_{∗}, X_{r}.

4 Conclusion

Les algorithmes d’optimisation globale sont déjà anciens; ils deviennent utilisables pour résoudre des problèmes de sciences de l’ingénieur; cependant de nombreux progrès sont à faire pour résoudre des problèmes complexes en un temps raisonable.

Références

[AGR98] H. Attouch, X. Goudou, and P. Redont. Te heavy ball with friction method. Technical report, Univesité de Montpellier, 1998.

[APPZ85] F. Aluffi-Pentini, V. Parisi, and F. Zirilli. Global optimization and stochastic differential equations. JOTA, 47(1):1–16, 1985.

[Aro] J.S. Arora. Global optimization methods for engineering design. In proc. 31st AIAA/ASME/ASCE/AHS/ASC structures, structural dynamics and material conference held in Long beach, CA, USA.

[Aze88] Robert Azencott. Simulated annealing. In Semin. Bourbaki, 40 eme Annee, Vol. 1987/88, pages 223–237. Asterisque, 1988.

[CHS87] T.S. Chiang, C.R. Hwang, and S.J. Sheu. Diffusions for global optimization in ℝ^{n}. Siam J. Control and Optimization, 25(25), 1987.

[DA96] E. Dubois and J. Audet. Global optimization of arrays by simulated annealing and genetic algorithms. In Conference in underwater defense technology, London, 1996.

[DA97] E. Dubois and J. Audet. Global time-domain optimization of multilayers by simulated annealing and genetic algorthms. In second world congress of structural and multidisciplinary optimization, 1997.

[dCC98] J.E. Souza de Cursi and M.B.S. Cortes. Continuous optimization by mixed genetic and random perturbation of the gradient method with a fixed parameter. Technical report, I.M.R. INSA Rouen, 1998?

[Dub97] E. Dubois. Méthodes d’optimisation globale appliquées à l’ acoutique sous marine. PhD thesis, Université de Nice Sophia-Antipolis, décembre 1997.

[EA96a] O. Elwakeil and J. Arora. Global optimization of structural systems using two new methods. Struct. optim., 12:1–10, 1996.

[EA96b] O. Elwakeil and J. Arora. Two algoritms for general global optimization of general nlp problems. Int. J. Numerical methods engineering, 39:3305–3325, 1996.

[EACH95] O. Elwakeil, J. Arora, A. Chalende, and C. Hsieh. Global optimization methods for engineering applications: a review. Struct. optim., 9:137– 159, 1995.

[GH86] S. Geman and C.R. Hwang. Diffusions for global optimization. Siam J. Control and Optimization, 24(5):1031–1043, 1986.

[GM91] S. Gelfand and S. Mitter. Recursive stochastic algoritms for global optimization in ℝ^{d}. SIAM J. control and Optimization, 29:999–1018, 1991.

[Gri81] A.O. Griewank. Generalized desent for global optimization. JOTA, 34:11–39, 1981.

[IC64] S. Inomata and M. Cumada. On the golf method. Bull. Electrotechnical Lab, 25(495-512), 1964.

[Jay57] E.T. Jaynes. Information theory and statistical mechanics. Phys. review, 106:620–630, 1957.

[Mic86] Michalewicz, Zbigniew. Genetic algorithms + data structures = evolution programs.3rd, rev. a. ext. ed. Springer, 1986.

[MRR98] C. Massat, C. Roques, and N. Rossel. A new approach to antenna array optimization. In Piers 98, juillet 1998.

[PdC94] M. Pogu and J.E. Souza de Cursi. Global optimization by random perturbation of the gradient method with a fixed parameter. J. of global optimization, 1994.