Le 08/06/2012 par Dion :
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.
Le 12/06/2012 par BylRO :
Bonjour,
>> Azul (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 ).
>> 2^1023 = 8.9885e+307 Solution ! à raison de 1million de solution par secondes, il te faut 2.8502e+292 siècles pour examiner toute tes solutions. Il y a une explosion combinatoire, donc c'est un problème NP-complet ... le reste dépend de ton problème.
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).
>> C'est normal que les algorithmes génétiques donnent des solutions différentes à chaque exécution (mais de valeurs proches généralement), c'est des méta-heuristiques.
>> Comment as-tu su que c'est des minimums locaux !?
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.
>> Tout est heuristique dans les AG ! Essaye plusieurs tailles de population, défini les proba de mutation, d croisement et de remplacement en fonction de cette taille ...
>> Je te conseille de favoriser l'élitisme ... et pour gagner du temps d'exécution essaye d'évaluer les fils par simple modification de l'évaluation de leur parents (évaluation incrémentale).
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.
>> Pas de règles théoriques .... Tout est empirique ! essayes de définir des tailles (même si sans aucun rapport avec N), Fais croiser 10% de ta population, 1% pour la mutation est raisonnable ... dans la sélection et le remplacement essayes l'élitisme.
>> A chaque exécution de ton programme, sauvegardes les meilleurs individus que tu pourrais injecter dans la population initiale de la prochaine exécution.
2) Connaissez-vous peut-être une autre méthode de recherche globale qui serait plus efficace pour un problème de ces caractéristiques?
>> Je ne connais pas bien ton problème, puis les AG c'est mon dada ... Je vais m'ouvrir un peu l'esprit aujourd'hui et je te propose une méthode Tabou ... comme ton espace de recherche est grand contentes-toi de faire un mouvement dans le voisinage dès l'amélioration (au lieu de cherche le max dans le voisinage).
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?
>> J'ai donné les quelques élément en haut, c'est tous ce que je peu dire.
Merci de votre attention.
>> Bon courage ... dans l'attente d'un retour expérience
Le 25/06/2012 par jerome06 :
Bonjour,
Les éléments que vous avez donnés ne suffisent absolument pas à affirmer que le problème est NP-complet. Le nombre de solutions possibles est une caractéristique combinatoire mais fort heureusement cela ne caractérise pas un problème NP-Complet. Pour se prononcer sur cette question, il faudrait savoir quelle est exactement la fonction que vous cherchez à optimiser sur cet espace. En fonction de cela, on peut imaginer de nombreux autres algorithmes et dans bon nombre de cas, la complexité est très inférieure à O(2^N).
Si vous souhaitez un avis plus personnalisé, je peux essayer de regarder (vous pouvez m'écrire à l'adresse jerome.galtier@orange.fr).
Bien cordialement,
Le 02/07/2012 par Dion :
Bonjour BylRO et merci de votre réponse,
Désolé pour ma réponse tardive mais le site ne fonctionnait pas pour moi.
2^1023 = 8.9885e+307 Solution ! à raison de 1million de solution par secondes, il te faut 2.8502e+292 siècles pour examiner toute tes solutions. Il y a une explosion combinatoire, donc c'est un problème NP-complet ... le reste dépend de ton problème.
En effet, un algorithme exacte fournirait la seule solution optimale en temps exponentiel. Pourtant je pense que pour prouver la NP-completude est plus complique que ça.
C'est normal que les algorithmes génétiques donnent des solutions différentes à chaque exécution (mais de valeurs proches généralement), c'est des méta-heuristiques.
>> Comment as-tu su que c'est des minimums locaux !?
Justement, quand je compare les valeurs et les vecteurs binaires de chaque solution je me rende compte que mes solutions ne sont pas du tout proches, alors je me dit que ça peut être que des optimums locaux. Je pensais que mon erreur était d'initialiser la recherche avec une population relativement petite, du genre N/20 individus/solutions. J'ai fait ça car ma fonction objective est relativement compliquée et ça met pas mal de temps à chaque itération. Je ne suis pas sur combien de temps il faut laisser l'algorithme marcher avant de fournir une solution acceptable pour un problème de cette taille.
>> Tout est heuristique dans les AG ! Essaye plusieurs tailles de population, défini les proba de mutation, d croisement et de remplacement en fonction de cette taille ...
>> Je te conseille de favoriser l'élitisme ... et pour gagner du temps d'exécution essaye d'évaluer les fils par simple modification de l'évaluation de leur parents (évaluation incrémentale).
>> Pas de règles théoriques .... Tout est empirique ! essayes de définir des tailles (même si sans aucun rapport avec N), Fais croiser 10% de ta population, 1% pour la mutation est raisonnable ... dans la sélection et le remplacement essayes l'élitisme.
>> A chaque exécution de ton programme, sauvegardes les meilleurs individus que tu pourrais injecter dans la population initiale de la prochaine exécution.
Merci beaucoup, c'est exactement le genre d'information que je cherchais! J'appliquais "roulette-wheel selection" et une mutation sur le 0.0005% de la solution avec probabilité de 0.01, ça m'étonne pas que ça restait dans des optimums locaux.
>> Je ne connais pas bien ton problème, puis les AG c'est mon dada ... Je vais m'ouvrir un peu l'esprit aujourd'hui et je te propose une méthode Tabou ... comme ton espace de recherche est grand contentes-toi de faire un mouvement dans le voisinage dès l'amélioration (au lieu de cherche le max dans le voisinage).
Je me demande si avec une telle complexité il est quand même garanti qu'avec la bonne parametrisation un AG est capable de fournir une solution presque optimale? Autrement dit, est-ce que les AG ont des limitations connues?
Cordialement
Le 03/07/2012 par BylRO :
Bonjour Dion,
Je préfère que l'on se tutoie sur ce forum, c plus facile ... enfin je pense.
En fait, la seule démonstration qu'on a de la convergence des algo génétiques c'est bien la modélisation de chaque étape par un état d'une chaîne (à espace d'états dénombrable), qu'il est facile de prouver qu'elle est de Markov, irréductible et apériodique donc ergodique !
Donc elle admet une distribution stationnaire qui est la distribution limite "indépendante" de l'état initial !! (c'est le coté stochastique de ce genre d'algorithmes)...Donc au final, tu ira vers l'optimum global après un certain nombre d'itération N "suffisamment grand". Malheureusement, je ne pourrais te dire la valeur de N. Mais on conjecture que N est raisonnable !
A part les limites que peut avoir une méta-heuristique en générale, les AG n'ont pas d'autre particulières. Ils sont très puissants et appliqués presque partout en optimisation difficile.
Si tu fait un peu de parallélisme, tu peux lancer plusieurs populations sur des processus différents (ilots) ... puis tu définit un nouvel opérateur qui est la migration...après chaque pas de temps (fixe ou aléatoire) des individus sélectionnés quittent leur ilots pour partir dans un autre.... c'est un peu ce que je t'ai proposé en gardant les meilleurs de chaque exécution que tu fais injecter à la prochaine...mais la parallélisation est un vrai atout !!
Merci de m'informer de l'évolution de tes travaux.
Cordialement
Le 03/07/2012 par Dion :
Bonjour BylRO,
Merci pour ces explications, ça aide beaucoup. T'aurais pas une publication à me proposer au sujet de la théorie de convergence derrière les AG?
Est-ce que la méthode que tu viens de décrire (avec l'opérateur de migration) est une variante d' AG qui porte un nom spéciale? Je pense qu'avec le bon paramétrage de l'AG canonique je peux éteindre mon but, pourtant il est toujours utile d'en connaître plus.
Cordialement
Le 03/07/2012 par Dion :
Bonjour Jerome et merci pour votre disponibilité,
Les éléments que vous avez donnés ne suffisent absolument pas à affirmer que le problème est NP-complet.
Je m'en suis douté, je me souviens de mes études qu'il fallait prouver que le problème appartient dans NP et NP-difficile. Est-ce qu'il y a pourtant quelque chose par rapport à la complexité de mon problème que l'on peut déduire sur la base de l'information donnée?
Le problème en question ne se base pas sur un problème connu, c'est un genre d'apprentissage combinatoire que j'ai modélise à partir d'un problème biologique réel. Je voudrais bien par contre le paralléliser avec un problème connu afin de pouvoir estimer sa complexité. L'étape d'optimisation ressemble à n'importe quel problème dont la solution peut se modélisée sous la forme d'un vecteur binaire, comme par exemple le problème de la coupe maximale (maximum cut), qui est en effet un problème NP-complet. C'est difficile à décrire exactement ce que ma fonction objective fait mais je peux affirmer qu'elle est au moins aussi complexe que celle du problème max-cut. Si vous êtes d'accord, je pourrais vous envoyer le code MATLAB ou bien un pseudocode simplifié qui indique la complexité de la fonction.
Cordialement
Le 03/07/2012 par BylRO :
Rebonjour,
Pour la convergence, je te conseil de piocher dans ... par exemple cette thèse http://tel.archives-ouvertes.fr/docs/00/26/89/27/PDF/global.pdf
Tu y trouveras des explications et références.
La variante de l'AG parallèles permet de profiter de l'exécution d'un AG sur plusieurs îlots, la migration de certains individus permet donc de sortir de coup (presque) sûr des minima locaux. Les individus qui survivent ne sont les plus forts ou les plus intelligents ... mais les plus adaptable !
(J'ai pu prendre connaissance de cette variante lors de mon passage à Lille).
Oui, il est sûr qu'il faut bien voir tous ce qui est s'attache à ton travail pour pouvoir maitriser ton sujet et peut être proposer quelque chose de spécifique à ton problème.
Bon courage.
Le 19/07/2012 par jerome06 :
Bonjour Dion,
Oui pas de souci pour jeter un oeil sur un code matlab ou autre simplifié.
Jerome
