Salut,
du K-partionnement de mémoire, donc le principe consiste à positionner chaque élément dans un espace à N dimensions, et à regrouper les points les plus proches (en créant K partitions de cet espace multi-dimentionnel).
Dans l'idée, tu dresses N caractéristiques pour chaque élève, tu donnes une valeur à chacune de ces caractéristiques, et tu groupe les points les plus proches entre eux. Je pense qu'il doit y avoir des groupements qui peuvent se faire par "sphères".
Sinon, avec des contraintes plutôt type "lui veut aller avec lui et lui ne veut pas être avec lui", tu dois pouvoir modéliser cela à base de ressort: chaque paire d'élève se voit liée à un ressort, qui tend à les rapprocher ou à les éloigner plus ou moins. En laissant ce système de ressorts libre, il finit par converger vers un point d'équilibre, et tu peux en tirer des groupes. Ca te fait un graph complet assez lourd, mais je pense que c'est solvable très facilement en pratique (genre tu peux construire un fichier graphviz à partir de ce mécanisme de ressorts, et graphviz de l'affichera en respectant ces "forces de ressorts"; bref, ce système de ressort est utilisé par GV pour placer ses noeuds... mais c'est du 2D là).
Avec des outils plus accessibles, sinon, tu peux modéliser l'exemple précédent des ressorts en SQL ou autre (pas forcément de façon complète, c'est à dire ne créer que certaines paires d'élèves, avec un coefficient 0 pour "j'm'en fous qu'ils soient ensembles", -1 pour "surtout pas ensemble" et 1 pour "doivent être ensemble"), et faire un calcul exhaustif de toutes les combinaisons de groupes possibles, déterminant ainsi le score d'affinité de chaque groupe d'élève, le score global, et en définissant un algorithme d'ordonnancement de ces groupes (ie: je prend la combinaison de groupes pour laquelle tous les groupes ont à peu près la même affinité, et dont la somme totale des affinités est la plus élevée possible). Vu que t'as probablement moins de ~30 élèves (je dirai), c'est jouable l'exhaustif.
Edit: Quoique j'ai mal lu: j'ai cru que c'était pour faire des groupes dans la classe... Alors que c'est pour faire les classes dans l'école. Là, l'échelle ne permettra peut-être pas de faire de l'exhaustif... Et à cette échelle, les "affinités" seront dures à déterminer. Pour dire que l'affinité entre deux élèves donnés est de X sur une échelle de 0 à 1, alors je pense qu'il faut doter chacun des deux élèves de "paramètres" genre notes, préférences pour certaines matières, etc et tirer de ces notes un "niveau", puis considérer que l'affinité entre deux élèves dépend de leur niveau respectif (deux élèves de niveau similaires auront une forte affinité, deux élèves de niveaux différents en auront une faible). Cela permettra aussi d'injecter, lors de la construction de cette affinité, d'autres paramètres comme le fait que deux élèves spécifiques se détestent... Et dans le calcul exhaustif, chaque ensemble de classes peut alors se voir doté d'un "score", reflétant le fait que les classes soient équilibrées (= que les élèves de chaque classe ont une bonne affinité) mais aussi le fait que les classes n'aient pas 1 fille pour 20 garçons (ou inversement), ou qu'un élève n'ait pas un niveau trop faible/fort.
Si le calcul exhaustif n'est pas faisable, l'autre méthode issue des calculs d'optimisation consiste à partir d'une configuration aléatoire, à calculer son "score", puis à changer un élève de classe. On recalcule alors le score, et s'il est meilleur, on réitère avec cette nouvelle configuration. Si le score est moins bon, on remet l'élève à sa place initiale, et on essaie avec un autre. Si, après X essais (en évitant de refaire les mêmes si possible, mais bon, c'est pas trop grave) on n'a pas trouvé d'agencement de classes avec un meilleur score global, alors on considère que cette configuration est un "optimum local". On relance alors l'algo avec une autre position initiale aléatoire, et on réitère autant de fois qu'on veut. On prend ensuite la meilleur configuration parmi tous ces "optimum locaux".
Tiens, je vais tenter de le modéliser, pour voir
du K-partionnement de mémoire, donc le principe consiste à positionner chaque élément dans un espace à N dimensions, et à regrouper les points les plus proches (en créant K partitions de cet espace multi-dimentionnel).
Dans l'idée, tu dresses N caractéristiques pour chaque élève, tu donnes une valeur à chacune de ces caractéristiques, et tu groupe les points les plus proches entre eux. Je pense qu'il doit y avoir des groupements qui peuvent se faire par "sphères".
Sinon, avec des contraintes plutôt type "lui veut aller avec lui et lui ne veut pas être avec lui", tu dois pouvoir modéliser cela à base de ressort: chaque paire d'élève se voit liée à un ressort, qui tend à les rapprocher ou à les éloigner plus ou moins. En laissant ce système de ressorts libre, il finit par converger vers un point d'équilibre, et tu peux en tirer des groupes. Ca te fait un graph complet assez lourd, mais je pense que c'est solvable très facilement en pratique (genre tu peux construire un fichier graphviz à partir de ce mécanisme de ressorts, et graphviz de l'affichera en respectant ces "forces de ressorts"; bref, ce système de ressort est utilisé par GV pour placer ses noeuds... mais c'est du 2D là).
Avec des outils plus accessibles, sinon, tu peux modéliser l'exemple précédent des ressorts en SQL ou autre (pas forcément de façon complète, c'est à dire ne créer que certaines paires d'élèves, avec un coefficient 0 pour "j'm'en fous qu'ils soient ensembles", -1 pour "surtout pas ensemble" et 1 pour "doivent être ensemble"), et faire un calcul exhaustif de toutes les combinaisons de groupes possibles, déterminant ainsi le score d'affinité de chaque groupe d'élève, le score global, et en définissant un algorithme d'ordonnancement de ces groupes (ie: je prend la combinaison de groupes pour laquelle tous les groupes ont à peu près la même affinité, et dont la somme totale des affinités est la plus élevée possible). Vu que t'as probablement moins de ~30 élèves (je dirai), c'est jouable l'exhaustif.
Edit: Quoique j'ai mal lu: j'ai cru que c'était pour faire des groupes dans la classe... Alors que c'est pour faire les classes dans l'école. Là, l'échelle ne permettra peut-être pas de faire de l'exhaustif... Et à cette échelle, les "affinités" seront dures à déterminer. Pour dire que l'affinité entre deux élèves donnés est de X sur une échelle de 0 à 1, alors je pense qu'il faut doter chacun des deux élèves de "paramètres" genre notes, préférences pour certaines matières, etc et tirer de ces notes un "niveau", puis considérer que l'affinité entre deux élèves dépend de leur niveau respectif (deux élèves de niveau similaires auront une forte affinité, deux élèves de niveaux différents en auront une faible). Cela permettra aussi d'injecter, lors de la construction de cette affinité, d'autres paramètres comme le fait que deux élèves spécifiques se détestent... Et dans le calcul exhaustif, chaque ensemble de classes peut alors se voir doté d'un "score", reflétant le fait que les classes soient équilibrées (= que les élèves de chaque classe ont une bonne affinité) mais aussi le fait que les classes n'aient pas 1 fille pour 20 garçons (ou inversement), ou qu'un élève n'ait pas un niveau trop faible/fort.
Si le calcul exhaustif n'est pas faisable, l'autre méthode issue des calculs d'optimisation consiste à partir d'une configuration aléatoire, à calculer son "score", puis à changer un élève de classe. On recalcule alors le score, et s'il est meilleur, on réitère avec cette nouvelle configuration. Si le score est moins bon, on remet l'élève à sa place initiale, et on essaie avec un autre. Si, après X essais (en évitant de refaire les mêmes si possible, mais bon, c'est pas trop grave) on n'a pas trouvé d'agencement de classes avec un meilleur score global, alors on considère que cette configuration est un "optimum local". On relance alors l'algo avec une autre position initiale aléatoire, et on réitère autant de fois qu'on veut. On prend ensuite la meilleur configuration parmi tous ces "optimum locaux".
Tiens, je vais tenter de le modéliser, pour voir