Résumé Dans le monde de l'intelligence artificiel aujourd'hui, on a tendance à recopier ce que fait la nature. Et quoi de plus normale que de copier le cerveau humain quand on parle d'intelligence et de réflexion.








télécharger 236.32 Kb.
titreRésumé Dans le monde de l'intelligence artificiel aujourd'hui, on a tendance à recopier ce que fait la nature. Et quoi de plus normale que de copier le cerveau humain quand on parle d'intelligence et de réflexion.
page3/10
date de publication16.05.2017
taille236.32 Kb.
typeRésumé
b.21-bal.com > loi > Résumé
1   2   3   4   5   6   7   8   9   10

Algorithmes génétiques



Introduction



Depuis Euclid (450 ans avant J.C) les mathématiques n’ont pas cessé de modéliser les phénomènes naturels en mettant au point des concepts de plus en plus raffinés pour prendre en compte les multiples aspects de ces derniers. Ainsi naquirent alors des théories toujours plus complexes et plus abstraites pour cerner le monde qui nous entoure. Mais voilà qu’en observant le détail microscopique de ‘’mère nature ‘’, elle nous suggère des modèles mathématiques…
En effet, l’observation du système immunitaire, de la solidification des métaux, des principes de la génétique (pour ne citer que ceux-là) a conduit vers le fondement des théories telles que le recuit simulé et les algorithmes génétiques. Ces derniers qui nous intéressent particulièrement ont résolu de façon très élégante une gamme de problèmes allant des questions de mathématiques pures aux applications concrètes de finances, de distribution, d’électronique et autres…
Cet exposé est un survol des algorithmes (AG). Nous relatons, d’abord, un bref historique de l’évolution des AG. Nous présentons, ensuite, les principes de fonctionnement de ces algorithmes ainsi que leurs champs d’application et des exemples simples qui faciliteront leur compréhension
 

Historique



Charles Darwin, biologiste, montre en 1859 (origin of species), que l’apparition d’espèces distinctes est le résultat de la sélection naturelle de variations individuelles.
Cette sélection naturelle est l’exercice d’une population qui lutte pour la vie et tente de s’étendre en faisant face aux multiples contraintes de l’environnement (conditions extérieures et les autres individus) et en disposant d’un espace et de ressources limités.
Les individus les plus adaptés (fitest en anglais) auront une meilleure longévité ainsi qu’une meilleure progéniture. Mendel explique, plus tard, les lois sur les principes du croisement et de la mutation génétiques.
J.H. Holland, professeur à l’université du Michigan, entreprit  avec ses étudiants, en 1975, une vaste étude qui permit de poser les fondements des AG en calquant les principes de Darwin (sélection, croisement, mutation, chromosome, gènes). Il parvint alors, à mettre au point les étapes de l’algorithme et ses principes de codage. Il Esquissa aussi les grandes perspectives d’application des algorithmes génétiques (AG). Ces travaux ont suscité un intérêt sans cesse croissant pour les mathématiciens dont Koza qui validé rigoureusement leurs mécanismes.
 

Fonctionnement général



Analogie avec le fonctionnement biologie

Un algorithme génétique recherche les extrêmas d’une fonction définie sur un espace de données appelé population initiale. Par analogie avec la génétique, chaque individu de cette population est un chromosome et chaque caractéristique de l’individu est un gène.
Dans un cas simple, un gène sera représenté par un bit (0 ou 1), un chromosome par une chaîne de bits et un individu par un ensemble de chaîne de bits.
Pour commencer, l’AG  génère aléatoirement une population initiale (comme solutions Possibles). Il opère, ensuite à un croisement des meilleurs chromosomes (les meilleurs sont choisis par une fonction d’évaluation propre au problème à résoudre). Ce croisement (hybridation) ou crossover, en anglais, consiste en l’échange d’un certain nombre de bits (gènes) entre les deux parents. Les meilleurs enfants obtenus seront croisés, à leur tour, pour obtenir encore une meilleure génération.
L’algorithme  crée des mutation (change la valeur de quelques bits aléatoirement) pour bien imiter le processus naturel. On répète ces étapes jusqu’à ce qu’à ce qu’un enfant soit estimé proche de la solution recherchée. Ces opérateurs génétiques seront définis rigoureusement plus loin.
Champ d’application
L’AG permet d’obtenir des solutions à un problème n’ayant pas de méthode de résolution décrite précisément, ou dont la solution exacte, si elle est connue, est trop compliquée pour être calculée en un temps raisonnable. Dans ce cadre, on peut citer quelques problèmes complexes bien connus :

  • Constitution des équipes de travail

  • Voyageur de commerce

  • Implémentation optimale de points de ventes

  • Problème du sac à dos

  • Mise au point d’un emploi du temps

  • Gestion de portefeuille (placements)

  • Optimisation dans les réseaux

  • …………………

