Recherche Documentaire Finale

Recherche Documentaire Finale

ALFA, Mischa:Production HUOT,Whilys:Recherche documentaire MALKl,Mehdi:Recherche documentaire Recherche Documentaire Thème ‘*Avancées scientifiques et réalisations techniques Sujet :Les algorithmes génétiques dans la réalisation matérielle Problématique : Les algorithmes génétiques peuvent Ils surpasser les ingénieurs humains ? or7 Sni* to View Sommaire: Qu’est-ce qu’un algor Qu’est-ce qu’un algorithme genetique? Comment un algorithme génétique intervient dans la réalisation matérielle? résultats obtenus,son aptitude à être efficacement parallélisé(scabilité)etc.

Les ordinateurs sur lesquels s’exécutent ces algorithmes ne sont pas infiniment rapides. L’analyse de la complexité algorithmique permet de prédire l’évolution en temps calcul nécessaire pour amener un algorithme à son terme, en fonction de la quantité de données à traiter. Non mathématiques : Dans la vie de tous les jours,on utilise sans le savoir plein de types d’algorithmes comme une rectte de cuisine par exemple avec des entrées,les instructions dont l’éxecution et le résultat ce qui correspond respectivement aux ingrédients et il ya la préparatlon(l’executlon) et le plat st prêt(résultat).

Exemple d’algorithme : Algorithme récursif pour calculer le nième terme de la suite de Fibbonacci PAG » rif 7 parle alors de formule et non plus des valeurs) Voici a quoi ressemble un algorithme génétique . La génétique a montrer l’existence de plusieurs opérations(étapes) au sein d’un organisme donnant lieu au

Désolé, mais les essais complets ne sont disponibles que pour les utilisateurs enregistrés

Choisissez un plan d'adhésion
brassage(filtrage) génétique. Ces opérations interviennent lors de la phase de reproduction lorsque les chromosomes de deux organismes fusionnent.

Ces opérations sont imitées par les algorithmes génétiques afin e faire évoluer les populations de manière progressive. Sélection pour savolr quels Individus sont plus aptes à obtenir les mellleurs résultats, on procède à une sélection. Ce processus est associé à un processus de sélection naturelle, les individus les plus adaptés gagnent la «compétition» de la reproduction tandis que les moins adaptés meurent avant la reproduction, ce qui améliore globalement l’adaptation. *AGF 3 c,F7 entre O et 1 strictement.

Mutations De façon aléatoire, un gène peut, au sein d’un chromosome être substitué à un autre. De la même manière que pour les enjambements, on définit ici un taux de mutation lors des changements de population qui est généralement compris entre 0,001 et 0,01 . Il est nécessaire de choisir pour ce taux une valeur relativement faible de manière à ne pas tomber dans une recherche aléatoire et conserver le principe de sélection et d’évolution. La mutation sert à éviter une convergence prématurée de l’algorithme.

Les algorlthmes génétiques, afin de permettre la résolution de problèmes, se basent sur les différents principes décrits ci- essus. De manière globale, on commence avec une population de base qui se compose le plus souvent de chaînes de caractères correspondant chacune à un chromosome(Codage) Le contenu de cette population initiale est généré aléatoirement. On attribue à chacune des solutions une note qui correspond ? son adaptation au problème. Ensuite, on effectue une sélection au sein de cette population.

Il existe plusieurs techniques de sélection. Voici es principales utilisées : Sélection par rang Cette technique de sélection choisit toujours les individus ossédant les meilleurs scores d’adaptation, le hasard n’entre donc pas dans ce mode de sélection. la sélection appliquée consiste à conserver les meilleurs individus en fonction d’une probabilité qui dépend du rang (et pas de la fonction d’évaluation). Roulette Pour chaque individu, la probabilité d’être sélectionné est proportionnel proportionnelle à son adaptation au problème.

Afin de sélectionner un individu, on utilise le principe de la roue de la fortune biaisée. Cette roue est une roue de la fortune classique sur laquelle chaque individu est représenté par une portion roportionnelle à son adaptation. On effectue ensuite un tirage au sort homogène sur cette roue. Sélection uniforme La sélection se fait aléatoirement. Chaque individu a donc une probabilité WP d’être sélectionné, où P=le nombre total d’individus dans la population.

Lorsque deux chromosomes ont été sélectionnés, on réalise un croisement. On effectue ensuite des mutations sur une faible proportion d’individus, choisis aléatoirement. Ce processus nous fournit une nouvelle population. On réitère le processus un grand nombre de f01S de manière à imiter le principe d’évolution. On peut arrêter le processus au bout d’un nombre arbitraire de générations ou lorsqu’une solution possède une note suffisamment satisfaisante. écessaire d’avoir la solution optimale, qui prendrait par exemple trop de temps et de ressources pour être calculée (ou tout simplement si personne n’est capable de la trouver de manière théorique). Codage binaire: On utilise plusieurs codage pour coder des solutions. Le plus utilisé reste le codage binaire car il présente plusieurs avantages. Son principe est de coder la solution selon une chaîne de bits (qui euvent prendre les valeurs O ou 1) La démonstration d’Holland (en 1 975) a prouvé la supériorité de ce type de codage. Il compara deux types de codage pour le même problème.

Le premier était composé de peu de types d’allèles mais avec des chromosomes d’une longueur importante (des chaînes de 100 bits par exemple), l’autre était composé de chaînes plus courtes mais contenant plus d’allèles (en sachant que tout autre codage, pour le même chromosome, aboutira à une chaîne plus courte). Il prouva que le codage sous forme de bits était plus efficace de manière assez simple. En effet, les chaînes de 100 bits permettent d’avoir plus de possibilités d’enjambement. Entre deux chromosomes du premier type, l’enjambement peut avoir lieu à 100 endroits différents contre 30 pour ceux du second type.

Le brassage génétique sur lequel repose l’efficacité des algorithmes génétiques sera donc plus important dans le premier cas. ll existe cependant au moins un côté négatif à ce type de codage qui fait que d’autres existent. En effet, ce codage est souvent peu naturel par rapport à un problème donné (l’évolution des poids d’arcs dans un g ouvent peu naturel par rapport à un problème donné (l’évolution des poids d’arcs dans un graphe par exemple est difficile à coder sous la forme d’une chaîne de bits).

Codage binaire:Tableau de valeur Un algorithme génétique sert a trouvé la solution optimal a un problème. Ce problème d’ordre technique comme : « une portière aérodynamique » pour une voiture par exemple. C’est la qu’un algorithme génétique a toute son importance car il va nous permettre de trouvé le meilleur résultat dans ce cas-la,une portière qui sera le plus aérodynamique possible. lalgorithme va donc procédé a une sélection de caractéristique(une portière fine et une autre épaisse par exemple)qui seront les plus aptes a répondre au problème(sélection par rang). On prend la meilleur on la croise et ainsi de suite jusqu’à ce qu’on tombe sur celle qui sera la plus optimal a répondre au problème(a la condition donné). Ceci va permettre au producteur de la voiture un gain de temps énorme et des résultats optimum. On peut en déduire qu’un algorithme génétique surpasse les ingénieures humains. L’homme s’en sert comme outils il en a besoin