Kilomaths.com

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é Narbonne sur son site internet (apparemment plus disponible).

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 ?

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 opérations pour construire les rapporteurs, et d’avantage encore () pour compter le nombre d’angles qu’ils mesurent.

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 rapporteurs (entre une centaine et quelques milliers par exemple), c’est-à-dire des tableaux de taille (nombre de marques désiré), contenant des angles compris entre 0 et 359, triés par ordre croissant. Le tri de ces tableaux est une opération relativement coûteuse (utilisation du tri rapide), mais il n’est effectué qu’une fois au début de l’algorithme.

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.

Le type affine fait correspondre à chaque individu une probabilité de survie qui est fonction affine du nombre d’angle qu’il mesure, c’est-à-dire de la forme , où et sont à déterminer arbitrairement.

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 qu’il mesure, c’est-à-dire de la forme , où et sont à déterminer arbitrairement. En agissant sur les coefficients, on peut accentuer ou diminuer la courbure selon la méthode de sélection voulue.

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

La nature est mathématique, les chefs-d’œuvre de l’art sont en consonance avec la nature ; ils expriment les lois de la nature et ils s’en servent.

Le Corbusier est un architecte, urbaniste et peintre française d’origine Suisse (1887-1965). Il a réalisé de nombreuses constructions en adoptant un module humain servant de base pour déterminer les dimensions des habitations comme celles de la Cité radieuse à Marseille en 1947. Il a appelé ce module le « modulor » : il s’agit d’un mot-valise composé sur « module » et « nombre d’or ». En effet, les proportions fixées par le modulor sont directement liées au nombre d’or. Le Modulor est né de l’observation de la nature, de l’étude des oeuvres d’art, de leurs tracés régulateurs (Choisy) et des travaux de Matila Ghyka consacrés au Nombre d’or dans la nature et dans l’art.

Le Corbusier affirmait que le Modulor (à l’échelle humaine) avait des avantages sur les deux systèmes de mesure qui divisent la planête : le système anglo-saxon du pied-pouce, peu pratique mais qui tient compte des mesures du corps, et le système métrique, décimal donc pratique, trop abstrait cependant, privé de  lien direct avec les dimensions du corps. Elle devait permettre, selon lui, un confort maximal dans les relations entre l’homme et son espace vital.

L’examen de ce dessin, qu’il a lui-même coté, montre :

soit le nombre d’or (à un millième près)

et soit le nombre d’or (à 4 millième près)

De même, le rectangle des pieds de l’homme à sa tête est un rectangle d’or, c’est-à-dire que le rapport de ces cotés est égal au nombre d’or.

Le Corbusier a indiqué les dimensions de l’homme debout accoudé, puis assis, assis accoudé… et le rapport des dimensions est toujours

où est le nombre d’or.

Les chiffres retenus par Le Corbusier sont des valeurs approchées. L’exactitude mathématique le préoccupe moins que de proposer une échelle d’harmonie visuelle qui puisse guider l’action de l’architecte.

Sources :

• http://expo.ifrance.com/lenombre/le%20corbusier.htm
• Le Modulor : ultime résurgence du mythe ?
• http://www.lenombredor.free.fr/modulor.htm

Aujourd’hui, Google se revêt d’un logo personnalisé (comme quelques fois dans l’année) pour une fois très mathématiques :

Nous sommes le 14 mars (la date s’écrit 3/14 en format américain) et aujourd’hui on honore la constante mathématiques . On la célèbre généralement à 1h59 (le matin si on utilise le format « 24h » et à quatorze heure moins une si on utilise le format « 12h ») dans les départements mathématiques de nombreuses universités pour obtenir l’approximation bien connue

.

Pendant ces festivités, on imagine un monde sans pi, on mange des pie (tartes) en buvant de la piña colada…

Sur le logo de Google, on retrouve l’aide d’un cercle de rayon :

la représentation graphique de la période d’un sinus (ou d’un cosinus), deux approximations de pi :

,

(l’encradrement est dû à Archimède, en 350 av. J.-C.) les volumes d’une sphère de rayon et d’un cylindre de hauteur et de base un disque de rayon :

et finalement la circonférence d’un cercle de rayon : .

Aujourd’hui, voir qu’on était la journée de m’a rappelé un livre que j’ai lu récemment :

Je suis né un jour bleu, de Daniel Tammet. Il s’agit d’une autobiographie écrite par un anglais atteint du syndrome d’Asperger, une forme d’autisme de haut niveau.

