Dans le cadre du T.I.P.E de seconde année de classe préparatoire aux Grandes Écoles, j’ai travaillé sur la recherche de rapporteurs de Golomb via les algorithmes génétiques ; une idée originale développée par André Nabonne sur son site internet).
Les algorithmes génétiques font parti de la famille des algorithmes évolutifs, et s’inspirent de l’évolution biologique telle que décrite par Darwin. Leur principale utilisation est la résolution de problèmes concrets d’optimisation, trop complexes pour être résolus de façon exhaustive, tel le problème du voyageur de commerce, où l’on cherche le meilleur itinéraire (c’est-à-dire le plus court) pour relier un nombre fini de villes.
Dans cet article, nous étudierons la possibilité d’appliquer les algorithmes génétiques pour découvrir des rapporteurs de Golomb.
Qu’est qu’un rapporteur de Golomb ?
Le mathématicien Solomon W. Golomb présenta en premier lieu « la règle de Golomb » qui est une règle mesurant plus de longueurs (discrètes) que le nombre de marques qu’elle contient. De plus, la même distance n’est pas mesurée deux fois.
Un exemple simple de cette règle est celle constituée des marques 0; 1; 4; 6 qui permet de mesurer les longueurs 1; 2; 3; 4; 5 et 6 une et une seule fois entre deux marques de la règle.
C’est en partant de cet exemple simple que la question s’est posée pour les rapporteurs : est-il possible de faire un rapporteur avec le moins de marque possible qui mesure les angles de 1 à 360 degrés ? Un rapide calcul montre que la limite minimale théorique est de 20 marques : en effet, avec 
La solution de l’algorithme génétique semble adaptée à ce problème. En effet, si pour 20 marques, l’on voulait tester toutes les possibilités, afin de trouver celle qui permet la mesure de 180 angles (si tant est que ce soit possible), avec les marques 0 et 1 fixées (une simple rotation nous y ramène), il faudrait près de 
Plan de l’algorithme
Génération : L’algorithme génétique présenté sur l’organigramme débute avec une génération de 
On calcule ensuite pour chaque rapporteur le nombre d’angles qu’il mesure, sachant que l’on cherche à en obtenir un mesurant tous les angles de 1 à 360 degrés.
Puis on répète le processus suivant un nombre fini de fois : (c’est-à-dire de générations)
- Calculs de la moyenne, du minimum, et du maximum d’angles mesurés, ce qui servira pour la sélection, et pour observer l’évolution de la population.
- Évaluation : On attribue à chaque rapporteur une probabilité de survie, dépendant du nombre d’angles qu’il mesure. Plus un rapporteur mesurera d’angles, plus il aura de chance de survivre. Les différentes fonctions d’évaluation seront décrites et comparées plus loin.
- Sélection : Si un rapporteur « survit », on le conserve pour la génération suivante. Sinon, on choisit au hasard deux parents, que l’on croise (Croisement) pour obtenir un « enfant », dont on compte les angles.
On obtient ainsi une nouvelle génération de même taille, sur laquelle on effectue éventuellement des mutations, avant de recommencer le processus.
Evaluation
Différents types de fonctions d’évaluation ont été étudiés afin d’obtenir une vitesse de convergence optimale, ainsi qu’un échantillonnage optimal. Le but étant de sélectionner les meilleurs individus, tout en
laissant une part de « moins bons » individus pour conserver une certaine diversité et variabilité. On évite ainsi la convergence rapide vers un individu optimal localement mais non solution au problème.
Rang Affine
Le type affine fait correspondre à chaque individu une probabilité de survie qui est fonction affine du nombre d’angle 
Cependant les meilleurs résultats ont été obtenus en utilisant des coefficients variables dépendant des variables moyenne, minimum et maximum du nombre d’angles mesurés.
Le type exponentiel fait correspondre à chaque individu une probabilité de survie qui est fonction exponentielle du nombre d’angle 
Rang Exponentiel
Une autre méthode, qui a produit de meilleurs résultats, est d’attribuer à chaque individu son rang (fonction du nombre d’angles mesurés), et de se servir de celui-ci plutôt que du nombre d’angles mesurés pour l’évaluation. Un tri par dénombrement a été utilisé pour déterminer le rang de chaque individu. L’évaluation peut ici aussi être fonction affine ou exponentielle du rang. Une comparaison entre ces deux méthodes sur 500 générations (statistiques sur plusieurs populations) révèle une convergence plus rapide et pas moins optimale pour la méthode affine.
Sélection
Deux méthodes ont été envisagées : soit construire la nouvelle génération uniquement à partir d’ « enfants » obtenus par croisement (cf. partie Croisement) de 2 parents, soit remplacer uniquement les parents non sélectionnés, et conserver ceux qui ont « survécu ». C’est cette dernière méthode qui a été retenue.
L’algorithme initial ne gardait pas les meilleurs individus, ce qui a été résolu par la suite. C’est ce que l’on appelle la méthode élitiste, qui a montré ses preuves dans beaucoup d’études faites sur les algorithmes génétiques, y compris sur cet exemple.
Croisement
Le premier croisement étudié était un croisement très simple : les tableaux de chaque parent étaient parcourus simultanément et, une des deux valeurs choisie aléatoirement (sauf si elle a déjà été choisie)
constituait la nouvelle valeur pour l’enfant créé. Cependant, cette méthode ne conservait pas la structure des parents, et était de ce fait trop aléatoire.
Le second croisement fut un croisement à 1 point : l’ordinateur choisissait un angle au hasard et découpait les parents pour fabriquer deux enfants, l’enfant 1 ayant la première moitié du parent 1 et la seconde du parent 2, et inversement pour l’enfant 2. A la vue de divers ouvrages sur les algorithmes génétiques, il nous est apparu que le croisement à deux points était plus avantageux (même principe qu’à un point mais avec un découpage en trois parties). En effet, il permet plus de combinaisons possibles à partir de mêmes parents, et ainsi permet une plus grande variabilité des individus. Ce fut donc le troisième et dernier croisement testé, et celui gardé pour l’algorithme final. Le choix entre les deux enfants est aléatoire, afin de ne pas nuire à la diversité en choisissant systématiquement le meilleur enfant.
Mutation
Là également diverses méthodes ont été essayées, mais elles n’ont pas donné de résultats significativement différents. Le principe est le même à chaque fois : on parcourt la population, on génère un nombre décimal aléatoirement entre 0 et 100, et s’il est inférieur à un coefficient de mutation défini au début de l’algorithme, on mute l’individu. La première mutation essayée était la modification d’un angle choisi au hasard en lui rajoutant plus ou moins 1. La seconde était le remplacement d’un angle au hasard par un nouvel angle choisi aléatoirement entre le précédent et le suivant.
La troisième mutation testée, et celle qui a été conservée, permet de jouer sur chaque angle de chaque individu, définissant le coefficient de mutation non plus pour un individu mais pour chaque angle. Ceci complique l’algorithme, mais a permis d’avantage de résultats pour 25 marques.
De la même façon pour le croisement, il est possible d’utiliser une méthode élitiste, c’est-à-dire de conserver l’individu obtenu après mutation seulement s’il est meilleur que l’original.
Celle-ci semble diminuer encore une fois la diversité, mais la comparaison ci-contre permet tout de même de valider celle-ci, et de décider du meilleur coefficient de mutation à choisir.
Un minimum de mutation est nécessaire pour améliorer et diversifier les individus. Mais s’il est trop élevé, chaque individu a une trop grande probabilité d’être muté, et de ce fait les résultats deviennent trop aléatoires.
Autre piste intéressante
Comme suggéré par André Nabonne, sur le site Internet sur lequel il a effectué un travail semblable, il est possible de rechercher les meilleurs éléments pour un nombre de marques moins important et le compléter ensuite pour obtenir un rapporteur qui mesure 360 angles avec 1 à 2 marques supplémentaires. Cependant ce n’est pas la méthode qu’il lui a permis de battre le record précédemment détenu par J. Cottereau avec 24 marques, en obtenant des rapporteurs de 23, et même de 22 marques.
Oui c’est joli le blabla… Mais on peut voir un vrai rapporteur de Golomb ?
– Pour 27 marques : 0, 8, 14, 40, 41, 42, 45, 58, 75, 99, 146, 151, 153, 175, 179, 180, 193, 218, 241, 276, 285, 300, 321, 323, 331, 348, 349
– Pour 26 marques : 0, 5, 49, 51, 65, 91, 92, 97, 107, 115, 136, 144, 148, 176, 180, 198, 200, 207, 210, 211, 219, 270, 287, 305, 327, 330
– Pour 25 marques : 0, 22, 41, 42, 44, 56, 60, 106, 132, 137, 189, 191, 219, 235, 236, 244, 246, 259, 310, 315, 322, 343, 347, 353