7/17/2019 7569_presentation.pdf
http://slidepdf.com/reader/full/7569presentationpdf 1/11
IntroductionAlgorithme Génétique
Optimisation par Essaim Particulaires
Heuristiques et Intelligence Collective:
Projets d’Optimisation Continue
Automne ’09
27 novembre 2009
Heuristiques: Projets Automne ’09
Professeur : Marco Tomassini
Assistant : F. Daolio
7/17/2019 7569_presentation.pdf
http://slidepdf.com/reader/full/7569presentationpdf 2/11
IntroductionAlgorithme Génétique
Optimisation par Essaim Particulaires
L’organisation des travauxLes functions à optimiser
Administratif
Groupes de 2-3 personnes
3 séances : 27 novembre, 4 et 11 décembre
À rendre avant le 17 décembre 2009, minuit :- rapport écrit d’environs 800 mots avec les résultats
1 séance de présentation : vendredi 18 décembre
Présentation de 15 minutes par groupe :
- Tous les membres participent et sont présents !
Heuristiques: Projets Automne ’09
7/17/2019 7569_presentation.pdf
http://slidepdf.com/reader/full/7569presentationpdf 3/11
IntroductionAlgorithme Génétique
Optimisation par Essaim Particulaires
L’organisation des travauxLes functions à optimiser
Optimisation de fonctions continues
à l’aide d’Heuristiques basées sur une population
Résoudre les 3 fonctions présentées ci-aprés
1 Technique à choisir sur 3 :1 Algorithme Génétique ∼ sélection2 Algorithme Génétique ∼ croisement3 Optimization par Essaim ∼ voisinage
Code donné sur le site du cours :https://www.hec.unil.ch/docs/mscis/cours/13/
Heuristiques: Projets Automne ’09
7/17/2019 7569_presentation.pdf
http://slidepdf.com/reader/full/7569presentationpdf 4/11
IntroductionAlgorithme Génétique
Optimisation par Essaim Particulaires
L’organisation des travauxLes functions à optimiser
Fonction Parabola ou “Sphère”
2D Sphere Function définition
f (x ) = x 12 + x 2
2
domaine de recherche
−100 ≤ x i ≤ 100
minimum globalx ∗ = (0, 0) f (x ∗) = 0
Heuristiques: Projets Automne ’09
I d i
7/17/2019 7569_presentation.pdf
http://slidepdf.com/reader/full/7569presentationpdf 5/11
IntroductionAlgorithme Génétique
Optimisation par Essaim Particulaires
L’organisation des travauxLes functions à optimiser
Fonction de Rosenbrock ou “Banane”
2D Rosenbrock’s Function définition
f (x ) = (1−x 12) + 100∗ (x 2− x 21 )2
domaine de recherche
−30 ≤ x i ≤ 30
minimum globalx ∗ = (1, 1) f (x ∗) = 0
Heuristiques: Projets Automne ’09
I t d ti
7/17/2019 7569_presentation.pdf
http://slidepdf.com/reader/full/7569presentationpdf 6/11
IntroductionAlgorithme Génétique
Optimisation par Essaim Particulaires
L’organisation des travauxLes functions à optimiser
Fonction de Rastrigin
2D Rastrigin’s Function
définition
f (x ) = 20+2
i =1
(x 2i −10cos(2πx i ))
domaine de recherche
−5.12 ≤ x i ≤ 5.12
minimum global
x ∗ = (0, 0) f (x ∗) = 0
Heuristiques: Projets Automne ’09
Introduction Modèle utilisé
7/17/2019 7569_presentation.pdf
http://slidepdf.com/reader/full/7569presentationpdf 7/11
IntroductionAlgorithme Génétique
Optimisation par Essaim Particulaires
Modèle utiliséProjet 1Projet 2
Genetic Algorithm Toolbox
Publié en 2007 par Kumara Sastryhttp://www.illigal.uiuc.edu
Une suite des méthodes en langage C++
Choix des paramètres par ficher .txt en entré
Documentation en un ficher .pdf
...petite démo...
Heuristiques: Projets Automne ’09
Introduction Modèle utilisé
7/17/2019 7569_presentation.pdf
http://slidepdf.com/reader/full/7569presentationpdf 8/11
IntroductionAlgorithme Génétique
Optimisation par Essaim Particulaires
Modèle utiliséProjet 1Projet 2
Projet 1 : méthodes de sélection
algorithme base
SGA real coded : tous les paramètres “default”
operateurs de sélection à essayer1 Binary Tournament2 Roulette Wheel3 Truncation
à observer sur les 3 fonctions
l’influence de la sélection sur la convergence
Heuristiques: Projets Automne ’09
Introduction Modèle utilisé
7/17/2019 7569_presentation.pdf
http://slidepdf.com/reader/full/7569presentationpdf 9/11
IntroductionAlgorithme Génétique
Optimisation par Essaim Particulaires
Modèle utiliséProjet 1Projet 2
Projet 2 : méthodes de croisement
algorithme base
SGA real coded : tous les paramètres “default”
operateurs de croisement à essayer1 One Point2 Two Point3 Simulated Binary Xover
à observer sur les 3 fonctions
l’influence du croisement sur la convergence
Heuristiques: Projets Automne ’09
IntroductionM dèl ili é
7/17/2019 7569_presentation.pdf
http://slidepdf.com/reader/full/7569presentationpdf 10/11
IntroductionAlgorithme Génétique
Optimisation par Essaim Particulaires
Modèle utiliséProjet 3
Standard PSO 2007
Publié en 2007 par Maurice Clerc et autreshttp://www.particleswarm.info
Un seul ficher en langage C
Choix des paramètres dans le code
Documentation dans les commentaires du code
...petite démo...
Heuristiques: Projets Automne ’09
IntroductionM dèl tili é
7/17/2019 7569_presentation.pdf
http://slidepdf.com/reader/full/7569presentationpdf 11/11
Algorithme GénétiqueOptimisation par Essaim Particulaires
Modèle utiliséProjet 3
Projet 3 : nombre d’informateurs
algorithme base
PSO avec topologie stochastique : tous les paramètres “default”
nombre d’informateurs à essayer1 K = 3 ( local best ring topology )2 3 < K < S
3 K = S ( global best topology )
à observer sur les 3 fonctions
l’influence du voisinage sur la convergence
Heuristiques: Projets Automne ’09
Recommended