Discussion :

[cybermaxs]

Bonjour à tous,

Dans le cadre d'un projet en cours, j'aurais besoin "d'explorer" les différentes pistes possibles pour la résolution du problème.
N'ayant que peu de références, je vous sollicite pour avoir des pistes (nom d'algo, références, ...).

Le problème
On dispose de N boîtes, a priori non liées en elles. On dispose aussi de M valeurs, non liées non plus, mais très faible par rapport à N. Par exemple, 100 boîtes, et 4 valeurs.
On souhaite disposer ces M valeurs aléatoirement sachant que l'on peut avoir des contraintes (une valeur doit ou ne doit pas être dans une boîte, une valeur doit être présente environ 40% de la globalité).

Avez vous quelques pistes d'algo possible ???
J'ai déjà écarté la méthode "brute" (trop de permutations), et pré-selectionné l'algo génétique général. Avez d'autres algo ?

Merci beaucoup d'avance

[pseudocode]

Pourquoi ne pas construire à la main les fonctions de répartitions (suivant tes contraintes) et faire un tirage aléatoire suivant la loi de proba ainsi construite ?

[cybermaxs]

C'est une belle idée, mais je cherche en réalité la solution optimale.

[250rgv]

Je n'ai que peu de connaissances théoriques en RO mais si tu a gardé le génétique, c'est tu a une fonction d'évaluation. Donc des méta-heuristiques comme le Recuit simulé, la recherche Tabou ou le HillClimbing (ou d'autres) doivent être acceptables non ?

Voir un mélange type AG & un peu de HC sur chaque individu histoire de voir si tu peut l'améliorer facilement.

Par contre quand tu dit

je cherche en réalité la solution optimale.

. Tu cherche un algo qui te donne la solution optimale ou un éventuel algo. qui répondrai exactement à ton besoin ?
Dans le 1er cas, à moins que tu ne connaisse la valeur que doit te retourner ton évaluation pour la solution optimale et que tu les laisse tourner jusqu'à la trouver, les métas ne peuvent pas te le garantir il me semble.
Pas trop à côté de la plaque les meilleurs que moi ?

[Trap D]

Il faut que tu saches définir les caractéristiques de la solution optimale.
Il me semble que la librairie de contraintes de Prolog (clpfd) pourrait t'aider à résoudre ton problème.

[CedricMocquillon]

Il faut effectivement que tu formalises ton problème: cherches tu une meilleure solution (au sens d'un critère donc, quel est ce critère? comment évalues tu une solution?) cherches tu juste une solution réalisable? (i.e. la faisabilité)
Quelle est la nature de tes contraintes?

Je te conseille de mettre alors ton problème en équations (si possibles linéaires), cf. méthode du simplex

Après tu auras deux possibilités: soit ton problèmes est difficile soit il est polynomial.
S'il est difficile, tu n'auras pas le choix, il va falloir explorer l'ensemble de l'espace de recherche (i.e. toutes les combinaisons) mais à priori vu tes données, ce ne devrait pas être un problème pour les solveurs récents.
S'il est polynomial, tu devras implémenter la méthode de résolution correspondante.

Bon la partie délicate, je ne te le cache pas est de déterminer la complexité de ton problème... mais pour ça il faut que tu ais ta fonction objectif et tes contraintes associées.