[PDF] [PDF] Intelligence Artificielle Heuristique - Université Paris Cité





Previous PDF Next PDF



INF4230 – Intelligence Artificielle Algorithme A*

– Ajout d'une heuristique. • A* et les heuristiques sont à la base de beaucoup de travaux en IA: – Recherche de 



Chapitre 8 : Introduction aux méthodes heuristiques

Méta-heuristiques : algorithmes d'optimisation (généralement de type Méthode heuristique en programmation dynamique : Algorithme A?.



Intelligence Artificielle Heuristique

Algorithmes et recherches heuristiques. Recherche meilleur d'abord. Recherche gloutonne. L'algorithme A?. Algorithmes de recherche locale.



Les méthodes de résolution approchées pour le Programmation en

2 Les algorithmes approchés : heuristiques Définition 2 : Un algorithme de résolution Heuristique est un algorithme qui fournit une solution réalisable ...



Méta-heuristiques

Les algorithmes génétiques reprennent ces mécanismes pour définir une méta- heuristique de résolution de problèmes d'optimisation combinatoire. L'idée est.



Algorithmes gloutons Problèmes doptimisation. Problèmes d

sous-problèmes) : heuristique de choix. Algorithmes gloutons – Stéphane Grandcolas – p.6. Algorithmes gloutons. Un algorithme glouton construit une solution 



Algorithmes heuristiques et exacts pour le probleme de lensemble

Algorithmes heuristiques et exacts pour le probl`eme de l'ensemble dominant connexe minimum par. Sofiane Soualah. Département d'informatique et de recherche 



Les Méthodes Hybrides en Optimisation Combinatoire:Algorithmes

28 avr. 2006 2.1 – Heuristique gloutonne pour le KP. 2.2.2 Calcul de bornes supérieures et élément critique. Calculer des bornes supérieures ou inférieures ( ...



Heuristique DSATUR

des exemples d'application nous aborderons le problème du temps de calcul de certains algorithmes



Coopération méta heuristique et logique floue pour le

Pour cela nous utilisons une approche pour la génération de base de r`egles floues et une optimisation automatiques au moyen d'algorithme génétique et d'un PSO 



[PDF] INF4230 – Intelligence Artificielle Algorithme A* - GDAC

une heuristique est une méthode (~algorithme) qui calcule rapidement (ex: en temps constant linéaire ou polynomiale) une solution pouvant être approximative 



[PDF] Intelligence Artificielle Heuristique - Université Paris Cité

Algorithmes et recherches heuristiques Recherche meilleur d'abord Recherche gloutonne L'algorithme A? Algorithmes de recherche locale



[PDF] Chapitre 8 : Introduction aux méthodes heuristiques

Quelques méthodes heuristiques 1 Algorithme A? 2 Recuit simulé 3 Algorithmes génétiques 4 Algorithme de colonies de fourmis



[PDF] Heuristiques

Dans cet algorithme la file contient des chemins issus de la racine à chaque étape on défile le chemin le plus prioritaire et on l'étend par les différentes 



[PDF] Algorithmes de recherche heuristique - Free

Les algorithmes de recherche aveugle ou "non-informés" – n'exploitent aucune information présente dans l'arbre de recherche pour optimiser la recherche



[PDF] Cours des Méthodes de Résolution Exactes Heuristiques et

1 1 1 Introduction Si les méthodes de résolution exactes permettent d'obtenir une En optimisation combinatoire une heuristique est un algorithme ap-



[PDF] Algorithmes Heuristiques et Techniques dApprentissage

6 mai 2010 · Chapitre 1 Introduction 1 1 Probl`emes difficiles et algorithmes heuristiques Une instance d'un probl`eme d'optimisation combinatoire est 



[PDF] Algorithmes de recherche informés - Irif

Les heuristiques • Algorithmes de recherche locale 1 Cours Intelligence Artificielle 2005-2006 Peter Habermehl Recherche meilleur d'abord



[PDF] Algorithmes Heuristiques et Evolutionnistes - Université de Lille

24 juil 2022 · 1! 4 2 Algorithme R8 : Introduction aux principes intéressons aux méthodes de résolution appliquées au format existant des formes



Algorithmes Et Recherches Heuristiques PDF - Scribd

