Le problème à résoudre et l’univers de recherche

Il y a « e » étudiants à répartir parmi « u » universités pour un total de « p » places. On respire un bon coup, on croise les doigts et on espère bien fort que p>=e, sinon on ne pourra jamais donner à chaque étudiant une affectation.

L’ensemble des solutions possibles, nommé « univers de recherche » correspond à toutes les façons existantes de répartir ces « e » étudiants dans ces « p » places. Ce nombre est gigantesque et l’exploration des solutions ne peut être faite aujourd’hui que par un ordinateur. Même pour un ordinateur, le problème prendrait des millions d’années, on doit trouver des façons de simplifier le problème, c’est-à-dire de réduire l’espace de recherche.

La réduction de l’espace de recherche

 

Les solutions équivalentes

 

On remarque d’abord que certaines solutions sont équivalentes entre elles.  Par exemple, si une école a 3 places et sélectionne au final 3 étudiants, 1, 2 et 3, peu importe le classement de ces étudiants. La solution (1,2,3) est, pour ce qui est des souhaits de l’école et de la satisfaction des étudiants ; identique à la solution (3,1,2). Ceci réduit immensément l’espace de recherche (si une université dispose de 1 000 places, il y a factorielle (1000) solutions équivalentes et ce nombre est immense).

Les souhaits des étudiants

Dans le cas de Parcours Sup, chaque étudiant a effectué 10 choix. Ce nombre peut sembler très important mais réduit aussi immensément l’espace de recherche puisqu’il existe quelques milliers d’affectations possible pour chaque étudiant en théorie.

Pourquoi 10 choix ?

10 est choisi visiblement pour que tous les choix soient exprimés (psychologiquement parlant, 99% des étudiants ont 3 ou 4 choix au maximum, les derniers sont donc en théorie inutiles. Ils assurent cependant que l’algorithme, ayant exploré les choix utiles comme inutiles, aura bien exploré tout l’univers des solutions dites raisonnables). 10 doit rester petit devant le nombre de choix possibles au départ (« u ») et plus grand cependant que le nombre de choix « psychologiques » maximum d’un étudiant.

Le principe d’équité

 

Chaque université classe les étudiants qui l’ont demandée selon des critères qui lui sont propres. On comprend bien que la fac d’allemand ne classe pas les étudiants de la même façon que la fac de maths, etc…

Le principe d’équité est le suivant :

si un étudiant est mieux classé qu’un autre dans le classement d’une université donnée, alors il est prioritaire pour l’inscription dans cette université et ceci quel que soit les autres choix faits par l’étudiant, les paramètres de l’algorithme, les contraintes de l’administration etc.

Le principe d’équité réduit lui aussi immensément l’univers de recherche en éliminant toutes les solutions d’affectation non équitables, qui sont d’un ordre de grandeur plus nombreuses que les solutions équitables.

Principe d’équité ou sélection ?

 

Il est à noter aussi que ce principe correspond aussi très exactement à ce qu’un grand nombre appellent « la sélection » puisque l’algorithme définit une méthode sélectionnant par le niveau les élèves affectés dans chaque université.

Si on veut (et ce sera la seule note politique de ce billet) éviter la sélection, il suffit en fait d’agrandir toutes les capacités des écoles pour qu’elles puissent accepter toutes les demandes, de créer 100 000 places à Polytechnique et Normale Sup, 100 000 médecins par an, etc. Solution absolument impossible, absurde, et qui aboutit à la destruction complète de l’enseignement supérieur. En vérité, toutes les grandes âmes qui refusent la « sélection » s’opposent en fait au principe d’équité. Et tout ceci finit alors par des tirages au sort…

La procédure « par tours successifs »

 

Ce principe d’équité, introduisant la notion de priorité, est à l’origine du délai de Parcours Sup. Une fois qu’on l’a introduit, chaque université est obligée de proposer aux « meilleurs » étudiants de choisir en premier. Les étudiants les moins bons doivent donc attendre les réponses des meilleurs. Ceci crée la procédure « par tours successifs », qui frustre actuellement tant de monde alors qu’elle est en fait garante de la qualité de l’affectation et de son caractère équitable. J’espère arriver à le faire sentir dans la suite de ce billet.

 

