Bonjour et merci pour cet excelent forum.
 
J'essaie de resoudre le probleme du sac a dos à l'aide d'un algorithme genetique.
 
J'ai eu quelques problemes à le modeliser et je vous demande d bien vouloir m'aider.
 
En fait j'ai modeliser le chromosome comme suite : une structure contenant le poids et la valeur.
 
Je n'arrive pas à trouver la fonction de fitness qui me permet de retrouver la meilleur population.
 
Je suis preneur de toute proposition.
 
Merci d'avance.

ben la fonction fitness reprends la definition de LA solution à savoir maximiser le poids en minimisant les ressources. donc à mon avis, il faut plutot voir la solution comme uen somme d'objet...donc sur un chromosome tu as les objets contenus dans ton sacs a dos... pour plus d'info, tu as fait une recherches sous google ou wiki ?

Ce problème se résoud très bien à l'optimal avec la programmation linéaire en nombres entiers . Des méthodes de coupes relativement efficaces génèrent des coupes profondes pour résoudre ce problème ; d'où l'existence de familles de coupes "Knapsack cuts" qui furent ajoutées dans les algorithmes de recherche. Le temps de résolution est pseudo polynomial. Donc si ton seul but est d'obtenir le meilleur résultat, abandonne les AG .
Pour la fonction de fitness, il suffit d'évaluer le coût (nombre de sac à dos utilisés) à partir de l'individu obtenu non Sinon il existe aussi pas mal de résolution heuristique pour ce problème (comme tous les problèmes NP-Complet d'ailleurs   )

Le pb du sac à dos, ça se résoud avec l'algo LPT, non? Tri des objets dans l'ordre décroissant de leur poid.
Sinon, j'avais fait un topic sur l'optimisation de CD-R et j'avais développé un composant en Delphi :  
http://forum.hardware.fr/hfr/Progr [...] 4853_1.htm
http://forum.hardware.fr/hfr/Progr [...] 6299_1.htm
http://forum.hardware.fr/hfr/Progr [...] 8444_1.htm
 
http://chris-jav.servhome.org/data/opt_cd/opt_cd.zip
http://chris-jav.servhome.org/data [...] cd_cmp.zip

 
Coder un algo de Branch&Cut pour la programmation linéaire qui fonctionne à peu près correctement n'est pas donné à tout le monde. Rien que de coder le simplexe utilisé au milieu, je ne préfère pas y penser à cause de tous les problèmes de mauvais conditionnement, de stabilité numérique, etc... qui peuvent apparaître.
 
As-tu un lien vers une preuve que le temps de résolution serait pseudo-polynomial en utilisant un tel algo ? La solution pseudo-polynomiale que je connais utilise la programmation dynamique : http://en.wikipedia.org/wiki/Knaps [...] g_solution
 
Pour un algo génétique, je dirais que la solution est un tableau de bit b1...bn où bi = 1 si l'objet est dans le sac, 0 sinon. La fonction de fitness faut 0 si somme des pi*bi > P ou pi est le poids d'un objet et P la taille du sac, somme des vi*bi où vi est la valeur d'un objet sinon. Pour faire les crossovers et les mutations, euh... chsais pas mais ça doit pas être trop compliqué. "Ajouter un objet", "enlever un objet et en ajouter un autre", tout ça tout ça...  
 
Avis lapidaire et très subjectif : c'est pourri, les AG.

ben les AG sont très facilement programmables en qq lignes de codes et permettent de résoudre pleins de pbs... Le tout c'est de trouver la bonne modélisation et le critère de convergence pour qu'à chaque nouvelle population engendrée, celle-ci s'améliore afin de fournir la solution attendue.

 
Je parle pas de réinventer l'eau chaude   , il existe déjà des solveurs de PLNE gratos qui inclus des familles de coupes (notamment knapsack cuts) : glpk, symphony, cbc, et d'autres

 
N'empêche que je doute toujours que la "pseudo-polynomialité" se prouve, contrairement à la résolution par programmation dynamique. M'enfin, on est HS, on se doute bien que l'initiateur du topic n'essaye pas vraiment de coder le meilleur solveur de sac-à-dos possible...

Bein j'avais fait mon mémoire de maitrise dessus (les algos génétiques sur un autre problème), la librairie C++ open beagle est livrée avec de nombreux exemples dont celui du sac à dos.

Pour mémoire pour la fonction de fitness était juste la valeur du sac à dos qu'il fallait maximiser (qui vallait 0 si le sac était trop plein). On peut aussi faire une fonction de fitness hierarchique qui à valeur égale dira que plus il reste de place, mieux c'est.

PS: je ne suis même pas sur qu'on ait prouvé qu'il y avait convergence (vers une solution optimale) d'une metaheuristique, même en temps infini, sur ce problème.

44

Salut je suis debutant en programmation genetique  
j'ai besoin de votre aide.
Si vous pouvez m'envoyez un algo genetique pour le pvc ou le pb de sac a dos