Avantage des AG
Contrairement à la recherche opérationnelle, l’AG n’exige aucune connaissance de la manière dont résoudre le problème. Il est seulement nécessaire de pouvoir évaluer la qualité de la solution. Également, dans le cas de recherche d’optimum de fonctions analytiques, on n’a besoin ni de dérivabilité ni de continuité.
La mise en œuvre d’un AG est aisée : le ‘’moteur’’ est commun; il y a donc peu de programmation spécifique au problème. Aussi, plus le problème est complexe, plus l’AG montre sa supériorité. Nous comparons, dans le tableau1, l’efficacité de l’approche classique et de l’approche génétique.



Les opérateurs génétiques
L’algorithme génétique réalise l’optimisation par la manipulation d’une population de chromosomes. À chaque génération, l’AG  crée un ensemble de nouveaux chromosomes au de diverses opérations appelées opérateurs génétiques :

La sélection qui consiste à élire des individus pour la reproduction. Les meilleurs peuvent être choisis plusieurs fois pour la prochaine génération, alors que les moins aptes auront moins de chance de l’être.

L’hybridation ou croisement (crossover) qui consiste à générer de nouveaux chromosomes par l’échange d’une partie de la chaîne entre des paires de chromosomes existants.
Exemple : 

La mutation qui consiste à changer la parité d’un chromosome pris au hasard.
Exemple : 


Éléments méthodologiques d’application des AG



Pour appliquer adéquatement l’AG, il est nécessaire d’identifier clairement les différentes étapes préalables à la programmation.

Procédé
Pour utiliser l’AG, on doit disposer de six éléments :
Un principe de codage de l’élément de population. Cette étape associe à chacun des points de l’espace considéré une structure de données. Elle se place après la phase  de modélisation mathématique du problème traité. Les codages binaires ont été les premiers à être utilisés. Actuellement, on se sert de plus en plus de codages réels notamment pour l’optimisation des problèmes à variables réelles.

Un mécanisme capable de générer une population initiale non homogène qui servira de base pour les générations futures. Ce choix conditionne la rapidité de la convergence vers l’optimum. Dans le cas où l’on ne connaît rien du problème à résoudre, il est essentiel que la population initiale soit répartie sur tout le domaine de recherche.

Une fonction à optimiser. Celle-ci retourne un réel positif appelé fonction d’évaluation (fitness).

Un mécanisme de sélection des individus candidats à l’évolution. On utilise généralement la ‘’roulette’’ du casino pour sélectionner les individus au hasard. Chaque individu occupe sur la roulette un secteur proportionnel à sa fonction d’évaluation : cela fait que le hasard est biaisé envers les éléments les plus justes (aptes) qui ont plus de chances d’être sélectionnés que les autres.

Des opérateurs permettant de diversifier la population au cours des générations et d’explorer l’espace d’état. L’opérateur de croisement recompose les gènes d’individus existants. L’opérateur de mutation a pour but de garantir l’exploration de l’espace.

Des paramètres de dimensionnement : taille de la population, critère d’arrêt, probabilité d’application des opérateurs génétiques.

Ce dernier point soulève la question de quantification. En fait, il n’existe pas de paramétrage universel. Cependant, certaines valeurs largement utilisées pour résoudre concrètement des problèmes méritent d’être retenues :

Taille de la population : entre 30 et 50 individus

Taux de croisement : entre 70% et 95%

Taux de mutation : 0,5% à1%.
Ossature de l’algorithme



Codage

Dans ce qui suit x **y signifiera x à la puissance y ; Pc probabilité de croisement et Pm probabilité de mutation.
Pour chercher le maximum d’une fonction f(x), dans l’intervalle [a, b], avec une précision de n chiffres significatifs, on procédera de la façon suivante :

L’intervalle [a, b] sera subdivisé en (b - a)(10**n) petits intervalles qui représenteront chacun un chromosome.

Chaque chromosome sera codé à l’aide de  k bits, avec k vérifiant les inéquations suivantes :
avec  a = 0000….00   et b = 1111….11.

Le code de chaque chromosome correspond à sa valeur binaire x’.

Le nombre réel correspondant au chromosome est déterminé par : x = a + x’(2/( (2**k)) – 1)

Un exemple numérique simple est donné à la fin du chapitre.

Calculs effectué pour chaque génération :

Calculer la fonction d’évaluation eval(vj) pour chaque chromosome vj.

Calculer l’évaluation totale, F, de la population (somme des évaluations de chaque chromosome).

Calculer la probabilité de sélection pj pour chaque chromosome vj : pj = eval(vj)/F.

Calculer la probabilité cumulative qj pour chaque vj (qj = p1+p2+….+pj).

Pour sélectionner, on fait tourner la roulette taille_population fois de la façon suivante : À chaque fois, on génère, au hasard, un nombre  r dans [0 , 1]  ,  Si r < q1 , sélectionner v,  Sinon, sélectionner vj , avec 2 =< j =
Pour chaque chromosome de la nouvelle population, on génère, au hasard, r dans [0,1], Si  r < Pc, sélectionner le chromosome pour le croisement,

