Dan ŞDan ŞteftefăănoiunoiuPProfesseurrofesseur
OptimisationOptimisation inspirinspirééee par la naturepar la nature
[email protected]@acse.pub.ro
http://acse.pub.ro/education/fr-ro-summer-school/http://acse.pub.ro/education/frhttp://acse.pub.ro/education/fr--roro--summersummer--schoolschool//
http://ro.linkedin.com/pub/danhttp://ro.linkedin.com/pub/dan--stefanoiu/30/bb/617stefanoiu/30/bb/617
Faculté d’Automatique et Ordinateurs
www.acs.pub.rowww.acs.pub.roDB!(!DB!(!OUJOUJ 31031253103125
Université „Politehnica“ de Bucarest
www.pub.rowww.pub.ro
11/64/64
SommaireSommaireVue gVue géénnéérale sur les techniques d'optimisationrale sur les techniques d'optimisation
Optimisation Optimisation àà stratstratéégie d'gie d'éévolutionvolution
Optimisation par colonies de fourmisOptimisation par colonies de fourmis
22
99
2020
Optimisation par essaims particulairesOptimisation par essaims particulaires 2727
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131
Optimisation par luciolesOptimisation par lucioles 3535
Optimisation par chauvesOptimisation par chauves--sourissouris 3939
Optimisation par abeillesOptimisation par abeilles 4747
Optimisation harmonique (Mozartienne)Optimisation harmonique (Mozartienne) 5656
ConclusionConclusion 6363
max
22/64/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131
Problème d'optimisationProblProblèème d'optimisationme d'optimisation
opt
a.c.:
a
f∈
⎡⎢⎢ ≤⎧⎢ ⎨ =⎢ ⎩⎣
x(x)
g(x) 0h(x) 0
D
critcritèère (d'optimisation)re (d'optimisation)(fonction) co(fonction) coûûtt
fitnessfitnessddéécisioncisionetc.etc.
minvariable (d'optimisation)variable (d'optimisation)
point/noeud (d'optimisation)point/noeud (d'optimisation)éétattat
variable de dvariable de déécisioncisionetc.etc.
domaine d'admissibilitdomaine d'admissibilitéénx
a ⊆D R• usuellement:usuellement:
scalair(e)scalair(escalair(e))
"avec contraintes""avec contraintes"((subjectsubject to)to)
contrainte(s) de type incontrainte(s) de type inéégalitgalitéé: nx ng→g R R• usuellement:usuellement:
contrainte(s) de type contrainte(s) de type éégalitgalitéé: nx nh→h R R• usuellement:usuellement:
Linéaire ou non linéaireLinLinééaire ou non linaire ou non linééaireaire
Vue générale sur les techniques d'optimisationVue générale sur les techniques d'optimisation
ExemplesExemplesExemples
{ }opt
a.c.:
a
T
∈
⎡ +⎢⎢ ≤⎧⎢ ⎨⎢ ≥⎩⎣
xc x d
Ax bx 0
D
Linéaire / AffineLinLinééaire / Affineaire / Affine
{ }
min max
min
a.c.:
a
T T
∈⎡ + +⎢⎢ ≤⎧⎢ ⎨ ≤ ≤⎢ ⎩⎣
xx Px q x r
Ax bx x x
D
QuadratiqueQuadratiqueQuadratique0≥P
2 2
,max
a.c.: e ln( ) e
a∈
⎡ ⎧ ⎫⎪ ⎪⎢ ⎨ ⎬⎢ ⎪ ⎪⎩ ⎭⎢
≤ +⎢⎣
x
x
x d
x d
x
D
Non linéaireNon linNon linééaireaire
Objectif:Objectif: Trouver le point d'optimum global et son coût avec une précision suffisante.Trouver le point d'optimum global et son coTrouver le point d'optimum global et son coûût t avec une pravec une préécision suffisantecision suffisante..
En cours de parution
En cours de En cours de parutionparution
33/64/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Vue générale sur les techniques d'optimisationVue générale sur les techniques d'optimisation
ExactesExactes MMéétaheuristiquestaheuristiques
En françaisEn franEn franççaisais
Catégories de méthodes d'optimisationCatCatéégories de mgories de mééthodes d'optimisationthodes d'optimisation
En françaisEn franEn franççaisais
201220122012
201320132013
En anglaisEn anglEn anglaisais
201420142014
201420142014
En anglaisEn anglEn anglaisais
44/64/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131
Techniques exactes d'optimisationTechniquesTechniques exactesexactes d'optimisationd'optimisationVue générale sur les techniques d'optimisationVue générale sur les techniques d'optimisation
Le critère doit être assez lissé, très peu affecté par des bruits.Le critLe critèère doit être assezre doit être assez lisslisséé, tr, trèès peu affects peu affectéé par des bruits.par des bruits.
pf ∈C
• Usuellement, le critUsuellement, le critèère est au moins re est au moins une fois dune fois déérivable. rivable.
p ∗∈N
• Le terme Le terme "exactes""exactes" est, en fait, est, en fait, inexactinexact, car ces , car ces techniques ont pour but l'obtention d'une techniques ont pour but l'obtention d'une solution solution optimale itoptimale itéérativerative (qui approxime la solution id(qui approxime la solution idééale, ale, optimum), avec une certaine proptimum), avec une certaine préécision (finie). cision (finie).
Résultat fondamental
RRéésultat sultat fondamentalfondamental
Théorème de Karush-Kuhn-Tucker(TKKT)
ThThééororèèmeme de de KarushKarush--KuhnKuhn--TuckerTucker((TKKTTKKT))
Programmation linProgrammation linééaireaire
Programmation non linProgrammation non linééaireaire
Programmation dynamiqueProgrammation dynamiqueRRééseaux de seaux de HopfieldHopfield & r& rééseaux de neuronesseaux de neuronesOptimisation par Moindres CarrOptimisation par Moindres CarrééssOptimisation des systOptimisation des systèèmes dynamiquesmes dynamiques
Optimisation des systOptimisation des systèèmes de grandes dimensionsmes de grandes dimensions
• Lagrange, simplexe Lagrange, simplexe
• CogginCoggin, section d'or, , section d'or, NelderNelder--MeadMead, Box, Cauchy, , Box, Cauchy, NewtonNewton--RaphsonRaphson, , GaussGauss--NewtonNewton, , FletcherFletcher--PowellPowell, , FletcherFletcher--ReevesReeves, , RosenRosen, , SeDuMiSeDuMi etc. etc.
• Euler, Euler, WeierstrassWeierstrass--ErdmannErdmann, Hamilton, , Hamilton, HamiltonHamilton--JacobiJacobi, Legendre, , Legendre, LQRLQR--LQGLQG, filtre de , filtre de KalmanKalman--BucyBucy etc.etc.
• Ritter, Ritter, RosenRosen, , BendersBenders, techniques de p, techniques de péénalisation etc.nalisation etc.
55/64/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131
Techniques métaheuristiques d'optimisationTechniquesTechniques mméétaheuristiquetaheuristiquess d'optimisationd'optimisationVue générale sur les techniques d'optimisationVue générale sur les techniques d'optimisation
Le critère a une nature fractale, étant souvent affecté par des bruits stochastiques.Le critLe critèère a une naturere a une nature fractalefractale, , éétant souvent affecttant souvent affectéé par des par des bruits stochastiquesbruits stochastiques..
• Dans ce cas, il est difficile, voire impossible, de tester la dDans ce cas, il est difficile, voire impossible, de tester la déérivabilitrivabilitéé du critdu critèère. re. • Ceci correspond aux critCeci correspond aux critèères en lien avec de donnres en lien avec de donnéées es naturellesnaturelles (r(rééelles). elles).
Beaucoup de faux optimums.Beaucoup de faux optimums.Beaucoup de faux optimums.
Problème d'optimisation granulaire
ProblProblèème d'optimisation me d'optimisation granulairegranulaire
66/64/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Vue générale sur les techniques d'optimisationVue générale sur les techniques d'optimisationComment déterminer l'optimum?Comment déterminer l'optimum?
StansilawStansilaw MarcimMarcim ULAMULAM(1916(1916--1984)1984)
en 1949en en 19491949
• InspirInspiréée par un de ses oncles, qui a gagne par un de ses oncles, qui a gagnéé et a et a perdu des fortunes aux casinos de Monteperdu des fortunes aux casinos de Monte--Carlo. Carlo.
• UtilisUtiliséée bien avant lui par e bien avant lui par NapolNapolééon Bonaparteon Bonaparte, , pour mesurer des surfaces. pour mesurer des surfaces.
Biblio: METROPOLIS N., ULAM S. - The Monte Carlo Method, Journal of the American Statistical Association, vol. 44, no. 247, pp. 335–341, 1949.
BiblioBiblio:: METROPOLIS N., METROPOLIS N., ULAMULAM S. S. -- The Monte Carlo MethodThe Monte Carlo Method, Journal of the , Journal of the American Statistical Association, vol. 44, no. 247, pp. 335American Statistical Association, vol. 44, no. 247, pp. 335––341, 1949.341, 1949.
ProcédureProcProcééduredure
Une batterie de canons tire un Une batterie de canons tire un grand nombre de boulets sur grand nombre de boulets sur le domaine d'admissibilité.le domaine d'admissibilité.On évalue le critère pour tous On évalue le critère pour tous les boulets tombés.les boulets tombés.On retient le meilleur boulet, qui On retient le meilleur boulet, qui mène mène àà la meilleure valeur du la meilleure valeur du critère et vérifie les contraintes.critère et vérifie les contraintes.
Le principe de base a étéintroduit par:Le principe de base a Le principe de base a ééttééintroduit par:introduit par:
Méthode de MonteMéthode de Monte--CarloCarlo
77/64/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Vue générale sur les techniques d'optimisationVue générale sur les techniques d'optimisationLa Méthode de Monte-CarloLa MLa Mééthode de Montethode de Monte--CarloCarlo
• Met en Met en éévidence la nvidence la néécessite d'utiliser un cessite d'utiliser un ggéénnéérateur de nombres (pseudorateur de nombres (pseudo--)al)alééatoiresatoiresàà distribution uniformedistribution uniforme. .
Est Est trtrèès inefficaces inefficace et peut engendrer un grand et peut engendrer un grand nombre d'nombre d'éévaluations du critvaluations du critèère d'optimisation.re d'optimisation.
ExempleExempleExemple Déterminer le nombre de PythagoreDDééterminer le nombre de Pythagoreterminer le nombre de Pythagore
,≅π 3 16667
3.000 boulets3.000 boulets3.000 boulets
,≅π 3 11467
6.000 boulets6.000 boulets6.000 boulets
,≅π 3 14633
12.000 boulets12.000 boulets12.000 boulets
,≅π 3 14756
18.000 boulets18.000 boulets18.000 boulets
,≅π 3 1445
24.000 boulets24.000 boulets24.000 boulets
,≅π 3 1436
30.000 boulets30.000 boulets30.000 bouletsGaspillage! Gaspillage! Gaspillage!
Procédure gloutonne!ProcProcéédure dure gloutonne!gloutonne!
((greedygreedy))
8/648/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Vue générale sur les techniques d'optimisationVue générale sur les techniques d'optimisationQuoi faire?Quoi faire?
Ajouter une stratégie de recherche pour l'optimum.Ajouter une stratAjouter une stratéégie de recherche pour l'optimum.gie de recherche pour l'optimum.
Éventuellement, s'inspirer de la nature. ÉÉventuellement, s'inspirer de la nature. ventuellement, s'inspirer de la nature.
… Car la nature dévoile beaucoup de mécanismes d'optimalité,……… Car la nature dCar la nature déévoile beaucoup voile beaucoup de mde méécanismes d'optimalitcanismes d'optimalitéé,,……
La nature se dévoilant a la science – Faculté de Médecine René Descartes, ParisLa nature se dLa nature se déévoilant a la sciencevoilant a la science –– FacultFacultéé de Mde Méédecine Rendecine Renéé Descartes, ParisDescartes, Paris
… quelques uns étant décrits ici:…… quelques uns quelques uns éétant dtant déécrits ici:crits ici:
MMéétaheurstiquestaheurstiques localeslocales• Ascension de la montagne Ascension de la montagne • Recherche Tabou Recherche Tabou • Recuit simulRecuit simuléé• TunnelingTunneling• GRASPGRASP
MMéétaheurstiquestaheurstiques globalesglobales• Optimisation Optimisation àà stratstratéégie d'gie d'éévolution volution
–– Algorithmes gAlgorithmes géénnéétiques tiques • Optimisation par colonie de fourmis Optimisation par colonie de fourmis • Optimisation par essaims Optimisation par essaims
particulaires particulaires • Optimisation par luciolesOptimisation par lucioles• Optimisation par chauvesOptimisation par chauves--sourissouris• Optimisation par abeillesOptimisation par abeilles• Optimisation harmoniqueOptimisation harmonique
Théorie de l'évolutionThThééororieie de l'de l'éévolutionvolution
99/64/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131
Adaptation & ÉvolutionAdaptation & Adaptation & ÉÉvolutionvolutionOptimisation Optimisation àà stratstratéégie d'gie d'éévolutionvolution
Charles Robert DARWIN Charles Robert DARWIN (1809(1809--1882)1882)
Biblio: DARWIN C. - On the Origin of Species by Means of Natural Selection, or The Preservation of Favoured Races in the Struggle for Life, John Murray Ed., London, U.K., 1859.
BiblioBiblio:: DARWIN C. DARWIN C. -- On the Origin of Species by Means of Natural SelectionOn the Origin of Species by Means of Natural Selection, or T, or The Preservation he Preservation of of FavouredFavoured Races in the Struggle for LifeRaces in the Struggle for Life, John Murray Ed., London, U.K., 1859., John Murray Ed., London, U.K., 1859.
185918591859
•Elle concerne Elle concerne chaque individuchaque individu d'une population d'êtres vivantes et se d'une population d'êtres vivantes et se passe sur une passe sur une durduréée assez re assez rééduiteduite. .
L'origine des espèces
L'origine des L'origine des espespèècesces
AdaptationAdaptation: ph: phéénomnomèène d'accommodation avec les conditions ne d'accommodation avec les conditions de vie (de l'environnement), de vie (de l'environnement), en vue de la survieen vue de la survie..
ÉÉvolutionvolution: ph: phéénomnomèène de modification des capacitne de modification des capacitéés de survie, s de survie, suite suite àà des adaptations successives aux conditions de des adaptations successives aux conditions de l'environnement, l'environnement, en vue de la perpen vue de la perpéétuation de l'esptuation de l'espèècece..•Elle concerne une Elle concerne une population entipopulation entièèrere (voire une (voire une espespèècece) d'êtres vivantes ) d'êtres vivantes
et net néécessite une cessite une durduréée assez longue, e assez longue, àà travers des gtravers des géénnéérationsrations. .
Point de
départ
Point Point de de
ddéépartpart
1010/64/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation Optimisation àà stratstratéégie d'gie d'éévolutionvolution
L'évolution d'une espèce est comme un algorithme itératif, ayant pour but d'améliorer (lire "optimiser") la qualité de la vie (comme critère naturel).L'L'éévolution d'une espvolution d'une espèèce est comme un ce est comme un algorithme italgorithme itéératifratif, ayant pour but , ayant pour but d'amd'amééliorer (lire liorer (lire "optimiser""optimiser") la ) la qualitqualitéé de la viede la vie (comme (comme critcritèère naturelre naturel).).
k 1k + 2k + L L
• Seuls Seuls les individus les plus aptes pour la reproductionles individus les plus aptes pour la reproduction peuvent assurer la peuvent assurer la perpperpéétuation de l'esptuation de l'espèèce. ce.
L'essentiel de laL'essentiel de laL'essentiel de la Théorie de l'évolutionThThééororieie de l'de l'éévolutionvolution
• La La strategiestrategie d'd'evolutionevolution est fondest fondéée sur: e sur:
La sélection naturelleLa sLa séélection naturellelection naturelle Les individus qui ne peuvent pas s'adapter sont éliminés.Les individus qui ne peuvent Les individus qui ne peuvent pas s'adapter sont pas s'adapter sont ééliminliminéés.s.
• Ils peuvent nIls peuvent nééanmoins avoir anmoins avoir des des hhééritiersritiers plus adaptables.plus adaptables.
• Le Le bagage gbagage géénnéétiquetique de chaque individu et de de chaque individu et de la population peut influencer l'la population peut influencer l'éévolution, qui, volution, qui, ààson tour, modifie ce bagage, afin d'augmenter son tour, modifie ce bagage, afin d'augmenter la vitesse d'la vitesse d'éévolution. volution.
kx
• Le Le moteur de l'moteur de l'éévolutionvolution est est le croisementle croisement entre individus, produisant des entre individus, produisant des hhééritiersritiers. . • Occasionnellement, des Occasionnellement, des mutantsmutants peuvent apparapeuvent apparaîître, pour prtre, pour prééserver server
la diversitla diversitéé de la populationde la population. .
1k+x 2k+x
Théorie de l'évolution? Quel rapport avec l'optimisation?Théorie de l'évolution? Quel rapport avec l'optimisation?
( )1kf +x( )2kf +x
( )kf x
11/6411/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation Optimisation àà stratstratéégie d'gie d'éévolutionvolutionBagage génétique?Bagage génétique?
DateDate: : 19441944
DNADNA:: any of various nucleic acids that are usually the molecular basany of various nucleic acids that are usually the molecular basis of heredity, is of heredity, are localized especially in cell nuclei, and are constructed of are localized especially in cell nuclei, and are constructed of a double helix held a double helix held together by hydrogen bonds between together by hydrogen bonds between purinepurine and and pyrimidinepyrimidine bases which project bases which project inward from two chains containing alternate links of inward from two chains containing alternate links of deoxyribosedeoxyribose and phosphate. and phosphate.
(Dolan DNA Learning Center, Cold Spring Harbor Laboratory, USA)(Dolan DNA Learning Center, Cold Spring Harbor Laboratory, USA)http://http://www.dnaftb.orgwww.dnaftb.org//
ADNADNADN
11 hydrogenhydrogen22 oxygenoxygen33 carbon in the helical phosphate ester chainscarbon in the helical phosphate ester chains44 carbon and nitrogen in the crosscarbon and nitrogen in the cross--linked linked
purinepurine and and pyrimidinepyrimidine basesbases55 phosphorusphosphorus
Double Double hélicehélice
Modèle Modèle moléculairemoléculaire
(Merriam Webster Dictionary)(Merriam Webster Dictionary)http://www.merriamhttp://www.merriam--webster.com/home.htmwebster.com/home.htm
En fait, l'évolution d'une espèce se manifeste au niveau microscopique, de l'ADN spécifique.En fait, l'En fait, l'éévolution d'une espvolution d'une espèèce se manifeste ce se manifeste au niveau microscopiqueau niveau microscopique, , de l'de l'ADNADN spspéécifique.cifique.
L'évolution et l'héréditéengendrent l'optimalité.L'L'éévolution et l'hvolution et l'héérrééditditééengendrent l'optimalitengendrent l'optimalitéé..
1212/64/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation Optimisation àà stratstratéégie d'gie d'éévolutionvolutionComment simuler le recherche de l'optimum par une Comment simuler le recherche de l'optimum par une
stratégie d'évolution?stratégie d'évolution?
John Henry HOLLAND John Henry HOLLAND ((NNéé en 1929)en 1929)
Par représentation numérique de l'ADN et de ses Par représentation numérique de l'ADN et de ses transformations évolutives.transformations évolutives.
197519751975 Algorithmes génétiquesAlgorithmes gAlgorithmes géénnéétiquestiques
Biblio: HOLLAND J.H. - Adaptation in Natural and Artificial Systems, First Edition: University of Michigan Press, U.S.A, 1975.
BiblioBiblio:: HOLLAND HOLLAND J.HJ.H. . -- Adaptation in Natural and Artificial SystemsAdaptation in Natural and Artificial Systems, , First Edition: University of Michigan Press, First Edition: University of Michigan Press, U.S.AU.S.A, 1975., 1975.
4646chromosomes chromosomes dans chaque dans chaque cellule cellule humaine.humaine.
Petit bréviaire biologiquePetit brPetit brééviaire biologiqueviaire biologique
ChromosomeChromosomeChromosome
Unique pour chaque organisme vivant.Unique pour chaque organisme vivant.Unique pour chaque organisme vivant.
Suite d'unités informationnelles, comme: bits, chiffres, lettres, noeuds d'un arbre etc.
Suite d'unités informationnelles, Suite d'unités informationnelles, comme: bits, chiffres, lettres, comme: bits, chiffres, lettres, noeuds d'un arbre etc.noeuds d'un arbre etc.
GèneGèneGène Bloc d'un chromosome.Bloc d'un chromosome.Bloc d'un chromosome.
Suite d'ADN.Suite Suite d'ADNd'ADN..
• DDééfinit une certaine caractfinit une certaine caractééristique ristique (couleur des yeux, hauteur, timbre (couleur des yeux, hauteur, timbre vocal etc.). vocal etc.).
• Sa position dans le chromosome est Sa position dans le chromosome est trtrèès importante. s importante.
Collection d'entités vivantes ou de chromosomes.Collection d'entités vivantes Collection d'entités vivantes ou de chromosomes.ou de chromosomes.
PopulationPopulationPopulation
Instance d'une population au cours de son évolution.Instance d'une population Instance d'une population au cours de son évolution.au cours de son évolution.
GénérationGénérationGénération
1313/64/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation Optimisation àà stratstratéégie d'gie d'éévolutionvolutionComment numériser l'évolution?Comment numériser l'évolution?
Par définition des opérations génétiques informatiques.Par dPar dééfinition des finition des opopéérations grations géénnéétiquestiques informatiques.informatiques.
pivotpivot
ParentsParents EnfantsEnfants
longueurlongueur
PP11GG PP11DDPP11CCPP22GG PP22DDPP22CCPP11GG PP11DDPP11CCPP11GG PP11DDPP11CCPP22GG PP22DDPP22CCPP22GG PP22DDPP22CC
CroisementCroisementCroisement
PP22CCPP11CCPP11CC
PP11GGPP22GG
PP11DDPP22DD
PP11GG PP11DDPP22CCPP22GG PP22DDPP11CCPP11GG PP11DDPP22CCPP22GG PP22DDPP11CC
• Changement des gChangement des gèènes entre chromosomes. nes entre chromosomes.
MutationMutationMutation
• Changement de l'orientation des Changement de l'orientation des unitunitéés informationnelles d'un s informationnelles d'un chromosome. chromosome. pivotspivots
Chromosome Chromosome initialinitial
Chromosome Chromosome mutmutéé
PermutationPermutationPermutation
• Changement de gChangement de gèènes nes d'un seul chromosome. d'un seul chromosome.
Opération principale, avec une probabilité élevée d'occurrence.OpOpéération principale, avec une ration principale, avec une probabilitprobabilitéé éélevlevéée d'occurrence.e d'occurrence. cP
00 00 11 11 00 11 11 00 11 11 11 00 00 11 00 11
pivotspivots
00 00 11 11 00 1111 00 1111 11 00 00 11 00 11Probabilités assez petites.ProbabilitProbabilitéés assez petites.s assez petites. mP pmP
Chromosome Chromosome initialinitial
Chromosome Chromosome ((perper)mut)mutéé
14/6414/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation Optimisation àà stratstratéégie d'gie d'éévolutionvolutionInversionInversionInversion
• Changement de succession des unitChangement de succession des unitéés informationnelles ou des gs informationnelles ou des gèènes nes d'un chromosome. d'un chromosome.
longueurlongueurpivotpivot
Chromosome Chromosome initialinitial
Chromosome Chromosome mutmutéé
… Car, en effet, il s'agit d'un type particulier de mutation.
…… Car, en effet, il s'agit Car, en effet, il s'agit d'un type particulier de d'un type particulier de mutation.mutation.
Probabilité assez petite.ProbabilitProbabilitéé assez petite.assez petite. iP
ExempleExempleExemple Définition du chromosome pour une fitness à variables entièresDDééfinition du chromosome pour une fitness finition du chromosome pour une fitness àà variables entivariables entièèresres
0,250nc∈ 0,250na∈
ChromosomeChromosomeChromosome
00 11 11 00 11 11 00 11 11 11 00 00 11 00 1100
na nc(8 bits)(8 bits) (8 bits)(8 bits)
(boulets de Napol(boulets de Napolééon)on)
Modèles ARMAModModèèles ARMA
les ARMA GènesGènesGènes
Population de chromosomesPopulation de chromosomesPopulation de chromosomes
15/6415/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation Optimisation àà stratstratéégie d'gie d'éévolutionvolution
Passer Passer àà la gla géénnéération suivanteration suivante
Construire une Construire une population initialepopulation initiale
Appliquer les opAppliquer les opéérations grations géénnéétiquestiques
SSéélectionner les reproducteurslectionner les reproducteurs
Mutation / PermutationMutation / PermutationCroisementCroisement InversionInversion
Viabiliser les hViabiliser les hééritiersritiers
Structure générale d'un Algorithme GénétiqueStructure gStructure géénnéérale d'un Algorithme Grale d'un Algorithme Géénnéétiquetique
Fitness à maximiser et domaine de rechercheFitness à maximiser et domaine de rechercheParamètres de configurationParamètres de configuration
cP mP pmP iP
16/6416/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation Optimisation àà stratstratéégie d'gie d'éévolutionvolution
OUIOUINONNON
Passer Passer àà la gla géénnéération suivanteration suivante
SSéélectionner les survivantslectionner les survivants
Remplacer les reproducteurs Remplacer les reproducteurs par les survivantspar les survivants
Structure générale d'un Algorithme GénétiqueStructure gStructure géénnéérale d'un Algorithme Grale d'un Algorithme Géénnéétiquetique
Test d’arrêtTest d’arrêt
Solution optimale: le chromosome Solution optimale: le chromosome de la population courante avec la de la population courante avec la meilleure fitnessmeilleure fitness
nombre maximum de gnombre maximum de géénnéérationsrationsfacteur maximum de surviefacteur maximum de survie
nombre maximum nombre maximum d'opd'opéérations grations géénnéétiquestiques
etc.etc.
17/6417/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation Optimisation àà stratstratéégie d'gie d'éévolutionvolutionStructure générale d'un Algorithme GénétiqueStructure gStructure géénnéérale d'un Algorithme Grale d'un Algorithme Géénnéétiquetique
Passer Passer àà la gla géénnéération suivanteration suivante
Construire une Construire une population initialepopulation initiale
Appliquer les opAppliquer les opéérations grations géénnéétiquestiques
SSéélectionner les reproducteurslectionner les reproducteurs
Mutation / PermutationMutation / PermutationCroisementCroisement InversionInversion
Viabiliser les hViabiliser les hééritiersritiers
Fitness à maximiser et domaine de rechercheFitness à maximiser et domaine de rechercheParamètres de configurationParamètres de configuration
cP mP pmP iP
(NON)(NON)
AvantagesAvantages DésavantagesDésavantages
18/6418/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation Optimisation àà stratstratéégie d'gie d'éévolutionvolutionCaractéristiques des Algorithmes GénétiquesCaractCaractééristiques des Algorithmes Gristiques des Algorithmes Géénnéétiquestiques
• Les dLes déétails d'impltails d'impléémentation des Algorithmes Gmentation des Algorithmes Géénnéétiques peuvent être trouvtiques peuvent être trouvéés dans s dans la littla littéérature scientifique, par exemple ici: rature scientifique, par exemple ici:
Biblio: MITCHELL M. - An Introduction to Genetic Algorithms, The MIT Press, Cambridge, Massachusetts, U.S.A., 1995.
BiblioBiblio:: MITCHELL M. MITCHELL M. -- An Introduction to Genetic AlgorithmsAn Introduction to Genetic Algorithms, The MIT Press, Cambridge, , The MIT Press, Cambridge, Massachusetts, U.S.A., 1995.Massachusetts, U.S.A., 1995.
STEFANOIU D., BORNE P., POPESCU D., FILIP F.G., ELKAMEL A. – Optimisation en sciences de l'ingénieur – Métaheuristiques, méthodes stochastiques et aide à la décision, Hermès-Lavoisier, Paris, France, 2014.
STEFANOIU D., BORNE P., STEFANOIU D., BORNE P., POPESCUPOPESCU D., D., FILIPFILIP F.G.F.G., , ELKAMELELKAMEL A. A. –– Optimisation en Optimisation en sciences de l'ingsciences de l'ingéénieur nieur –– MMéétaheuristiques, mtaheuristiques, mééthodes stochastiques et aide thodes stochastiques et aide àà la la ddéécisioncision, , HermHermèèss--LavoisierLavoisier, Paris, France, 2014., Paris, France, 2014.
☺☺ Plus rapides et moins gloutons que la Plus rapides et moins gloutons que la MMééthode de Montethode de Monte--Carlo. Carlo.
Configuration initiale assez difficile.Configuration initiale assez difficile.
• Il existe une stratIl existe une stratéégie de sgie de séélection des lection des solutions candidates, solutions candidates, qui simule la qui simule la sséélection naturellelection naturelle. .
• La recherche ne s'effectue pas La recherche ne s'effectue pas àà l'aveugle. l'aveugle.
☺☺ TrTrèès bien adapts bien adaptéés pour l'impls pour l'impléémentation mentation sur des machines parallsur des machines parallèèles. les.
TrTrèès sensibles aux fautes de configuration s sensibles aux fautes de configuration (surtout comme vitesse de convergence).(surtout comme vitesse de convergence).
• Beaucoup de paramBeaucoup de paramèètres tres àà prprééciser ciser ddèès le ds le déébut. but.
• Usuellement, plusieurs itUsuellement, plusieurs itéérations rations sont nsont néécessaires pour arriver a la cessaires pour arriver a la "bonne" configuration. "bonne" configuration.
TrTrèès sensibles s sensibles àà la manila manièère re d'impld'impléémentation.mentation.• Le programmeur doit être Le programmeur doit être
professionnel. professionnel.
☺☺ Assez versatiles sur la plupart des Assez versatiles sur la plupart des machines. machines.
Plus lents que d'autres algorithmes Plus lents que d'autres algorithmes inspirinspiréés par la nature.s par la nature.
☺☺ Produisent des solutions optimales pour Produisent des solutions optimales pour une palette assez grande de problune palette assez grande de problèèmes mes d'optimisation granulaire. d'optimisation granulaire.
19/6419/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation Optimisation àà stratstratéégie d'gie d'éévolutionvolution
Convergence?Convergence?
Dans la programmation évolutionnaire, il n'existe pasdes résultats généraux de convergence.Dans la programmation Dans la programmation éévolutionnaire, volutionnaire, il n'existe pasil n'existe pasdes rdes réésultats gsultats géénnééraux de convergence.raux de convergence.
Caractéristiques des Algorithmes GénétiquesCaractCaractééristiques des Algorithmes Gristiques des Algorithmes Géénnéétiquestiques
• Les Algorithmes GLes Algorithmes Géénnéétiques ont ouvert une nouvelle branche dans la conception des tiques ont ouvert une nouvelle branche dans la conception des logiciels: logiciels:
Programmation évolutionnaireProgrammation Programmation éévolutionnairevolutionnaire
Néanmoins, il existe des conjectures célèbres de convergence(Holland, Nix-Vose, Vose-Liepins etc.).NNééanmoins, il existe des anmoins, il existe des conjectures cconjectures cééllèèbres de convergencebres de convergence((HollandHolland, , NixNix--VoseVose, , VoseVose--LiepinsLiepins etc.).etc.).
En faitEn faitEn fait Si bien configure, un algorithme évolutionnaire peut converger assez rapidement vers un optimum global, dans la plupart des applications.Si bien configure, un algorithme Si bien configure, un algorithme éévolutionnaire peut converger assez volutionnaire peut converger assez rapidement vers un optimum global, dans la plupart des applicatirapidement vers un optimum global, dans la plupart des applications.ons.
Il existe pourtant des applications où un algorithme évolutionnaire échoue sans raison visible, alors qu'un autre réussit.Il existe pourtant des applications oIl existe pourtant des applications oùù un algorithme un algorithme éévolutionnaire volutionnaire ééchoue sans raison visiblechoue sans raison visible, alors qu'un autre r, alors qu'un autre rééussit.ussit.
• La convergence est influencLa convergence est influencéée par e par le compromis le compromis explorationexploration--exploitationexploitation..
ExplorationExplorationExploration
• CapacitCapacitéé d'un algorithme de couvrir d'un algorithme de couvrir une aire de recherche une aire de recherche assez largeassez large. .
ExploitationExploitationExploitation
• CapacitCapacitéé d'un algorithme de focaliser d'un algorithme de focaliser la recherche sur une la recherche sur une zone zone éétroitetroite. .
en lien avecen lien avec La diversité de la populationLa La diversitédiversité de la populationde la population
• Grande dispersion (comme fitness). Grande dispersion (comme fitness).
en lien avecen lien avec La concentration de la populationLa La concentrationconcentration de la populationde la population
• Petite dispersion (comme fitness). Petite dispersion (comme fitness).
Résultat fondamental
RRéésultat sultat fondamentalfondamental
Théorème des schémas (Holland)
ThThééororèème des me des schschéémas mas ((HollandHolland))
20/6420/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131
Fourmis naturellesFourmis naturellesFourmis naturellesOptimisation par colonies de fourmisOptimisation par colonies de fourmis
• Les fourmis sont rapidement capables de trouver Les fourmis sont rapidement capables de trouver le plus court cheminle plus court chemin du nid du nid ààune source de nourriture. une source de nourriture.
Comment?Comment?
Par stigmérie.Par Par stigmstigméérierie.. Échange d’information, par modification de l'environnement.ÉÉchange d’information, par modification de l'environnement.change d’information, par modification de l'environnement.
• Beaucoup d'animaux Beaucoup d'animaux marquent leur territoiremarquent leur territoire. . • Dans le cas des fourmis, elles utilisent des Dans le cas des fourmis, elles utilisent des
traces detraces de phphééromoneromone. . Comportement naturelComportement naturelComportement naturelLes fourmis partent dans des Les fourmis partent dans des directions choisies au hasard, en directions choisies au hasard, en déposant chacune une trace de déposant chacune une trace de phéromone sur son passage.phéromone sur son passage.
Dès que l’une d’entre elles a Dès que l’une d’entre elles a trouvé de la nourriture, elle trouvé de la nourriture, elle retourne au nid, en déposant retourne au nid, en déposant à nouveau de la phéromone.à nouveau de la phéromone.
Les fourmis ont tendance à Les fourmis ont tendance à suivre de façon privilégiée les suivre de façon privilégiée les chemins ayant la plus forte chemins ayant la plus forte concentration de phéromone.concentration de phéromone.
21/6421/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131
Fourmis artificiellesFourmis artificiellesFourmis artificiellesOptimisation par colonies de fourmisOptimisation par colonies de fourmis
• La colonie des fourmis artificielles peut rLa colonie des fourmis artificielles peut réésoudre des problsoudre des problèèmes d'optimisation dans mes d'optimisation dans lesquels le domaine d'admissibilitlesquels le domaine d'admissibilitéé est organisest organiséé comme un comme un graphe graphe éétiquettiquetéé. .
ExempleExempleExemple Réseau de villes françaisesRRééseau de villes franseau de villes franççaisesaises
PaPa
LiLi
MeMeStSt
LyLy
ReRe
BoBo
CaCa
NaNa
ToTo
PoPo
NiNiRoRo
(n(nœœud) parentud) parent
(n(nœœuds) enfantsuds) enfants
arc arc éétiquettiquetéé
ÉtiquettesÉtiquettesÉtiquettes
distancesdistancescocoûûtsts
durdurééesesdissipationsdissipations
etc.etc.
CritèreCritèreCritère Fonction qui exprime la somme des étiquettes sur des chemins dans le graphe.Fonction qui exprime la Fonction qui exprime la somme des somme des étiquettesétiquettes sur sur des cheminsdes chemins dans le graphe.dans le graphe.
Problème d'optimisationProblProblèème d'optimisationme d'optimisationTrouver le chemin qui optimise le critère.Trouver le chemin qui optimise le critère.Trouver le chemin qui optimise le critère.
• Minimiser la distance parcourue, le coMinimiser la distance parcourue, le coûût du t du voyage, la durvoyage, la duréée totale, l'e totale, l'éénergie dissipnergie dissipéée etc. e etc.
Caractéristiques des fourmis artificiellesCaractCaractééristiques des fourmis artificiellesristiques des fourmis artificiellesChaque fourmi est dotChaque fourmi est dotéée de d’’une une mméémoiremoirepropre lui permettant de garder souvenir des propre lui permettant de garder souvenir des chemins parcourus et des critchemins parcourus et des critèères affres afféérents.rents.Chaque fourmi dChaque fourmi déépose une pose une trace de trace de phphééromoneromone sur son trajet, la densitsur son trajet, la densitéé en en éétant tant ddééterminterminéée par la valeur du crite par la valeur du critèère courant.re courant.
Les fourmis peuvent être dotLes fourmis peuvent être dotéées de es de capacitcapacitéés s prpréédictivesdictives facilitant lfacilitant l’’exploration de chemins exploration de chemins non encore envisagnon encore envisagéés.s.Initialement, la colonie se distribue Initialement, la colonie se distribue quasiquasi--uniformuniforméémentment sur le nsur le nœœuds et choisit les uds et choisit les premiers trajets premiers trajets au hasardau hasard..
22/6422/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par colonies de fourmisOptimisation par colonies de fourmis
Comportement des fourmis artificiellesComportement des fourmis artificiellesComportement des fourmis artificielles
Le domaine d'admissibilité est représente par une structure arborescente, dans laquelle les arcs contiennent non seulement les étiquettes, mais aussi l'intensité courante de la trace de phéromone.
Le Le domaine d'admissibilitédomaine d'admissibilité est représente par une est représente par une structure arborescentestructure arborescente, , dans laquelle les arcs contiennent non seulement les étiquettes,dans laquelle les arcs contiennent non seulement les étiquettes, mais mais aussi l'intensité courante de la trace de phéromone.aussi l'intensité courante de la trace de phéromone.
La colonie de fourmis est une autre structure (ou collection de cellules)dont les champs sont les fourmis (artificielles).La La colonie de fourmiscolonie de fourmis est une autre est une autre structure (ou collection de cellules)structure (ou collection de cellules)dont les champs sont les fourmis (artificielles).dont les champs sont les fourmis (artificielles).
Une fourmi (artificielle) est une zone de mémoire contenant: le trajet courant sur le domaine d'admissibilité, l'intensité de la trace de phéromone et la valeur du critère sur ce trajet.
Une Une fourmi (artificielle)fourmi (artificielle) est une est une zone de mémoirezone de mémoire contenant: le contenant: le trajet trajet courantcourant sur le domaine d'admissibilité, l'sur le domaine d'admissibilité, l'intensité de la trace de intensité de la trace de phéromonephéromone et la et la valeur du critèrevaleur du critère sur ce trajet. sur ce trajet.
• Une fois arrivUne fois arrivéée sur un ne sur un nœœud, la fourmi doit choisir un de ses enfants pour avancer. ud, la fourmi doit choisir un de ses enfants pour avancer.
?
Parent nParent n
Enfant mEnfant m
• Dans ce but, la fourmi utilise les intensitDans ce but, la fourmi utilise les intensitéés s des traces existantes de phdes traces existantes de phééromone sur romone sur chaque trajet chaque trajet parentparent--enfantenfant, pour calculer la , pour calculer la probabilitprobabilitéé de toucher cet enfant. de toucher cet enfant.
n
n m n m n mn m
n l n l n ll
α β γ
α β γ
∈
τ η ϕ=
τ η ϕ∑E
> > >>
> > >
p
poids dpoids dééfinies a priorifinies a priori
1n m
n mdη =>
>
1n m
n mcϕ =>
>
n md >
n mc >
: n mτ >M
trajet trajet parentparent--enfantenfant
distancedistancecocoûûtt
intensitintensitéé mméémorismoriséée de e de la trace de phla trace de phééromoneromone
indicateurs indicateurs de probabilitde probabilitéé
0≥
• La fourmi dLa fourmi déégage de la phgage de la phééromone sur le trajet romone sur le trajet nn mm choisichoisi. .
EnfantsEnfantsnE
23/6423/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par colonies de fourmisOptimisation par colonies de fourmis
Placer les fourmis de la colonie Placer les fourmis de la colonie sur les points de dsur les points de déépartpart
Tant que le test d'arrêt n'est pas passTant que le test d'arrêt n'est pas passéé
Structure générale d'un Algorithme à fourmisStructure gStructure géénnéérale d'un Algorithme rale d'un Algorithme àà fourmisfourmis
Critère à optimiser et domaine de rechercheCritère à optimiser et domaine de rechercheParamètres de configurationParamètres de configuration
Marquer tous les arcs avec la Marquer tous les arcs avec la même intensitmême intensitéé de phde phééromoneromone
Calculer les probabilitCalculer les probabilitéés d'avancement s d'avancement pour chaque fourmi active (non bloqupour chaque fourmi active (non bloquéée)e)
DDéésactiver et msactiver et méémoriser les fourmis bloqumoriser les fourmis bloquéées es (qui ne peuvent plus avancer)(qui ne peuvent plus avancer)
nombre maximum nombre maximum de trajetsde trajets
toutes les fourmis toutes les fourmis sont bloqusont bloquééeses
tous les fourmis sur tous les fourmis sur le même cheminle même chemin
etc.etc.
24/6424/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par colonies de fourmisOptimisation par colonies de fourmis
Calculer la quantitCalculer la quantitéé de phde phééromone romone àà ddééposer par chaque fourmiposer par chaque fourmi
Tant que le test d'arrêt n'est pas passTant que le test d'arrêt n'est pas passéé
RRééactualiser les traces de phactualiser les traces de phééromone romone dans tout le domaine d'admissibilitdans tout le domaine d'admissibilitéé
ÉÉvaluer la performance de chaque fourmivaluer la performance de chaque fourmi
Structure générale d'un Algorithme à fourmisStructure gStructure géénnéérale d'un Algorithme rale d'un Algorithme àà fourmisfourmis
Faire avancer les fourmis a l'aide d'un gFaire avancer les fourmis a l'aide d'un géénnéérateur de nombres rateur de nombres pseudopseudo--alalééatoiresatoires àà distribution de probabilitdistribution de probabilitéé prprééciscisééee
Solution optimale: une fourmi (active ou Solution optimale: une fourmi (active ou bloquée) de la colonie courante avec le bloquée) de la colonie courante avec le meilleur critère sur son cheminmeilleur critère sur son chemin
LiLi
CaCa
ReRe
NaNaPoPo
BoBo RoRo
ToTo
NiNi
LyLy
StStMeMe
PaPaPaPa
LiLi
MeMeStSt
LyLy
ReRe
BoBo
CaCa
NaNa
ToTo
PoPo
NiNiRoRo
25/6425/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par colonies de fourmisOptimisation par colonies de fourmisComment réactualiser la trace de phéromone?Comment réactualiser la trace de phéromone?
On prend en compte deux phénomènes: évaporation et renforcement.On prend en compte deux phOn prend en compte deux phéénomnomèènes: nes: éévaporationvaporation et et renforcementrenforcement..
(1 ) ( )n m
n m n m n m∈
τ ← −ρ τ + Δτ∑f F
f>
> > >
facteur d'facteur d'éévaporationvaporation
ensemble des fourmis ensemble des fourmis de la colonie qui ont de la colonie qui ont parcouru le trajet en parcouru le trajet en
même tempsmême temps
quantitquantitéé de phde phééromone romone ddééposposééeepar la fourmi sur le trajetpar la fourmi sur le trajet
0
( )( )n m
n m
Qf
Δτ =ff>
>L> >
quantitquantitéé initiale de phinitiale de phééromone se trouvant romone se trouvant dans le rdans le rééservoir de la fourmiservoir de la fourmi
valeur du critvaleur du critèère, calculre, calculéée pour le chemin parcouru par e pour le chemin parcouru par la fourmi depuis son dla fourmi depuis son déépart jusqupart jusqu’’au noeud suivantau noeud suivant
Ici, le critère est à minimiser.Ici, le critIci, le critèère est re est àà minimiser.minimiser.
[0,1]∈
ExempleExempleExemple Problème du voyageur de commerceProblProblèème du voyageur de commerceme du voyageur de commerce
• Le voyageur de commerce doit visiter Le voyageur de commerce doit visiter chaque ville chaque ville une fois et une seuleune fois et une seule. .
• Il faut trouver Il faut trouver le chemin le plus courtle chemin le plus courtàà voyager. voyager.
• Initialement, les fourmis partent Initialement, les fourmis partent de toutes les villes en même de toutes les villes en même temps, temps, les traces de phles traces de phééromone romone éétant identiquestant identiques. .
• Finalement, presque toute la colonie Finalement, presque toute la colonie se dse dééplace sur le même cheminplace sur le même chemin ––celui celui optimaloptimal. .
trace forte de trace forte de phphééromoneromone
26/6426/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par colonies de fourmisOptimisation par colonies de fourmis
AvantagesAvantages DésavantagesDésavantages
Caractéristiques des Algorithmes à fourmisCaractCaractééristiques des Algorithmes ristiques des Algorithmes àà fourmisfourmis
• Les dLes déétails d'impltails d'impléémentation des Algorithmes d'optimisation par colonies de fourmismentation des Algorithmes d'optimisation par colonies de fourmispeuvent être trouvpeuvent être trouvéés dans la litts dans la littéérature scientifique, par exemple ici: rature scientifique, par exemple ici:
Biblio: COLORNI A., DORIGO M., MANIEZZO V. – Distributed Optimization by Ant Colonies, Proceedings of ECAL’91 conference, Elsevier Publishing, Paris, France, pp. 134-142, 1992.
BiblioBiblio:: COLORNICOLORNI A., A., DORIGODORIGO M., M., MANIEZZOMANIEZZO V. V. –– Distributed Optimization by Ant ColoniesDistributed Optimization by Ant Colonies, , Proceedings of ECALProceedings of ECAL’’91 conference, Elsevier Publishing, Paris, France, pp. 13491 conference, Elsevier Publishing, Paris, France, pp. 134--142, 1992.142, 1992.
STEFANOIU D., BORNE P., POPESCU D., FILIP F.G., ELKAMEL A. – Optimisation en sciences de l'ingénieur – Métaheuristiques, méthodes stochastiques et aide à la décision, Hermès-Lavoisier, Paris, France, 2014.
STEFANOIU D., BORNE P., STEFANOIU D., BORNE P., POPESCUPOPESCU D., D., FILIPFILIP F.G.F.G., , ELKAMELELKAMEL A. A. –– Optimisation en Optimisation en sciences de l'ingsciences de l'ingéénieur nieur –– MMéétaheuristiques, mtaheuristiques, mééthodes stochastiques et aide thodes stochastiques et aide àà la la ddéécisioncision, , HermHermèèss--LavoisierLavoisier, Paris, France, 2014., Paris, France, 2014.
☺☺ Plus rapides et moins gloutons que la Plus rapides et moins gloutons que la MMééthode de Montethode de Monte--Carlo et même que les Carlo et même que les Algorithmes GAlgorithmes Géénnéétiques. tiques.
Le compromis Le compromis explorationexploration--exploitationexploitation ne ne peut pas être contrôlpeut pas être contrôléé d'une manid'une manièère re directe par l'utilisateur.directe par l'utilisateur.
• La colonie de fourmis a une stratLa colonie de fourmis a une stratéégie gie de recherche basde recherche baséée sur stigme sur stigméérie. rie.
☺☺ Algorithmes assez peu sensibles aux Algorithmes assez peu sensibles aux conditions initiales et aux paramconditions initiales et aux paramèètres de tres de configuration. configuration.
Ils peuvent rIls peuvent réésoudre seulement une soudre seulement une catcatéégorie de problgorie de problèèmes d'optimisation.mes d'optimisation.
Même dans le cas des structures Même dans le cas des structures arborescentes, ils peuvent devenir trarborescentes, ils peuvent devenir trèès s lents si un nlents si un nœœud possud possèède trop d'enfants.de trop d'enfants.
• Le domaine admissible doit être Le domaine admissible doit être arborescentarborescent. .
☺☺ Chaque fourmi rChaque fourmi rééalise d'abord une alise d'abord une exploitationexploitation de son voisinage et ensuite de son voisinage et ensuite une une explorationexploration vers d'autres voisinages. vers d'autres voisinages. Leur convergence est intuitive, mais ne Leur convergence est intuitive, mais ne
peut pas être dpeut pas être déémontrmontréée rigoureusement. e rigoureusement.
☺☺ DegrDegréé éélevlevéé de parallde paralléélisme, ce qui favorise lisme, ce qui favorise les implles impléémentations sur des machines mentations sur des machines parallparallèèles ou processeurs graphiques les ou processeurs graphiques (même avec plusieurs colonies). (même avec plusieurs colonies).
• Le nombre de fourmis de la colonie Le nombre de fourmis de la colonie peut partiellement rpeut partiellement réégler ce gler ce compromis. compromis.
vvpp k
27/6427/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par essaims particulairesOptimisation par essaims particulaires
vvv
Chaque individu d'une population peut être considère comme une Chaque individu d'une population peut être considère comme une particuleparticule. . •Chaque particule se déplace dans l'espace de recherche avec une Chaque particule se déplace dans l'espace de recherche avec une vitesse instantanéevitesse instantanéeet a une et a une inertieinertie. .
•
nx∈x R
nx∈v R
Comportement cognitif et social des particulesComportement cognitif et social des particulesComportement cognitif et social des particules
La vitesse peut se modifier chaque fois qu'une nouvelle positionLa vitesse peut se modifier chaque fois qu'une nouvelle position est occupée est occupée par la particule, qui est soumise a par la particule, qui est soumise a 3 tendances3 tendances. .
•
AventureuseAventureuse
ConservatriceConservatrice
PanurgiennePanurgienne
+
vvpp,,aa k
λp,cλp,ck λp,sλp,s
k
continuer dans la continuer dans la même direction, même direction,
par par inertieinertie
changer de direction changer de direction selon sa propre selon sa propre
conscience cognitiveconscience cognitive
nouvelle vitessenouvelle vitessevitesse courantevitesse courante
éécouter l'avis des autres particules de couter l'avis des autres particules de l'essaim pour trouver une direction selon la l'essaim pour trouver une direction selon la
conscience socialeconscience sociale
facteur de facteur de mobilitmobilitéé
variance cognitivevariance cognitive
μpμpk
variance socialevariance sociale
La particule est comme une fourmi, mais plus intelligente.La particule est comme une La particule est comme une fourmi, mais fourmi, mais plus intelligenteplus intelligente..
28/6428/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par essaims particulairesOptimisation par essaims particulaires
DoncDoncDonc1
, , , ,k k k k k k kp p p p c p c p s p s+ = μ + λ + λv v v v
1,p P∀ ∈ k∀ ∈N
nombre de particules nombre de particules de l'essaimde l'essaim
indice d'itindice d'itéérationration
Facteur de mobilitéFacteur de mobilitéFacteur de mobilité
Grande inertie dans le voisinage de l'optimum et petite inertie loin de lui. Grande inertie dans le voisinage de l'optimum et petite inertieGrande inertie dans le voisinage de l'optimum et petite inertie loin de lui. loin de lui.
Opposé a l'inertie.OpposOpposéé a l'a l'inertieinertie..
1k kp pμ = −η ( ) ( )
( ) ( )t
o
po,
t ,, op pt k
kp
kp
k
pp
pkf f
f f
−η =
−x
x
x
x
meilleuremeilleure position de la particuleposition de la particule
, [0,1]k kp pμ η ∈
pirepire position de la particuleposition de la particule
Par rapport a un critère qui doit être maximisé.
Par rapport a un critPar rapport a un critèère qui doit être re qui doit être maximismaximiséé..
Vitesse de la tendance conservatrice
Vitesse de la tendance Vitesse de la tendance conservatriceconservatrice
opt,
,,
kpk
p c k
kp
p cT−
=Δ
xv
x durée de retour à sa durée de retour à sa meilleure positionmeilleure position
opt,kp
kpx x>
À choisir/calculer. ÀÀ choisir/calculer. choisir/calculer.
Vitesse de la tendance panurgienne
Vitesse de la tendance Vitesse de la tendance panurgiennepanurgienne
opt
,,
,kp
k mpk
p s kp sT
−=
Δ
x xv E
durée de migration durée de migration vers la meilleure vers la meilleure
position communiquée position communiquée par les informatricespar les informatrices
opt,kp
kkpx x
E>
À choisir/calculer. ÀÀ choisir/calculer. choisir/calculer.
Variance cognitiveVariance Variance cognitivecognitive
, [0,2]kp cλ ∈
, , 1.19k kp c p sλ = λ =• usuellement:usuellement: k
pE
Variance socialeVariance Variance socialesociale
, [0,2]kp sλ ∈
InformatricesInformatricesOn peut les calculer de manière adaptative. On peut les calculer de maniOn peut les calculer de manièère adaptative. re adaptative.
29/6429/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par essaims particulairesOptimisation par essaims particulairesMécanisme d'optimisation avec particulesMMéécanisme d'optimisation avec particulescanisme d'optimisation avec particules
Caractéristiques des particulesCaractCaractééristiques des particulesristiques des particulesL'objectif de la particule est de L'objectif de la particule est de se dse dééplacer placer vers un point d'optimum et d'occuper sa vers un point d'optimum et d'occuper sa positionposition..Bien que la particule ait une Bien que la particule ait une vie limitvie limitééee àà un un certain nombre de gcertain nombre de géénnéérations (itrations (itéérations), rations), sa route est continusa route est continuéée par des e par des hhééritiersritiers..
La La reproductionreproduction et la et la sséélectionlection des hdes hééritiers ritiers des particules peut s'effectuer a l'aide des des particules peut s'effectuer a l'aide des opopéérations grations géénnéétiquestiques (notamment le (notamment le croisement).croisement).Initialement, l'essaim se distribue Initialement, l'essaim se distribue quasiquasi--uniformuniforméémentment sur le domaine admissible.sur le domaine admissible.
La strategie d'évolution des particules vers le point d'optimum peut se fonder sur d'autres principes que la sélection naturelle.La strategie d'La strategie d'éévolution des particules vers le point d'optimum peut volution des particules vers le point d'optimum peut se fonder sur d'autres principes que la sse fonder sur d'autres principes que la séélection naturelle.lection naturelle.NéanmoinsNéanmoinsNéanmoins
ÉvolutionÉÉvolutionvolutionAppliquer un Appliquer un impulse au hasardimpulse au hasard à chaque particule. à chaque particule. •
1k =
passer à la passer à la génération suivantegénération suivante
Deux générations initiales différentes sont nécessaires pour démarrer la recherche de l'optimum.DeuxDeux ggéénnéérations initiales rations initiales diffdifféérentesrentes sont nsont néécessaires cessaires pour dpour déémarrer la recherche de l'optimum.marrer la recherche de l'optimum.
0k =
{ }00 1,p p P∈= xP
aD
Évaluer la vitesse initiale Évaluer la vitesse initiale de chaque particule. de chaque particule.
•1 0
00
p pp
pT−
=Δ
x xv
1,p P∀ ∈
durée de transition durée de transition (choisie au hasard)(choisie au hasard)
{ }11 1,p p P∈= xP
30/6430/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par essaims particulairesOptimisation par essaims particulaires
Comment passer a la génération suivante?Comment passer a la génération suivante?
En utilisant la vitesse instantanée, supposée constante durant la transition.En utilisant la En utilisant la vitesse instantanvitesse instantanééee, suppos, supposéée e constante durant la transitionconstante durant la transition..
1 1 1k k k kp p p pT− − −= + Δx x v
position couranteposition couranteposition suivanteposition suivante
durée de transition (choisie au hasard)durée de transition (choisie au hasard)
ÉvolutionÉÉvolutionvolutionLa population passe d'une génération a l'autre, afin de trouver La population passe d'une génération a l'autre, afin de trouver l'optimum. l'optimum. •
L'optimum est détecte a l'aide de l'agglomération des particules. L'optimum est dL'optimum est déétecte a l'aide de l'agglomtecte a l'aide de l'aggloméération des particules. ration des particules.
2k =k 1k +L
2 1 1p p p= + Δx x x 1 1k k k
p p p− −= + Δx x x 1k k k
p p p+ = + Δx x xL
terme terme correcteurcorrecteur
1,p P∀ ∈ k ∗∀ ∈N
1kp−Δx
• Usuellement, utilisUsuellement, utiliséée pour e pour viabiliser les positionsviabiliser les positions..
31/6431/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par essaims particulairesOptimisation par essaims particulairesL'essaim est un structure (ou collection de cellules) dont les champs principaux sont les particules.L'L'essaimessaim est un est un structure (ou collection de cellules)structure (ou collection de cellules) dont les champs principaux dont les champs principaux sont les particules.sont les particules.
Une particule est une zone de mémoire contenant: le trajet courant sur le domaine d'admissibilité, la meilleur et la pire de ses positions sur le trajet etc. Une Une particuleparticule est une est une zone de mémoirezone de mémoire contenant: le trajet courant sur le contenant: le trajet courant sur le domaine d'admissibilité, la meilleur et la pire de ses positionsdomaine d'admissibilité, la meilleur et la pire de ses positions sur le trajet etc. sur le trajet etc.
Hormis les particules, l'essaim doit inclure quelques champs de maintenance, pour mémoriser: la meilleure et la pire des particules avec leurs performances, la variance de la population des particules etc.
Hormis les particules, l'essaim doit inclure quelques Hormis les particules, l'essaim doit inclure quelques champs de maintenancechamps de maintenance, , pour mémoriser: la meilleure et la pire des particules avec leurpour mémoriser: la meilleure et la pire des particules avec leurs performances, s performances, la variance de la population des particules etc.la variance de la population des particules etc.
ExempleExempleExemple Trouver le prédicteur optimal dans la classe ARMATrouver le prTrouver le préédicteur optimal dans la classe ARMAdicteur optimal dans la classe ARMA
0,250nc∈ 0,250na∈
opt ?nc =opt ?na =qualité de prédictionqualité de prédiction
À maximiser. ÀÀ maximiser. maximiser.
Plusieurs zones optimales sont détectées en même temps. Plusieurs zones optimales sont dPlusieurs zones optimales sont déétecttectéées en même temps. es en même temps.
32/6432/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par essaims particulairesOptimisation par essaims particulaires
RRéépartir les particules de l'essaim sur le domaine partir les particules de l'essaim sur le domaine d'admissibilitd'admissibilitéé (uniform(uniforméément, si possible)ment, si possible)
Tant que le test d'arrêt n'est pas passTant que le test d'arrêt n'est pas passéé
Structure générale d'un Algorithme à particulesStructure gStructure géénnéérale d'un Algorithme rale d'un Algorithme àà particulesparticules
Critère à optimiser et domaine de rechercheCritère à optimiser et domaine de rechercheParamètres de configurationParamètres de configuration
Donner des impulses aux particules, Donner des impulses aux particules, pour bouger dans d'autres positionspour bouger dans d'autres positions
nombre maximum nombre maximum d'itd'itéérationsrations
nombre maximum nombre maximum de gde géénnéérationsrations
facteur de surviefacteur de survie
etc.etc.
RRééviser les tendances de chaque particuleviser les tendances de chaque particule
+
RRééactualiser la vitesse instantanactualiser la vitesse instantanééee
ConservatriceConservatrice
kpμ ,
kp cλ ,
kp sλ
AventureuseAventureuse PanurgiennePanurgienne
dispersion de dispersion de l'essaiml'essaim
33/6433/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par essaims particulairesOptimisation par essaims particulaires
Tant que le test d'arrêt n'est pas passTant que le test d'arrêt n'est pas passéé
Structure générale d'un Algorithme à particulesStructure gStructure géénnéérale d'un Algorithme rale d'un Algorithme àà particulesparticules
Calculer la position suivante de chaque particuleCalculer la position suivante de chaque particule
Viabiliser les nouvelles positionsViabiliser les nouvelles positions
ÉÉvaluer la performance de chaque valuer la performance de chaque particule et renouveler son historiqueparticule et renouveler son historique
Solution optimale: la meilleure particule Solution optimale: la meilleure particule de l'essaim et sa performance ou une de l'essaim et sa performance ou une moyenne de quelques meilleures particules moyenne de quelques meilleures particules et la performance associéeet la performance associée
Passer a la gPasser a la géénnéération suivanteration suivante
34/6434/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par essaims particulairesOptimisation par essaims particulaires
AvantagesAvantages DésavantagesDésavantages
Caractéristiques des Algorithmes à particulesCaractCaractééristiques des Algorithmes ristiques des Algorithmes àà particulesparticules
• Les dLes déétails d'impltails d'impléémentation des Algorithmes d'optimisation par essaims mentation des Algorithmes d'optimisation par essaims particulaires peuvent être trouvparticulaires peuvent être trouvéés dans la litts dans la littéérature scientifique, par exemple ici: rature scientifique, par exemple ici:
Biblio: KENNEDY J., EBERHART R.C. – Particle Swarm Optimization, Proceedings of the IEEE International Conference on Neural Networks, Piscataway, U.S.A., vol. IV, pp. 1942-1948, 1995.
BiblioBiblio:: KENNEDY J., KENNEDY J., EBERHARTEBERHART R.CR.C. . –– Particle Swarm OptimizationParticle Swarm Optimization, Proceedings of the IEEE , Proceedings of the IEEE International Conference on Neural Networks, Piscataway, U.S.A.,International Conference on Neural Networks, Piscataway, U.S.A., vol. IV, pp. 1942vol. IV, pp. 1942--1948, 1995.1948, 1995.
STEFANOIU D., BORNE P., POPESCU D., FILIP F.G., ELKAMEL A. – Optimisation en sciences de l'ingénieur – Métaheuristiques, méthodes stochastiques et aide à la décision, Hermès-Lavoisier, Paris, France, 2014.
STEFANOIU D., BORNE P., STEFANOIU D., BORNE P., POPESCUPOPESCU D., D., FILIPFILIP F.G.F.G., , ELKAMELELKAMEL A. A. –– Optimisation en Optimisation en sciences de l'ingsciences de l'ingéénieur nieur –– MMéétaheuristiques, mtaheuristiques, mééthodes stochastiques et aide thodes stochastiques et aide àà la la ddéécisioncision, , HermHermèèss--LavoisierLavoisier, Paris, France, 2014., Paris, France, 2014.
☺☺ En gEn géénnééral, plus efficaces et plus faciles ral, plus efficaces et plus faciles ààimplimpléémenter et configurer que les menter et configurer que les Algorithmes GAlgorithmes Géénnéétiques. tiques.
Pour bPour béénnééficier de tous les avantages, ficier de tous les avantages, leur implleur impléémentations nmentations néécessitent des cessitent des programmeurs professionnels .programmeurs professionnels .
• Ils peuvent s'avIls peuvent s'avéérer suprer supéérieurs en tant rieurs en tant que vitesse de convergence et que vitesse de convergence et ressources de calcul. ressources de calcul.
☺☺ Avec une initialisation exhaustive, Avec une initialisation exhaustive, l'optimum global est trl'optimum global est trèès rarement rats rarement ratéé. .
La performance de convergence dLa performance de convergence déépend pend fortement de la mafortement de la maîîtrise du compromis trise du compromis explorationexploration--exploitationexploitation..
Il est trIl est trèès difficile (voire impossible) de s difficile (voire impossible) de ddéémontrer des rmontrer des réésultats de convergence.sultats de convergence.
• La procLa procéédure numdure numéérique peut rique peut commencer commencer àà osciller entre osciller entre plusieurs optimums. plusieurs optimums.
☺☺ Pour les versions adaptatives Pour les versions adaptatives àà stratstratéégie gie d'd'éévolution, l'utilisateur peut mavolution, l'utilisateur peut maîîtriser d'une triser d'une manimanièère directe le compromre directe le compromis is exploitationexploitation--explorationexploration. .
Si le critSi le critèère d'optimisation est trop re d'optimisation est trop fractal, seuls les algorithmes amfractal, seuls les algorithmes amééliores liores peuvent aboutir (les versions primaires peuvent aboutir (les versions primaires sont assez faibles). sont assez faibles).
☺☺ Excellents pour les implExcellents pour les impléémentations sur mentations sur des machines paralldes machines parallèèles ou processeurs les ou processeurs graphiques (même avec plusieurs essaims). graphiques (même avec plusieurs essaims).
Chaque luciole est associée avec un point dans le domaine d'admissibilité.Chaque luciole est associée avec Chaque luciole est associée avec un point dans le domaine d'admissibilitéun point dans le domaine d'admissibilité..
35/6435/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par luciolesOptimisation par luciolesLucioles naturellesLucioles naturellesLucioles naturelles
• Les lucioles sont de petits colLes lucioles sont de petits colééoptoptèères volants capables de produire cycliquement res volants capables de produire cycliquement une une lumilumièère froidere froide pour une attraction mutuelle. pour une attraction mutuelle.
Comportement naturelComportement naturelComportement naturelDans la nature, les femelles peuvent imiter les signaux lumineuxDans la nature, les femelles peuvent imiter les signaux lumineuxdd’’autres espautres espèèces pour attirer les mces pour attirer les mââles qules qu’’elles capturent et elles capturent et ddéévorent.vorent.Chaque luciole est attirChaque luciole est attiréée e par les lucioles plus brillantes qupar les lucioles plus brillantes qu’’elleelle..Chaque luciole Chaque luciole se dse dééplace vers une autre, en fonction de la place vers une autre, en fonction de la manimanièère dans laquelle elle perre dans laquelle elle perççoit les signaux lumineux.oit les signaux lumineux.
LL’’attractivitattractivitéé est proportionnelle est proportionnelle àà ll’’intensitintensitéé lumineuse, lumineuse, qui qui ddéécrocroîît avec la distancet avec la distance..Les lucioles les plus brillantes Les lucioles les plus brillantes se dse dééplacent de faplacent de faççon alon alééatoireatoire..
L'intensité lumineuse peut être associée avec le critère d'optimisation.
L'intensitL'intensitéé lumineuse peut être associlumineuse peut être associéée avec e avec le critle critèère d'optimisation. re d'optimisation. Lucioles artificiellesLucioles artificiellesLucioles artificielles
L'essaim des lucioles inclut des individus asexués, l'objectif étant d'indiquerpar leurs brillance les valeurs du critère dans différentes locations.L'essaim des lucioles inclut des individus asexués, l'objectif éL'essaim des lucioles inclut des individus asexués, l'objectif étant d'tant d'indiquerindiquerpar leurs brillance par leurs brillance les valeurs du critère dans différentes locationsles valeurs du critère dans différentes locations..
La position de chaque luciole se modifie en fonction de l'intensité lumineuse des autres lucioles de l'essaim, la plus grande étant favorisée. La position de chaque luciole La position de chaque luciole se modifie en fonction de l'intensité lumineuse se modifie en fonction de l'intensité lumineuse des autres lucioles de l'essaimdes autres lucioles de l'essaim, la plus grande étant favorisée. , la plus grande étant favorisée.
Durant son vol, la luciole peut être influencée par d'autres lucioles. Durant son vol, la luciole Durant son vol, la luciole peut être influencéepeut être influencée par d'autres lucioles. par d'autres lucioles.
Distribution de LévyDistribution de LDistribution de Léévyvy
36/6436/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par luciolesOptimisation par luciolesComment "volent" les lucioles artificielles?Comment "volent" les lucioles artificielles?
Par une formule de calcul itératif de la position de chaque luciole.Par une formule de calcul itPar une formule de calcul itéératif de ratif de la positionla position de chaque luciole.de chaque luciole.
( ) ( )1, a
k k k k k k kp p p q q p+ = +β − +α φx x x x ξ D
nombre de luciolesnombre de lucioles
indice d'itindice d'itéérationration
position couranteposition courante
position suivanteposition suivante
intensitintensitéé lumineuse en lumineuse en provenance de la luciole provenance de la luciole qq, ,
perperççue par la luciole ue par la luciole ppll’’influence des autres directions influence des autres directions
que la luciole est tentque la luciole est tentéée e dd’’emprunter durant son volemprunter durant son vol
[ 1, 1]− +• tirtiréé au hasard dans au hasard dans 2
, 0expp q p qI ⎡ ⎤β = −γ −⎢ ⎥⎣ ⎦x x
distance entre distance entre deux lucioles deux lucioles
intensitintensitéélumineuse lumineuse
ididééaleale• usuellement usuellement
unitaire unitaire variation de variation de
l'attractivitl'attractivitéé de de l'essaim de lucioles l'essaim de lucioles
1
a
γ =φD
biolog
ie
biolog
ie
diamdiamèètre du domaine tre du domaine d'admissibilitd'admissibilitéé { }
,sup
aa∈
φ = −x y
x yDD
1,p P∀ ∈ k∀ ∈N
direction perturbatrice direction perturbatrice par rapport par rapport àà la direction la direction principale de la luciole principale de la luciole pp
vecteur pseudovecteur pseudo--alalééatoire, a distribution atoire, a distribution
de probabilitde probabilitéé spspéécifiquecifique
0, nxk ∈ φ⎡ ⎤⎣ ⎦ξ S
biolog
ie
( )u u−λ=pu∀ ∈R
paramparamèètre exptre expéérimental rimental [0,3]λ∈ 1.5λ =• usuellement: usuellement:
37/6437/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par luciolesOptimisation par lucioles
RRéépartir les lucioles de l'essaim sur le domaine partir les lucioles de l'essaim sur le domaine d'admissibilitd'admissibilitéé (uniform(uniforméément, si possible)ment, si possible)
Tant que le test d'arrêt n'est pas passTant que le test d'arrêt n'est pas passéé
Structure générale d'un Algorithme à luciolesStructure gStructure géénnéérale d'un Algorithme rale d'un Algorithme àà lucioleslucioles
Critère à optimiser et domaine de rechercheCritère à optimiser et domaine de rechercheParamètres de configurationParamètres de configuration
DDééterminer la luciole la plus "lumineuse" terminer la luciole la plus "lumineuse" (qui m(qui mèène ne àà la meilleure valeur du critla meilleure valeur du critèère)re)
nombre maximum nombre maximum d'itd'itéérationsrations
facteur de surviefacteur de survieetc.etc.
RRééactualiser les positions des luciolesactualiser les positions des lucioles
ÉÉvaluer les nouvelles positions que les autres lucioles valuer les nouvelles positions que les autres lucioles volant vers elle devrait occupervolant vers elle devrait occuper
Solution optimale: la luciole la plus Solution optimale: la luciole la plus brillante de l'essaim et sa performancebrillante de l'essaim et sa performance
38/6438/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par luciolesOptimisation par lucioles
AvantagesAvantages DésavantagesDésavantages
Caractéristiques des Algorithmes à luciolesCaractCaractééristiques des Algorithmes ristiques des Algorithmes àà lucioleslucioles
• Les dLes déétails d'impltails d'impléémentation des Algorithmes d'optimisation par lucioles peuvent êtmentation des Algorithmes d'optimisation par lucioles peuvent être re trouvtrouvéés dans la litts dans la littéérature scientifique, par exemple ici: rature scientifique, par exemple ici:
Biblio: YANG X.S. – Firefly algorithm for multimodal optimization, Stochastic algorithms: Foundation and applications, SAGA 2008, Lectures notes in Computer Science, no. 5792, pp. 169-178, 2009.
BiblioBiblio:: YANG YANG X.SX.S. . –– Firefly algorithm for multimodal optimization, Stochastic algoriFirefly algorithm for multimodal optimization, Stochastic algorithms: Foundation thms: Foundation and applicationsand applications, SAGA 2008, Lectures notes in Computer Science, no. 5792, pp. 1, SAGA 2008, Lectures notes in Computer Science, no. 5792, pp. 16969--178, 2009.178, 2009.
STEFANOIU D., BORNE P., POPESCU D., FILIP F.G., ELKAMEL A. – Optimisation en sciences de l'ingénieur – Métaheuristiques, méthodes stochastiques et aide à la décision, Hermès-Lavoisier, Paris, France, 2014.
STEFANOIU D., BORNE P., STEFANOIU D., BORNE P., POPESCUPOPESCU D., D., FILIPFILIP F.G.F.G., , ELKAMELELKAMEL A. A. –– Optimisation en Optimisation en sciences de l'ingsciences de l'ingéénieur nieur –– MMéétaheuristiques, mtaheuristiques, mééthodes stochastiques et aide thodes stochastiques et aide àà la la ddéécisioncision, , HermHermèèss--LavoisierLavoisier, Paris, France, 2014., Paris, France, 2014.
☺☺ En gEn géénnééral, d'une complexitral, d'une complexitéé moins moins éélevlevéée que les algorithmes d'auparavant. e que les algorithmes d'auparavant. • Il faut pourtant faire attention Il faut pourtant faire attention àà
l'impll'impléémentation, surtout dans mentation, surtout dans l'l'éévaluation de la direction valuation de la direction perturbatrice. perturbatrice.
☺☺ Avec une initialisation exhaustive, Avec une initialisation exhaustive, l'optimum global est trl'optimum global est trèès rarement rats rarement ratéé. .
L'utilisateur ne peut pas maL'utilisateur ne peut pas maîîtriser le triser le compromis compromis explorationexploration--exploitationexploitation d'une d'une manimanièère si directe que dans le cas des re si directe que dans le cas des particules.particules.
Il est trIl est trèès difficile (voire impossible) de s difficile (voire impossible) de ddéémontrer des rmontrer des réésultats de convergence.sultats de convergence.
• L'L'ééquation de renouvellement des quation de renouvellement des positions des lucioles favorise positions des lucioles favorise l'exploration au dl'exploration au déétriment de triment de l'exploitation. l'exploitation.
☺☺ Assez bons rAssez bons réésultats dans beaucoup sultats dans beaucoup d'applications, même si le critd'applications, même si le critèère est re est stochastique par nature (mieux stochastique par nature (mieux adaptadaptéés s àà ce type de critce type de critèères que res que d'autres md'autres méétaheuristiques). taheuristiques). Le dLe dééplacement des lucioles est plus placement des lucioles est plus
chaotique que celui des particules ou chaotique que celui des particules ou fourmis, ce qui limite la vitesse de fourmis, ce qui limite la vitesse de convergence. convergence. ☺☺ Bien adaptBien adaptéés aux impls aux impléémentations sur des mentations sur des
machines parallmachines parallèèles ou processeurs les ou processeurs graphiques (même avec plusieurs essaims). graphiques (même avec plusieurs essaims).
Le nombre de lucioles doit être assez Le nombre de lucioles doit être assez grand pour une bonne efficacitgrand pour une bonne efficacitéé..
39/6439/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par chauvesOptimisation par chauves--sourissourisChauves-souris naturellesChauvesChauves--souris naturellessouris naturelles
• Les petites chauvesLes petites chauves--souris se nourrissent essentiellement dsouris se nourrissent essentiellement d’’insectes quinsectes qu’’elles delles déétectent tectent par par éécholocationcholocation. .
Comportement naturelComportement naturelComportement naturelAu dAu déébut, la chauvebut, la chauve--souris survole aveuglement souris survole aveuglement ll’’espace de recherche, tout en espace de recherche, tout en éémettant des trains mettant des trains dd’’impulsions ultrasoniques, dimpulsions ultrasoniques, d’’une certaine une certaine amplitudeamplitude ((intensitintensitéé) et ) et tauxtaux ((densitdensitéé). ). Entre les trains dEntre les trains d’’impulsions, elle perimpulsions, elle perççoit les signaux oit les signaux de retour (son propre signal et, de retour (son propre signal et, ééventuellement, les ventuellement, les signaux des autres chauvessignaux des autres chauves--souris de lsouris de l’’essaim), par essaim), par éécholocation et les interprcholocation et les interprèètete..Si les signaux reSi les signaux reççus en retour ont une faible intensitus en retour ont une faible intensitéé et/ou un taux puissant, alors il est et/ou un taux puissant, alors il est trtrèès probable qus probable qu’’une proie soit dune proie soit déétecttectéée et la chauvee et la chauve--souris doit se diriger vers elle. souris doit se diriger vers elle.
• La direction et lLa direction et l’’intensitintensitéé du signal de retour leur permettent de localiser la proie du signal de retour leur permettent de localiser la proie potentielle en potentielle en directiondirection, aussi qu'en , aussi qu'en distancedistance. .
• De plus, elles ont une capacitDe plus, elles ont une capacitéé surprenante surprenante de faire trde faire trèès rapidement la diffs rapidement la difféérence entre un rence entre un obstacle et la proie. obstacle et la proie.
Au fur et Au fur et àà mesure que la chauvemesure que la chauve--souris ssouris s’’approche de la proie, elle approche de la proie, elle intensifieintensifie graduellement graduellement la la quantitquantitéé dd’’impulsionsimpulsions (le taux d(le taux d’’ultrasons) et, en même temps, ultrasons) et, en même temps, diminuediminue progressivement progressivement ll’’intensitintensitééde ces impulsionsde ces impulsions. . Si les signaux reSi les signaux reççus sont de taux trus sont de taux trèès faibles, elle continue son vol s faibles, elle continue son vol àà ll’’aveugle, sans changer aveugle, sans changer ll’’intensitintensitéé et le taux du train det le taux du train d’’ultrasons ultrasons éémis. mis.
La distance jusquLa distance jusqu’à’à la proie est estimla proie est estiméée par le par l’’effet de Dopplereffet de Doppler en en variant la frvariant la frééquence quence des ultrasons des ultrasons éémismis, sur une bande assez large. , sur une bande assez large.
directiondirection
distancedistance
( ) min max1k k kp p p p pϕ = −β ϕ +β ϕ
Chauves-souris artificiellesChauvesChauves--souris artificiellessouris artificielles
Chaque chauve-souris est associée avec un point dans le domaine d'admissibilité.Chaque chauveChaque chauve--souris est associée avec souris est associée avec un point dans le domaine d'admissibilitéun point dans le domaine d'admissibilité..
L'objectif de l'essaim des chauves-souris est d'indiquer par leurs positions les valeurs du critère dans la proximité de la meilleure proie.L'objectif de l'essaim des chauvesL'objectif de l'essaim des chauves--souris est d'souris est d'indiquerindiquer par leurs positions par leurs positions les les valeurs du critère dans la proximité de la meilleure proievaleurs du critère dans la proximité de la meilleure proie..
La position de chaque chauve souris se modifie en fonction de l'intensité et de la fréquence des ultrasons émis (par elle-même et par ses compagnons). La position de chaque chauve souris La position de chaque chauve souris se modifie en fonction de l'intensité et de la se modifie en fonction de l'intensité et de la fréquence des ultrasons émisfréquence des ultrasons émis (par elle(par elle--même et par ses compagnons). même et par ses compagnons).
40/6440/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par chauvesOptimisation par chauves--sourissouris
Comment "volent" les chauvesComment "volent" les chauves--souris artificielles?souris artificielles?
Par une formule de calcul itératif de la vitesse de chaque chauve-souris.Par une formule de calcul itPar une formule de calcul itéératif de ratif de la vitessela vitesse de chaque chauvede chaque chauve--souris.souris.
( )1 opt,k k k k kp p p p+ = + − ϕv v x xC
vitesse courantevitesse courante
nouvelle vitessenouvelle vitesse
position optimale de l'essaim position optimale de l'essaim CCdes chauvesdes chauves--sourissouris position optimale de position optimale de
la chauvela chauve--sourissouris
min max,p p⎡ ⎤∈ ϕ ϕ⎣ ⎦
• entre certaines entre certaines limites biologiques limites biologiques
1,p P∀ ∈ k∀ ∈N
nombre de chauvesnombre de chauves--sourissouris
indice d'itindice d'itéérationration
frfrééquence courante de lquence courante de l’’ultrason ultrason éémis par la chauve sourismis par la chauve souris
150 kHz≤25 kHz≥
biolog
ie
nombre tirnombre tiréé alalééatoirement atoirement dans [0,1]dans [0,1]
La manière de réglage des fréquences des chauves- souris est peu connue par les
biologistes.
La maniLa manièère de rre de rééglage glage des frdes frééquences des quences des chauveschauves-- souris est souris est peu connuepeu connue par les par les
biologistesbiologistes..
min 0%pϕ =• usuellement: usuellement:
max 100%pϕ =
Diminue.Diminue.Diminue.
(0,1)∈
1k kp pA A+ = α ⋅
41/6441/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par chauvesOptimisation par chauves--sourissouris
DoncDoncDonc ( )1 opt,k k k k kp p p p+ = + − ϕv v x xC
1,p P∀ ∈ k∀ ∈N
La vitesse de la chauveLa vitesse de la chauve--souris est souris est petite dans la proximitpetite dans la proximitéé de la proiede la proie..Elle Elle se dse déépêchepêche quand la proie se trouve quand la proie se trouve àà une une grande distancegrande distance..
direction & distance par direction & distance par rapport a la proie possiblerapport a la proie possible
Et la position?Et la position?
Similairement aux particules.Similairement aux particules.Similairement aux particules.
1 1 1k k k kp p p pT+ + += + Δx x vSi une proie a
été détectéeSi une proie a Si une proie a été détectéeété détectée
durduréée de transition tire de transition tiréée au hasarde au hasard
1,p P∀ ∈ k∀ ∈N
[ ]0,T∈• utilisutiliséée de même pour e de même pour
viabiliserviabiliser les positions les positions
1 kk k kp p p p
A+ = + ξx xSinonSinonSinon incursion alincursion alééatoireatoire ((randomrandom walkwalk))
capacitcapacitéé de perception des trains de perception des trains d'ultrasons d'ultrasons éémis par les autres mis par les autres
chauveschauves--souris de l'essaimsouris de l'essaim[ 1, 1]− +• tirtiréé au hasard dans au hasard dans
moyenne des amplitudes des moyenne des amplitudes des ultrasons ultrasons éémis par les autres mis par les autres chauveschauves--souris de l'essaimsouris de l'essaim
1,p P∀ ∈ k∀ ∈N
1
11
Pk k
qpqq p
A AP =
≠
=− ∑
biolog
ie• utilisutiliséée de même pour e de même pour
viabiliserviabiliser les positions les positions constante exprimant la vitesse constante exprimant la vitesse
relative drelative d’’attattéénuation des nuation des amplitudes des ultrasons amplitudes des ultrasons éémismis
max0, A⎡ ⎤∈ ⎣ ⎦
(0,1)∈
42/6442/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par chauvesOptimisation par chauves--sourissourisComment savoir si une proie a été détectée ou non?Comment savoir si une proie a été détectée ou non?
Par détection et réactualisation du taux des trains d'ultrasons émis.Par dPar déétection et rtection et rééactualisation du actualisation du taux des trains d'ultrasonstaux des trains d'ultrasons éémis.mis.
( )0 1 expkp pr r k= − −γ⎡ ⎤⎣ ⎦
constante exprimant la vitesse relative constante exprimant la vitesse relative dd’’augmentation des taux daugmentation des taux d’é’émissions dmissions d’’ultrasonsultrasons
biolog
ie
taux initialtaux initialAugmente.Augmente.Augmente.taux couranttaux courant
0>
La proie est détectée quand l'amplitude et le taux perçus par la chauve souris sont inférieure à l'amplitude émise, respectivement supérieur au taux émis.
La proie est La proie est ddéétecttectééee quand quand l'amplitudel'amplitude et le et le taux pertaux perççusus par la chauve souris sont par la chauve souris sont infinféérieure rieure àà l'amplitude l'amplitude éémisemise, respectivement, respectivement supsupéérieur au taux rieur au taux éémismis..
ggéénnéérréés au hasards au hasard [0,1]perpr ∈
Et les constantes?Et les constantes?
biolog
ie Il est difficile àpréciser…Il est difficile Il est difficile ààprprééciserciser……
Par défaut
Par Par défautdéfaut
0.9α = 0.9γ =
{ }0 max max
1,0.95 ,p p P
A A A∈
⎡ ⎤⊂ ⎣ ⎦
max 100A =
{ }0 7 1
1,10 ,10p p P
r − −
∈⎡ ⎤⊂ ⎣ ⎦
min 0%pϕ = max 100%pϕ =
(grandes)(grandes)
(petits)(petits)
En vue d'une viabilisation efficace des positions, les constantes doivent être adaptées a l'échelle du domaine d'admissibilité.
En vue d'une viabilisation efficace En vue d'une viabilisation efficace des positions, les constantes des positions, les constantes doivent être doivent être adaptadaptéées a l'es a l'ééchelle du chelle du domaine d'admissibilitdomaine d'admissibilitéé..
max0,perpA A⎡ ⎤∈ ⎣ ⎦
[0,1]∈1,p P∀ ∈ k∀ ∈N
43/6443/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par chauvesOptimisation par chauves--sourissouris
Tant que le test d'arrêt n'est pas passTant que le test d'arrêt n'est pas passéé
Structure générale d'un Algorithme à chauves-sourisStructure gStructure géénnéérale d'un Algorithme rale d'un Algorithme àà chauveschauves--sourissouris
Critère à optimiser et domaine de rechercheCritère à optimiser et domaine de rechercheParamètres de configurationParamètres de configuration
nombre maximum nombre maximum d'itd'itéérationsrations
facteur de surviefacteur de survieetc.etc.
Choisir au hasard les vitesses de dChoisir au hasard les vitesses de déépart des chauvespart des chauves--sourissouris
RRéépartir les chauvespartir les chauves--souris de l'essaim sur le souris de l'essaim sur le domaine d'admissibilitdomaine d'admissibilitéé (uniform(uniforméément, si possible)ment, si possible)
Choisir au hasard les amplitudes et les taux des ultrasons initiChoisir au hasard les amplitudes et les taux des ultrasons initialement alement éémismis
DDééterminer la chauveterminer la chauve--souris la plus proche d'une possible proie souris la plus proche d'une possible proie (qui m(qui mèène ne àà la meilleure valeur du critla meilleure valeur du critèère)re)
Pour chaque chauvePour chaque chauve--souris, gsouris, géénnéérer au hasard rer au hasard le taux d'ultrasons perle taux d'ultrasons perççusus
44/6444/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par chauvesOptimisation par chauves--sourissouris
Tant que le test d'arrêt n'est pas passTant que le test d'arrêt n'est pas passéé
Structure générale d'un Algorithme à chauves-sourisStructure gStructure géénnéérale d'un Algorithme rale d'un Algorithme àà chauveschauves--sourissouris
OUIOUINONNON Taux perçu Taux perçu
>>taux émis?taux émis?
(proie d(proie déétecttectéée)e)(proie pas encore d(proie pas encore déétecttectéée)e)
Choisir au hasard le facteur Choisir au hasard le facteur de frde frééquence et quence et éévaluer la valuer la
frfrééquence de l'ultrason quence de l'ultrason éémismis
RRééactualiser la vitesse vers la proieactualiser la vitesse vers la proie
RRééactualiser et viabiliser la nouvelle position de la chauveactualiser et viabiliser la nouvelle position de la chauve--sourissouris
Pour chaque chauvePour chaque chauve--sourissouris
Choisir au hasard la capacitChoisir au hasard la capacitéé de de perception de la chauveperception de la chauve--sourissouris
kpϕ
kpβ
kpξ
ÉÉvaluer l'amplitude moyenne des ultrasons valuer l'amplitude moyenne des ultrasons éémis par les autres chauves sourismis par les autres chauves souris k
pA
Conserver la vitesse de vol (Conserver la vitesse de vol (àà l'aveugle)l'aveugle)
45/6445/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par chauvesOptimisation par chauves--sourissouris
Tant que le test d'arrêt n'est pas passTant que le test d'arrêt n'est pas passéé
Structure générale d'un Algorithme à chauves-sourisStructure gStructure géénnéérale d'un Algorithme rale d'un Algorithme àà chauveschauves--sourissouris
OUIOUINONNON Ampli perçue Ampli perçue
<<ampli émise?ampli émise?
(proie d(proie déétecttectéée)e)(obstacle d(obstacle déétecttectéé))
Diminuer l'amplitude et augmenter Diminuer l'amplitude et augmenter le taux de l'ultrason le taux de l'ultrason éémismis
RRééactualiser la performance de l'essaim des chauves sourisactualiser la performance de l'essaim des chauves souris
Pour chaque chauvePour chaque chauve--sourissouris
Conserver l'amplitude et le taux Conserver l'amplitude et le taux de l'ultrason de l'ultrason éémismis
1kpr+1k
pA +
ÉÉvaluer sa performance (le critvaluer sa performance (le critèère dans la nouvelle position)re dans la nouvelle position)
GGéénnéérer au hasard l'amplitude d'ultrasons perrer au hasard l'amplitude d'ultrasons perççusus
Solution optimale: la meilleure chauveSolution optimale: la meilleure chauve--souris souris de l'essaim et sa performancede l'essaim et sa performance
46/6446/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par chauvesOptimisation par chauves--sourissouris
AvantagesAvantages DésavantagesDésavantages
Caractéristiques des Algorithmes à chauves-sourisCaractCaractééristiques des Algorithmes ristiques des Algorithmes àà chauveschauves--sourissouris
• Les dLes déétails d'impltails d'impléémentation des Algorithmes d'optimisation par lucioles peuvent êtmentation des Algorithmes d'optimisation par lucioles peuvent être re trouvtrouvéés dans la litts dans la littéérature scientifique, par exemple ici: rature scientifique, par exemple ici:
Biblio: YANG X.S. – A New Metaheuristic Bat-Inspired Algorithm, Studies in Computational Intelligence, Springer, Berlin, Germany, no. 284, pp. 65-74, 2010.
BiblioBiblio:: YANG YANG X.SX.S. . –– A New A New MetaheuristicMetaheuristic BatBat--Inspired AlgorithmInspired Algorithm, Studies in Computational , Studies in Computational Intelligence, Springer, Berlin, Germany, no. 284, pp. 65Intelligence, Springer, Berlin, Germany, no. 284, pp. 65--74, 2010.74, 2010.
STEFANOIU D., BORNE P., POPESCU D., FILIP F.G., ELKAMEL A. – Optimisation en sciences de l'ingénieur – Métaheuristiques, méthodes stochastiques et aide à la décision, Hermès-Lavoisier, Paris, France, 2014.
STEFANOIU D., BORNE P., STEFANOIU D., BORNE P., POPESCUPOPESCU D., D., FILIPFILIP F.G.F.G., , ELKAMELELKAMEL A. A. –– Optimisation en Optimisation en sciences de l'ingsciences de l'ingéénieur nieur –– MMéétaheuristiques, mtaheuristiques, mééthodes stochastiques et aide thodes stochastiques et aide àà la la ddéécisioncision, , HermHermèèss--LavoisierLavoisier, Paris, France, 2014., Paris, France, 2014.
☺☺ ComplexitComplexitéé moins moins éélevlevéée que pour les e que pour les autres algorithmes, mais plus autres algorithmes, mais plus éélevlevéée que e que pour les algorithmes pour les algorithmes àà lucioles. lucioles.
• Ce qui engendre une amCe qui engendre une améélioration de lioration de la vitesse de convergence par la vitesse de convergence par rapport aux lucioles. rapport aux lucioles.
☺☺ Avec une initialisation exhaustive et des Avec une initialisation exhaustive et des paramparamèètres de configuration bien choisis, tres de configuration bien choisis, l'optimum global est trl'optimum global est trèès rarement rats rarement ratéé. .
La maLa maîîtrise de l'utilisateur concernant le trise de l'utilisateur concernant le compromis compromis explorationexploration--exploitationexploitation reste reste faible.faible.
Il est trIl est trèès difficile (voire impossible) de s difficile (voire impossible) de ddéémontrer des rmontrer des réésultats de convergence.sultats de convergence.
• NNééanmoins elle s'est beaucoup anmoins elle s'est beaucoup amamééliorlioréée par rapport e par rapport àà l'algorithme l'algorithme avec lucioles. avec lucioles.
☺☺ Assez peu sensibles Assez peu sensibles àà la nature la nature fractale du critfractale du critèère d'optimisation. re d'optimisation.
Assez sensibles aux paramAssez sensibles aux paramèètres de tres de configuration. configuration.
☺☺ Assez bien adaptAssez bien adaptéés aux impls aux impléémentations mentations sur des machines parallsur des machines parallèèles ou processeurs les ou processeurs graphiques (même avec plusieurs essaims). graphiques (même avec plusieurs essaims).
Il faut connaIl faut connaîître assez bien les limites et tre assez bien les limites et les les ééchelles de reprchelles de repréésentation du sentation du domaine d'admissibilitdomaine d'admissibilitéé, afin d', afin d'ééviter un viter un grand nombre de viabilisations.grand nombre de viabilisations.
• Même intuitivement, la convergence Même intuitivement, la convergence n'est pas n'est pas éévidente. vidente. • Pas assez testPas assez testéés pourtant. s pourtant.
47/6447/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par abeillesOptimisation par abeillesAbeilles naturellesAbeilles naturellesAbeilles naturelles
• La population des abeilles nLa population des abeilles n’’est pas seulement caractest pas seulement caractéérisriséée par une certaine dynamique, e par une certaine dynamique, mais aussi par un mais aussi par un comportement coopcomportement coopéératifratif, fond, fondéé sur une sur une structure sociale histructure sociale hiéérarchiquerarchique. .
Comportement naturelComportement naturelComportement naturelLes Les ééclaireursclaireurs font la recherche des meilleurs sites, en font la recherche des meilleurs sites, en éévoluant voluant alalééatoirement dans latoirement dans l’’espace accessible de la ruche. espace accessible de la ruche.
• Pour lPour l’’optimisation heuristique, c'est la optimisation heuristique, c'est la population ouvripopulation ouvrièèrere des abeille qui ddes abeille qui déévoile voile un mun méécanisme d'optimalitcanisme d'optimalitéé intintééressant. ressant.
ÉclaireursÉclaireurs GlaneursGlaneurs
Deux types d'ouvriersDeux types d'ouvriersDeux types d'ouvriers
en charge de la en charge de la ddéécouverte de sites couverte de sites
de nourriturede nourriture
en charge de la collecte en charge de la collecte et du transport de la et du transport de la
nourriturenourriture
Ils retournent Ils retournent àà la ruche avec leurs la ruche avec leurs ééchantillons de rchantillons de réécoltecolte..Ils sont alors dirigIls sont alors dirigéés vers un compartiment sps vers un compartiment spéécial cial appelappeléé salle de dansesalle de danse, o, oùù chaque chaque ééclaireur doit claireur doit interprinterprééter ter la danse de la rla danse de la réécoltecolte..
ButBut DDéémontrer la richesse et la qualitmontrer la richesse et la qualitéé du nectar du nectar et du pollen sur le site des fleurs visitet du pollen sur le site des fleurs visitéé..
48/6448/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par abeillesOptimisation par abeilles
Pendant la danse, Pendant la danse, àà cause du frcause du fréétillement, ltillement, l’é’éclaireur se dclaireur se déécharge progressivement de sa rcharge progressivement de sa réécolte. colte. L'L'ééclaireur peut alors participer claireur peut alors participer àà nouveau nouveau àà une expune expéédition, soit de recherche, dition, soit de recherche, soit de transport de la nourriture.soit de transport de la nourriture.Pendant la danse, les Pendant la danse, les ééclaireurs les plus chargclaireurs les plus chargéés de s de nourriture de qualitnourriture de qualitéé attirent autour dattirent autour d’’eux deux d’’autres autres ouvriers, qui sont recrutouvriers, qui sont recrutéés ensuite en tant que glaneurs.s ensuite en tant que glaneurs.
Une grande quantité de nourriture de mauvaise qualité ou qu’une petite quantitéde nourriture d’une très bonne qualité présente peu d’intérêt pour les abeilles.Une Une grande quantitgrande quantitéé de nourriture de de nourriture de mauvaise qualitmauvaise qualitéé ou quou qu’’une une petite quantitpetite quantitééde nourriture dde nourriture d’’uneune trtrèès bonne qualits bonne qualitéé prpréésente sente peu dpeu d’’intintéérêtrêt pour les abeilles.pour les abeilles.bi
olog
ie
Chaque Chaque ééclaireur communique claireur communique àà ses glaneurs les ses glaneurs les informations concernant la direction et la distance informations concernant la direction et la distance du site des fleurs ddu site des fleurs déécouvert.couvert.
Les glaneurs partent vers le site indiquLes glaneurs partent vers le site indiquéé et et retournent retournent àà la ruche avec de la rla ruche avec de la réécolte.colte.Les glaneurs rapportant une rLes glaneurs rapportant une réécolte plus colte plus grande que la plupart des grande que la plupart des ééclaireurs claireurs deviennent deviennent ééclaireurs, alors que lclaireurs, alors que l’é’éclaireur claireur qui ne trouvent pas de site intqui ne trouvent pas de site intééressant pour ressant pour ll’’essaim des abeilles ou qui rapporte une essaim des abeilles ou qui rapporte une nourriture faible en quantitnourriture faible en quantitéé et/ou en qualitet/ou en qualitéédevient glaneur.devient glaneur.
Les abeilles peuvent s'éloigner jusqu'à 14 kmde la ruche, sans perdre la route de retour.Les abeilles peuvent s'Les abeilles peuvent s'ééloigner jusqu'loigner jusqu'àà 14 km14 kmde la ruche, de la ruche, sans perdre la route de retoursans perdre la route de retour..bi
olog
ie Grande capacitéd'exploration.
Grande capacitGrande capacitééd'exploration.d'exploration.
49/6449/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par abeillesOptimisation par abeillesLe travail des abeilles n'est pas seulement coopératif, mais aussi auto-catalytique.Le travail des abeilles n'est pas seulement Le travail des abeilles n'est pas seulement coopcoopéératif,ratif, mais aussi mais aussi autoauto--catalytiquecatalytique..
LL’’information sur les sites dinformation sur les sites d’’intintéérêt constitue une motivation pour un nombre rêt constitue une motivation pour un nombre de plus en plus grand dde plus en plus grand d’’abeilles abeilles àà participer participer àà la rla réécolte. colte. Grande capacité
d'exploitation de même.Grande capacitGrande capacitééd'exploitation de même.d'exploitation de même.Abeilles artificiellesAbeilles artificiellesAbeilles artificielles
Il est souhaitable que le domaine admissible soit délimité par un parallélépipède.Il est souhaitable que le domaine admissible soit délimitIl est souhaitable que le domaine admissible soit délimitéé par un par un parallélépipèdeparallélépipède..min max,i i ix x x⎡ ⎤∈ ⎣ ⎦
1,i nx∀ ∈
La fitness d'une abeille est définie comme suit (a partir du critère d'origine, à minimiser):La La fitnessfitness d'une abeille est définie comme suit d'une abeille est définie comme suit (a partir du critère d'origine, (a partir du critère d'origine, àà minimiserminimiser):):
À maximiser.ÀÀ maximiser.maximiser.
ÉÉclaireursclaireurs(scouts)(scouts)
Glaneurs restants Glaneurs restants ((remainingremaining foragersforagers))
Glaneurs d’élite Glaneurs d’élite ((eliteelite foragersforagers))
• RRééalisent lalisent l’’exploration de exploration de ll’’espace de recherche, afin espace de recherche, afin de trouver les points de trouver les points centraux des sites dcentraux des sites d’’intintéérêt. rêt.
• Au nombre de Au nombre de sP
• Produisent les meilleures Produisent les meilleures valeurs de la fitness sur les valeurs de la fitness sur les sites de travailsites de travail. .
• Au nombre de Au nombre de ef ef esP N M= ⋅nombre des sites nombre des sites dd’é’élite lite àà exploiterexploiter
nombre des glaneurs dnombre des glaneurs d’é’élite lite pour chaque site dpour chaque site d’é’élitelite
• Produisent une valeur assez Produisent une valeur assez grande de la fitness sur les grande de la fitness sur les autres sites exploitautres sites exploitéés que s que les sites dles sites d’é’élitelite. .
• Au nombre de Au nombre de ( )rf rf bs esP N M M= ⋅ −
nombre total des meilleurs nombre total des meilleurs sites sites àà exploiterexploiter
nombre des glaneurs restants nombre des glaneurs restants pour chaque site restantpour chaque site restant
Catégories d'abeilles artificiellesCatCatéégories d'abeilles artificiellesgories d'abeilles artificielles
1 , si ( ) 01 ( )( )1 ( ) , si ( ) 0
fff f
⎧ ≥⎪ += ⎨⎪ − <⎩
xxxx x
F
50/6450/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par abeillesOptimisation par abeillesDoncDoncDonc ( )s ef rf s ef es rf bs esP P P P P N M N M M= + + = + + −
nombre dnombre d’’abeilles de l'essaimabeilles de l'essaim
RestrictionRestrictionRestriction 0s bsP M− > Des éclaireurs (les plus faibles) peuvent ainsi être remplacés par des glaneurs avec une bonne fitness.Des Des ééclaireurs (les plus faibles) peuvent ainsi être claireurs (les plus faibles) peuvent ainsi être remplacremplacéés par des glaneurs avec une bonne fitness.s par des glaneurs avec une bonne fitness.
ButBut ÉÉviter que lviter que l’’essaim des abeilles soit piessaim des abeilles soit piééggéé dans le voisinage ddans le voisinage d’’un optimum local un optimum local et pret prééserver ainsi la server ainsi la diversitdiversitéé de lde l’’essaim.essaim.
Comment réagissent les abeilles artificielles?Comment réagissent les abeilles artificielles?
Il faut rester proche du comportement des abeilles naturelles.Il faut rester proche du comportement des abeilles naturelles.Il faut rester proche du comportement des abeilles naturelles.Initialement, le groupe des Initialement, le groupe des ééclaireurs est rclaireurs est rééparti sur lparti sur l’’espace de recherche espace de recherche pour rpour rééaliser une premialiser une premièère exploration.re exploration. sP
Calculer les valeurs de la fitness des Calculer les valeurs de la fitness des ééclaireurs cclaireurs c’’est en fait organiser la danse de la rest en fait organiser la danse de la réécolte.colte.
Les Les ééclaireurs sont ensuite classclaireurs sont ensuite classéés selon leur fitness, en ordre ds selon leur fitness, en ordre déécroissant.croissant.
Les meilleurs Les meilleurs ééclaireurs indiquent les sites qui mclaireurs indiquent les sites qui mééritent dritent d’’être exploitêtre exploitéés.s. bsM
Les autres Les autres ééclaireurs sont claireurs sont ddéégradgradééss et ils deviennent des glaneurs solitaires.et ils deviennent des glaneurs solitaires.
LL’é’élite des lite des ééclaireurs recrutent des glaneurs, pour le transport de la nourriclaireurs recrutent des glaneurs, pour le transport de la nourriture.ture.s bsP M−
Les meilleurs Les meilleurs ééclaireurs claireurs restantsrestants recrutent des glaneurs, de même.recrutent des glaneurs, de même.
Parmi les meilleurs Parmi les meilleurs ééclaireurs une claireurs une éélite lite se forme.se forme. esM
ef esN M
Les glaneurs partent vers les sites indiquLes glaneurs partent vers les sites indiquéés pour le recueil de la rs pour le recueil de la réécolte.colte.Les Les ééclaireurs dclaireurs déégradgradéés partent au hasard en solitaire pour explorer s partent au hasard en solitaire pour explorer le domaine d'admissibilitle domaine d'admissibilitéé sur d'autres sites.sur d'autres sites.
Un tel site est centrUn tel site est centréé sur le point indiqusur le point indiquéé par lpar l’é’éclaireur et associclaireur et associéé virtuellement virtuellement àà une fleur.une fleur.
( )rf bs esN M M−
L'hyper-cube peut être ajusté selon les contraintes du problème d'optimisation.L'L'hyperhyper--cubecube peut être ajustpeut être ajustéé selon les selon les contraintes du problcontraintes du problèème d'optimisation.me d'optimisation.
51/6451/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par abeillesOptimisation par abeillesAprAprèès le ds le déépart des glaneurs, les part des glaneurs, les ééclaireurs attendent le retour de la rclaireurs attendent le retour de la réécolte. colte. Tout glaneur de retour ayant une fitness supTout glaneur de retour ayant une fitness supéérieure rieure àà son son ééclaireur en attente, claireur en attente, le remplacera et l'le remplacera et l'ééclaireur devient glaneur.claireur devient glaneur.
Si, sur un site exploitSi, sur un site exploitéé, aucun glaneur n, aucun glaneur n’’est capable de dest capable de déépasser la passer la performance de son performance de son ééclaireur, alors claireur, alors le site doit être comprimle site doit être compriméé, tout , tout en gardant le nombre de glaneurs.en gardant le nombre de glaneurs.
Une fois arrivUne fois arrivéés sur leur site, les glaneurs commencent s sur leur site, les glaneurs commencent àà exploiter les fleurs dexploiter les fleurs d’’une maniune manièère alre alééatoire.atoire.
Le meilleur éclaireur peut ou non être détrôné.Le meilleur Le meilleur ééclaireur peut ou non être dclaireur peut ou non être déétrôntrônéé..
Comment délimiter un site pour l'exploitation?Comment délimiter un site pour l'exploitation?
Tout d'abord, le site est centre dans la position de son éclaireur.Tout d'abord, le site est centre dans la Tout d'abord, le site est centre dans la position de son position de son ééclaireurclaireur.. ,e ix1,i nx∀ ∈Puis, un hyper-cube habille la fleur centrale.Puis, un Puis, un hyperhyper--cubecube habillehabille la fleur centrale.la fleur centrale.
,e ix
constante connue a prioriconstante connue a priori
{ } { }min min max max, , , ,max , min ,e i e i i i e i i e ix x A x x x A x x= − ≤ ≤ + =
1,i nx∀ ∈iy
( )max min, ,1i i e i i e iy x x= γ + − γ
1,i nx∀ ∈
tire au tire au hasardhasard
[0,1]∈
max, ,
max min, ,
e i e ii
e i e i
x xx x
−γ ≠
−A A←α⋅(0,1)∈constanteconstanteSi aucune fleur visitSi aucune fleur visitéée par les glaneurs ne par les glaneurs n’’est est
capable dcapable d’’amamééliorer la fitness de lliorer la fitness de l’é’éclaireur claireur apraprèès un certain nombre de compressions, s un certain nombre de compressions, alors le site doit être abandonnalors le site doit être abandonnéé..• Les glaneurs doivent être Les glaneurs doivent être
affectaffectéés s àà un autre site, selon un autre site, selon une une distribution de probabilitdistribution de probabilitéé. .
( ) ( )( )
1,
bs
qq M
jj j p= ≠
=
∑
yy
yp
F
F1, \{ }bsq M p∀ ∈
glaneur glaneur ààrepartirrepartir
d'autres glaneurs d'autres glaneurs choisis au hasard choisis au hasard des meilleurs sitesdes meilleurs sites
52/6452/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par abeillesOptimisation par abeillesStructure générale d'un Algorithme par abeillesStructure gStructure géénnéérale d'un Algorithme par abeillesrale d'un Algorithme par abeilles
Critère à optimiser et domaine de rechercheCritère à optimiser et domaine de rechercheParamètres de configurationParamètres de configuration
RRéépartir les partir les ééclaireurs de l'essaim d'abeilles sur le claireurs de l'essaim d'abeilles sur le domaine d'admissibilitdomaine d'admissibilitéé (uniform(uniforméément, si possible)ment, si possible)
Retour des abeilles Retour des abeilles àà la ruchela ruche
ExplorationExploration du domaine par les du domaine par les ééclaireurs dclaireurs déégradgradéés, solitairess, solitaires
s bsP M− ( )ef es rf bs esN M N M M+ −
Envoyer les abeilles pour Envoyer les abeilles pour explorerexplorer et et exploiterexploiterle domaine de recherchele domaine de recherche
Abandon du siteAbandon du site
ExploitationExploitation des meilleurs sites des meilleurs sites (de l(de l’é’élite et restants)lite et restants)
Relocalisation sur Relocalisation sur un autre siteun autre site
Compression du siteCompression du site
53/6453/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par abeillesOptimisation par abeillesStructure générale d'un Algorithme par abeillesStructure gStructure géénnéérale d'un Algorithme par abeillesrale d'un Algorithme par abeilles
OUIOUINONNON
Organiser la danse de la rOrganiser la danse de la réécoltecolte
Mise Mise àà jour de ljour de l’’essaim dessaim d’é’éclaireursclaireurs
Test d’arrêtTest d’arrêt
Solution optimale: l'éclaireur de Solution optimale: l'éclaireur de l'essaim avec la meilleure fitnessl'essaim avec la meilleure fitness
nombre maximum de gnombre maximum de géénnéérationsrationsfacteur maximum de surviefacteur maximum de survie
nombre maximum de nombre maximum de sites visitsites visitééss
etc.etc.
Envoyer les abeilles pour Envoyer les abeilles pour explorerexplorer et et exploiterexploiterle domaine de recherchele domaine de recherche
54/6454/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par abeillesOptimisation par abeillesStructure générale d'un Algorithme par abeillesStructure gStructure géénnéérale d'un Algorithme par abeillesrale d'un Algorithme par abeilles
Critère à optimiser et domaine de rechercheCritère à optimiser et domaine de rechercheParamètres de configurationParamètres de configuration
RRéépartir les partir les ééclaireurs de l'essaim d'abeilles sur le claireurs de l'essaim d'abeilles sur le domaine d'admissibilitdomaine d'admissibilitéé (uniform(uniforméément, si possible)ment, si possible)
Retour des abeilles Retour des abeilles àà la ruchela ruche
s bsP M− ( )ef es rf bs esN M N M M+ −
Envoyer les abeilles pour Envoyer les abeilles pour explorerexplorer et et exploiterexploiterle domaine de recherchele domaine de recherche
Abandon du siteAbandon du site
ExploitationExploitation des meilleurs sites des meilleurs sites (de l(de l’é’élite et restants)lite et restants)
Relocalisation sur Relocalisation sur un autre siteun autre site
Compression du siteCompression du site
(NON)(NON)
ExplorationExploration du domaine par les du domaine par les ééclaireurs dclaireurs déégradgradéés, solitairess, solitaires
55/6455/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation par abeillesOptimisation par abeilles
AvantagesAvantages DésavantagesDésavantages
Caractéristiques des Algorithmes par abeillesCaractCaractééristiques des Algorithmes par abeillesristiques des Algorithmes par abeilles
• Les dLes déétails d'impltails d'impléémentation des Algorithmes d'optimisation par abeilles peuvent êtmentation des Algorithmes d'optimisation par abeilles peuvent être re trouvtrouvéés dans la litts dans la littéérature scientifique, par exemple ici: rature scientifique, par exemple ici:
Biblio: KARABOGA D. – An idea based on honey bee swarm for numerical optimization, Technical Report TROG, Ercizes University, Computer Engineering Department, 2005.
BiblioBiblio:: KARABOGAKARABOGA D. D. –– An idea based on honey bee swarm for numerical optimizationAn idea based on honey bee swarm for numerical optimization, , Technical Report Technical Report TROGTROG, , ErcizesErcizes University, Computer Engineering Department, 2005.University, Computer Engineering Department, 2005.
STEFANOIU D., BORNE P., POPESCU D., FILIP F.G., ELKAMEL A. – Optimisation en sciences de l'ingénieur – Métaheuristiques, méthodes stochastiques et aide à la décision, Hermès-Lavoisier, Paris, France, 2014.
STEFANOIU D., BORNE P., STEFANOIU D., BORNE P., POPESCUPOPESCU D., D., FILIPFILIP F.G.F.G., , ELKAMELELKAMEL A. A. –– Optimisation en Optimisation en sciences de l'ingsciences de l'ingéénieur nieur –– MMéétaheuristiques, mtaheuristiques, mééthodes stochastiques et aide thodes stochastiques et aide àà la la ddéécisioncision, , HermHermèèss--LavoisierLavoisier, Paris, France, 2014., Paris, France, 2014.
☺☺ MaMaîîtrise assez directe du compromis trise assez directe du compromis explorationexploration--exploitationexploitation. .
• En gEn géérant sagement les catrant sagement les catéégories gories d'abeilles artificielles. d'abeilles artificielles.
☺☺ Peu de paramPeu de paramèètres de configuration et tres de configuration et sensibilitsensibilitéé rrééduite aux diffduite aux difféérents choix rents choix de ces paramde ces paramèètres. tres.
ComplexitComplexitéé assez assez éélevlevéée.e.
Il est trIl est trèès difficile (voire impossible) de s difficile (voire impossible) de ddéémontrer des rmontrer des réésultats de sultats de convergence.convergence.
• Peu d'opPeu d'opéérations arithmrations arithméétiques, tiques, mais une organisation astucieuse mais une organisation astucieuse de l'espace mde l'espace méémoire est nmoire est néécessaire. cessaire.
☺☺ Bons rBons réésultats même pour des critsultats même pour des critèères res d'optimisation d'une nature trd'optimisation d'une nature trèès fractale. s fractale.
Ils peuvent converger assez lentement. Ils peuvent converger assez lentement. ☺☺ Excellents pour les implExcellents pour les impléémentations sur mentations sur des machines paralldes machines parallèèles ou processeurs les ou processeurs graphiques (même avec plusieurs graphiques (même avec plusieurs essaims). essaims).
• Intuitivement, plusieurs sites Intuitivement, plusieurs sites àà la la fois peuvent concentrer des groups fois peuvent concentrer des groups d'abeilles. d'abeilles.
• L'optimum global est trL'optimum global est trèès bien s bien approximapproximéé. .
Pour bPour béénnééficier de tous les avantages, ficier de tous les avantages, leur implleur impléémentations nmentations néécessitent des cessitent des programmeurs professionnels.programmeurs professionnels.
56/6456/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation harmonique (Mozartienne)Optimisation harmonique (Mozartienne)Chercher l'harmonie parfaite pour une composition musicale. Chercher l'harmonie parfaite pour une composition musicale. Chercher l'harmonie parfaite pour une composition musicale.
Quel rapport avec l'optimisation?...Quel rapport avec l'optimisation?...
Il existe une analogie entre les deux terminologies.Il existe une analogie entre les deux terminologies.Il existe une analogie entre les deux terminologies.
Instrument musicalInstrument musical
TonTon
Processus Processus d’optimisationd’optimisation
Improvisation musicaleImprovisation musicale
Harmonie musicaleHarmonie musicale
Qualité de l’harmonie musicaleQualité de l’harmonie musicale
Processus de Processus de composition musicalecomposition musicale
Variable de décisionVariable de décision
Valeur de la variable de décisionValeur de la variable de décision
ItérationItération
Fonction objectifFonction objectif
Valeur de la fonction objectifValeur de la fonction objectif
Wolfgang Amadeus Wolfgang Amadeus MOZART (1756MOZART (1756--1791)1791)
• Il existe une corrIl existe une corréélation surprenante entre la lation surprenante entre la MMééthode de thode de MonteMonte--CarloCarlo et la maniet la manièère non conventionnelle de laquelle re non conventionnelle de laquelle Mozart composaitMozart composait une partie de ses piune partie de ses pièèces musicales. ces musicales.
• Usuellement, Mozart devait livrer sa composition dans un Usuellement, Mozart devait livrer sa composition dans un ddéélai si courtlai si court, qu, qu’’il nil n’’avait avait pas le temps de rpas le temps de rééflflééchirchir sur le sur le ththèème musical le plus approprime musical le plus appropriéé au sujet de la commande au sujet de la commande rereççue. ue.
• NNééanmoins, la plupart des pianmoins, la plupart des pièèces musicales de Mozart sont ces musicales de Mozart sont considconsidéérréées es ggéénialesniales (donc (donc optimalesoptimales au sens artistique). au sens artistique).
{4,3}{4,3}
{3,4}{3,4}{3,1}{3,1}
{2,3}{2,3}{2,2}{2,2}{1,4}{1,4}{1,3}{1,3}{1,1}{1,1}
57/6457/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation harmonique (Mozartienne)Optimisation harmonique (Mozartienne)Et comment faisait il, Mozart?...Et comment faisait il, Mozart?...
Il disposait d'une grande boIl disposait d'une grande boîîte dans laquelle, au cours te dans laquelle, au cours du temps, il avait accumuldu temps, il avait accumuléé une une éénorme quantitnorme quantitéé de de morceaux de papier contenant de petites harmonies, morceaux de papier contenant de petites harmonies, ququ’’il pouvait combiner il pouvait combiner àà volontvolontéé. . Le nombre de ces harmonies Le nombre de ces harmonies éétait si grand, qutait si grand, qu’’il ne il ne pouvait pas faire de spouvait pas faire de séélection exhaustive. lection exhaustive.
Il Il éétalait alors les harmonies au hasard sur une grande surface, talait alors les harmonies au hasard sur une grande surface, comme dans une matrice. comme dans une matrice. Ensuite, avec un ensemble de dEnsuite, avec un ensemble de déés, il faisait s, il faisait des tirages au sort des des tirages au sort des ééllééments de cette ments de cette matrice virtuelle. matrice virtuelle.
{2,2}{2,2} {4,3}{4,3}
{1,4}{1,4} {1,1}{1,1}
{3,4}{3,4} {3,1}{3,1}
{2,3}{2,3} {1,3}{1,3}
Si lSi l’’harmonie choisie ne lui convenait pas : harmonie choisie ne lui convenait pas : • soit il la remettait dans la matrice ; soit il la remettait dans la matrice ; • soit il lui trouvait une place satisfaisante soit il lui trouvait une place satisfaisante
dans la pidans la pièèce musicale en construction ; ce musicale en construction ; • soit il faisait une soit il faisait une nouvelle harmonienouvelle harmonie, ,
improvisimprovisééee (proche de celle(proche de celle--ci), qu'il ci), qu'il éécrivait sur un morceau de papiercrivait sur un morceau de papier……
…… et qu'il ajoutait et qu'il ajoutait aux autres dans aux autres dans la bola boîîte. te.
La composition s'achève ainsi.La composition La composition s'achève ainsi.s'achève ainsi.
58/6458/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation harmonique (Mozartienne)Optimisation harmonique (Mozartienne)La recherche s'effectue a l'aide d'une matrice de tons repartis dans le domaine d'admissibilité.La recherche s'effectue a l'aide d'une La recherche s'effectue a l'aide d'une matrice de tonsmatrice de tons repartis repartis dans le domaine d'admissibilité.dans le domaine d'admissibilité.
nombre de tonsnombre de tons
( )( )
( )( )
1,1 1,2 1, 1 1, 1
2,1 2,2 2, 1 2, 2
1,1 1,2 1, 1 1, 1
,1 ,2 , 1 ,
nx nx
nx nx
H
P P P nx P nx P
P P P nx P nx P
x x x x f
x x x x f
x x x x f
x x x x f
−
−
− − − − − −
−
⎡ ⎤⇒⎢ ⎥⎢ ⎥
⇒⎢ ⎥⎢ ⎥= ⎢ ⎥⎢ ⎥⇒⎢ ⎥⎢ ⎥
⇒⎢ ⎥⎣ ⎦
x
x
x
x
L
L
MM M O M M
L
L
M
tons tons produisant produisant harmoniesharmonies
mméémoire moire harmonique harmonique
Avancer vers lAvancer vers l’’optimum du critoptimum du critèère cre c’’est est improviserimproviser avec de nouveaux tons, qui soient plus ou moins avec de nouveaux tons, qui soient plus ou moins liliéés s àà la mla méémoire harmonique. moire harmonique. La matrice La matrice changechange quand les nouveaux tons produisent des harmonies de quand les nouveaux tons produisent des harmonies de qualitqualitéé supsupéérieurerieureàà la qualitla qualitéé des tons qudes tons qu’’elle contient. elle contient.
harmonieharmonie
Improvisation?...Improvisation?...
Choisir un ton en utilisant les règles suivantes, inspirées du processus de composition musicale:Choisir un ton en utilisant les rChoisir un ton en utilisant les rèègles suivantes, gles suivantes, inspirinspiréées du processus de composition musicale:es du processus de composition musicale:• Le ton doit être choisi arbitrairement soit de la mLe ton doit être choisi arbitrairement soit de la méémoire harmonique, moire harmonique,
soit du domaine des tons. soit du domaine des tons. • Le ton ainsi choisi peut être ajustLe ton ainsi choisi peut être ajustéé dd’’une certaine maniune certaine manièère. re. • Si le ton choisi (et Si le ton choisi (et ééventuellement ajustventuellement ajustéé) a une qualit) a une qualitéé harmonique harmonique
supsupéérieure au ton le moins harmonique (dissonant) de la mrieure au ton le moins harmonique (dissonant) de la méémoire, moire, alors il peut remplacer ce ton dans la malors il peut remplacer ce ton dans la méémoire. moire.
qxy qx
59/6459/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation harmonique (Mozartienne)Optimisation harmonique (Mozartienne)
Choix d'un nouveau tonChoix d'un nouveau tonChoix d'un nouveau ton H∈y M
H∉y Mavec une probabilitavec une probabilitéé PMavec une probabilitavec une probabilitéé 1 P− M
• Chaque composante du vecteur harmonique Chaque composante du vecteur harmonique nouvellement crnouvellement créééé peut être ajustpeut être ajustéée e avec la probabilitavec la probabilitéé ( ]0,aP P P∈M M
une ligne de la une ligne de la matrice harmoniquematrice harmonique choisi au hasard du choisi au hasard du
domaine d'admissibilitdomaine d'admissibilitéé
Ajustée?...Ajustée?...
Par composantes.Par composantes.Par composantes. i i i iy y← +ξ ⋅Δω
inspiration du inspiration du compositeurcompositeur
Tire au hasard.Tire au Tire au hasard.hasard.[ 1,1]∈ −
1,i nx∀ ∈
largeur de bande maximum avec laquelle largeur de bande maximum avec laquelle le ton peut changer de frle ton peut changer de frééquencequence
ExempleExempleExemplemax min
2i i
ix x−
Δω =1,i nx∀ ∈
• Si le ton Si le ton reste inchangreste inchangéé et coet coïïncide avec un des ncide avec un des tons de la mtons de la méémoire harmonique, il vaut mieux le moire harmonique, il vaut mieux le remplacerremplacer par une combinaison des tons de cette par une combinaison des tons de cette mméémoire.moire.
avec la probabilitavec la probabilitéé 1 aP P− M
ExempleExempleExemple( )
( )1
1
Pk kp p
pP
kp
p
f
f
=
=
=∑
∑
x xy
x
Chaque ton participe avec sa qualité harmonique.Chaque ton participe avec Chaque ton participe avec sa qualitsa qualitéé harmonique.harmonique.
• Le nouveau ton remplace le ton dissonant Le nouveau ton remplace le ton dissonant de la mde la méémoire harmonique.moire harmonique.
1x
2x……
……Px
Si meilleur que celui-ci.Si meilleur Si meilleur que celuique celui--ci.ci.
Choisir un ton de la Choisir un ton de la mméémoire harmoniquemoire harmonique
Choisir un ton Choisir un ton àà l'extl'extéérieur rieur de la mde la méémoire harmoniquemoire harmonique
PM 1 P− M
60/6460/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation harmonique (Mozartienne)Optimisation harmonique (Mozartienne)
RRéépartir les tons sur le domaine d'admissibilitpartir les tons sur le domaine d'admissibilitéé(uniform(uniforméément, si possible)ment, si possible)
Tant que le test d'arrêt n'est pas passTant que le test d'arrêt n'est pas passéé
Structure générale d'un Algorithme d'optimisation harmoniqueStructure gStructure géénnéérale d'un Algorithme d'optimisation harmoniquerale d'un Algorithme d'optimisation harmonique
Critère à optimiser et domaine de rechercheCritère à optimiser et domaine de rechercheParamètres de configurationParamètres de configuration
Improviser pour trouver une meilleure harmonieImproviser pour trouver une meilleure harmonie
nombre maximum nombre maximum d'improvisationsd'improvisationsfacteur de surviefacteur de survie
etc.etc.
ÉÉvaluer les largeurs maximums des bandes de frvaluer les largeurs maximums des bandes de frééquence, quence, en accord avec la topologie du domaine des tonsen accord avec la topologie du domaine des tons { } 1,i i nx∈
Δω
DDééterminer le ton le pus harmonieux et le ton dissonant terminer le ton le pus harmonieux et le ton dissonant de la matrice harmonique initiale de la matrice harmonique initiale
0HM
61/6461/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation harmonique (Mozartienne)Optimisation harmonique (Mozartienne)
Tant que le test d'arrêt n'est pas passTant que le test d'arrêt n'est pas passéé
Structure générale d'un Algorithme d'optimisation harmoniqueStructure gStructure géénnéérale d'un Algorithme d'optimisation harmoniquerale d'un Algorithme d'optimisation harmonique
aP PM ( )1 nxaP P− M
Ajuster les composantes du nouveau tonAjuster les composantes du nouveau ton
Composante courante Composante courante Aucune composanteAucune composante
i i i iy y← +ξ ⋅Δω ( )
( )1
1
Pk kp p
pP
kp
p
f
f
=
=
=∑
∑
x xy
x
Viabiliser le nouveau tonViabiliser le nouveau ton
NONNONOUIOUI Ton plus Ton plus harmonieux?harmonieux?
Solution optimale: le ton le plus harmonieux Solution optimale: le ton le plus harmonieux de la matrice harmonique et sa performancede la matrice harmonique et sa performance
DDééterminer le ton le pus harmonieux et le ton dissonant de la matrterminer le ton le pus harmonieux et le ton dissonant de la matrice harmoniqueice harmonique
RRééactualiser la matrice harmoniqueactualiser la matrice harmonique Conserver la matrice harmoniqueConserver la matrice harmonique
62/6462/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131Optimisation harmonique (Mozartienne)Optimisation harmonique (Mozartienne)
AvantagesAvantages DésavantagesDésavantages
Caractéristiques des Algorithmes d'optimisation harmoniqueCaractCaractééristiques des Algorithmes d'optimisation harmoniqueristiques des Algorithmes d'optimisation harmonique
• Les dLes déétails d'impltails d'impléémentation des Algorithmes d'optimisation harmonique peuvent êtrementation des Algorithmes d'optimisation harmonique peuvent êtretrouvtrouvéés dans la litts dans la littéérature scientifique, par exemple ici: rature scientifique, par exemple ici:
Biblio: GEEM Z., KIM J., YOON Y. – Optimal layout of pipe networks using harmony search, Proceedings of the 4-th International Conference on Hydro-science and Engineering, Seoul, South Korea, 2000.
BiblioBiblio:: GEEMGEEM Z., KIM J., YOON Y. Z., KIM J., YOON Y. –– Optimal layout of pipe networks using harmony searchOptimal layout of pipe networks using harmony search, Proceedings , Proceedings of the 4of the 4--th International Conference on Hydroth International Conference on Hydro--science and Engineering, Seoul, South Korea, 2000.science and Engineering, Seoul, South Korea, 2000.
STEFANOIU D., BORNE P., POPESCU D., FILIP F.G., ELKAMEL A. – Optimisation en sciences de l'ingénieur – Métaheuristiques, méthodes stochastiques et aide à la décision, Hermès-Lavoisier, Paris, France, 2014.
STEFANOIU D., BORNE P., STEFANOIU D., BORNE P., POPESCUPOPESCU D., D., FILIPFILIP F.G.F.G., , ELKAMELELKAMEL A. A. –– Optimisation en Optimisation en sciences de l'ingsciences de l'ingéénieur nieur –– MMéétaheuristiques, mtaheuristiques, mééthodes stochastiques et aide thodes stochastiques et aide àà la la ddéécisioncision, , HermHermèèss--LavoisierLavoisier, Paris, France, 2014., Paris, France, 2014.
☺☺ TrTrèès bonne mas bonne maîîtrise du compromis trise du compromis explorationexploration--exploitationexploitation. .
• Avec un choix judicieux des Avec un choix judicieux des probabilitprobabilitéés. s.
☺☺ Peu de paramPeu de paramèètres de configuration. tres de configuration.
Un peu rudimentaires (stratUn peu rudimentaires (stratéégie de gie de recherche assez proche de celle de la recherche assez proche de celle de la mmééthode de Montethode de Monte--Carlo).Carlo).
Il est trIl est trèès difficile (voire impossible) de s difficile (voire impossible) de ddéémontrer des rmontrer des réésultats de sultats de convergence.convergence.
• La recherche peut durer assez La recherche peut durer assez longtemps. longtemps. ☺☺ Facile Facile àà implimpléémenter menter
(surtout en Matlab). (surtout en Matlab).
RRéésultats modestes dans le cas des sultats modestes dans le cas des critcritèères d'une nature trop fractale. res d'une nature trop fractale.
☺☺ Facile Facile àà adapter pour des probladapter pour des problèèmes mes d'optimisation en provenance de d'optimisation en provenance de diffdifféérents domaines. rents domaines.
Pas trPas trèès bien adapts bien adaptéés pour s pour implimpléémentation sur des machines mentation sur des machines parallparallèèles.les.
• On peut quand même travailler avec On peut quand même travailler avec plusieurs matrices harmoniques. plusieurs matrices harmoniques.
63/6463/64
DB!(!OUJ 31DB!(!DB!(!OUJOUJ 3131ConclusionConclusion
Plus l'utilisateur peut contrôler le compromis exploration-expoitation,
plus l'algorithme métaheuristique est
efficace.
Plus l'utilisateur peut Plus l'utilisateur peut contrôler le compromis contrôler le compromis explorationexploration--expoitationexpoitation, ,
plus l'algorithme plus l'algorithme mméétaheuristique est taheuristique est
efficaceefficace..
Lac Robert, FranceLac Robert, France(Danny’s photo gallery)(Danny’s photo gallery)
Dan StefanoiuDan StefanoiuDan Stefanoiu
[email protected]@[email protected]@[email protected]@acse.pub.ro
Merci!Merci!
http://ro.linkedin.com/pub/dan-stefanoiu/30/bb/617http://ro.linkedin.com/pub/danhttp://ro.linkedin.com/pub/dan--stefanoiu/30/bb/617stefanoiu/30/bb/617