Règles et rapporteurs de Golomb par algorithme génétique

Résumé / Abstract

La détermination de règles de Golomb optimales fait l'objet de nombreuses recherches.
Le problème voisin des "rapporteurs de Golomb" a été moins étudié. Nous présentons ici les résultats obtenus à partir d'un algorithme génétique, qui a permis d'améliorer la meilleure solution connue jusqu'alors.

The determination of optimal Golomb or sparse rulers is the target of multiple researches.
We present here the associated notion of "Golomb protractors", and the results we reached starting with a genetic algorithm. This one has allowed to improve the best solution known so far.

Les règles optimales de Golomb (ou "OGR", pour Optimal Golomb Rulers), introduites par le mathématicien du même nom, ont des applications pratiques dans divers domaines (cristallographie à rayons X, radioastronomie, combinatoire, théorie du codage, communications…).

Le site du "projet OGR" pourra être consulté pour avoir accès à l'ensemble des connaissances sur le sujet, et aux records actuels.

La détermination des OGR constitue un problème dit "NP-complet", dont la complexité croit exponentiellement avec la taille.

Les algorithmes génétiques sont particulièrement adaptés à la résolution de ce type de problèmes: on verra par exemple la première tentative d'adaptation aux OGR réalisée en 1995 par Soliday, Homaifar, Lebby. Ils ne permettent cependant en général pas d'obtenir des solutions optimales.

La notion de "rapporteur de Golomb" est voisine de celle des OGR. Elle a été définie et étudiée par quelques auteurs: on consultera sur ce sujet les numéros de décembre 1981, janvier et mars 2000 du magazine Pour la Science.

Le problème est celui de la construction d'un rapporteur ayant un nombre minimal de marques, capable de mesurer tous les angles exprimés en degrés, de 1 à 360.

Le meilleur résultat obtenu était un rapporteur de 24 marques. La réalisation d'un programme basé sur un algorithme génétique m'a permis d'améliorer deux fois ce résultat, en produisant des rapporteurs de 22 marques seulement.