Discussion :

[Trap D]

Bonjour

je cherche à l'aide d'algos génétiques à trouver l'issue d'un labyrinthe.
J'y arrive mais en utilisant une fonction d'évaluation adaptée au labyrinthe étudié.
Par exemple, pour ce labyrinthe,

la fonction d'évaluation force la montée vers le haut, tant que la colonne est plus petite que 6 puis à descendre après.
Pour celui-ci

je favorise la montée jusqu'à la cinquième ligne, puis ensuite le déplacement vers la droite.

Enfin pour celui-ci,

je n'ai toujours rien trouvé

En conclusion, ces fonctions d'évaluation sont trop spécifiques et si je veux trouver la solution d'un labyrinthe créé aléatoirement ça ne fonctionne pas. Si vous avez une piste de recherche ...

J'avais pensé à favoriser les parcours les plus longs, mais rien n'empêche les retours sur des cases déjà visitées et de plus, travaillant en Prolog, je suis un peu limité en taille, j'ai une population de 100 individus ayant 50 gênes. (ce qui fait que mon parcours fait au plus 50 étapes ce qui est juste suffisant).

Merci d'avance de vos remarques.

Trap D

[acx01b]

salut

partir de l'ensemble "toutes les cases"
et en supprimer progressivement c'est autorisé ?

dans ce cas la fonction d'évaluation c'est le nombre de cases et si l'ensemble n'est pas connexe alors on tue l'individu

oops en prolog ça ne va pas être marrant de coder "l'ensemble est-il connexe"

[Trap D]

Salut

Merci de ta réponse mais elle me laisse perplexe.

Le principe de l'algo génétique est qu'on a un ensemble d'individus ayant un certain nombre de gênes, mais ce nombre est fixe.
Ensuite on on peut classer les individus, on doit en principe au moins conserver le "meilleur", on fait muter, croiser les individus, on peut aussi faire des sélections.


Pour ma part, les individus sont des chemin à partir du point de départ en bas à gauche et les génes représentent les déplacements à partir de la case courant, chaque gêne est un mouvement de 1 case vers le Nord, Est, Sud ou Ouest.

Comment envisages-tu les individus et les gênes ?

[acx01b]

oui je suis d'accord que c'est pas très élégant

ma proposition pour le codage :

les gènes: 1 la case est dans l'ensemble
0 la case n'est pas dans l'ensemble

un individu c'est 0 ou 1 pour chaque case (un individu c'est un ensemble de cases)

les mutations: enlever une case
les croisements: tu peux en faire mais ça ne sert pas trop à priori c'est plutôt enlever une case qui sert à quelque chose

à la rigueur il y a aussi rajouter une case comme mutation possible pour éviter les minimas locaux mais après je ne m'y connais pas trop (peut être que ça le fait déja avec les croisements ?)

EDIT: ça doit pas être évident d'éviter les minimas locaux avec ce codage

[pseudocode]

Ensuite on on peut classer les individus, on doit en principe au moins conserver le "meilleur", on fait muter, croiser les individus, on peut aussi faire des sélections.

Quelle mesure as tu choisi pour trouver le "meilleur" individu ?

[Trap D]

Quelle mesure as tu choisi pour trouver le "meilleur" individu ?

Pour les cas où j'ai trouvé la fonction d'évaluation, j'utilise une paire (Ligne-Colonne)
Par exemple, pour le premier labyrinthe

la fonction d'évaluation force la montée vers le haut, tant que la colonne est plus petite que 6 puis à descendre après.

La fonction d'évaluation s'écrit en Prolog :

Code :

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

1
2
3
4
5
6
% evaluation pour le labyrinthe
evaluation(9, [0, 0]).
 