Elise Bonzon (Université Paris Descartes) Intelligence artificielle Licence 3 Informatique 1 / 23 Algorithmes et recherches heuristiques 

  • C'est quoi la méthode heuristique ?

    La méthode heuristique repose sur une évaluation quasi continue, principalement formative. L'acquisition des notions est évaluée lors des observations de l'enseignant. L'évaluation s'appuie sur des critères explicites et partagés avec les élèves.

  • Comment calculer l'heuristique ?

    Cet algorithme utilise une heuristique qui calcule pour chaque nœud n le coût chemin g(n) depuis l`état initial jusqu'au nœud n. Le coût chemin g(n) est une fonction croissante le long d`un chemin : chacune n dans E, s dans Successeurs(n), g(n) <= g(s).

  • Comment savoir si une heuristique est admissible ?

    L'heuristique admissible Dans la science informatique, en particulier dans les algorithmes liés à pathfinding, une fonction heuristique est dite admissible si elle surestime jamais le coût pour atteindre l'objectif, à savoir que le coût qu'il estime pour atteindre l'objectif ne dépasse pas le coût le plus bas possible
  • h1 et h2 admissible implique pour tout noeud n h1(n) ? h?(n) et h2(n) ? h?(n). Donc pour tout noeud n on a max(h1(n),h2(n)) ? h?(n) donc max(h1,h2) est admissible.

Intelligence Artificielle

Heuristique

Bruno Bouzy

http://web.mi.parisdescartes.fr/~bouzy bruno.bouzy@parisdescartes.fr

Licence 3 Informatique

UFR Mathématiques et Informatique

Université Paris Descartes

Algorithmes et recherches heuristiques

Algorithmes et recherches heuristiques

Recherche meilleur d'abord

Recherche gloutonne

L'algorithme A

Algorithmes de recherche locale

2 / 23Intelligence articielle

N

Algorithmes et recherches heuristiques

Algorithmes et recherches heuristiques

Recherche meilleur d'abord

Recherche gloutonne

L'algorithme A

Algorithmes de recherche locale

3 / 23Intelligence articielle

N

Algorithmes et recherches heuristiques

Recherche meilleur d'abord

Rappel: Une strategie est denie en choisissant un ordre dans lequel les etats sont developpesIdee: Utiliser unefo nctiond 'evaluationfpour chaque noeud !mesure l'utilite d'un noeud !introduction d'unef onctionhe uristiqueh(n)q uiestimele co^ut du chemin

le plus court pour se rendre au butInsertAllinsere le nud par ordre decroissant d'utiliteCas speciaux:Recherche gloutonne(u nc hoixn'e stj amaisr emisen cau se)

A

4 / 23Intelligence articielle

N

Algorithmes et recherches heuristiques

Algorithmes et recherches heuristiques

Recherche meilleur d'abord

Recherche gloutonne

L'algorithme A

Algorithmes de recherche locale

5 / 23Intelligence articielle

N

Algorithmes et recherches heuristiques

Recherche gloutonne

Fonction d'evaluationf(n) =h(n) (heuristique)h(n) : estimation du co^ut denvers l'etat nalPar exemple,hdd(n) est la distance a vol d'oiseau entre la villenet

BucharestLarecherche gloutonnedeveloppe le nud quip ara^tle p lusp roched e l'etat nal

6 / 23Intelligence articielle

N

Algorithmes et recherches heuristiques

Le voyage en Roumanie

AradZerind

TimisoaraOradea

Sibiu Lugoj

Mehadia

Dobreta

CraiovaRimnicu VilceaFagaras

PitestiBucharest

GiurgiuUrziceni

Hirsova

EforieVasluiLasiNeamt

75
11871

140151

111
70
75
12080
14699

13897211

101

908598

801429287Ligne droite jusqu'a Bucharest

Arad366

Bucharest0

Craiova160

Dobreta242

Eforie161

Fagaras176

Giurgiu77

Hirsova151

Lasi226

Lugoj244

Mehadia241

Neamt234

Oradea380

Pitesti100

Rimnicu Vilcea193

Sibiu253

Timisoara329

Urziceni80

Vaslui199

Zerind374

7 / 23Intelligence articielle

N

Algorithmes et recherches heuristiques

Recherche gloutonne

Completude: Incomplet (peut rester bloque dans des boucles)Exemple : Arad!Zerind!Arad!:::Complet si on ajoute un test pour eviter les etats repetes

Temps:O(bm)Une bonne heuristique peut ameliorer grandement les performances Espace:O(bm) : Garde tous les nuds en memoireOptimale: Non8 / 23Intelligence articielle N

