Discussion :

[DrSnake]

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é.

[Invité]

- 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.

- 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.

- 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.

- Qu'est ce qu'un individu ?

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

- 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

[DrSnake]

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 ?

[Invité]

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

[DrSnake]

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é>

[mr_langelot]

Bonjour,

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.