J’ai trouvé cette autobiographie très intéressante : elle permet en premier lieu de découvrir comment les autistes appréhendent le monde et nous aide à comprendre les réactions de ces derniers. Une autre chose extrêmement troublante et intrigante est la synesthésie du personnage : l’auteur nous montre comment il modélise les nombres et les mots par des formes et des couleurs, ce qui lui permet d’accomplir des prouesses extraordinaires telles que mémoriser plus de 22500 décimales du nombre , faire des calculs mentaux aussi rapidement qu’une machine ou apprendre une nouvelle langue en quelques semaines. Ce record est le record européen et date du 15 mars 2004 : pendant 5 heures et 9 minutes, Danniel Tammet a énoncé les décimales de en parcourant les paysages de son esprits représentés par le nombre . Ce livre nous apprend beaucoup d’autre chose sur le regard d’un autiste sur le monde, mais ceci ne rentrerait pas vraiment dans le cadre de cet article.

L’année dernière, Daniel Tammet a d’ailleurs écrit un poème sur le nombre à l’occasion de la journée du Pi 2009 :

PI

Three, One, Four, One, Five, and On
The numbers recount their endless tale.
Three – Barefoot green, a silent voice.
White as hunger, One is twice
Bright like babies’ eyes.
Four is timid, envious of E.
Five, Punctuation or a pregnant sigh
Precedes proud Nine, colour of falling night.
Two, an unfastened knot,
A wayward wind, the hollow of Six resounding.
Nearby, Eight, a cloud of fireflies above a lake
Over which I skim Sevens
Remembering that Zero is nothing but a circle.

On trouvera la traduction en français de ce poème, par Daniel Tammet lui-même, sur son blog. Ce poème rappelle bien évidemment les moyens mnémotechniques que l’on peut utiliser pour retenir les décimales du nombre via un poème par exemple :

Que j’aime à faire apprendre ce nombre utile aux sages !	3 1 4 1 5 9 2 6 5 3 5
Immortel Archimède, artiste ingénieur,	8 9 7 9
Qui de ton jugement peut priser la valeur ?	3 2 3 8 4 6 2 6
Pour moi, ton problème eut de pareils avantages.	4 3 3 8 3 2 7 9
Jadis, mystérieux, un problème bloquait	5 0 2 8 8
Tout l’admirable procédé, l’œuvre grandiose	4 1 9 7 1 6 9
Que Pythagore découvrit aux anciens Grecs.	3 9 9 3 7 5
Ô quadrature ! Vieux tourment du philosophe	1 0 5 8 2 9
Insoluble rondeur, trop longtemps vous avez	9 7 4 9 4 4
Défié Pythagore et ses imitateurs.	5 9 2 3 0
Comment intégrer l’espace plan circulaire ?	7 8 1 6 4 0
Former un triangle auquel il équivaudra ?	6 2 8 6 2 0
Nouvelle invention : Archimède inscrira	8 9 9 8
Dedans un hexagone ; appréciera son aire	6 2 8 0 3 4
Fonction du rayon. Pas trop ne s’y tiendra :	8 2 5 3 4 2 1 1 7
Dédoublera chaque élément antérieur ;	0 6 7 9
Toujours de l’orbe calculée approchera ;	8 2 1 4 8 0
Définira limite ; enfin, l’arc, le limiteur	8 6 5 1 3 2 8
De cet inquiétant cercle, ennemi trop rebelle	2 3 0 6 6 4 7
Professeur, enseignez son problème avec zèle	0 9 3 8 4 4

(la longueur de chaque mot donne une décimale (un mot de 10 lettres code zéro) et la ponctuation ne code rien.) et si jamais cela vous parait trop compliqué, vous pouvez toujours déclamer :

How I wish I could enumerate Pi easily, since all these horrible mnemonics prevent recalling any of pi’s sequence more simply.

Bon, il est temps d’aller se préparer une bonne tarte chocolatée avec pour fêter ce nombre si extraordinaire.

Et pour les colleurs de prépa en première année de la semaine prochaine, un petit exercice est tout indiqué pour faire travailler la décomposition en éléments simples :

En calculant l’intégrale

,

montrer que .

Bonne journée !

Pour aller plus loin, quelques liens :

• Journée de Pi (wikipédia)
• Records de déclamations de Pi
• Une tétralogie par Eljj sur son blog de vulgarisation (1-2-3-4)
• Beaucoup de choses sur le nombre Pi

Jeudi 24 septembre 2009, des chercheurs américains et thaïlandais ont annoncé avoir mis au point un vaccin permettant de réduire de 31,2 % les infections au virus du sida. Cette information a circulé tout autour de la terre comme un formidable message d’espoir… Dans l’article que j’ai lu, ils parlaient d’une expérience effectuée sur 16000 individus… qui ont été divisés en deux groupes, l’un ayant le vaccin et le second un placebo. Cependant, aucune autre information n’était disponible : combien de cas de sida dans chaque groupe, comment ont été constitués les groupes, quels étaient les risques de contamination des individus, et un certain nombre d’informations importantes… Et surtout : comment ce nombre de 31,2% a-t-il été calculé ?