Algorithmes et recherches heuristiques

Algorithmes et recherches heuristiques

Recherche meilleur d'abord

Recherche gloutonne

L'algorithme A

Algorithmes de recherche locale

9 / 23Intelligence articielle

N

Algorithmes et recherches heuristiques

Algorithme A

Idee: Eviter de developper des chemins qui sont deja chersFonction d'evaluation:f(n) =g(n) +h(n)g(n) est leco ^utd el' etatin itial al 'etatnh(n) est leco ^utes timep ourat teindrel' etat nalf(n) est leco ^utt otalest imep oura llerde l' etatin itial al 'etat nalen

passant parnA

utilise une heuristiquea dmissibleh(n)h(n) ouh(n) est le co^ut reel pour aller denjusqu'a l'etat nalUne heuristique admissible ne surestime jamais le co^ut reel pour atteindre

le but. Elle est

o ptimistePar exemplehddne surestime jamais la vraie distanceSih(n) = 0 pour toutn, alors Aest equivalent a l'algorithme de Dijkstra

de calcul du plus court cheminTheoreme: Aest optimale10 / 23Intelligence articielle N

Algorithmes et recherches heuristiques

Le voyage en Roumanie

AradZerind

TimisoaraOradea

Sibiu Lugoj

Mehadia

Dobreta

CraiovaRimnicu VilceaFagaras

PitestiBucharest

GiurgiuUrziceni

Hirsova

EforieVasluiLasiNeamt

75
11871

140151

111
70
75
12080
14699

13897211

101

908598

801429287Ligne droite jusqu'a Bucharest

Arad366

Bucharest0

Craiova160

Dobreta242

Eforie161

Fagaras176

Giurgiu77

Hirsova151

Lasi226

Lugoj244

Mehadia241

Neamt234

Oradea380

Pitesti100

Rimnicu Vilcea193

Sibiu253

Timisoara329

Urziceni80

Vaslui199

Zerind374

11 / 23Intelligence articielle

N

Algorithmes et recherches heuristiques

Preuve d'optimalite de A

Supposons qu'il y ait un etat nal non optimalG0genere dans la liste des nuds a traiterSoitnun nud non developpe sur le chemin le plus court vers un etat nal optimalGstart n GG

0f(G0) =g(G0) carh(G0) = 0

>g(G) carG0n'est pas optimale f(n) carhest admissiblef(G0)>f(n), donc Ane va pas choisirG012 / 23Intelligence articielle N

Algorithmes et recherches heuristiques

Algorithme A

Completude: Oui, sauf s'il y a une innite de nuds tels queff(G)Temps: exponentielle selon la longueur de la solutionEspace: exponentielle (garde tous les nuds en memoire)Habituellement, on manque d'espace bien avant de manquer de temps

Optimale: Oui13 / 23Intelligence articielle

N

Algorithmes et recherches heuristiques

Que faire sifdecro^t?Avec une heuristique admissible,fpeutdecro^treau cours du cheminPar exemple, sipest un successeur den, il est possible d'avoirn

pg= 4,h= 8,f= 12g= 5,h= 4,f= 9On perd de l'information

f(n) = 12, donc le vrai co^ut d'un chemin a traversnest12Donc le vrai co^ut d'un chemin a traverspest aussi12

)Au lieu def(p) =g(p) +h(p), on utilisef(p) =max(g(p) +h(p);f(n)) !fne decro^t jamais le long du chemin14 / 23Intelligence articielle N

Algorithmes et recherches heuristiques

Que faire sifdecro^t?Avec une heuristique admissible,fpeutdecro^treau cours du cheminPar exemple, sipest un successeur den, il est possible d'avoirn

pg= 4,h= 8,f= 12g= 5,h= 4,f= 9On perd de l'information

f(n) = 12, donc le vrai co^ut d'un chemin a traversnest12Donc le vrai co^ut d'un chemin a traverspest aussi12)Au lieu def(p) =g(p) +h(p), on utilisef(p) =max(g(p) +h(p);f(n))

!fne decro^t jamais le long du chemin14 / 23Intelligence articielle N

Algorithmes et recherches heuristiques

Exemple d'heuristiques admissibles: le

taquinh

1(n) = le nombre de pieces mal placees

!h1(S) = 8h

2(n) = la distance de Manhattan totale (la distance de chaque piece

entre sa place actuelle et sa position nale en nombre de places) !h2(S) = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 1815 / 23Intelligence articielle N

