Introducing 

Prezi AI.

Your new presentation assistant.

Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.

Loading…
Transcript

L'algorithme Génétique

Nom: TEMANI Malek || HADDAD Safa

Groupe: 3LAID2

Institut Supérieur de Gestion Tunis

Introduction

Algorithme Génétique

L’algorithme génétique (AG) est un algorithme de recherche basé sur les mécanismes de la sélection naturelle et de la génétique.

Il combine une stratégie de ”survie des plus forts” avec un échange d’information aléatoire mais structuré. Pour un problème pour lequel une solution est inconnue, un ensemble de solutions possibles est créé aléatoirement.

Définition

Les lois de la sélection naturelle

Historique

Algorithme

L'informaticien

en vacances

Exemple

L'informaticien en vacances doit visiter plusieurs villes durant ses vacances : { A,B,C,D,E,F,G,H,I,J }.

Il cherche donc le chemin le plus court pour passer par chacune d'elles. Il souhaite également assister à un maximum de festivals musicaux (ayant lieu dans les villes A,B et C) .

Nous n'allons pas parcourir tous les chemins possibles, il y en aurait trop.

Nous créons une population d'individus au hasard :

par exemple {A,B,C,D,E,F,G,H,I,J}, {D,A,F,J,C,E,G,H,B,I}, {J,A,H,F,D,C,I,G,E,B} ou encore {J,F,A,C,B,E,I,H,G,D}.

Population

L'évaluation du critère relatif à la distance parcourue est simplement la somme de toutes les distances parcourues.

Et l'évaluation du critère relatif au nombre de festivals est simplement le nombre de festivals auxquels l'informaticien a pu assister (0,1,2 ou 3).

Une solution amenant {50 km, 2 festivals} dominera une solution {60 km, 1 festivals}, mais ne dominera pas une solution {40 km, 3 festivals} car elle n'est pas meilleure sur tous les critères

Evaluation

Sélection

Sélection

Améliorons la population

Mutation

&

croisement

ALGORITHMIQUE

Algorithmique

1) Initialiser la population initiale P

2) Evaluer P.

3) maxi=100

4) k=0

5) Tant Que (K < > maxi) faire :

a) P ' = Sélection des Parents dans P

b) P ' = Appliquer Opérateur de Croisement sur P '

c) P ' = Appliquer Opérateur de Mutation sur P '

d) P = Remplacer les Anciens de P par leurs Descendants de P '

e) Evaluer P

f) k=k+1

FinTantQue

Conclusion

• cette technique connait aujourd’hui un franc succès. On l’utilise dans la résolution de problèmes complexes, nécessitant des temps de calcul élevés.

• Les applications des AG sont multiples : traitement d’image (alignement de photos satellites, reconnaissance de suspects...), optimisation d’emplois du temps, optimisation de design, apprentissage des réseaux de neurones [Renders, 1995], etc.

Learn more about creating dynamic, engaging presentations with Prezi