Sac à dos et algorithme génétique

Bonjour à tous.

Comme indiqué dans le titre, je dois utiliser les algorithmes génétiques (AG) pour résoudre le problème du sac à dos, enfin approcher une solution puisque l'on parle des AG.

En ce qui concerne les sac à dos, le principe est très facile à comprendre :
- un sac avec un poids maximum
- un nombre d'objets disponibles avec un poids et une valeur

=> maximiser la somme totale des valeurs des objets dans le sac tout en respectant le poids maximum.

Jusque la tout va bien.

Par contre, pour les AG, ben je n'y connais rien, j'ai fait quelques recherches. J'ai trouvé cette page (entre autres) et voici ce que je comprends :
- On tend petit à petit vers une solution optimisée mais sans pour autan savoir si on l'atteint.

Après il y a beaucoup de choses qui restent floues :
- La population : ensemble de cas non optimisés répondant à mon problème (ici, une liste de sacs remplis) ?
- Un chromosome : un cas non optimisé répondant à mon problème (ici, une liste d'objet qui remplissent le sac) ?
- la fonction fitness : méthode d'évaluation des éléments appartenant à un chromosome (ici, évaluation d'un objet) ?
- Qu'est ce qu'un individu ?
- Dans l'hybridation et la mutation, il est question d'arborescence puisqu'on peut lire les termes parents et fils. Qu'est ce que cette structure arborescente vient faire la ?

Voila, si j'arrive à comprendre déjà ça je devrais pouvoir avancer.

Merci d'avance.

PS : Afin de prévenir de réponses sans rapport avec ma demande d'aide, je précise que je DOIS utiliser les AG pour résoudre le problème du sac, même si ce n'est pas le mieux indiqué.

Citation:

---

Envoyé par DrSnake

- La population : ensemble de cas non optimisés répondant à mon problème (ici, une liste de sacs remplis) ?

---

Oui, au début tu fabriques un certain nombre de sacs, au hasard (vides ou pleins, peu importe). Ensuite, l'algorithme va progressivement modifier cette population, de facon à ce que les sacs qu'elles contient soient (en moyenne) meilleurs de génération en génération.

Citation:

---

Envoyé par DrSnake

- Un chromosome : un cas non optimisé répondant à mon problème (ici, une liste d'objet qui remplissent le sac) ?

---

Ici un chromosome c'est probablement un des sacs composant la population. Donc oui, une liste d'objets qui tiennent dans un sac.

Citation:

---

Envoyé par DrSnake

- la fonction fitness : méthode d'évaluation des éléments appartenant à un chromosome (ici, évaluation d'un objet) ?

---

Non, valeur du sac : somme des valeurs des objets qu'il contient (ou zéro s'il déborde). Ton but est de maximiser cette fonction.

Citation:

---

Envoyé par DrSnake

- Qu'est ce qu'un individu ?

---

Je crois que c'est la même chose qu'un chromosome, ici...

Citation:

---

Envoyé par DrSnake

- Dans l'hybridation et la mutation, il est question d'arborescence puisqu'on peut lire les termes parents et fils. Qu'est ce que cette structure arborescente vient faire la ?

---

Non, l'algorithme procède par étapes, que l'on appelle "générations", d'où le terme de parents et fils.

En gros, à chaque étape, on évalue (selon la fonction de fitness) tous les individus de la population. On les recombine entre eux, selon les opérateurs d'hybridation et de mutation, et en fonction de leur fitness, pour obtenir une population plus large, dont on conserve les meilleurs.

Les individus de la génération précédente sont appelés parents, ceux de la génération suivante enfants.

Francois

Merci francois pour cette réponse claire et rapide.

Donc pour les points qu'il me manquait, si j'ai suivi :

- ma population de niveau 0 est composée de tout et n'importe quoi, et pas seulement de sac répondant à somme des poids <= poids maxi. Il peut y avoir des sacs vides et des sacs dépassant le poids maxi.

- la fonction fitness est l'axiome principal de mon problème : somme des valeurs des objets. Je dois l'améliorer.

- l'amélioration se fait sur un individu ou à base de plusieurs individus, en composant des générations qui évoluent au fur et à mesure de l'évolution.

Déjà là, je comprends mieux le principe de sélection naturelle.


Dernier point dont j'ai oublié de parler : La génération des objets


Est elle totalement aléatoire ou est ce qu'elle suit certaines règles ? Je m'explique. J'ai une fonction qui va me générer un poids et une valeur aléatoire pour chaque objet. Les paramètres de cette génération doivent-ils être " réalistes " ou potentiellement farfelus. Exemple :

J'ai un sac de poids maxi fixé à 100. J'ai lance une génération d'objet dont le poids peut être supérieur à 100 ou est ce que je m'arrange pour que tous mes objets rentrent au moins à l'unité dans le sac, genre avec une limite haute à 10 pour le poids ?

Salut,

Pour le poids maxi, tu as deux façons d'aborder le problème.

