Algorithmes génétiques - Sujets avancés

Dans cette section, nous présentons quelques sujets avancés sur les algorithmes génétiques. Un lecteur à la recherche d'une simple introduction aux GA peut choisir de sauter cette section.

Problèmes d'optimisation contraints

Les problèmes d'optimisation sous contrainte sont les problèmes d'optimisation dans lesquels nous devons maximiser ou minimiser une valeur de fonction objective donnée soumise à certaines contraintes. Par conséquent, tous les résultats dans l'espace de solution ne sont pas réalisables, et l'espace de solution contient des régions réalisables, comme illustré dans l'image suivante.

Dans un tel scénario, les opérateurs de croisement et de mutation pourraient nous apporter des solutions irréalisables. Par conséquent, des mécanismes supplémentaires doivent être utilisés dans l'AG pour traiter des problèmes d'optimisation contraints.

Certaines des méthodes les plus courantes sont -

  • En utilisant penalty functions qui réduit l'adéquation des solutions irréalisables, de préférence de sorte que l'adéquation soit réduite proportionnellement au nombre de contraintes violées ou à la distance de la région faisable.

  • En utilisant repair functions qui prennent une solution irréalisable et la modifient pour que les contraintes violées soient satisfaites.

  • Not allowing infeasible solutions entrer dans la population du tout.

  • Utiliser un special representation or decoder functions qui garantit la faisabilité des solutions.

Contexte théorique de base

Dans cette section, nous discuterons du schéma et du théorème de la NFL ainsi que de l'hypothèse du bloc de construction.

Théorème de schéma

Les chercheurs ont essayé de comprendre les mathématiques derrière le fonctionnement des algorithmes génétiques, et le théorème de schéma de Holland est un pas dans cette direction. Au cours de l'année, diverses améliorations et suggestions ont été apportées au théorème de schéma pour le rendre plus général.

Dans cette section, nous ne nous plongerons pas dans les mathématiques du théorème de schéma, nous essayons plutôt de développer une compréhension de base de ce qu'est le théorème de schéma. La terminologie de base à connaître est la suivante -

  • UNE Schemaest un «modèle». Formellement, c'est une chaîne sur l'alphabet = {0,1, *},

    où * est indifférent et peut prendre n'importe quelle valeur.

    Par conséquent, * 10 * 1 pourrait signifier 01001, 01011, 11001 ou 11011

    Géométriquement, un schéma est un hyperplan dans l'espace de recherche de solution.

  • Order d'un schéma est le nombre de positions fixes spécifiées dans un gène.

  • Defining length est la distance entre les deux symboles fixes les plus éloignés du gène.

Le théorème de schéma stipule que ce schéma avec une aptitude supérieure à la moyenne, une longueur de définition courte et un ordre inférieur est plus susceptible de survivre au croisement et à la mutation.

Hypothèse de base

Les Building Blocks sont des schémas d'ordre bas, de faible longueur de définition avec la forme moyenne donnée ci-dessus. L'hypothèse des blocs de construction dit que ces blocs de construction servent de base au succès et à l'adaptation de l'AG dans les AG à mesure qu'il progresse en identifiant et en recombinant successivement ces «blocs de construction».

No Free Lunch (NFL) Théorème

Wolpert et Macready ont publié en 1997 un article intitulé «Aucun théorème de déjeuner gratuit pour l'optimisation». Il déclare essentiellement que si nous faisons la moyenne sur l'espace de tous les problèmes possibles, alors tous les algorithmes de boîte noire non revisitant présenteront les mêmes performances.

Cela signifie que plus nous comprenons un problème, notre GA devient plus spécifique au problème et donne de meilleures performances, mais il compense cela en fonctionnant mal pour d'autres problèmes.

Apprentissage automatique basé sur GA

Les algorithmes génétiques trouvent également une application dans l'apprentissage automatique. Classifier systems sont une forme de genetics-based machine learning(GBML) fréquemment utilisé dans le domaine de l'apprentissage automatique. Les méthodes GBML sont une approche de niche de l'apprentissage automatique.

Il existe deux catégories de systèmes GBML -

  • The Pittsburg Approach - Dans cette approche, un chromosome a codé une solution, et ainsi la forme physique est attribuée aux solutions.

  • The Michigan Approach - une solution est généralement représentée par de nombreux chromosomes et la forme physique est donc attribuée à des solutions partielles.

Il faut garder à l'esprit que les problèmes standard tels que le croisement, la mutation, le lamarckien ou le darwinien, etc. sont également présents dans les systèmes GBML.