Pourquoi les étudiants n’ont-ils pas eu à classer leurs souhaits ?

 

L’impossibilité de trier les choix.

 

Si on demande aux étudiants de trier leur choix d’universités de la plus souhaitable à la moins souhaitable, il faut voir qu’on réduit de fait l’espace de choix des étudiants et surtout la qualité finale du résultat que donnera l’algorithme. En effet, on peut concevoir un étudiant qui, devant un choix réduit à maths et physique choisira physique, mais entre physique et anglais, il choisira anglais. Et entre maths et anglais, il choisirait maths. Sur 3 matières, ceci tient un peu du paradoxal mais sur 5 choix possibles, de tels cas existent toujours et il vous suffira de discuter avec n’importe quel étudiant pour le comprendre. Entre les différences de cursus, les distances, les coûts, etc…, il est impossible en général pour un étudiant de prédéfinir tous ses choix.

Le tri a priori des choix crée un biais injuste entre les étudiants.

 

Si on demande aux étudiants de trier les choix a priori ou, ce qui revient au même, de coefficienter leurs  choix, la notion de stratégie vis-à-vis de l’algorithme jaillit. Un étudiant pourra mettre tous ses points sur une seule école et « influencer » l’algorithme en faveur de ce choix. Ceci pourrait aller contre le principe d’équité défini plus haut. L’algorithme ajouterait dans son évaluation une quantité prenant en compte le classement de l’étudiant dans l’école choisie au souhait de l’étudiant, avec comme conséquence la rupture du principe d’équité : un étudiant moins bien classé pourrait se voir proposer une école avant un étudiant mieux classé parce qu’il a fortement coefficienté cette école.

 

La nature du problème, la fonction de coût

 

Un problème NP complet

 

Le problème à résoudre, à chaque tour, est le suivant : maximiser la satisfaction des élèves en respectant les contraintes posées par le principe d’équité. Il s’agit d’un problème informatique classique, nommé « optimisation sous contraintes ».

Comme on n’a pas demandé aux élèves de trier leurs souhaits, on peut définir une fonction de satisfaction très simple, par exemple, la satisfaction est égale au nombre de choix satisfaits de l’élève, valeur toujours comprise entre 0 et 10. C’est probablement ce qui a été fait dans Parcours Sup, avec peut être quelques variantes prenant en compte les contraintes de l’administration. Par exemple, à chaque affectation correspond un budget de fonctionnement. On peut concevoir que l’administration cherche à le minimiser et donc introduire des composantes supplémentaires, plus ou moins faciles à calculer dans la fonction de coût.

En dépit de toutes les simplifications effectuées plus haut, le nombre de combinaisons que doit calculer l’algorithme reste impossible à explorer pour un ordinateur car il croît de façon exponentielle avec le nombre d’élèves. En termes mathématiques, le problème est NP complet. Ceci veut dire qu’il faudrait des milliers d’années pour optimiser chaque tour. Un tel délai engendrerait de grandes frustrations chez les étudiants.

On utilise donc des heuristiques, c’est-à-dire des simplifications pour explorer au mieux l’univers de recherche. Ce faisant, on renonce à obtenir le meilleur résultat possible, qui correspond à l’optimum global de la fonction de coût, à son minimum lorsqu’on teste toutes les possibilités. On tente simplement d’obtenir un optimum local. Les algorithmes utilisés garantissent en général l’atteinte d’un optimum local, c’est-à-dire que toutes les solutions d’affections proches du résultat obtenu sont moins bonnes. Je ne définis pas le terme « proche » volontairement ici, mais il est à prendre au sens mathématique, c’est-à-dire topologique.

Un exemple de résolution

 