1- Tu peux considérer que tous les poids sont autorisés, mais que les sacs ayant un poids dépassant le maximum ont un fitness de zéro. Ca augmente la taille de ton espace de recherche (tous les sacs), mais ca simplifie les opérateurs de crossover et de mutation (pas besoin de controler les sacs qu'ils produisent). A mon avis, si tu suis cette voie, il te faudra travailler avec une population plus large.

2- tu peux limiter ton problème aux seuls sacs admissibles. Et là, tu dois vérifier à chaque génération que les "nouveaux sacs" ne dépassent pas la taille. Cela complique un peu tes opérateurs de cross over et de mutation (il doivent tester, et eventuellement faire plusieurs essais avant de produire un nouvel individu), mais je pense que tu y gagnes en vitesse de calcul au final, parce que ton espace de recherche est borné (c'est une sorte de "simplexe" de ton espace des phases: toutes les combinaisons d'objets inférieures à un certain poids)

En fait, si tes sacs ne sont pas trop gros, tu peux peut être utiliser une approche hybride : tu limites les sacs à un nombre de chaque objet (qui dépasse le poids), et tu utilises la fonction de fitness pour éliminer ce qui dépasse.

La génération des objets c'est le coeur du système. Pour produire une nouvelle génération, tu sélectionnes les parents en fonction de leur fitness. Les parents les plus aptes ont plus d'enfants, les parents les moins aptes en ont moins. Il faut juste éviter que la population de s'appauvrisse trop vite (parce que seuls deux parents, toujours les mêmes, sont pris...). C'est généralement le rôle assigné à l'opérateur de mutation, mais on peut également le faire au niveau de la sélection des parents.

Si tu le trouves, essaye de lire le livre de Goldberg, les premiers chapitres expliquent très bien tout cela...

Francois

Ok, je vais me limiter dans un premier temps à un poids d'objet maximum contrôlé.
Bon ben il ne reste plus qu'à me lancer.
Merci pour ces éclaircissements.

PS : Je laisse le post ouvert car je sens que je vais encore en avoir besoin :).

<part acheter beaucoup de café>

Bonjour,

ça revient à une équation avec ai le nombre d'objets

Code:

---

a1 * poids objet 1 + a2 * poids objet 2 + ... + an * poids objet n = poids max

---

ou le fitness est de respecter le poids max est d'avoir la somme des objets la plus grande possible.

J'avais résolu ce genre d'équation par algo génétique en mettant les ai en binaire, le chromosome étant chaque bit.

Hop me revoilà après quelques lignes de codes en plus (moins que je pensais).

Alors, avant de parler des choix que j'ai fait, une question me titille. Voici le graphe de mes résultats.

Moyenne de la somme du poids des objets dans les sacs.
http://thomasdurif.fr/extern_img/dev...enetic_002.jpg
En abscisse, les générations.
En ordonnée, la moyenne de la somme du poids des objets dans les sacs par génération.

Moyenne de la somme de la valeur des objets dans les sacs.
http://thomasdurif.fr/extern_img/dev...enetic_001.jpg
En abscisse, les générations.
En ordonnée, la moyenne de la somme de la valeur des objets dans les sacs par génération.

Alors pour les poids, le poids maxi par sac que j'ai fixée étant 600, ça se balade autour donc ça va.
Par contre pour la valeur, aux alentours de 90, on observe une diminution, ça remontre sec jusqu'à 140, puis bim, c'est l'oubliette.

J'ai augmenté le nombre de générations pour d'autres tests et ça stagne sous les 2090. Le poids quand à lui reste aux alentours des 600.

Alors question : Est ce que ce résultat est possible/correct selon un quelconque modèle ou est ce que c'est complètement farfelu ?

