Le théorème du schéma de Holland

Le schéma 1*10*1 décrit l'ensemble de toutes les chaînes de longueur 6 avec des 1 aux positions 1, 3 et 6 et un 0 à la position 4. Le * est un symbole de remplacement, ce qui signifie que les positions 2 et 5 peuvent avoir une valeur de 1 ou de 0. L'ordre d'un schéma o ( H ) {\displaystyle o(H)} est défini comme le nombre de positions fixes dans le modèle, tandis que la longueur de définition δ ( H ) {\displaystyle \delta (H)} est la distance entre la première et la dernière position spécifique. L'ordre de 1*10*1 est 4 et sa longueur de définition est 5. L'adéquation d'un schéma est l'adéquation moyenne de toutes les chaînes correspondant au schéma. L'adéquation d'une chaîne est une mesure de la valeur de la solution codée du problème, telle que calculée par une fonction d'évaluation spécifique au problème. En utilisant les méthodes établies et les opérateurs génétiques des algorithmes génétiques, le théorème du schéma stipule que les schémas courts, d'ordre inférieur, dont l'aptitude est supérieure à la moyenne, augmentent de manière exponentielle au cours des générations successives. Exprimé sous la forme d'une équation :

E ( m ( H , t + 1 ) ) ≥ m ( H , t ) f ( H ) a t [ 1 - p ] . Nom de l'opérateur {E} (m(H,t+1))\geq {m(H,t)f(H) \over a_{t}}[1-p]. }

Ici, m ( H , t ) est le nombre de chaînes de caractères appartenant au schéma H à la génération t f(H) est l'aptitude moyenne observée du schéma H et a t est l'aptitude moyenne observée à la génération t. La probabilité de perturbation p {\displaystyle p} est la probabilité que le croisement ou la mutation détruise le schéma H {\displaystyle H} . Elle peut être exprimée sous la forme :

p = δ ( H ) l - 1 p c + o ( H ) p m {\displaystyle p={\delta (H) \over l-1}p_{c}+o(H)p_{m}}

où o ( H ) est l'ordre du schéma, l est la longueur du code, p m est la probabilité de mutation et p c est la probabilité de croisement. Ainsi, un schéma dont la longueur de définition est plus courte δ ( H )/style d'affichage \delta (H)} est moins susceptible d'être perturbé.
Un point souvent mal compris est la raison pour laquelle le théorème du schéma est une inégalité plutôt qu'une égalité. La réponse est en fait simple : le théorème néglige la faible, mais non nulle, probabilité qu'une chaîne appartenant au schéma H soit créée "de toutes pièces" par mutation d'une seule chaîne (ou recombinaison de deux chaînes) qui n'appartenait pas au schéma H dans la génération précédente.

Le théorème du schéma tient sous l'hypothèse d'un algorithme génétique qui maintient une population infiniment grande, mais ne se reporte pas toujours à la pratique (finie) : en raison d'une erreur d'échantillonnage dans la population initiale, les algorithmes génétiques peuvent converger sur des schémas qui n'ont pas d'avantage sélectif. Cela se produit notamment dans l'optimisation multimodale, où une fonction peut avoir plusieurs pics : la population peut dériver pour préférer l'un des pics, en ignorant les autres.

La raison pour laquelle le Schéma Théorème ne peut pas expliquer la puissance des algorithmes génétiques est qu'il s'applique à tous les cas de problèmes et ne peut pas faire la distinction entre les problèmes pour lesquels les algorithmes génétiques sont peu performants et ceux pour lesquels ils sont performants.