Ne disposant pas de ces résultats et voulant mettre en garde les étudiants de médecine auxquels je donnais des cours cette année, je leur ai fait tester l’hypothèse : « le vaccin n’a aucun effet » sur un échantillon de 16000 personnes, 6000 ayant reçu le vaccin et 10000 un placebo; avec une prévalence (très élevée) de 1% dans la population. Ainsi, sur le groupe de 10 000 individus, 100 présentaient le virus, et 42 parmi le groupe ayant été vacciné, ce qui – ramené à effectif comparable – est une baisse de 30% du virus du sida. Après de petits calculs, on ne peut pas rejeter l’hypothèse faite au risque 5%… c’est-à-dire qu’il est possible que les différences d’effectifs soient le seul fait du hasard (mais pas forcément que le vaccin n’a eu aucun effet) à 95% ! Conclusion : impossible d’en dire plus…

Aujourd’hui, je suis tombé sur une brève de l’AFP, expliquant un peu mieux comment ont été formés les groupes, etc. En refaisant une comparaison de pourcentage à l’aide du test du , on obtient au risque 5% le rejet de l’hypothèse, c’est-à-dire qu’avec un risque de 5% de se tromper, on peut dire que le vaccin a eu un effet ! Bon, après, il faut relativiser : le chiffre avancé de 31,2% est assez… arbitraire ! Rien ne dit que le vaccin provoque une immunité dans 30% des cas : ce chiffre est fortement contesté par la communauté scientifique. De plus, ce sont deux groupes de volontaires, donc ce n’est pas un essai thérapeutique randomisé, on ne sait pas s’il s’agit d’un test en double aveugle (c’est-à-dire médecins et patients ignorent s’ils ont le vaccin ou un placebo) ou si seul le patient ignore le produit qui lui a été injecté. On ne sait rien des effets à long terme, et on ne sait pas si ce vaccin serait utilisable en Afrique (population à haut risque, avec un type différent de virus) !

Bref, une modeste avancée, mais qui s’avère statistiquement significative au risque 5%… Mais on est loin des 31,2% de protection annoncés !

Le matraquage médiatique et les pourcentages lancés sans aucune explication permettent une manipulation importante d’une population non prévenue… Il existe de nombreux exemples de cette manipulation :

- Suite au premier tour de l’élection présidentielle française en 2002 (et la surprise pour une grande partie des français des résultats du front national), le canard enchaîné (hebdomadaire satirique) avait publié une image mettant en avant la corrélation entre les retombées radioactives de Tchernobyl et les résultats du Front National dans les départements

Mais ce qu’il faut savoir, c’est qu’une corrélation entre deux phénomènes de ce genre, en mathématiques, indique une relation du genre :

si on est dans une région ayant eu de fortes retombées suite à la catastrophe de Tchernobyl, alors le vote Front National est élevé dans notre région, et inversement

En effet, si notre département a beaucoup voté FN, on doit être dans l’est et du coup, il y a de grandes chances que les retombées du nuage radioactif aient été importantes. Mais il n’y a pas forcément dépendance entre les événements, c’est-à-dire que ça ne signifie pas qu’un des éléments a causé le second !

- Quand la sécurité routière annonce des pourcentages, elle dit qu’il y a par exemple 97% des accidents sur des lignes droites le jour et 3% la nuit, et donc qu’il faut être prudent le jour aussi, etc. Ce qu’elle ne mentionne pas, c’est qu’il y a beaucoup plus de circulation le jour que la nuit, et que proportionnellement, la probabilité d’avoir un accident sur une ligne droite le jour est très faible, alors que cette probabilité est beaucoup plus importante de nuit !

Les nombres permettent de manipuler les individus, il convient de rester vigilant et critique envers tous ces pourcentages qui jonchent l’actualité !

Ce blog a été créé par deux étudiants à l’époque en M1 de mathématiques dans deux universités différentes pour partager leurs passion, leurs réflexions et découvertes sur les mathématiques, leurs projets et leurs exposés, leurs énigmes et leurs sourires… Du sérieux, du moins sérieux, des mathématiques vulgarisées, niveau pré-bac, post-bac, voire au-delà… Bref, tout ce qui nous passe par la tête et que l’on a envie de partager.

Nous vous souhaitons une excellente visite sur ce site, qui va s’étoffer au fil du temps…

Tukikun & Valvino.