Algorithmes génétiques à la recherche de la solution la plus appropriée

2008/01/01 Galarraga Aiestaran, Ana - Elhuyar Zientzia Iturria: Elhuyar aldizkaria

• Eboluzioa
• Matematika

Dans la nature, la population initialement existante change avec le temps. De génération en génération, certains facteurs font disparaître les individus qui s'adaptent le mieux, tandis que ceux qui s'adaptent le mieux vivent. Ainsi, dans la population augmente la proportion de meilleurs. Cependant, il est possible que quelqu'un qui ne semble pas si bon continue à avoir une stratégie différente ou par hasard. Et il pourrait croiser les autres, comme les autres se croisent. Par conséquent, il est possible que la caractéristique de l'individu, prétendument mauvaise, apparaisse dans la prochaine génération dans d'autres membres.

De temps en temps, une autre variable apparaît : la mutation. Bien qu'il ne soit pas très fréquent, il influence les caractéristiques des membres de la population. En raison des croisements, mutations et agents qui misent sur les meilleurs, une fois le temps écoulé, la population est formée par les membres les mieux adaptés à l'environnement.

Il a expliqué, plus ou moins, Darwin dans la théorie de l'évolution des espèces, et c'est ce que font les algorithmes génétiques. La population initiale est constituée des solutions possibles à un problème. Ces solutions possibles sont sélectionnées au hasard et sont appelées chromosomes. Les différents aspects de chaque chromosome sont appelés gènes.

En cas de candidature, une fonction leur est appliquée. Comme c'est normal, la plupart des candidats sont inadéquats, mais d'autres, en quelque sorte, fonctionnent et restent.

Les candidats qui ont avancé se multiplient et se croisent. Par conséquent, dans la prochaine génération, certains ont plusieurs copies et d'autres ont tort. En outre, quelques-uns ne sont pas exactement les mêmes que les précédents: ils ont déménagé, c'est à dire, ils ont modifié au hasard un certain gène.

La génération résultante est différente de la précédente et l'aptitude de ces candidats est mesurée. Ainsi, les candidats qui ne sont pas meilleurs que les précédents sont écartés, ceux qui restent sont de meilleures solutions que les initiales. Ils se reproduisent et se produisent des croix et même des mutations. Les nouveaux candidats sont évalués et les meilleurs sont rééligibles, le processus est répété toutes les cent ou mille fois. La population résultante est formée de très bonnes solutions au problème.

Chiffres, lettres et arbres

Pour commencer à travailler les algorithmes génétiques, il est nécessaire de coder les solutions possibles du problème afin que l'ordinateur puisse le traiter. Une option est de coder dans les chaînes binaires : Ces chaînes sont composées de 1 et 0 et le chiffre à chaque endroit de la chaîne représente la valeur d'un aspect de la résolution.

Une autre façon de coder est par des chaînes de nombres entiers ou décimaux. Comme dans le cas précédent, le nombre à chaque endroit indique la valeur d'un aspect concret de la résolution. Vous obtenez plus de précision et de complexité qu'avec le code binaire, car il limite moins que d'utiliser deux nombres. D'autre part, les chiffres peuvent être remplacés par des lettres pour coder les candidats.

Avec ces trois méthodes il est très facile de définir les opérations qui effectueront au hasard des croix et des mutations entre les candidats; il est facile de mettre un 1 où il y a un 0 ou vice versa; ajouter ou supprimer une valeur à un nombre; ou remplacer une lettre par une autre.

En outre, il existe d'autres façons de coder, comme celle réalisée avec des arbres. Les données sont représentées ramifiées et les modifications sont effectuées en changeant la valeur des patchs ou en remplaçant certaines branches de l'arbre par d'autres.

Sélection et modification

Coder d'une manière ou d'une autre, programmer le choix des individus à copier pour la prochaine génération. La sélection peut être effectuée de différentes façons et généralement plusieurs d'entre elles sont utilisées à la fois. L'une d'elles est la sélection élitiste, c'est-à-dire la sélection des meilleurs de chaque génération. Une autre forme dépend de la capacité: à une plus grande capacité, plus de possibilités de choix.

En outre, pour garantir la diversité de la population, on peut utiliser une roue de roulette: à chaque candidat correspond une partie de la roulette; à plus grande capacité, la plupart s'adapte au candidat. En tournant la roue, ceux qui ont une grande partie ont plus de chances d'être choisis, mais il peut s'adapter à un candidat avec peu de capacité à être choisi pour la prochaine génération. Cela garantit que la prochaine génération ne soit pas trop égalitaire.

