Discussion :

[mortal]

Bonjour.

Je dois déterminer l'un des meilleurs chemins entre une source et une destination dans un graphe de plus de 500 nœuds. J'ai écris un script
qui fonctionne comme suit:

Code :

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

1
2
3
Faire k fois
Générer n chemins aléatoires
Choisir le meilleur chemin parmi les n (en fonction du coût)
Prendre le meilleur par les k chemins.

Donc, je ne me limite qu'à générer aléatoirement la population et sélectionner les meilleurs individus dans faire de croisement ni de mutation? Est ce que je peux qualifier ce procédé de génétique? Sinon de qu'elle types d'algorithmes se rapproche t'il?

Merci.

[dourouc05]

J'aurais tendance à dire qu'un algorithme génétique doit faire évoluer sa population. Là, je parlerais plus d'optimisation stochastique (aussi dite aléatoire) : tu tires des solutions au hasard, sans corrélation. Si tu génères tes n chemins en regardant le précédent, ça serait plus une recherche locale : tu pars d'une solution au hasard, tu l'améliores (au moins, tu tentes).

A priori, à moins d'avoir une grande valeur de , j'aurais tendance à dire que ton algorithme n'a pas beaucoup de chance de trouver une solution même proche de l'optimalité… Une approche génétique pourrait partir d'une population, tenter de croiser des chemins (détecter des chemins qui se correspondent jusqu'à un certain point, créer un enfant qui prend la partie commune et le chemin le plus court des deux parents — en se basant sur le principe de sous-chemin optimal) ou d'en muter quelques-uns (choisir un nœud, rechercher la meilleure manière de le remplacer dans le chemin).