Croiser les chromosomes ainsi obtenus deux à deux. Si le nombre de chromosomes obtenu est impair, on peut décider d’élaguer un ou de prendre un autre.

Générer, au hasard, r dans [0,1]  (autant de fois qu’il y a de bits dans toute la population). Si r =< Pm, muter le bit.

Convergence et paramétrage


 

La convergence et le choix des valeurs des paramètres des AG ne sont pas, jusque là, fixés mathématiquement de façon rigoureuse. Cependant, des heuristiques permettent d’y conclure. Aussi, leur efficacité et leur optimalité ont été constatées dans plusieurs thèses dont nous rapportons quelques résultats.
Convergence
La convergence peut être mesurée par la performance statistique : si à une certaine génération, une forte concentration d’individus s’agglutine autour du meilleur (étude de la dispersion), on peut conclure à la convergence. On peut aussi l’observer en mesurant comment les individus changent à chaque position de gène. Un gène est dit avoir convergé lorsque 95% de la population partage la même valeur. La population est qualifiée d’avoir convergé si tous les gènes ont convergé.
 
Choix des valeurs des paramètres
-Taille de la population :


  • Trop faible : l’AG n’a pas assez d’échantillons de l’espace de recherche

  • Élevée : l’AG est plus uniforme et prévenu contre la convergence prématurée dite aussi  stagnation locale ou dérive génétique.

  • Trop élevée : le nombre élevé d’évaluations de la fonction d’adaptation par génération ralentit la convergence.


-Taux de croisement :


  • Trop élevé : les bonnes structures risquent d’être cassées trop vite par rapport à l’amélioration que peut apporter la sélection.

  • Trop faible : la recherche risque de stagner à cause du faible taux d’exploration.


Le taux habituel est choisi entre 60% et 100%.
 -Taux de mutation :


  • Trop élevé : la recherche devient trop aléatoire.

  • Trop faible : la recherche risque de stagner à cause du faible taux d’exploration.


Si la taille de la population est faible, un taux de croisement faible doit être combiné avec un taux de mutation élevé. Ces observations restent valables pour les fonctions continues sans contraintes avec codage binaire.

Conclusion



La performance d’un AG dépend plus du codage et de la fonction d’évaluation que de l’influence des paramètres. Cependant, un choix judicieux de ces derniers est essentiel pour l’efficacité de l’algorithme. Il faut souligner que si les valeurs utilisées (60% à 100% pour le croisement et 0.1% à 5% pour la mutation) sont des marges de manœuvre utilisées, dans la pratique elles demeurent trop larges. Nous pensons qu’une étude à ce sujet mérite d’être menée par champs d’application (programmation dynamique, théorie de graphes…) pour de restreindre les intervalles de ces valeurs.

 

1   2   3   4   5   6   7   8   9   10

similaire:

Résumé Dans le monde de l\Programme Histoire et civilisations
«Peut-être arrivera-t-il bientôt dans la manière d’écrire l’histoire ce qui est arrivé dans la physique. Les nouvelles découvertes...

Résumé Dans le monde de l\* Culture & loisirs Expositions & musées
«Osez l’Intelligence économique avec les cci de Rhône-Alpes», ce document présente les différentes composantes et métiers de l'Intelligence...

Résumé Dans le monde de l\Les formes substantielles chez Malebranche et Leibniz
«devenir comme maître et possesseur de la nature» -, on parle de l’appropriation, de la tutelle jetée sur la nature qui fait le drame...

Résumé Dans le monde de l\Résumé S’il fallait démontrer l’actualité de Pierre Janet, IL suffit...
«La psychologie proprement dite, qui, par peur, de la métaphysique s’était jetée dans les mathématiques dans une prétendue anatomie...

Résumé Dans le monde de l\Thèse pour le Doctorat de sociologie
«Comme tous mes amis sans exception sont des êtres de grand talent et de vaste intelligence, les conceptions qu’ils expriment seraient...

Résumé Dans le monde de l\RÉsumé IL y a aujourd'hui un consensus pour reconnaître que les années...

Résumé Dans le monde de l\Un apprentissage compatible avec le cerveau
Corps-cerveau (bodybrain) : terme inventé par Susan Kovalik pour traduire l’implication dynamique et intégrée de l’ensemble de l’organisme...

Résumé Dans le monde de l\Questionnaire plan
«la bande d’adolescents» qui est aujourd’hui un phénomène actuel mais différent, d’où aujourd’hui IL est étudié différemment qu’auparavant,...

Résumé Dans le monde de l\Il livre une comparaison entre les obsessions qui effrayaient le...
«terrorisme» qui exclut le terrorisme qui fait le plus de dégâts en vies humaines et en destructions matérielles- le terrorisme d’Etat....

Résumé Dans le monde de l\L’écriture avait depuis longtemps conquis d’autres domaines que celui...
«connais-toi toi-même», si bien repris dans la pensée socratique, introduisit sur la place publique le débat principal de la réflexion...








Tous droits réservés. Copyright © 2016
contacts
b.21-bal.com