Cela ne me choque pas : Je sais qu'il arrive que au bout d'un moment, la qualité des individus se dégrade (j'ai eu le problème en les utilisant pour du bin-packing). Maintenant, je ne connaît pas assez la théorie des GA pour pouvoir te dire avec précision d'où cela vient ni comment le corriger exactement...
As-tu essayé avec plusieurs valeurs de probabilité de mutation/croisement ?
Quelles sont les méthodes de croisement et de sélection que tu utilise ?

Au pire, tu pourrais forcer de la mutation ou la sélection de quelques mauvais individus toutes les x générations, histoire que le pool génétique ne s'appauvrisse pas trop vite.

Sur quoi porte ta fonction de fitness ? sur la valeur du sac, son poids ou un mix des deux ?

Dans le problème du sac a dos, les données sont connu au départ, comme le problème du voyageur de commerce, sinon ça n'a que peut de sens.

Posons donc le problème suivant :

Le sac ne doit pas dépasser 10 Kg.
Les objets possibles sont :
A: 2Kg -> 100 Eur
B: 3Kg -> 200 Eur
C: 7Kg -> 30 Eur
D: 1Kg -> 50 Eur
E: 6Kg -> 20 Eur
F: 8Kg -> 80 Eur

A partir de ces données il faut trouver la meilleurs combinaisons de piece tel que la somme des pièces dans le sac est la plus optimal par rapport au poids.

Je pense que ton algo génétique devra faire ceci :

Distributions des pièces au hasard dans une population, avec la conditions de ne pas dépasser le poids du sac = 10Kg.

Chaque individu se retrouve donc avec un sac, qui est son "ADN" :

exemple :

Titi -> [0][1][1][1][0][0] = B+C+D = 11kg > 10kg -> eliminé
Toto -> [0][1][0][1][0][0] = B+D = 250€ / 4Kg -> gardé
Tata -> [0][0][0][1][1][0] = D+E = 70€ / 7Kg -> gardé

Dans la population, on ne garde que ceux qui sont conforme au poids du sac, et on fait un classement des meilleurs individu avec une fonction de fitness, par exemple le plus petit ratio Poids/Valeur

Ensuite on déroule le scénario typique des AG... croisement avec simple cross-over ou double, etc..

Hop désolé pour mes retours un peu trop éparses sur mon topic, alors voici comment je procède actuellement :

D'abord les paramètres :
range des poids d'objets = [1;10]
range des valeurs d'objets = [1;20]
poids maximum dans un sac = 500
nombre d'objets dans un sac = 100
nombre de sac initial = 100

Ordre des tâches :
Avant le programme :
- J'ai un petit prog annexe qui me génère une série de 100 sacs avec 100 objets construits aléatoirement. J'ai créé cette liste il y a un moment, et je travaille maintenant toujours sur cette même liste histoire de voir l'évolution de mon algo par rapport à une même liste.

Pendant le programme :
- Je load ma liste de sac
- Je trie ma liste de sac
Boucle tant que j'ai plus de 10 sacs dans ma liste de sac (que j'appelle A ici)
- 30% des meilleurs éléments de A sont gardés tels quels et sont envoyés dans une liste FINALE. Les autres vont dans une liste B.
- Je lance un tournoi sur toute la liste B en mode 6 par 6. Les bons vont dans FINALE, les autres vont dans une liste C.
- 30% de la liste C passent au croisement, le résultat va dans FINALE.
- Le reste de la liste C passent à la mutation.
- Le résultat de la mutation va dans FINALE.
- Je trie FINALE.
- Je supprime le dernier (houuu le nul !)
- Je met FINALE dans A
Fin de boucle (donc fin d'une génération)

Après le programme :
Je stocke chacune de mes générations d'individus donc là je lance une écriture dans un fichier en mode csv, et pour chaque génération, j'écris le poids et la valeur du meilleur sac.


Pour ma comparaison de sac
j'utilise la valeur suivante :
sac.currentValue - (abs(sac.maxWeightForBag - sac.currentWeight))²

Je suis en Java, donc dans ma classe Bag, mon compareTo compare ces valeurs pour deux objets quand j'utilise un .sort sur une ArrayList<Bag>.

Croisement
http://thomasdurif.fr/extern_img/dev...sement_001.png

Tournoi
Je ne garde que les 2 meilleurs à chaque round.

Mutation
Pour tous les sacs qu'il me reste au moment de la mutation, je supprime aléatoirement 2 objets.

Et voici ce que j'obtiens pour la valeur de mon meilleur sac ( et non plus pour une moyenne des valeurs des sacs ) :
http://thomasdurif.fr/extern_img/dev...enetic_003.png
La descente forte au début correspond à un rapprochement de mon poids vers la valeur fixée. Je vais garder bien au frais cette version du code avec mon fichier initial, mais j'attends toute remarque ou recommandation constructive de votre part :P.

Voilou :)

bonjour bonjour,

- serai ce possible d'avoir ton cas de départ (liste d'objet) ?

Je n'aime pas beaucoup ta courbe d'évolution.. ça ne devrait pas "stagner" autant sur le même résultat, cela veux dire que ta population reste bloqué sur le même meilleur pendant trop longtemps, ça arrive souvent quand il n'y à pas assez de "sel" ou d'élément perturbateur dans la population, on appel cela aussi un maximum local de ta fonction de résultat.

Pour ceux qui est de ton programme, pourquoi ne fait tu pas plus simple ? (ce qui est déjà très complexe dans le cas des AG).


mon conseil :
1- Prends ta liste des 100 gugus avec leurs beau petit sac à dos, ensuite range lès dans l'ordre.

2 - Reproduit toute ta population comme ceci :

Tire au sort 1 individu parmi les 20 premiers, puis un autres parmi les 70 restant, croise lès = nouvelle individu de la population n+1

garde les 10 premiers à chaque fois dans ta nouvelle population.

3 - réitère ce schéma autant de fois que nécessaire (100 fois devrais suffire à donnée des résultat)

Après cela (cad quand ça marche) essaye de mettre en place un algo qui donnera naissance à une malformation dans un individu de la population n+1, avec 2 ou 3% de chance que ça se réalise à chaque nouvelle population.

heu okok, ma liste de départ, c'est 100sacs x 100 items donc 10000 lignes.
Il est téléchargeable ici.

J'expérimente plusieurs facettes de l'algo mais la stagnation nous rappelle juste que le meilleur est toujours le même sur plusieurs générations, mais vu que j'ai bcp de sacs, il se peut que ça turbine sec pour les autres sacs, sans jamais devenir meilleur.

Je dois me sauver ce soir donc je testerais ta proposition demain. :)