Discussion :

[Supernul]

Bonjour à tous,

J'ai une grille G de taille l*c.
Chaque cellule de cette grille dispose d'un état e parmi un ensemble E.
Pour chaque état e de E, je dispose d'une grille de probabilité qu'une cellule soit dans l'état e (la probabilité 0 signifie que la cellule ne peut prendre l'état e) et d'un vecteur V contenant la quantité v de cellules e attendues. La somme des v est inférieure ou égale à l*c.

Je cherche à affecter dans ma grille G l'ensemble de mes états e en cherchant à maximiser les probabilités.

J'ai déjà un algorithme glouton qui fonctionne bien si les contraintes ne sont pas trop fortes (il faut que je rajoute une étape d'actualisation des probabilités pour tenir compte du nombre de cellules restantes pour chaque état e).

Je ne trouve pas d'approche permettant d'approcher une solution "optimale" dans un temps acceptable. Ma grille est de taille 4000*4000 mais possiblement plus avec entre 10 et 20 états e et somme(v) représente entre 85% et 100% de la taille de la grille.

N'étant pas informaticien de formation, je me dis qu'il me manque certains outils qui m'aideraient à résoudre ce problème.
Je vous remercie de votre aide.

[tbc92]

Je reformule, pour être sûr d'avoir compris.