Exemple d’heuristique : à partir d’une affectation donnée et faite « au hasard », on prend un élève et on tente de le changer d’affectation en échangeant sa place avec n’importe quel autre élève, ce qui fait « e-1 » possibilités. On valide le changement si la satisfaction globale obtenue est meilleure. On répète ceci pour chaque élève, on a donc effectué e x (e-1) permutations, ce qui est grosso modo égal à e² car e est très grand. On est ainsi passé d’une complexité exponentielle à une complexité polynômiale. Or les problèmes de complexité polynômiale sont parfaitement traitables par les ordinateurs.

On peut imaginer différentes heuristiques plus ou moins complexes. Par exemple, au lieu de swapper 2 affectations, on peut tenter d’en swapper 3, 4,… 10 à la fois (on obtient une complexité polynomiale de degré supérieur au carré et le problème reste traitable, bien que plus complexe à traiter, par l’ordinateur. Dans Parcours Sup, le cas me semble si bien adapté au traitement informatique que la simple permutation dont je parle plus haut, éventuellement répétée plusieurs fois, doit pouvoir suffire.

Une analogie physique le recuit simulé

 

Dans la nature, les systèmes physiques discrets sont stables lorsque leur énergie est minimale. L’énergie est donc la fonction de coût et la recherche des optima locaux correspond aux états métastables. Ces considérations ont inspiré diverses heuristiques très belles, en particulier celle du « simulated annealing » (recuit simulé) où au lieu d’accepter une permutation simplement si on fait baisser la fonction de coût, on introduit une composante liée au hasard : la permutation aura d’autant plus de chances d’être acceptée que la fonction de coût diminue et qu’une variable nommée température diminue. Au départ, la température étant très haute, presque toutes les transformations sont acceptées même si elles font monter la fonction de coût (et ainsi, on donne à l’algorithme une chance de se sortir des états métastables et de mieux explorer l’univers de recherche).  A chaque étape, on baisse la température et quand on atteint le 0 absolu, l’énergie du système est minimisée (on montre aussi que, mathématiquement, la fonction de coût a alors atteint son minimum global). Wikipedia réussit le tour de force d’introduire cet algorithme sans jamais évoquer Maxwell-Boltzmann, ce qui est une vraie honte. Je vous conseille plutôt d’aller voir sur tangenteX.

Pourquoi Parcours Sup va donner de bons résultats

 

Parcous Sup est un Tétris géant

 

Quand vous jouez à Tetris, vous cherchez à minimiser la surface prise par les formes que vous donne le jeu. La fonction de coût est donc la surface totale prise par les formes. Quand les formes sont casées, elles font de la place et disparaissent, laissant la place aux nouvelles formes qui vous tombent dessus. Vous faites permuter (via des rotations) ces formes pour minimiser l’encombrement et les trous. Les premières formes envoyées, ce sont les meilleurs étudiants.  Il ne s’agit pas d’une simple analogie et le jeu de Tetris, lui aussi NP complet se ramène, à peu de choses près, au même problème et au même algorithme que Parcours Sup. Parcours Sup est une sorte de Tétris géant comportant « e » formes et « u » colonnes. « e » et « u » sont tellement grands qu’aucun humain ne sait plus jouer à un tel jeu mais l’ordinateur va très bien se débrouiller. Tout joueur de Tétris peut comprendre ceci : il ne sait pas jouer à Tétris s’il y a 10 000 colonnes et 1 millions de formes alors que l’ordinateur le peut.

Mon retour d’expérience

 

Les méthodes que je décris plus haut sont antérieures à la révolution numérique. Elles ont été découvertes à partir des années 50 et utilisées sur des problèmes complexes en informatique au début des années 80 aux Etats-Unis. Je faisais partie des premières équipes de recherche appliquant ces techniques pour optimiser le positionnement des transistors sur une puce informatique pour en minimiser la taille (début des années 90, vous noterez qu’il s’agit là encore d’une sorte de Tétris) au moment où les puces commençaient à intégrer quelques milliers de transistors. La fonction de coût est la surface prise par la puce, dont dépendent la consommation, la vitesse et finalement la puissance du processeur obtenu. Jusqu’à 5000 transistors, un ingénieur humain hyper compétent (il y en avait moins de 500 dans le monde à l’époque) peut battre l’ordinateur (en y passant infiniment plus de temps cependant). A partir de 5000 transistors, l’ordinateur est gagnant, même programmé par des ingénieurs moins compétents. Une puce comprend aujourd’hui des millions de transistors, autrement dit, seuls des ordinateurs peuvent résoudre ces problèmes. Les meilleurs « designers » de puce sont devenus les meilleurs programmeurs d’algorithme. Bref, il n’y aucun doute pour moi que la qualité du résultat que peut atteindre un algorithme est meilleure, en toute hypothèse, que celle atteinte par un humain ou une équipe d’humains.

La simplicité des algorithmes utilisés

Les algorithmes utilisés sont simples bien connus, faciles à implémenter. Même si les programmeurs ont fait des erreurs (bugs), même si la fonction de coût est incorrectement définie, j’ai pu constater, dès les années 90, que la qualité des résultats obtenus restait surprenante. Des algorithmes triviaux ou peu optimisés, des algorithmes faisant parfois de mauvais choix, une fonction de coût mal conçue permettent quand même, dans la plupart des cas, d’obtenir de bons résultats (c’est-à-dire que l’écart de coût par-rapport à un « bon » algorithme va expérimentalement rester assez faible). Bref, l’Etat français, même si son niveau technique est faible, a les moyens de développer ou faire développer un tel programme. On n’est pas dans le cas du logiciel Louvois, dont la mise au point infiniment plus complexe dépasse les moyens techniques de l’Etat.

Angoisse = Nouveauté + Attente

 

Le système étant nouveau, peu compris et long (plusieurs tours), il génère de l’angoisse chez les candidats. Dès l’année prochaine, tout ira plus vite. On saura par exemple que telle école recrute jusqu’à 5000 élèves sur sa liste d’attente et, le nombre variant peu d’année en année pour des raisons de moyenne statistique, les élèves auront beaucoup plus tôt une vision de leurs choix possibles, en fonction de leur position en liste d’attente. Ceci réduira le nombre de « tours ». Aujourd’hui, les élèves sont dans le noir total. Ceci ne rend pas le processus injuste ou peu performant, mais augmente leur angoisse.

Et après Parcours Sup ?

 

Les élèves sans affectation à la fin du processus

 

Imaginons un étudiant mauvais en maths qui demande 10 classes prépa scientifiques, il devrait être partout refusé. Il y aura forcément à la fin du processus des élèves sans affectation car leur choix n’était pas « possible » au sens de l’algorithme. Il me semble donc que pour ces élèves, une redéfinition des choix compte tenu de ce qui est réellement envisageable pour eux devra être effectuée.

L’équité, le raisonnable, le possible.

 

J’ai parlé au début de ce billet d’un processus forcément équitable, compte tenu des places réellement disponibles. Il s’agit d’une équité théorique. Les exigences de l’équité républicaine vont bien au-delà de l’équité théorique assurée par l’algorithme. Imaginons qu’il y ait un besoin pour 1000 mathématiciens, qu’il y ait 1000 étudiants voulant le devenir et étant capables de le devenir mais seulement 500 places proposées : les étudiants classés entre 500 et 1000 peuvent en vouloir à la République. Les choix « non possibles » des étudiants dont je parle dans le paragraphe précédent seraient pourtant des choix « raisonnables » puisqu’il y aurait des débouchés et que les étudiants seraient en capacité de maîtriser ces métiers. En ce sens, Parcours Sup ne résout certainement pas tous les problèmes d’équité liés à l’enseignement supérieur. Mais à infrastructure universitaire donnée, il est sans doute la meilleure solution possible. Le travail du gouvernement consiste, dans le futur, à faire en sorte que les choix « possibles» (l’univers au sens de l’algorithme) coïncident au maximum avec les choix « raisonnables » (le monde tel qu’il est).