Algorithme G
Forum 'Discussions' - Sujet créé le 2012-06-08
Bonjour,
J'ai un problème combinatoire dans lequel une solution réalisable est modélisée sous la forme d'un vecteur binaire de taille N (donc le domaine de recherche est 2^N ).
Je souhaite a trouver une solution presque optimale pour l'instance de N=20000. J'ai programmé un algorithme génétique standard mais, après beaucoup d'effort, il arrive toujours pas a échapper les optimums locaux. Ceci dit, l'algo converge toujours a des solutions carrément différentes (ce qui devrait pas être le cas).
La taille de ma population initiale est 2*N.
La mutation affecte entre 5 et 10 gènes avec une probabilité p_m = 0.01.
Je voudrais alors poser les questions suivantes:
1) Je me demande si quelqu'un pourrait me conseiller par rapport a ces paramètres. Y-a-t-il des règles sur la taille de la population initiale et/ou le processus de mutation par rapport a la taille du problème N?
Par exemple j'avais lu quelque part que la taille de la population initiale doit être au moins 100*N mais dans mon cas cela rendrait les choses très compliquées.
2) Connaissez-vous peut-être une autre méthode de recherche globale qui serait plus efficace pour un problème de ces caractéristiques?
3) La complexité n'est pas mon point fort mais, dans ce cas la, il est clair que la solution exacte serait trouvée en temps exponentiel O(2^N). Est-ce que cela pourtant rend le problème NP-difficile, NP-complet ou NP? Comment est-ce que je pourrais le caractériser?
Merci de votre attention.
J'ai un problème combinatoire dans lequel une solution réalisable est modélisée sous la forme d'un vecteur binaire de taille N (donc le domaine de recherche est 2^N ).
Je souhaite a trouver une solution presque optimale pour l'instance de N=20000. J'ai programmé un algorithme génétique standard mais, après beaucoup d'effort, il arrive toujours pas a échapper les optimums locaux. Ceci dit, l'algo converge toujours a des solutions carrément différentes (ce qui devrait pas être le cas).
La taille de ma population initiale est 2*N.
La mutation affecte entre 5 et 10 gènes avec une probabilité p_m = 0.01.
Je voudrais alors poser les questions suivantes:
1) Je me demande si quelqu'un pourrait me conseiller par rapport a ces paramètres. Y-a-t-il des règles sur la taille de la population initiale et/ou le processus de mutation par rapport a la taille du problème N?
Par exemple j'avais lu quelque part que la taille de la population initiale doit être au moins 100*N mais dans mon cas cela rendrait les choses très compliquées.
2) Connaissez-vous peut-être une autre méthode de recherche globale qui serait plus efficace pour un problème de ces caractéristiques?
3) La complexité n'est pas mon point fort mais, dans ce cas la, il est clair que la solution exacte serait trouvée en temps exponentiel O(2^N). Est-ce que cela pourtant rend le problème NP-difficile, NP-complet ou NP? Comment est-ce que je pourrais le caractériser?
Merci de votre attention.