evaluation(Case, [Ligne, Col]) :-
	Col is 10 - (Case mod 10) ,
	(   Col > 4 -> Ligne is 20 - (Case // 10) ; Ligne is Case // 10).

D'abord une remarque sur le codage :
- Les case sont numérotées de 0 en bas à gauche à 99 en haut à droite.
- Nécessité Prolog j'utilise un keysort, basé sur un couple de valeurs appelées (Ligne, Colonne), et comme je veux avoir en tête de liste les meilleurs éléments, plus le score est bon, plus Ligne et Colonne doivent être petits.

Dans un premier temps, partant de la case 0 en bas à gauche, (codée donc colonne 10), je veux forcer à monter donc comme les lignes varient de 1 en bas à 10 en haut, pour obtenir une valeur Ligne faible je fais 20- le numéro de ligne, puis après il faut redescendre, donc lorsque la colonne est plus petite que 4 je prend pour Ligne le numéro de ligne simplement.

je ne prends pas en compte la longueur de chemin, car avec la méthode que j'utilise, les retours en arrière sont courants.

Je suis en train de faire des tests avec un autre type d'évaluation (basés justement sur la longueur de chemin et le numéro de colonne mais ce n'est pas probant du tout.

Je vais réfléchir aussi à ce que suggère acx01b qui m'a l'air très intéressant, c'est une approche complètement différente, j'étais trop centré sur la dynamique de création de chemin.

[pseudocode]

Pour les cas où j'ai trouvé la fonction d'évaluation, j'utilise une paire (Ligne-Colonne)

la fonction d'évaluation force la montée vers le haut, tant que la colonne est plus petite que 6 puis à descendre après.

Une fonction d'évaluation qui dépend de la future solution, c'est un peu de la triche, non ?

Pourquoi ne pas prendre une fonction du genre "distance (L1) entre le dernier element et la sortie" ?

[Trap D]

Une fonction d'évaluation qui dépend de la future solution, c'est un peu de la triche, non ?

Mais tout à fait, c'est pour celà que je viens demander conseils.

je suis parti sur un exemple trouvé sur Internet, le prof disait de prendre comme fonction d'évaluation la ligne d'arrivée et la longueur de chemin.

Je suis parti de celà, mais la longueur du chemin n'est pas un bon critère, je n'interdis pas les retours en arrière.

La distance à la case d'arrivée n'est pas forcément un bon critère car dans le dernier labyrinthe, elle peut être à un moment de 3 et on est encore loin d'être arrivé puisqu'il faut s'en éloigner pour y revenir !!!
Maintenant, parles-tu de la distance à vol d'oiseau ou de la distance effective "par la route", auquel cas celà suppose que je connais la solution ...

Bref je suis un peu coincé et complètement en panne d'inspiration, il est tant que je prenne des vacances !

[pseudocode]

La distance à la case d'arrivée n'est pas forcément un bon critère car dans le dernier labyrinthe, elle peut être à un moment de 3 et on est encore loin d'être arrivé puisqu'il faut s'en éloigner pour y revenir !!!
Maintenant, parles-tu de la distance à vol d'oiseau ou de la distance effective "par la route", auquel cas celà suppose que je connais la solution ...

Je parlais de la distance "à vol d'oiseau". Effectivement certains chemins peuvent obtenir un score proche de 0 mais mener à une impasse. Il faut alors autoriser des chemins avec un score plus grand (facon recuit simulé).

Sinon une autre technique consisterai a créer 2 populations de demi chemins (partant du départ, et partant de l'arrivé) et a considerer la distance minimum "a vol d'oiseau" entre ces 2 populations.

[Trap D]

Je suis en train de réfléchir à une solution basée sur l'idée de acx01b
Les individus auraient 100 gênes codés 0 ou 1. Je conserverais les individus qui correspondent à des chemins partant de 0 ou arrivant à 9. (un peu ce que tu proposes

Sinon une autre technique consisterai a créer 2 populations de demi chemins (partant du départ, et partant de l'arrivé) et a considerer la distance minimum "a vol d'oiseau" entre ces 2 populations

J'éliminerais les autres.
Ensuite par croisements, mutations et autres, on peut peut-être arriver à trouver le chemin !

Je vous tiens au courant.

En tout cas les échanges sont générateurs d'idées, merci à tous.

Maintenant, je vais corriger des copies, autre genre de distractions.

[Matthieu Brucher]

Je parlais de la distance "à vol d'oiseau". Effectivement certains chemins peuvent obtenir un score proche de 0 mais mener à une impasse. Il faut alors autoriser des chemins avec un score plus grand (facon recuit simulé).

Il est toujours conseillé de ne pas que sélectionner les meilleurs solutions pour un algo génétique, il me semble. Ce cas illustre bien cette nécessité.

[coyotte507]

Bonjour,

Je ne connais pas prolog,
mais concernant les retours en arrière, ne serait-il pas mieux que lorsqu'il y a un retour sur une case X déjà visitée , de supprimer du chemin tout le morceau de parcours qui part de X et revient à X?

Je dis ça, mais je ne sais pas du tout si c'est compatible avec prolog...

[pseudocode]

C'est surtout que c'est pas très compatible avec l'idée que je me fais des algos génétiques. Ca ressemble plus a de l'exploration façon A-star.

[acx01b]

il y a-t-il des boucles, ou plusieurs chemins de A à B dans ton labyrinthe ?
car si non alors avec ton codage ça supprime le problème du retour en arrière (interdit d'avoir droite puis gauche, ou haut puis bas ...) et avec mon codage ça supprime le problème de la connexité de l'ensemble: il suffit de regarder sur un 4 voisinage de la case pour savoir si la supprimer garde la connexité

pour résumer: s'il n'y a qu'un seul chemin de A à B dans le labyrinthe alors le problème est facile à résoudre

[JeromeBcx]

Je rejoinds Pseudocode, je doute de l'intéret d'utiliser un AG pour ce problème... l'algo des fourmis me parait plus approprié.

NB : en théorie, il vaut mieux avoir une forte probabilité de cross-over et une faible proba de mutation dans l'utilisation d'un AG.

[Trap D]

I'm back

Je rejoinds Pseudocode, je doute de l'intéret d'utiliser un AG pour ce problème... l'algo des fourmis me parait plus approprié.

J'avais envie de faire un algo génétique, n'en ayant jamais fait, et j'ai trouvé sur Internet un exemple.
Je suis parti sur l'exemple, avec fonction d'évaluation spécifique, comme ça marchait plutôt pas mal, j'essaye maintenant de généraliser.
je vais étudier l'idée d'individus de 100 gênes codés 0/1 simulant des chemins du départ à l'arrivée, ce sera beaucoup plus général et applicables à tous les labyrinthes de n'importe quelles dimensions.

Maintenant, je pense que rien n'est mieux qu'une recherche en largeur des chemins pour tropuver l'issue, mais celà n'engage que moi

NB : en théorie, il vaut mieux avoir une forte probabilité de cross-over et une faible proba de mutation dans l'utilisation d'un AG.

N'étant pas très familier avec le vocabulaire des A.G., je suppose que tu veux dire qu'il vaux mieux avoir beaucoup de croisements d'individus que de mutations ?

[JeromeBcx]

N'étant pas très familier avec le vocabulaire des A.G., je suppose que tu veux dire qu'il vaux mieux avoir beaucoup de croisements d'individus que de mutations ?

Oui, pardon pour les termes anglais...