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

Même si les mathématiques ont l’air d’une science exacte, où la Vérité est figée à tout jamais, il existe quelques sujets qui poussent aux débats sans fin. J’en connais quelques uns :

• l’entier 1 est-il premier ?
• doit-on considérer les ensembles finis comme dénombrables ?
• pour ou contre l’axiome du choix ?
• qui a inventé le calcul différentiel? Newton ou Leibniz ?
• les statistiques font-elles parties des mathématiques ?
• est-ce que la façon d’aborder les mathématiques de Bourbaki est LA bonne façon de procéder ?

En connaissez-vous d’autres ?

Voici quelques propositions des commentaires :

• Dans Bourbaki, un espace quasi-compact est un espace topologique vérifiant la propriété de Borel-Lebesgue. Un espace compact est un espace quasi-compact séparé. Par contre, dans les textes mathématiques écrits en anglais, un espace est compact n’est pas nécessairement séparé. Quid ?
• La définition de est erronée, et l’erreur s’est perpétuée depuis l’antiquité.
• Une forme sesquilinéaire est-elle linéaire à gauche ou à droite?
• Dans les coordonnées sphériques, que désignent et ?
• Combien vaut ?
• Est-ce que les notions d’ « application » et de « fonction » sont identiques ?
• L’espace topologique vide est-il connexe ?
• Quelle est la dimension de Krull de l’anneau nul ?
• La suite « converge-t-elle » ou « diverge-t-elle » vers l’infini ?
• …

C’est sans doute un thème récurrent dans les blogs, la baisse de niveau des étudiants, la génération dyslexique en maths : que de formules peu flatteuses pour l’enseignement des mathématiques actuel… Bien que j’aie connue la baisse drastique de niveau des mathématiques (jeunesse oblige), j’ai eu envie de venir apporter ma pierre à cette polémique maintes fois exposée, n’ayant pas la prétention d’innover, mais juste celle de redire encore et encore les surprises que l’on peut rencontrer lorsque l’on enseigne…

Je donne actuellement des « cours » — disons plutôt que j’entraîne sauvagement les étudiants au concours — dans une prépa privée pour les étudiants de PCEM 1 / PCEP 1  (i.e. étudiants de médecine et de pharmacie de première année). La formation étant exclusivement basée sur la rapidité, la connaissance du cours et l’application des méthodes (et non pas de la compréhension), je peux difficilement juger de leur capacité à comprendre les mathématiques. Par contre, je peux — et je ne m’en prive pas — tester leur capacité à calculer.

En effet, la calculatrice est interdite le jour du concours, sans doute pour éviter les fraudes (qui consisterait à la remplir de formules à appliquer à tous les exercices). En conséquence de quoi le concours déjà fort long se complique un peu d’avantage : non seulement il faut aller vite, mais il faut en plus faire un nombre non négligeable de calculs de tête.

En analyse, outre les dérivées de fonctions parfois assez corsées (du genre de l’évolution de la population bactérienne par le modèle de Verhulst : , à dériver deux fois pour rechercher les points d’inflexion), il faut aussi calculer des incertitudes (comme l’incertitude sur la pression connaissant l’incertitude sur la température et le volume d’un gaz parfait), et tout cela… de tête. Et là, c’est terrible… les élèves se braquent pour diviser 2802 par 41, s’effraient devant les dérivées de la forme où et ne sont pas des simples fonctions polynomiales qui rendent les calculs faciles…

En biostatistique, il faut donner des intervalles de confiance de moyenne, il faut calculer des covariances de variables aléatoire, les VPP et VPN (valeurs prédictives positives et négatives d’un test diagnostic, i.e. respectivement la probabilité d’être malade sachant que le test est positif et la probabilité de ne pas être malade sachant que le test est négatif), et parfois même des formules compliquées, avec des ou où est la taille de l’échantillon…

Je reconnais que ça fait beaucoup de calculs, et parfois vraiment pas évidents… Mais le recours à la calculatrice étant si immédiat, on en oublie la manière de calculer, on en oublie de regarder les ordres de grandeur (pour évincer une solution parfaitement fausse du premier coup d’oeil)… Je passais dans les rangs et je voyais des multiplications farfelues orner les brouillons… des multiplications pour ou pour ! Alors évidemment, après on me dit que mon sujet était trop long… c’est évident. Si même les petits calculs prennent du temps, que doivent donner les divisions de milliers par des dizaines…

Le non recours à la calculatrice est assez injustifié pour les calculs que les cours nécessitent de faire… il faut constamment redonner avant quelques valeurs arrondies pour qu’ils puissent traiter la question… mais pour les élèves que le calcul mental n’effraie pas, c’est excellent ! C’est excellent donc, pour une pincée d’étudiants… Eux qui pensaient se débarrasser des mathématiques, les voilà obligés de faire plein de petits calculs, et c’est ça plus que tout le reste, qui leur prend du temps et qui les handicape sérieusement…