Tu as une grille de taille l*c ( environ 4000*4000)
Chaque cellule peut prendre un état e parmi un ensemble E (environ 20 états possibles).
Pour chaque état e, on donne une note si telle ou telle case a cet état ; ça, je vais le reformuler : pour chaque case de la grille on a un vecteur de 20 éléments, disant la note obtenue si cette case est dans cet état (dans l'énoncé initial , tu parlais de probabilité, mais je préfère parler de note).
NoteGrille(l,c,e) = la note obtenue si la case (l,c) prend la valeur e
On veut remplir la grille en maximisant la somme de ces notes.
La solution 'simpliste' serait de remplir chaque case avec l'état e qui a la note maximale... problème résolu, mais on a une autre contrainte : pour chaque état e, on a un nombre maxi de cellules qui peuvent prendre cet état.
NBmax(e) = Nombre max de cellules qui ont la valeur e.

Et tu donnes une autre contrainte qui me paraît contradictoire avec le début : La somme des nombres de cases autorisées pour tous les états e donne un total inférieur à l*c ... On va donc avoir des cellules vides ?
Si c'est bien ça, j'ai envie d'ajouter un état supplémentaire (noté f) qui vérifie :
Nbmax(f) = l*c : on peut remplir toutes les cases avec cet état fictif
NoteGrille(l,c,f) = 0 : cet état fictif rapporte 0 point.

C'est conforme à ta demande ?

Comme ça, les cases remplies avec cet état fictif f sont traitées comme les autres, ça va certainement simplifier le traitement.

[Supernul]

Bonjour,

Merci du temps que tu prends pour mon problème.
Ta formulation est tout à fait juste. Je traite actuellement les Nbmax() comme des Nb(), ce qui conduit à considérer Nbmax(f) = l*c - Somme(Nbmax(e)).

J'imagine que l'approche à utiliser est issue de l'optimisation combinatoire.

[Flodelarab]

Bonjour

Je traiterais le problème comme le concours au grandes écoles. On trie les couples case-état par ordre décroissant des probabilités et on remplit les places disponibles dans l'ordre d'arrivée.
Les premiers vont trouver naturellement leur place, et les derniers prendront les miettes, "de la moins mauvaise manière".

Vas-tu avoir beaucoup d'ex-aequo ? (probabilités égales)

[tbc92]

Sauf que si la case (c,l) a des notes comme 0.99 , 0.98 ou 0.97 pour les états 1 2 3, on va l'affecter à l'état n°1 (0.99) et si par malchance, Nbmax(1) est plutôt petit, c'est du gâchis. Pour cette case (c,l), la meilleure solution sera peut-être de la mettre dans l'état 2 ou 3.

[Supernul]

Re,

Merci @Flodelarab pour ton idée. C'est la première version de l'algorithme glouton que j'avais codé mais dans certains cas, je me retrouve avec des résidus que je ne peux pas affecter car la probabilité 0.0 empêche l'affectation. C'est typique le cas d'un état e avec des probabilités qui se trouvent à un rang élevé lorsque je classe toutes les probabilités de tous les états par ordre décroissant. Les cellules de ma grille sont déjà remplies par un autre état.

La deuxième version de mon algorithme inclut un mécanisme complémentaire d'affectation de ces résidus. Je prends la probabilité la plus forte parmi les résidus et je remplace l'état existant dans la cellule concernée. Ce dernier état obtient un résidu de 1 et la probabilité pour cet état devient 0.0 (sinon je boucle à l'infini) et je continue jusqu'à faire disparaître les résidus ou tombé sur une situation stable.

La troisième version sur laquelle je travaille est toujours un algorithme glouton mais intègre un mécanisme de tension variant de 0 à 1 dont le calcul est Nbmax(e) / {nb de cellules pour lesquelles la probabilité de l'état e est P>0.0}. Une fois la tension d'un état e valant 1, j'affecte en toutes les cellules non déjà affectées l'état e. Le soucis est que je crée aussi des situations insolvables lors de cette affectation en masse car je peux faire passer la tension d'un autre état à une valeur supérieure à 1.0 (plus de demande que de cellules possibles)

Je travaille à deux autres algorithmes :
- à partir de la troisième version, si j'obtiens un état insolvable suite à cette affectation de masse pour l'état noté e_t1, je calcule le nombre de cellules que je ne peux affecter pour l'état dont la tension est >1.0 (noté E_t2). Je retire les affections réalisées pour les état différents de e_t1 et e_t2 et je leur affecte e_t1 et e_t2 à la place. Cela produit une demande pour les état remplacés. Pour ces derniers états, la probabilité des cellules remplacées devient 0.0. A voir si j'arrive à un état insolvable.
- à partir du deuxième algorithme, je n'utilise plus directement les probabilités mais je les multiplient par la tension de chaque état (Nbmax(e) qui reste à affecter / {nb de cellules non affectées pour lesquelles la probabilité de l'état e est P>0.0}). Lorsque les tensions de chaque état sont très différentes, cela devrait fonctionner assez bien. Mais pour des tensions similaires, je devrais aboutir au même résultat que le deuxième algorithme.

De plus ces deux derniers algorithmes restent des algorithmes gloutons pour lesquels j'ajoute des étapes de calcul pour limiter le risque de tomber sur un état stable comportant des quantités non affectables pour certains états, sans être certain d'éviter une situation avec résidus non affectés. Ce qui signifie, un allongement du temps de calcul.

[Flodelarab]

je me retrouve avec des résidus que je ne peux pas affecter car la probabilité 0.0 empêche l'affectation.

Mouai. Bof. Je comprends bien. Mais il suffit que le nombre v d'état e soit toujours inférieur au nombre de cases encore disponibles (de probabilité supérieure à 0). Donc on compte et on esquive le blocage.
D'ailleurs, tenir ce compte est nécessaire dès le début, car, si tu dois affecter 4 états e1 dans seulement 3 cases de probabilité non nulle, ton algorithme n'aboutira jamais.

Pour cette case (c,l), la meilleure solution sera peut-être de la mettre dans l'état 2 ou 3.

Ah oui. Ça, c'est beaucoup plus grave. 0.4+0.1<0.3+0.3.
La solution serait-elle de faire une dream team pour chaque état et gérer les chevauchements ?

Sauf que si la case (c,l) a des notes comme 0.99 , 0.98 ou 0.97 pour les états 1 2 3,

Pour un total de 294% !

[Supernul]

Merci @Flodelarab

En effet, je vérifie en amont pour toutes les arrangements possibles d'états e (les 20 états ensembles, 19 états parmi les 20, ...) d'avoir assez de cellules pour les affecter.
Pour plus de clarté sur la première remarque, je joins un exemple avec trois états (j'y masque l'état f qui sert à compléter les 3 cellules non demandées et dont la probabilité serait uniforme et strictement inférieure à la plus petit probabilité non nulle des autres états).

Dans cet exemple:
- sur la gauche les probabilités pour chacun des trois états
- au centre, le masque définissant si l'affectation est possible ou non dans la cellule
- Nbmax de l'état
- en bas la séquence d'affectation et les résultat : il y a assez de cellules pour affecter les 13 demandes. Cependant avec la première version de l'algorithme, on constate que seules 10 des 13 demandes peuvent être résolues, d'où les autres algorithmes que j'ai testés.

[Supernul]

Bonjour,

je vous remercie de votre aide sur ma question. J'ai croisé un collègue qui m'a dit qu'il s'agissait d'un problème d'optimisation sous contrainte.
Je vais regarder à exprimer mon problème sous une formulation mathématique exploitable dans un solveur. La formulation en français ressemblerait à : chercher à maximiser les probabilités de chaque état tout en minimisant la valeur absolue entre le nombre de pixels attendu pour chaque état et le nombre de pixel pour lequel la probabilité de l'état est la plus grande parmi touts les états.

EDIT : j'ai trouvé la solution recherchée avec une implémentation en python grâce à minimize de scipy.