Discussion :

[zurguoli]

Salut!!!

je recherche de l'aide pour implementer un algorithme génétique en utilisant comme population initiale des arbres couvrants, générés a partir de réseaux de distribution d'eau. Le but étant de trouver l'arbre couvrant de poid minimum comme expliquer sur ce document :

http://www.cri.ensmp.fr/people/boucheba/DEA.ps

Merci

(si possible sous Matlab)

[jobherzt]

ok, formidable, mais on va pas le faire a ta place... surtout si tu as deja un document qui explique tout ca en detail.. tu l'as lu ? tu as compris ? tu a cherché ce que c'etait qu'un algo genetique ? un arbre couvrant ?

[zurguoli]

Evidement, que j'ais lu et compris ce document. Et en effet je connais un peu les arbres couvrants. Par contre je débute avec l'algorithme génétique même si je pense avoir compris le fonctionnement. Le seul problème que j'ais, c'est pour implementer cette méthode.

Je ne comprend pas trop comment générer la population initiale. Au début j'avais choisit de la générer en utilisant un programme qui me donne tous les arbres couvrants d'un graphe et après dans choisir certains aléatoirement, mais avec certains graphes cet méthode est impossible (trop de solutions) donc je m'oriente vers la méthode expliquer dans le document qui utilise deux heuristiques.

L'implémentation de cet méthode sous Matlab me pose problème.

[Nemerle]

Evidement, que j'ais lu et compris ce document... Le seul problème que j'ais, c'est pour implementer cette méthode.

donc plus humblement, si comprendre c'est pouvoir implémenter, c'est... que tu n'as pas compris!

Ou alors, tu as compris QUOI??

[alexrtz]

Salut,

Je ne comprend pas trop comment générer la population initiale. Au début j'avais choisit de la générer en utilisant un programme qui me donne tous les arbres couvrants d'un graphe et après dans choisir certains aléatoirement, mais avec certains graphes cet méthode est impossible (trop de solutions)

Le principe des algorithmes génétiques est justement de ne pas générer toutes les solutions.
Tu pars d'un nombre raisonnable de solutions (c'est à dire qui ne demande pas 30 siècles à être générer) et, à chaque itérations, tu croises tes solutions selon les critères que tu auras définis.
Il n'est pas certain que tu trouves une solution optimale avec ce genre d'algo.