-
Notifications
You must be signed in to change notification settings - Fork 2
Mise en Cohérence des Objectifs du Tipe
INFORMATIQUE (Informatique pratique), INFORMATIQUE (Informatique Théorique). MATHEMATIQUES (Mathématiques appliquées)
- Algorithme génétique = Genetic algorithm
- Fonction d'adéquation = Fitness Function
- Enjambement/Recombinaison = Crossover
- Mutation = Mutation
- Régression symbolique = Symbolic regression (G. Pauvert)
- Expression régulière = Regular expression (G. Bertholon)
En 1859, Charles Darwin établit un modèle pour expliquer l'évolution des formes biologiques basé sur le principe de sélection naturelle. L'adéquation d'un individu à son environnement détermine la probabilité avec laquelle ses caractéristiques sont transmises à la génération suivante, avec une éventuelle modification ou recombinaison [1]. Cette évolution probabiliste peut facilement s'adapter à un problème d'optimisation informatique en simulant le processus naturel. John Holland a ainsi initié les algorithmes génétiques dans son œuvre Adaptation in Natural and Artificial Systems publiée en 1975 [2 page 2].
La simulation de l'évolution d'une population nécessite de représenter les individus à l'aide d'une structure de données adaptée au problème traité (arbre, séquence binaire, etc [3 chapitres 6-7]) et de choisir une fonction d'adéquation permettant d'évaluer les individus selon les critères établis par les contraintes du problème. Le problème se ramène à une recherche de maximum pour cette fonction sur l'ensemble des individus.
L'algorithme consiste à faire évoluer une population initiale choisie pour être représentative de l'espace de recherche en construisant itérativement de nouvelles générations par mutations et recombinaisons entre individus parmi les mieux adaptés. La réponse au problème d'optimisation est le meilleur individu de la dernière génération [2 figure 4, 3 partie I]. Les opérateurs génétiques (initialisation, mutation, recombinaison et méthode de sélection) dépendent fortement du problème et il en existe de nombreuses variantes [3 partie II].
Bien qu'ils apportent empiriquement des résultats satisfaisants pouvant rivaliser avec des solutions basées sur une recherche conventionnelle [4], les algorithmes génétiques n'offrent que peu de garanties théoriques sur leur convergence vers un maximum global. En effet, si l'algorithme converge nécessairement dans le cas où le meilleur individu est conservé d'une génération à l'autre [5], rien n'indique que dans ce cas la vitesse de convergence soit acceptable et que le résultat en temps limité soit meilleur que celui d'une recherche purement aléatoire.
Le problème du bloat, c'est-à-dire le remplissage de la totalité de la population par des individus proches d'un même maximum local, peut fortement freiner l'évolution. Des solutions à ce problème ont été développées pour assurer une certaine diversité de la population [6], comme l'ajout d'individus formés de manière aléatoire à chaque génération.
Le domaine d'application des algorithmes génétiques est très varié, ils permettent par exemple de concevoir des filtres électroniques ou de créer des programmes de manière automatisée [2, 3 chapitre 12, 4]. Cependant, le No Free Lunch theorem montre qu'il est impossible de trouver des opérateurs génétiques performants pour tous les problèmes à la fois.
Appliqué à la régression symbolique, un algorithme génétique permet d'approximer un nuage de points par une fonction obtenue en cherchant à minimiser les écarts verticaux des points à sa courbe représentative. L'implémentation nécessite le choix d'un ensemble d'opérateurs mathématiques servant à former les expressions symboliques et de nombreux paramètres influant sur le déroulement du programme [7]. L'utilisation de la régression symbolique pour la modélisation de séries temporelles permet d'effectuer des prévisions stochastiques, notamment dans le domaine de l'économie (bourse, etc.) [8].
Dans le cadre de la recherche d’expression régulière, l’objectif est de trouver une expression régulière qui valide un type de chaînes de caractères à partir d'un ensemble représentatif d’exemples et de contre-exemples. Les recherches récentes sur l’extraction textuelle permettent désormais d’obtenir de meilleurs résultats avec un algorithme génétique qu'avec des sujets humains pour fabriquer une expression régulière qui reconnaisse un type précis d’information au milieu d’un texte [9]. Pour cela les chercheurs ont combiné le mécanisme d’algorithme génétique avec une méthode diviser pour régner pour traiter les alternatives (|). Parallèlement, l’utilisation des algorithmes génétiques dans la recherche d’expression régulière s’est montrée utile pour la création automatisée de filtres anti-spam [10].
Les algorithmes génétiques sont un pilier des méta-heuristiques et plus généralement des algorithmes d'optimisation.
L'implémentation d'un algorithme génétique ouvre de nombreuses perspectives d'exploitation et d'expérimentation. Le paramétrage est délicat et dépend du problème traité.
Je prévois de coder un système générique et facilement paramétrable d’algorithme génétique en OCaml avec mon binôme et de l’utiliser pour réaliser la régression symbolique d'un set de points donné. Je me propose ensuite d'étudier l’influence du choix des paramètres et opérateurs génétiques sur les individus générés pour essayer d’optimiser les résultats de mes expériences sur la régression symbolique.
Je prévois premièrement de coder avec mon binôme un système générique et facilement paramétrable d’algorithme génétique en OCaml. Je compte ensuite me concentrer uniquement sur le problème de la recherche d'expression régulière. Il faudra alors programmer les opérateurs génétiques appropriés puis produire des tests qui consisteront en deux lots d'exemples et de contre-exemples afin de valider la solution sur des données différentes de l'entrée et donc de vérifier la pertinence des résultats. Je pense alors étudier l’influence du choix des paramètres sur les individus générés pour essayer d’optimiser les résultats et ajouter la méthode diviser pour régner pour les alternatives.
[1] Charles Darwin: L'origine des espèces: https://fr.wikisource.org/wiki/L%E2%80%99Origine_des_esp%C3%A8ces
[2] John R. Koza : Genetic Programming as a Means for Programming Computers by Natural Selection : http://www.genetic-programming.com/jkpdf/scjournallong.pdf - DOI: 10.1007/BF00175355
[3] Riccardo Poli, William B. Langdon, Nicholas F. McPhee : A Field Guide to Genetic Programming : http://dces.essex.ac.uk/staff/rpoli/gp-field-guide/A_Field_Guide_to_Genetic_Programming.pdf - ISBN: 978-1-4092-0073-4
[4] John R. Koza : Human-Competitive Awards 2004 – Present : https://ls11-www.cs.uni-dortmund.de/people/rudolph/publications/papers/TNN5.1.pdf
[5] Günter Rudolph : Convergence Analysis of Canonical Genetic Algorithms : https://ls11-www.cs.uni-dortmund.de/people/rudolph/publications/papers/TNN5.1.pdf
[6] Sara Silva, Ernesto Costa : Dynamic limits for bloat control in genetic programming and a review of past and current bloat theories : DOI: 10.1007/s10710-008-9075-9
[7] Chi Zhang : Genetic Programming for Symbolic Regression : http://web.eecs.utk.edu/~czhang24/projects/cs528_Project2_Zhang.pdf
[8] Thomas Vallée, Murat Yıldızoglu : Présentation des algorithmes génétiques et de leurs applications en économie : http://deptinfo.unice.fr/twiki/pub/Minfo04/IaDecision0405/Prsentationdesalgorithmesgntiquesetdeleursapplicationsenconomie_P.pdf
[9] Alberto Bartoli, Andrea De Lorenzo, Eric Medvet, Fabiano Tarlao : Can A Machine Replace Humans In Building Regular Expressions? A Case Study : http://www.human-competitive.org/sites/default/files/bartoli-delorenzo-medvet-tarlao-is-paper.pdf
[10] Vitor Basto-Fernandes, Iryna Yevseyeva, Rafael Z. Frantz, Carlos Grilo, Noemí Pérez Díazd, Michael Emmerich : An automatic generation of textual pattern rules for digital content filters proposal, using grammatical evolution genetic programming : www.sciencedirect.com/science/article/pii/S2212017314002576