Algorithmes et recherches heuristiques

Exemple d'heuristiques admissibles: le

taquinh

1(n) = le nombre de pieces mal placees!h1(S) = 8h

2(n) = la distance de Manhattan totale (la distance de chaque piece

entre sa place actuelle et sa position nale en nombre de places) !h2(S) = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 1815 / 23Intelligence articielle N

Algorithmes et recherches heuristiques

Exemple d'heuristiques admissibles: le

taquinh

1(n) = le nombre de pieces mal placees!h1(S) = 8h

2(n) = la distance de Manhattan totale (la distance de chaque piece

entre sa place actuelle et sa position nale en nombre de places) !h2(S) = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 1815 / 23Intelligence articielle N

Algorithmes et recherches heuristiques

Exemple d'heuristiques admissibles: le

taquinh

1(n) = le nombre de pieces mal placees!h1(S) = 8h

2(n) = la distance de Manhattan totale (la distance de chaque piece

entre sa place actuelle et sa position nale en nombre de places)!h2(S) = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 1815 / 23Intelligence articielle

N

Algorithmes et recherches heuristiques

Dominance

h

1domineh2sih1eth2sont admissibles et queh1(n)h2(n) pour toutnh

1est alors meilleure pour la rechercheExemple :

d= 12 IDS: 3;644;035 nuds A (h1): 227 nuds A (h2): 73 nuds d= 24 IDS: trop de nuds A (h1): 39;135 nuds A (h2): 1;641 nuds16 / 23Intelligence articielle N

Algorithmes et recherches heuristiques

Comment trouver des heuristiques ad-

missibles?Considerer uneversion simpliee du problemeLe co^ut exact d'une solution optimale du probleme simplie est une

heuristique admissible pour le probleme originalExemple : simplication des regles du taquin une piece peut ^etre deplacee partout !h1(n) donne la plus petite solutionune piece peut ^etre deplacee vers toutes les places adjacentes !h2(n) donne la plus petite solution17 / 23Intelligence articielle N

Algorithmes et recherches heuristiques

Algorithmes et recherches heuristiques

Recherche meilleur d'abord

Recherche gloutonne

L'algorithme A

Algorithmes de recherche locale

18 / 23Intelligence articielle

N

Algorithmes et recherches heuristiques

Algorithmes de recherche locale

Dans de nombreux problemes d'optimisation, le chemin qui mene vers une solution n'est pas importantL'etatlu i-m^emee stla s olution Idee : Modier l'etat en l'ameliorant au fur et a mesure Espace d'etats : ensemble des congurations possible des etats Besoin de denir une fonction qui mesure l'utilite d'un etat

19 / 23Intelligence articielle

N

Algorithmes et recherches heuristiques

Exemple : lesnreinesPlacernreines sur un plateau de taillenn, sans que deux reines se trouvent sur la m^eme ligne, colonne ou diagonaleDeplacer une reine pour reduire le nombre de con itsh = 5h = 2h = 0 20 / 23Intelligence articielle N

Algorithmes et recherches heuristiques

Algorithmes de recherche locale

On cherche un maximum globalcurrent

state objective function state space global maximum local maximum "flat" local maximum shoulder21 / 23Intelligence articielle N

Algorithmes et recherches heuristiques

Algorithmes de recherche locale

Algorithme d'ascension du gradient:

22 / 23Intelligence articielle

N

Algorithmes et recherches heuristiques

Algorithmes de recherche locale

On peut aussi considerer la descente du gradient

On peut ^etre bloque dans un maximum local

Probleme : les plateaux

Solution : on admet des mouvements de c^ote

23 / 23Intelligence articielle

Nquotesdbs_dbs44.pdfusesText_44
[PDF] généralités sur les systèmes automatisés de production

[PDF] structure fonctionnelle d'un système automatisé

[PDF] méthodes heuristiques d'optimisation

[PDF] définition d'un système automatisé de production

[PDF] méthodes heuristiques et métaheuristique d'optimisation

[PDF] méthode heuristique optimisation

[PDF] système automatisé de production sap

[PDF] les métaheuristiques en optimisation combinatoire

[PDF] système automatisé de production pdf

[PDF] système automatisé de production ppt

[PDF] cours aide soignante module 1 pdf

[PDF] qcm module 1 aide soignante gratuit

[PDF] cours aide soignante module 2

[PDF] module 1 aide soignante résumé

[PDF] les 8 modules aide soignante