Je dois avouer qu’ayant toujours aimé les maths (je me souviens de la découverte des équations du premier degré à résoudre de tête avec mon père en voiture alors que j’étais vraiment jeune), les calculs ne m’effraient pas. Je ne suis pas excellent, loin de là, mais j’aime assez ne pas recourir à la calculatrice lorsque je peux l’éviter… Mais je suis bien conscient que c’est loin d’être le cas pour la majorité des étudiants, même ceux en université de mathématiques…

Dans un tout autre registre, et peut-être plus grave encore (quoique l’âge plus jeune contrebalance…) : j’avais demandé à une élève de troisième qui venait de voir les identités remarquables de calculer . Après avoir fait de longs calculs (en temps !), elle finit péniblement par trouver … Je lui explique alors que et donc que . Tu as compris ? Oui oui… Ok, calcule moi alors . Réapparition immédiate de l’identité remarquable… J’attends deux, trois minutes. Finalement, elle reste bloqué avant de marquer la solution, et trace un zéro lent et hésitant… C’est faux hein ? Hé non… c’était bon…

Jeunesse décadente va ! Enfin, j’vous aime bien quand même Les étudiants que j’ai cette année sont très sympa ! Puis globalement, je ne suis pas à plaindre, je suis avec des étudiants quand même doués, et motivés…

Le 23 juin dernier, tous les étudiants de métropole et de la Réunion passaient leur baccalauréat de mathématiques, avec deux sujets différents comme chaque année. Ayant du temps pour les regarder et en faire une correction (sujet et corrigé de métropole et de la Réunion), j’ai été surpris par la différence de niveau attendue des lycéens… Le bac de la Réunion sauce 2009 est clairement plus corsé que celui de métropole !

D’où me vient ce constat ? Prenons par exemple l’exercice d’Analyse d’étude de fonctions. Dans le sujet métropole, en 3 questions sont demandés la limite en +∞, de comparer le signe de la dérivée à 1-x et d’en déduire le tableau de variations. Dans le sujet de la Réunion, pour  »la même fonction », il est demandé de conjecturer ces trois choses d’après le graphique, et de le montrer : il n’y a pas d’indication ! Déjà, rien que cela est étonnant, mais après tout, pourquoi pas ? Ils pourraient bien se rattraper autre part… et c’est là que l’on déchante ! Face à l’exercice facile sur les suites en métropole (où il fallait conjecturer que ) s’oppose un QCM sur les complexes (certes à espérance positive) mais avec une équation complexe du type qui a dû déstabiliser beaucoup de candidats. Pour les probabilités, la Réunion propose (encore) un exercice sur la loi binomiale alors que le sujet de métropole conserve des probabilités  »classiques », beaucoup plus appréciées par les lycéens. Et bien que l’exercice (facile) d’arithmétique de métropole amuse avec ses 3 références à l’année 2009 (jolies – soit dit en passant), on trouve un exercice de géométrie dans l’espace et de surfaces à la Réunion, avec une question ouverte intéressante et plutôt difficile. Reste le dernier exercice, celui pour ceux qui ne sont pas en spécialité mathématiques. Ceux de la Réunion ont dû beaucoup souffrir : leur exercice est carrément difficile, avec une question ouverte à la fin qui nécessitait des idées, et beaucoup de raisonnement et de calculs pour arriver à ses fins ! La différence de niveau est palpable entre les deux baccalauréats : c’est assez bluffant !

Intrigué par cette nette différence, je suis allé survoler les baccalauréats de ces deux lieux jusqu’en 2005, et nettement les sujets de la Réunion tiennent la palme de la difficulté (avec deux sujets longs en 2005 et 2009). QCM une année sur deux à peu près, mais ceux de la Réunion, c’est avec deux réponses justes parmi les 4, avec parfois des points en moins pour les réponses fausses), et ceux de métropole restent tranquilles avec une seule réponse juste (il suffit d’éliminer les autres, avec la palme du vrai/faux en 2006 qui n’enlève pas de points !). Peu d’arithmétique (et en plus il est difficile en 2005) à la Réunion, moins d’étude de fonction et d’équations différentielles, même si l’on voit apparaître une équation fonctionnelle, ce qui reste assez rare dans les sujets de baccalauréat. Et surtout, un amour (pourquoi donc ?!) pour les lois binomiales en probabilités, alors que la métropole reste  »classique » ou s’essaye (en 2008) aux probabilités continues…

Puis en vrac, à la Réunion, on trouve des équations de tangentes (ah, ce n’est pas aimé ça !), des probabilités avec un graphique et de l’analyse (sur 6 points en 2006 – pour un jeu de fléchette, à regarder c’est intéressant !), géométrie dans l’espace à foison, probabilités avec loi binomiale, une équation fonctionnelle qui donne une équation différentielle… bref, souvent des exercices pour préparer à la prépa MPSI…

Étonnant non ?