Une autre façon de garantir cela est par la réalisation de groupes par niveau de compétence et le choix des meilleurs de chaque groupe, de sorte que le meilleur du groupe à faible capacité avancerait. Les équipes peuvent également être faites au hasard et peuvent ensuite être obligés de rivaliser entre eux, les vainqueurs passent à la prochaine génération.

Il existe d'autres méthodes de sélection : sélection échelonnée, hiérarchique... Dans tous les cas, l'objectif est que les candidats de la prochaine génération soient en moyenne meilleurs que les précédents. En outre, certains changements aléatoires ont été apportés aux candidats sélectionnés pour la prochaine génération dans l'espoir que de meilleurs individus apparaissent.

Il existe deux façons de faire les changements: mutation et croisement. La mutation est de changer un aspect concret, un gène. Le croisement consiste à échanger une partie du code contre un autre candidat. Le "enfant" ainsi formé a en commun les caractéristiques des deux "parents". Il s'agit donc d'une recombinaison entre les chromosomes paternels et maternels dans la reproduction sexuelle.

Pour et contre

Grâce à la sélection, la mutation et le croisement de génération en génération, les algorithmes génétiques se rapprochent de la solution du problème. Dans de nombreux cas, l'algorithme génétique ne sera pas suffisant pour résoudre le problème, mais il peut donner des solutions raisonnablement bonnes, et en appliquant les méthodes habituelles à cette population finale, vous pouvez obtenir la meilleure solution.

Un des avantages des algorithmes génétiques est qu’ils sont «aveugles», c’est-à-dire qu’ils ne savent rien du problème qu’ils doivent résoudre. Il peut sembler plus qu'un avantage désavantageux, mais il est très bon, car il ne rejette pas dès le début un candidat avec un mauvais aspect. En outre, la croisière et la mutation créent des solutions étonnantes. D'une certaine façon, les préjugés n'affectent pas les algorithmes génétiques, ils ne se soucient que d'avancer.

En outre, ils travaillent en parallèle, c'est-à-dire sur différentes voies à la fois. La plupart des algorithmes fonctionnent en série et ne peuvent avancer que dans une direction à chaque occasion. Quand vous réalisez que vous avez pris la mauvaise voie, vous devez abandonner tout le travail et recommencer. Cependant, les algorithmes génétiques n'ont pas ce problème et sont particulièrement efficaces dans la résolution de problèmes avec de nombreuses solutions possibles.

Ils ont plus d'avantages mais aussi quelques inconvénients. La première est la difficulté d'écrire la définition du problème. Le codage des candidats n'est pas simple et il est parfois difficile d'écrire la fonction qui mesure la capacité. La taille de la population, la fréquence des mutations et des croisements, ainsi que le type et la force de la sélection, sont des facteurs très importants dans les algorithmes génétiques, qui, s'ils ne sont pas bien conçus, n'avancent pas.

Apps

Malgré leurs limites, ils sont utilisés pour résoudre des problèmes tels que acoustique, aérospatiale, astronomie et astrophysique, chimie, marché financier, jeux, géophysique, génie des matériaux, mathématiques, biologie moléculaire, télécommunications, etc.

Par exemple, en 2002, des chercheurs de l'Université Kobe du Japon ont utilisé des algorithmes génétiques pour concevoir une salle de musique. Ils sont partis d'une salle en forme de boîte à chaussures et ont défini les paramètres qu'ils devaient avoir pour obtenir la meilleure acoustique. L'algorithme a donné deux résultats, tous deux sous forme d'hôte, qui semblent avoir une acoustique spectaculaire. Selon les chercheurs, ils sont comme le Grosser Musikvereinsaal de Vienne, le meilleur du monde.

Pour sa part, la NASA les a utilisés dans la conception d'emballages, mais aussi dans l'étude des naines blanches et dans la conception des horaires. En fait, les algorithmes génétiques sont très efficaces pour la réalisation des horaires dans les entreprises, les aéroports et les écoles.

Dans les écoles, par exemple, le bon horaire est un problème. Un professeur par classe est requis et un professeur ne peut pas être dans deux salles simultanément. Bien sûr, chaque professeur doit donner son sujet et, peut-être, certains meilleurs sujets qui sont donnés à une heure et non à une autre (il ne convient pas de mettre à la dernière minute les mathématiques, la physique, etc. ). En outre, il faut tenir compte des préférences ou des besoins des enseignants. Comme il faut prendre en compte autant de facteurs, dans les grands centres, il est très difficile d'obtenir un bon programme horaire. Eh bien, les algorithmes génétiques sont parfaits.

Les experts n'ont aucun doute que, bien qu'ils soient relativement nouveaux (les premiers sont apparus dans les années 1960), ils ont eu un développement rapide et, selon les mathématiques Mª Teresa Iglesias, "il ne faut pas les arrêter".