L'idée..

• [^]Re: L'idée..

  Posté par Mickaël Sibelle (Jabber id, page perso, ) le 09/01/2005 à 13:54. (lien). Évalué à 6.

  Les algorithmes génétiques permettent principalement à un système de s'auto-optimiser en fonction de son utilisation.
  
  AMHA il est donc difficile de mesurer le gain, puisqu'il faut pour cela généraliser, faire des moyennes.
  
  Mais effectivement, cette idée ne me semble pas exploitable dans le monde du "desktop".
  
  Sinon, il y a des gens qui bossent à fond sur l'ordonnencement dans les FAC : y'a plus qu'à savoir s'ils y ont pensé ;)

• [^]Re: L'idée..

  Posté par Rémi Hérilier (page perso, ) le 09/01/2005 à 14:08. (lien). Évalué à 6.

  Les algo G (génétiques) servent à résoudre un problème (ou une classe de problème). Changer l'utilisation à de grande chance de déformer le problème et donc d'entrainer une perte de perf le temps que le système se restabilise. D'ailleurs, il est question de sortir l'algo G du noyau, quid de changer les paramètres selon les besoins du moment ?
  
  Sinon, il est question de 1-3% de perf, mais pas du type de la machine ? monoproc, bi, quadri ?

• [^]Re: L'idée..

  Posté par MiniMoi () le 09/01/2005 à 14:10. (lien). Évalué à 7.

  Tout à fait d'accord avec toi, l'idée est très intéressante, et même si l'utilité n'est pas évidente, il y a quelque chose à creuser de ce côté là.
  Par contre ce que je crains c'est que cette optimisation entraîne un grande complexification de certaines parties du kernel, et que finalement un avantage devienne un inconvénient...
  Même si ce patch est implémenté sous forme de "hooks", il doit quand meme y avoir quelques modifications de l'ordonnanceur qui est déjà assez complexe!
  Les algorithmes génétiques sont un sujet vaste et complexe, mais en tout cas l'idée me séduit beaucoup!
  
  Et puis si ça peut servir comme argument marketing pour Linux (il y a bien une dizaine depersonne au moins qui seront tres fières d'avoir un kernel auto-tuné...). Il ne reste plus qu'à trouver un nom "sympa", comme "Auto-tuning intelligent genetic system®"

  • [^]Re: L'idée..

    Posté par Sebastien Binet () le 09/01/2005 à 14:21. (lien). Évalué à 10.

    Il ne reste plus qu'à trouver un nom "sympa", comme "Auto-tuning intelligent genetic system®"
    
    Ou alors, DNA/Linux "Genetic patents inside" :P

  • [^]Re: L'idée..

    Posté par XHTML/CSS inside (page perso, ) le 10/01/2005 à 21:39. (lien). Évalué à 0.

    Ou Tuned Intelligent Genetic Environnement Reality.
    
    Merde, c'est déjà pris : TIGER...
    
    J'y file ======>[]

    --
    In tartiflette we trust !

• [^]Re: L'idée..

  Posté par Antoine J. (Jabber id, ) le 09/01/2005 à 17:54. (lien). Évalué à 10.

  Humm... Je crois qu'il est plus urgent d'utiliser cet algorithme génétique pour améliorer les techniques de drague des geeks. Les ordonnanceurs attendront, il en existe déjà qui fonctionnent honorablement.

Algorithme génétique ?

• [^]Re: Algorithme génétique ?

  Posté par Julien Duponchelle (page perso, ) le 09/01/2005 à 13:55. (lien). Évalué à 4.

  Regarde le troisieme liens de la depeche c'est explique.

• [^]Re: Algorithme génétique ?

  Posté par Mickaël Sibelle (Jabber id, page perso, ) le 09/01/2005 à 13:56. (lien). Évalué à 5.

  L'idée c'est que la nature se démerde très bien
  et de lui piquer son "idée" (attention : la nature a breveté son idée !!!)
  
  En gros : tu as des solutions.
  Tu les fait se "reproduire" pour avoir de nouvelles solutions en pondérant les bonnes propriétés des "parents"...

  • [^]Re: Algorithme génétique ?

    Posté par PsychoFox () le 12/01/2005 à 08:30. (lien). Évalué à 2.

    L'idée c'est que la nature se démerde très bien
    et de lui piquer son "idée" (attention : la nature a breveté son idée !!!)
    
    Oui bon pas toujours hein. Sinon on n'aurait probablement pas de dents de sagesses, pas d'apindicite, les femmes n'auraient pas de règles souvent douloureuses, etc (la plupart des espèces animales ont d'ailleurs au moins un truc inutile qui les fait souffrir pour rien, des trucs qui ne servaient qu'aux poissons, reptiliens et autre et qu'on a gardé bêtement).

    • [^]Re: Algorithme génétique ?

      Posté par tgl () le 12/01/2005 à 08:49. (lien). Évalué à 2.

      En fait, la nature fait du bon boulot mais elle ne le finit jamais...

      • [^]Re: Algorithme génétique ?

        Posté par Black Fox (page perso, ) le 13/01/2005 à 19:43. (lien). Évalué à 3.

        La nature devrait se reconvertir dans l'informatique... Ca ne la changerait pas des masses :D

    • [^]Re: Algorithme génétique ?

      Posté par Sylvain Sauvage () le 12/01/2005 à 19:41. (lien). Évalué à 2.

      des trucs qui ne servaient qu'aux poissons, reptiliens et autre et qu'on a gardé bêtement
      La Nature travaille sur la durée : on sait jamais ça pourra peut-être resservir quand les glaciers de l'Antarctique auront fondu...

• [^]Re: Algorithme génétique ?

  Posté par koxinga () le 09/01/2005 à 14:01. (lien). Évalué à 6.

  Si j'ai bien compris, ce sont des algorithmes qui génèrent plein de solutions, ne gardent que les meilleures, et regénèrent d'autres solutions à partir de celles la. Ils se comportent comme la sélection naturelle, en gros. Ca ne permet pas forcément de trouver la solution idéale et il faut beaucoup de génération pour que cela vaille le coup. C'est surtout cela qui m'impressionne ici, il arrive à compenser le coût de son algorithme et à gagner de la performance en plus.

  • [^]Re: Algorithme génétique ?

    Posté par liberforce (Jabber id, page perso, ) le 09/01/2005 à 14:14. (lien). Évalué à 8.

    ça permet surtout de déterminer des solution optimum, sans avoir d'à priori sur les solutions.... L'avantage des algos génétique c'est que tu peux tester des solutions que tu n'aurais pas testé autrement, parce que tu te serais dit : trop gros, passera pas... Alors qu'il y a peut être une excellente solution dans l'espace que tu as choisi de ne pas explorer...
    
    Je trouve que non, ce n'est définitivement pas une solution de geek, et que c'est sans doute une solution d'avenir même : cela permettrait après une réécriture d'une partie sensible au niveau performance du noyau d'éviter tout la partie "tuning" qui peut être très difficile à réaliser lorsqu'il y a beaucoup de paramètres. Effectivement, pour le desktop cela n'apporte pas grand chose, mais pour des supercalculateurs voire des serveurs, je pense que le gain rapporté au nombre de machines peut être beaucoup plus intéressant...
    
    Je pense sincèremement que c'est une technique qui a de l'avenir et qui gagne à être développée...

    • [^]Re: Algorithme génétique ?

      Posté par Croconux () le 09/01/2005 à 17:06. (lien). Évalué à 8.

      L'avantage des algos génétique c'est que tu peux tester des solutions que tu n'aurais pas testé autrement
      
      C'est même pour ça que c'est très utilisé dans la conception des processeurs. J'ai eu un prof en électronique qui a bossé au Japon chez un fabricant d'électronique (Motorola, je crois) et qui m'a raconté qu'étant donné le niveau de complexité des puces modernes, il est très difficile de trouver une solution optimale à la main. On peut concevoir facilement une implémentation naïve mais on utilise 10 fois trop de transistors. Avec un algorithme génétique on découvre des implémentations qui font la même chose du point de vue logique mais avec beaucoup moins de transistors, donc moins chères à produire. Ce sont souvent des solutions auquelles on aurait jamais pensé.

  • [^]Re: Algorithme génétique ?

    Posté par Beretta_Vexee (Jabber id, ) le 09/01/2005 à 16:14. (lien). Évalué à 10.

    Si j'ai bien compris, ce sont des algorithmes qui génèrent plein de solutions, ne gardent que les meilleures, et regénèrent d'autres solutions à partir de celles la.

    
    
    Ton approche est ce qu'on appel un algo Maximiseur ou MiniMax, on effectue une coupe franche en fonction de la performance mesuré pour un ensemble de solution partiel, ça marche très bien pour certains problèmes mais pas pour d'autre. Pour prendre un exemple, si tes algo jouent aux échecs, Minimax écartera systématiquement les solution qui implique la perte d'une pièce, alors que cela peut ouvrir des solutions plus intéressante par la suite ( on appel ça un minimum local ).
    
    Un algo génétique n'écarte une branche ou un élément de solution un "géne" qu'au bout de plusieurs générations infructueuses quand il est poussé a l'extinction par d'autre "géne", c'est beaucoup plus efficace mais aussi beaucoup plus lourd le nombre de solution a traité est toujours assez grand, mais l'on limite tous de même le nombre de test a la population tous en s'approchant d'une solution optimale.
    
    

    Ils se comportent comme la sélection naturelle, en gros. Ca ne permet pas forcément de trouver la solution idéale et il faut beaucoup de génération pour que cela vaille le coup.

    
    
    Ce type d'algorithme est principalement utiliser sur les probléme dit NP complexe, Non Polynomiale Complexe, c'est une notion mathématique que je ne maîtrise pas pour en gros dire que pour telle problème le temps de traitement est incroyablement long avec un algo simple du type je teste toutes les solutions et que n'est pas efficace MiniMax ( je n'ai pas de critère efficace qui me permet des tronçonner mon arbre de test ) , concrètement l'exemple type c'est le problème du voyageur de commerce ( un voyageur doit passer par tout un ensemble de ville, une seul fois et en parcourant le chemin le plus court ).
    
    Hors on ne trouve que très rarement la meilleur solution a un problème NP complet, on est déjà bien contant d'avoir une bonne solution.
    
    

    C'est surtout cela qui m'impressionne ici, il arrive à compenser le coût de son algorithme et à gagner de la performance en plus.

    
    
    Il ne faut pas s'enflammer non plus les algo génétique ne sont pas la panacée universelle. Ce n'est pas le seul algo auto-adaptatif, ( y a les réseaux de neurones, les fourmis, le recuit ) en général c'est assez/trés dur a maîtriser et utiliser, de plus c'est non déterministe ( son temps d'exécution n'est pas connue ) ce qui est leurs principaux défauts.

    --
    Il relève de la responsabilité du lecteur de contrôler, par tous moyens, l'adéquation du message à ses besoins et de s'assurer qu'il ne causera pas de dommages aux personnes et aux biens.

    • [^]Re: Algorithme génétique ?

      Posté par pifou () le 09/01/2005 à 17:12. (lien). Évalué à 5.

      Tout à fait d'accord avec tes compléments d'informations, on peut même ajouter le problème de compréhension des solutions générées. Car même si on trouve une solution efficace grâce à un algorithme génétique ça n'est pas évident qu'on arrive à comprendre pourquoi ! Ce qui est un peu bête si on veut vérifier si par hazard ce n'est pas la solution optimum et donc de continuer à chercher quelque chose de mieux (qui n'existe peut être pas). Je me rappelle l'exemple d'un algo génétique qui simuler le bon vieux cas d'école des fourmis (recherche de nourriture, trace de phéromone ...), et bien ils étaient tombé sur la solution optimale (d'après les paramètres mis en jeu) mais on mis un temps énorme à le prouver :).

      • [^]Re: Algorithme génétique ?

        Posté par Beretta_Vexee (Jabber id, ) le 09/01/2005 à 18:01. (lien). Évalué à 2.

        Les algo génétique et ce que l'on appel l'algo fourmis ( Ant Algorithme ), sont assez different. Si ma mémoire est bonne l'algo de la fourmis c'est que de la théorie des graphs ( avec des noeuds coeffiencés et les liens avec des poids correspondant aux phéromones ... ). C'est marrent mais j'ai jamais trop comprit quel application cela pouvait avoir par rapport aux autre heuristiques.
        
        Cinon oui pour prouver que l'on a la solution optimale a un NP je crois qu'il n'y a pas d'autre solution de tous calculer, donc ca a dut leur prendre un bon bout de temps en effet.

        --
        Il relève de la responsabilité du lecteur de contrôler, par tous moyens, l'adéquation du message à ses besoins et de s'assurer qu'il ne causera pas de dommages aux personnes et aux biens.

        • [^]Re: Algorithme génétique ?

          Posté par Sebastien Binet () le 09/01/2005 à 18:10. (lien). Évalué à 2.

          Toi qui a l'air d'etre bien cale...
          Quelle est la difference avec ceci : Support Vector Machine algorithms[1]
          (Desole, mais je vois pas trop comment je pourrais le traduire)
          
          [1] : http://projects.fnal.gov/run2aag/mini_jun02/svm.ps.gz(...)

          • [^]Re: Algorithme génétique ?

            Posté par Beretta_Vexee (Jabber id, ) le 09/01/2005 à 19:20. (lien). Évalué à 2.

            "machine à vecteurs de support" C'est a peut prés tous ce que je peux t'en dire apres 15 min de google. Cinon je ne suis absolument pas calé en algo, je n'ai que quelques bases.

            --
            Il relève de la responsabilité du lecteur de contrôler, par tous moyens, l'adéquation du message à ses besoins et de s'assurer qu'il ne causera pas de dommages aux personnes et aux biens.

            • [^]Re: Algorithme génétique ?

              Posté par Besnard Jerome () le 10/01/2005 à 00:50. (lien). Évalué à 7.

              Les SVM sont une algorithmique assez recente mise au point pour attaquer les problemes classiques du machine learning, modelisation empirique fonctionnelle, classification,...
              
              Ses deux originalités, ou particularites, sont de construire un espace de representation qui est beaucoup plus grand que l'espace de depart de facon automatique, et aussi de savoir "redescendre" (supprimer les dimensions peu utiles) de facon robuste.
              
              Ca n'est pas la panacee (mais c'est sympa) ca n'est pas en concurrence avec les algo genetiques.
              
              Son nom vient du fait qu'il considere (ce qui est malin) que seul certains points sont interessant (support vector) ceux qui sont au "bords" des varietes qui nous interessent (dans l'espace de representation). Ce qui est assez bien vu faut le dire.
              
              V.Vapnik en est le concepteur. Il a aussi fait beacoup pour la théorie de l'apprentissage en general.

          • [^]Re: Algorithme génétique ?

            Posté par mpstarix () le 10/01/2005 à 12:52. (lien). Évalué à 7.

            En gros, le principe de base d'une SVM est le suivant :
            Séparer par un (hyper)plan des points d'un espace avec une marge maximale.
            
            "Avec les mains", tu imagines une population de points rouges et une autre de points bleus que tu sais séparer avec une droite. Ensuite, tu imagines que ta droite va enfler comme un matelas pneumatique et s'épaissir. Elle finit par prendre appui sur des points rouges et des points bleus "limite".
            
            Dans ce cas, tu prends le milieu de ton matelas pneumatique, et tu dis, "cette droite sépare mes points rouges et mes points bleus avec une marge (la moitié de l'épaisseur du matelas) maximale".
            
            L'intérêt principal de la méthode, c'est que tu n'as plus besoin de TOUS les points rouges et de TOUS les points bleus. Seuls les points "limite" suffisent à définir ta frontière.
            
            Maintenant, si on s'intéresse au cas non séparable, il faut faire un compromis sur la marge d'erreur (saleté de point bleu qui s'est mis au milieu des rouges !).
            
            Enfin, on peut essayer de passer dans des dimensions supérieures. Ca permet, en revenant à la dimension initiale, d'avoir une forme de délimitation plus complexe qu'un demi espace. Par exemple, en passant de la dimension 2 à la dimension 6, on sépare par des côniques (ellipse, parabole, hyperbole) au lieu de bête droites.
            
            Ce qui deivent intéressant, c'est de ne pas trier des points rouges et des points bleus, mais des vrais mails et du SPAM, en s'appuyant sur quelques mails "limite" définis par l'utilisateur.
            
            Pour plus d'infos sur la théorie, il faut commencer à maîtriser les multiplicateurs de Lagrange.
            
            D'autres explications sur http://www.kernel-machines.org/(...)

            • [^]Re: Algorithme génétique ?

              Posté par Sebastien Binet () le 10/01/2005 à 13:05. (lien). Évalué à 3.

              Bonne explication avec les mains ! :)
              
              Pour plus d'infos sur la théorie, il faut commencer à maîtriser les multiplicateurs de Lagrange
              
              La c'est assez inquietant. Je suppose que les multiplicateurs de Lagrange sont la pour prendre en compte la contrainte de la marge maximale (j'ai bon ?).
              Dans ce cas-la, la methode des SVM ne peut alors s'appliquer que sur des echantillons dont les erreurs sont gaussiennes (ce qui n'est pas forcement le cas de *tous* les problemes rencontres).
              
              Bon je vais me plonger dans la biblio de kernel-machines.
              Encore merci :)

              • [^]Re: Algorithme génétique ?

                Posté par mpstarix () le 10/01/2005 à 19:09. (lien). Évalué à 2.

                Exactement : Il faut trouver un vecteur (a1,...an,b) tel que pour chaque vecteur (x1,x2,..,xn), le produit (a1*x1 + ... + an*xn + b) soit plus grand que 1 ou plus petit que -1, ce qui s'interprete géométriquement comme la distance entre X et ton plan de séparation.
                
                En augmentant d'une dimension, avec pour coordonnée 1 le vecteur X, et en prenant les coords du plan noté sous la forme du vecteur A (a1,...,an,b), et quitte à changer des signes, il suffit d'avoir
                
                A.X >= 1 pour tout vecteur X. Avec m points, on a une famille de Xi (1<i<m) qui forme m contraintes
                
                et là, on optimize la fonction de la mort l1*A*X1 + ... + lm*A*Xm (où l1,..lm sont les multiplicateurs de Lagrange).
                
                Et la magie, c'est que les multiplicateurs de Lagrange sont non nuls si et seulement si le point réalise la limite de la contrainte.
                
                Donc, il y a un moyen mathématique connu (et simple ?) de trouver les points qui réalisent la limite.
                
                
                Par contre, je ne vois pas le rapport avec la gaussianité des problèmes. Le but est de réduire une population d'échantillons bien triés aux cas limite pour avoir un apprentissage (statistique) qui n'explose pas avec le nombre de samples. Typiquement, pour les points du plans, s'ils sont bien séparables, tu passes de n points à 3 ou 4 points. Au maximum 10.
                
                Si le problème n'est pas gaussien dans la dimension où tu le regardes, peut être qu'il l'est en dimension supérieure, ou avec un noyau plus astucieux que les polynômes.

                • [^]Re: Algorithme génétique ?

                  Posté par Sebastien Binet () le 10/01/2005 à 19:58. (lien). Évalué à 3.

                  La gaussiannite du probleme est une des hypotheses de travail pour l'application des multiplicateurs de Lagrange.
                  
                  Arf, je n'ai plus de pointeur vers l'article qui m'a servi de base pour avancer ceci.
                  En tout cas l'ajustement par les ML demande que les variables de ton vecteur x soient distribuees normalement (a la louche je pencherais bien pour le fait que lorsque tu fais ton ajustement, le Chi2 que tu construis et minimise requiert que les variables soient normales).
                  
                  Auto citation :
                  http://agenda.cern.ch/fullAgenda.php?ida=a041294(...)
                  et le lien direct :
                  http://agenda.cern.ch/askArchive.php?base=agenda&categ=a041294&(...)

                  • [^]Re: Algorithme génétique ?

                    Posté par mpstarix () le 11/01/2005 à 13:29. (lien). Évalué à 1.

                    Heu "tableau de décodage incorrect" d'après Adobe Reader 6...
                    
                    Je suis très sceptique quant à la nécessité d'avoir un problème gaussien pour utiliser les ML : je n'ai aucun souvenir d'une telle contrainte, et d'après les quelques sites qui parlent de ML, je n'ai pas trouvé cette contrainte dans les hypothèses. Et d'ailleurs, vu que ça repose sur le Théorème des fonctions implicites qui lui même repose, si mes souvenirs sont bons sur le théorème d'inversion locale), il n'y a pas d'hypothèse sur la répartition statistique des points. Du reste, j'imagine qu'au prix d'une mesure de distance appropriée, et en regardant le problème de suffisamment loin, on ne doit pas être trop loin d'une loi Gaussienne (le théorème central limite aide un peu).
                    
                    Et puis les problèmes de reconnaissance / tri sont souvent basés sur le concept "une collection de prototypes, et je cherche à trouver le prototype le plus proche de mon exemple", donc l'idée que ce soit gaussien n'est pas complètement inepte. Enfin ça doit dépendre de ce pour quoi tu voudrais utiliser des SVM.

                    • [^]Re: Algorithme génétique ?

                      Posté par Sebastien Binet () le 11/01/2005 à 14:38. (lien). Évalué à 2.

                      Heu "tableau de décodage incorrect" d'après Adobe Reader 6...
                      Ah ben j'ai point eu de probleme avec mon xpdf :)
                      Ca vient sans doute de la feuille de style un peu surchargee que j'ai utilisee avec LaTeX-Beamer....
                      
                      Le fait que les variables soient normalement distribuees n'est pas per se une contrainte qui vient des ML. Cela vient en fait de la maniere dont tu realises ton ajustement : dans mon cas l'ajustement se fait en minimisant un chi-2, ce qui est realise en annulant les derivees de ton equation de contrainte par rapport a chacune des dimensions de ton vecteur x ainsi que par rapport au(x) (differents) multiplicateur(s) de Lagrange.
                      Tu resouds ce systeme. Et voila (apres une tripotee d'inversion de matrices et autres joyeusetes consommatrices de memoire et de CPU).
                      
                      Mais pour que ton ajustement (par la methode des moindres carres) soit valide, il faut que tu te places dans le cas ou les erreures sont gaussiennes.
                      
                      Desole pour cette approximation/generalisation-abusive ...
                      
                      PS: J'ai retrouve la reference :
                      3rd CERN School of Physics (1964) CERN 64-13-V-1
                      "Kinematical analysis of bubble chamber pictures"
                      B. Ronne

        • [^]Re: Algorithme génétique ?

          Posté par TeXitoi (Jabber id, page perso, ) le 09/01/2005 à 20:50. (lien). Évalué à 4.

          
          C'est marrent mais j'ai jamais trop comprit quel application cela pouvait avoir par rapport aux autre heuristiques.
          

          
          
          ca se généralise assez bien, j'ai étudier un algo de fourmis qui gère le probleme du sac à dos (problème d'optimisation "remplir le mieu possible son sac à dos). En pratique, il est utilisé pour optimiser les noeuds des réseaux féroviers de la SNCF. Donc c'est plutôt utile en fait...
          
          Tout ces algos d'optimisations (métaheuristiques) sont assez facilement adaptable à un problème donné. L'algo génétique est le premier et donc le plus connu et appliqué à toutes les sauces, mais pas forcément le plus adapté.
          
          L'idée de l'algo de fourmis, c'est de lancer des chercheurs de solutions qui laissent une trace, les chercheurs suivant vont favoriser les chemins où la trace est la plus forte.

          • [^]Re: Algorithme génétique ?

            Posté par Bench () le 09/01/2005 à 23:02. (lien). Évalué à 5.

            Les algos de formis sont aussi utilisé pour les résaux téléphoniques mobile...quand certains relais sont engorgés, l'algo adapte en temps réels le chemins que prennent les données...car si les données mettent trop de temps à aller d'un point à un autre les phéromones s'amenuisent et les autres fourmies n'empreintent plus le chemin! En gros l'avantage de cet algo, c'est qu'il permet de recalculer les poids de chaque points du graphe en live...la solution s'adapte automatiquement à chaque nouvelle configuration!

            • [^]Re: Algorithme génétique ?

              Posté par Noj Han (Jabber id, page perso, ) le 10/01/2005 à 09:14. (lien). Évalué à 2.

              Je précise qu'on peut également les employer dans des cas comme celui qui nous occupe (problème d'optimisation à variables mixtes entières/réelles il me semble).
              
              Cependant, dans de tels problèmes, en adaptant un algo du type colonies de fourmis : soit on se rapproche d'un algo génétique (infâme cuisine de règles où on ne comprends pas ce qui se passe, mais adaptable à tout) soit d'un algorithme à estimation de distribution (plus simple, mais avec plus ou moins d'apriori sur le problème).

      • [^]Re: Algorithme génétique ?

        Posté par lasher () le 09/01/2005 à 18:19. (lien). Évalué à 4.

        Mmmh
        
        Ce que tu dis est surtout valable pour les réseaux de neurones (car la solution construite n'est pas forcément quelque chose que nous pouvons retracer, pauvres humains que nous sommes). Un algo génétique demande beaucoup de ressources pour être efficace, mais on peut quasiment toujours retracer le chemin de "pensée" suivi par l'algo.

        • [^]Re: Algorithme génétique ?

          Posté par pifou () le 09/01/2005 à 19:54. (lien). Évalué à 2.

          Je n'ai pas dit le contraire, effectivement on retrace assez facilement les résultats d'un algo génétique mais de là à comprendre le résultat il a un grouffre. Prennons l'exemple des paramètres du noyau Linux, tu auras beau avoir le cheminement de l'algo G qui donne une bonne solution, ça ne sera pas facile de comprendre pourquoi cette ensemble de valeurs marche bien. Bref, c'est assez empirique comme façon de faire, on arrive à un bon résultat sans être capable de l'expliquer facilement (afin par exemple de le reproduire dans un contexte un peu différent). Je me trompe peut être (surement), je n'ai pas regardé les algos G depuis plus d'un an et les méthodes d'analyses des résultats ont surement évoluées. En tout cas, c'était le ressentiment que j'avais eu à l'époque (qui vaut ce qu'il vaut).

    • [^]Re: Algorithme génétique ?

      Posté par Merlin () le 09/01/2005 à 19:33. (lien). Évalué à 4.

      NP complexe, Non Polynomiale Complexe

      
      
      Si je me souviens bien c'est plutot Non-deterministe Polynomial Complet
      
      Enfin, c'est juste une precision

      • [^]Re: Algorithme génétique ?

        Posté par TeXitoi (Jabber id, page perso, ) le 09/01/2005 à 20:37. (lien). Évalué à 3.

        C'est exactement ça.
        
        Pour expliquer en gros ce que ca veux dire:
        
        Non-deterministe Polynomial : on a un algo polynomial qui dit si une solution est bonne ou pas.
        
        Exemple sur le voyageur de commerce : si on lui donne un chemin, il est capable de dire en temps polynomial si cette solution est la meilleur solution (polynomial, ca peux etre affreux, mais pas exponentiel).
        
        Par contre, pour trouver LE meilleur chemin, il faudrait generer tout les chemins (en nombre exponentiel) et les tester.
        
        Le NP-complet veux en gros dire (c'est bien compliqué en fait...) qu'il n'existe pas d'algo polynomiaux resolvant le probleme (dans le cas général).

        • [^]Re: Algorithme génétique ?

          Posté par tuxyl () le 09/01/2005 à 22:47. (lien). Évalué à 4.

          Le NP-complet veux en gros dire (c'est bien compliqué en fait...) qu'il n'existe pas d'algo polynomiaux resolvant le probleme (dans le cas général).

          
          
          C'est faux ! Du moins c'est pas prouvé!
          Par contre si tu le prouves, t'es riche ;-)
          
          http://fr.wikipedia.org/wiki/NP-complet#Polyn.C3.B4mial_contre_non_(...)

        • [^]Re: Algorithme génétique ?

          Posté par Zakath (page perso, ) le 10/01/2005 à 00:11. (lien). Évalué à 5.

          Non, ce n'est pas encore ça.
          
          Résumons : on a NP, l'ensemble des problèmes dont on peut vérifier qu'une solution est la bonne en un temps polynomial. Par exemple pour le problème de la satisfiabilité des formules booléennes (on me donne une formule de la forme c_1 ET c_2 ET c_3 ET ... où c_i est de la forme x_j OU x_k OU ..., les x_j étant des variables booléennes), si on me donne une distribution des variables (on appelle ça un certificat), je suis capable de vérifier en un temps linéaire (donc polynomial) qu'elle met bien ma formule à Vrai.
          
          On a ensuite une sous classe de NP qui s'appelle P : l'ensemble des problèmes qu'on peut résoudre en temps polynomial (on peut donc à fortiori vérifier une solution en temps polynomial : P est bien inclus dans NP).Exemple : 2-SAT, le problème de la satisfiabilité en se limitant à deux variables par clause, mais aussi la plupart des algorithmes que nous rencontrons dans la vie de tous les jours.
          
          Enfin, une autre sous-classe de NP est l'ensemble des problèmes NP-complets : trouver un algorithme polynômial pour l'un d'entre eux revient à trouver un algorithme polynômial pour tous les problèmes de NP. Pour ça, un monsieur très fort a commencé par montrer de manière fort peu simple que le problème de la satisfiabilité était NP-complet puis on a des procédés qui permettent, étant donné un problème, de se ramener à SAT ou à l'un des autres problèmes NP-complet que l'on connait. On trouve toutes sortes de problèmes comme SAT, le voyageur de commerce, le bin-packing, pas mal de choses sur les graphes.
          Comme on n'a encore jamais trouvé d'algorithme polynômial pour un de ces problèmes (ce serait montrer P=NP), ils sont considérés comme difficile : soit on explore l'ensemble des solutions (exponentiel donc long), soit on utilise des algorithmes d'approximation s'il en existe, qui garantissent souvent une certaine borne de la solution optimale.
          
          
          Tout le défi P!=NP à l'heure actuelle est donc de réussir à montrer qu'il y a un problème de NP qui n'est pas dans P (ce que tout le monde croit). Et il y a effectivement 1000000$ à la clé (mais vu le cours du dollar en ce moment...)

          --
          Vous devriez vraiment visiter mon portfolio !

          • [^]Re: Algorithme génétique ?

            Posté par fmaz fmaz () le 10/01/2005 à 07:18. (lien). Évalué à 4.

            Puisque j'en suis à expliquer des trucs, continuons.
            
            Si on a deux problème A et un B et qu'on peut transformer A pour en faire un
            problème B rapidement -- par exemple en temps polynomial, alors le problème
            A est plus cimple que le problème B. En effet, si on sait résoudre B, alors on sait
            résoudre A: on prend A, on transforme en B, on résoud le problème B
            correspondant et on obtient la soluce. Pour ceux qui suivent, je donne un exemple
            après.
            
            De cette façon, on peut définir des hiérarchies de problèmes.
            Si on se donne des réductions polynomiales et que NP!=P, il existe des problèmes
            NP qui sont plus compliqué que n'importe quel problème P. Dans ce cas, la
            relation d'ordre obtenue n'est pas ridicule. On peut chercher les problèmes NP
            les plus difficiles. Or Steve Cook à montré en 71 que tous les problèmes NP étaient plus simple que SAT. On a donc une classe de problèmes NP qui sont
            les plus difficiles: les problèmes NP-complets. Et si on montre qu'un seul de ses
            problèmes est dans P, ben alors P=NP.
            
            
            Frédéric
            
            P.S. pour les plus courageux.
            
            SAT: une formule du type (a ou b ou non c ou d...) et (non a ou c...) et ...
            est-elle satisfiable?
            
            3-SAT: SAT dans lequel les (a ou b ou non ) comportent exactement 2 ou.
            
            Exemple de réduction: SAT est plus simple que 3-SAT.
            Si on a une clause (a ou b ou c ou d), on ajoute une variable e et on écrit:
            ( (a ou b)<=> e) et (e ou c ou d).
            
            Si on arrive à écrire (a ou b)<=>e sous la bonne forme, on a gagné.
            (a ou b)<=> e s'écrit (a ou b)=>e et e=>(a ou b).
            
            Or u=>v s'écrit (non u) ou v:
            e=>(a ou b) s'écrit donc ((non e) ou a ou b) (chouette, on y arrive).
            et
            (a ou b)=>e s'écrit:
            - (non (a ou b)) ou e;
            - donc ( (non a) et (non b)) ou e;
            - donc ((non a) ou e) et ((non b) ou e).
            
            La formule (a ou b ou c ou d) s'écrit donc
            (e ou c ou d) et ((non e) ou a ou b) et ((non a) ou e) et ((non b) ou e) qui est
            bien de la forme voulue.
            
            De plus on montre que la taille de la formule obtenue est polynomiale en la
            taille de la formule initiale.
            
            On a codé une formule SAT dans une formule 3-SAT et la première formule est
            satisfiable si et seulement si la seconde l'est.
            
            SAT est plus simple que 3-SAT donc 3-SAT est NP-complet.

        • [^]Re: Algorithme génétique ?

          Posté par fmaz fmaz () le 10/01/2005 à 06:34. (lien). Évalué à 7.

          Je vais me permettre de pousser une petite gueulante car la « vraie » définition
          de NP-complet n'est pas celle là (cf le lien wikipedia).
          
          Tout d'abord, il y a les machines de Turing déterministes.
          
          ---
          On a
          - un ruban sur laquelle il y a des caractères écrits (alphabet fini),
          - une tête de lecture à un endroit précis;
          - un automate fini.
          
          L'automate lit le caractère sous la tête de lecture et en fonction du résultat
          et de son état initial, il écrit quelque chose et se déplace à droite ou à gauche.
          La machine peut aussi s'arêter.
          
          Certaines machine permettent de répondre à des questions. On écrit sur le
          ruban la question et à la fin, la machine s'arête en écrivant oui ou non.
          ---
          
          
          Il y a aussi les machines non déterministes.
          ---
          À chaque la machine peut « se délocaliser » -- ce terme est de moi.
          C'est à dire qu'au lieu de passer dans l'état 18, d'écrire un r et d'aller à gauche,
          elle effectue plusieurs transition en même temps: elle est aussi passée dans
          l'état 34, a écrit un z et à déplacé la tête de lecture à droite.
          
          À l'étape d'après, toutes les « machines délocalisées » effectuent simultanément
          leur transition.
          
          Une telle machine répond oui si *une* des machines délocalisées répond oui
          et elle répond non si *toutes* les machines délocalisées répondent non.
          
          Ça, si c'est pas du massivement parallèle mon gars!
          ---
          
          Comme le temps nous intéresse, on définit des classes de complexité.
          
          La classe P est l'ensemble des problèmes tels qu'il existe une machine
          déterministe qui répond en temps polynomial.
          La classe NP est l'ensemble des problèmes tels qu'il existe une machine
          non-déterministe qui répond en temps polynomial.
          
          Le problème, c'est que manipuler une machine non déterministe, c'est un brin
          chiant. Heureusement, il un théorème qui dit qu'un problème est NP s'il existe
          une machine déterministe avec oracle polynomial qui vérifie la solution en temps
          polynomial. En gros, on donne la solution à la machine et elle vérifie que c'est
          bien une solution.
          
          Les gens ont tendance à préférer cette seconde version mais elle n'est pas
          toujours adaptée comme pour le voyageur de commerce. Si la question
          est:« l'optimal est-il de longueur inférieur à k », il est très facile de faire une
          machine non déterministe. À chaque étape, elle prend tous les chemins
          possibles simultanément. Si une des machines trouve un chemin mieux que k,
          elle dit oui et si son chemin est plus grand que k, elle dit non.
          
          Un exemple de problème qui se traite vraiment bien avec la seconde méthode,
          c'est le problème SAT (http://fr.wikipedia.org/wiki/Probl%C3%A8me_SAT(...)).
          Si une formule SAT est satisfiable, il existe une assignation des variables qui
          la rend vraie. Si on se donne cette assignation, il est alors trivial de vérifier que
          la formule est effectivement satisfiable.
          
          wala wala wala
          
          Frédéric

          • [^]Re: Algorithme génétique ?

            Posté par TeXitoi (Jabber id, page perso, ) le 10/01/2005 à 12:11. (lien). Évalué à 2.

            Bon, déjà, désolé pour la boulette.
            
            Au passage, tu n'as pas expliqué le point sur lequelle j'ai fait une boulette : la completude ;-) (le reste etant bon et etant en gros ce que tu dis, en moins expliqué, en tout cas)
            
            Ensuite, L'explication pas les machines de turing est une explication, et pas forcément l'unique solution pour expliquer le probleme.
            
            

            Le problème, c'est que manipuler une machine non déterministe, c'est un brin
            chiant. Heureusement, il un théorème qui dit qu'un problème est NP s'il existe
            une machine déterministe avec oracle polynomial qui vérifie la solution en temps
            polynomial. En gros, on donne la solution à la machine et elle vérifie que c'est
            bien une solution.

            
            
            Un problème NP est un probleme "Non-déterministe Polynomial", c'est a dire qu'il existe une machine de turing non déterministe qui résoud le problème (d'apres ta propre définition). Or, une "machine de turing non déterministe" est équivalent à "une machine déterministe polynomial avec oracle" et pas "une machine déterministe avec oracle polynomial" (c'est la machine déterministe qui est polynomial, pas l'oracle). Je pense que c'est ce que tu voulais dire mais que tu t'es mal exprimé.
            
            Pour finir, il existe en théorie des machines de turing non déterministe. Elles sont basé sur "l'ordinateur à ADN", c'est a dire qu'on modelise le probleme sous forme ADN, on met tout dans une grosse bassine et on recupere le résultat (en temps polynomial). Le problème, c'est que si c'est en temps polynomial, ca semble etre en espace exponentiel, ce qui arrange pas vraiment le probleme (et gerer des tonnes d'ADN, c'est pas vraiment réaliste...).

• [^]Re: Algorithme génétique ?

  Posté par Sebastien Binet () le 09/01/2005 à 14:09. (lien). Évalué à 6.

  Ma réponse rapide : viendez voir les liens donnés ! (Surtout celui vers Wikipedia!)
  
  Et pour ceux qui en veulent toujours plus, il y avait fin septembre une conference qui en parlait [1,2].
  Et puis pour encore approfondir [3] (avec d'autres methodes d'optimisation).
  
  Pour resumer, en physique des particules on s'en sert essentiellement pour optimiser un jeu de coupures pour extraire avec la plus grande purete ainsi que la plus grande efficacite, le signal par rapport au bruit de fond qui nous em..., qui nous embete.
  
  [1] : http://indico.cern.ch/contributionDisplay.py?contribId=49&sessi(...)
  [2] : http://chep2004.web.cern.ch/chep2004(...)
  [3] : http://www.slac.stanford.edu/econf/C030908/proceedings.html(...)
  
  Voila.
  Bonne lecture ;)

  • [^]Re: Algorithme génétique ?

    Posté par Noj Han (Jabber id, page perso, ) le 09/01/2005 à 15:28. (lien). Évalué à 4.

    J'en profite pour ajouter que les algorithmes génétiques ne sont qu'une des manières de résoudre ce genre de problèmes.
    
    Les algorithmes génétiques sont en effet une classe d'un ensemble plus large, qu'on a coutume d'appeler les "métaheuristiques". Or, bien qu'ils soient les plus connus, ce ne sont pas forcément les plus facile à concevoir ni à manipuler !
    
    Au delà de l'effet "c'est beau la nature, hein, quand même", n'hésitez pas à creuser un peu plus loin et à découvrir toutes les méthodes qui tournent dans ce domaine, il y en beaucoup... Cela va du recuit simulé aux algorithmes de colonies de fourmis (très "marketing" aussi), en passant par les "essaims particulaires"... bref, de quoi satisfaire n'importe quel adepte de "l'intelligence artificielle" facilement.
    
    À titre personnel, je vous conseille les algorithmes à estimation de distribution, qui sont en quelque sorte une généralisation des algorithmes génétiques, et qui sont plus facile à manipuler.
    
    Voilà voilà.

    • [^]Re: Algorithme génétique ?

      Posté par Sebastien Binet () le 09/01/2005 à 15:38. (lien). Évalué à 3.

      je vous conseille les algorithmes à estimation de distribution
      
      Un peu dans le genre de ceci ?
      http://www.slac.stanford.edu/econf/C030908/papers/TUHT002.pdf(...)
      
      (Je demande, hein, je suis loin d'etre un expert et meme si je (re)commence une petite biblio sur le sujet, la plupart du temps je les utilise essentiellement comme boite noire, honte a moi).

      • [^]Re: Algorithme génétique ?

        Posté par Noj Han (Jabber id, page perso, ) le 10/01/2005 à 09:04. (lien). Évalué à 3.

        Tout à fait, plus d'infos ici :
        http://www.springeronline.com/sgw/cda/frontpage/0,11855,5-40356-72-(...)
        http://portal.acm.org/citation.cfm?id=585661(...)

      • [^]Re: Algorithme génétique ?

        Posté par oliv () le 10/01/2005 à 10:51. (lien). Évalué à 3.

        Pour la biblio, concernant le recuit simulé, les articles de Lester Ingber sont plutôt pas mal. En plus, son code est disponible.
        http://www.ingber.com/(...) (pas les fichiers "karate" mais les fichiers "ASA" ;) )

qualité de l'article sur wikipedia

.

• [^]Re: .

  Posté par Sebastien Binet () le 09/01/2005 à 15:09. (lien). Évalué à 0.

  Hurd 2.0
  
  Haha...
  Blague a part, je pense que justement, Hurd/L4Ka (ou Fiasco [1]) pourrait avantageusement tirer parti de ces algorithmes G, de part la maniere dont c'est "architecturé" (cf le(s) post(s) de Manuel [2])
  
  Mais je parle (un peu?) sans trop savoir, en fait.
  
  [1] : Fiasco : http://os.inf.tu-dresden.de/fiasco/overview.html(...)
  [2] : Hurd : https://linuxfr.org/comments/517501.html#517501(...)

Qu'en pense José ?

• [+] [^]Re: Qu'en pense José ?

  Posté par Mickaël Sibelle (Jabber id, page perso, ) le 09/01/2005 à 16:50. (lien). Évalué à -1.

  Mais non, c'est génial la technogie !
  
  T'y connais rien parce que t'es un vieilounet \o/
  Allez viens, je vais t'expliquer... avec une bonne Guiness !

  • [+] [^]Re: Qu'en pense José ?

    Posté par Ellendhel (page perso, ) le 09/01/2005 à 22:29. (lien). Évalué à -2.

    Guinness on dit.
    
    Et elle n'a pas intérêt à être génétiquement modifiée...
    
    Je suis hors sujet --> [ ]

• [^]Re: Qu'en pense José ?

  Posté par gc (page perso, ) le 10/01/2005 à 13:52. (lien). Évalué à 7.

  Même sous couvert de blague, c'est dommage d'alimenter cette méprise. Les (enfin la plus grande frange des) anti-OGM français ne disent pas qu'ils sont contre l'ingénierie génétique, ils disent qu'il est irresponsable de cultiver des champs d'OGM dans l'état actuel de nos connaissances sur le sujet.
  
  Pour prendre une illustration simple : il y a quelques années, tous les scientifiques qui travaillaient sur les OGM prétendaient que la "barrière des espèces" étant une sorte de mur infranchissable, on pouvait cultiver un champ d'OGM et en laissant quelques mètres de sécurité sur les bords, il n'y avait aucun risque de dissémination. Aujourd'hui, après avoir constaté de la dissémination à plusieurs centaines de mètres entre des espèces pourtant éloignées génétiquement, leur position a évolué.
  
  Les "anti-OGM" (dont je fais partie, bas les masques) disent seulement "faites toutes les expérimentations que vous voulez en laboratoire, en serre, mais pas en plein champ car c'est encore du domaine de la bidouille".
  
  Pour prendre un autre exemple particulièrement intéressant et quasiment inconnu, en génétique on croit depuis Crick & Watson que la plupart des gènes, l'expérience montrant qu'ils sont non-codants (la séquence de bases ne produit pas une protéine), sont donc inutiles (violant par là-même un principe universel de la nature, à savoir que rien dans le vivant n'est inutile, mais passons). On se sert de cela lorsqu'on veut ajouter un gène à un organisme : on l'insère à un endroit non-codant. Malheureusement, on vient de faire une découverte fondamentale il y a quelques années : on a constaté expérimentalement qu'après manipulation génétique, l'expression d'un gène pourtant situé loin de l'endroit de la manipulation (peut-être même dans un autre chromosome, mais ma mémoire défaille) était altérée ; c'était la première preuve de l'utilité du non-codant, et une remise en question totale de toutes les manipulations génétiques effectuées depuis la découverte de l'ADN. Le non-codant contrôle l'expression des gènes ; mais bien sûr, on n'a pas la première idée sur comment ça marche.
  
  Et j'ajouterai pour conclure que tous les organismes manipulés génétiquement se sont révélés extrêmement fragiles. Bien sûr, on n'a pas le début d'une explication non plus.
  
  Alors avec tout ça, planter à tout va en plein champ, moi ça ne me semble pas raisonnable.

nombre d'or

• [^]Re: nombre d'or

  Posté par Antoine () le 09/01/2005 à 20:58. (lien). Évalué à 6.

  La solution est d'effectuer la recherche d'optimum "en usine", c'est-à-dire avant la sortie du noyau, et de figer ensuite les résultats dans la version distribuée. C'est exactement ce que fait Spamassassin pour les coefficients des règles de détection (je crois qu'ils sont récemment passés d'un algorithme générique à un réseau de neurones, par contre).

  • [^]Re: nombre d'or

    Posté par Nicolas Boulay () le 10/01/2005 à 12:43. (lien). Évalué à 3.

    spamassassin utilise un réseau baysien qui se base sur des proba conditionnel rien à voirdonc.

    --
    "Plus un État censure, moins il est démocratique. Mais parce qu’on vous ment sur internet, on va le censurer pour ceux qui télechargent."

    • [^]Re: nombre d'or

      Posté par tene (page perso, ) le 10/01/2005 à 14:25. (lien). Évalué à 1.

      Rien à voir avec quoi? avec un réseau de neurones?... un filtre bayesian peut pourtant être vu comme un réseau de neurones...

    • [^]Re: nombre d'or

      Posté par Tony Flow () le 11/01/2005 à 01:21. (lien). Évalué à 3.

      non je crois qu'il a raison !
      spamassassin utilise un ensemble de règles, chacune apportant une note, afin d'obtenir un score final déteminant le degré de spam d'un message.
      
      les filtres bayésiens ne sont que des règles parmis les autres...
      et il est bien question de faire tourner un algo afin de calculer au mieux le poids de chacunes des règles en fonction de leur pertinence.

• [^]Re: nombre d'or

  Posté par jigso () le 09/01/2005 à 21:00. (lien). Évalué à 1.

  Pas forcément, la solution interressante peut-être dupliquée pour optimiser directement la version "de base" du noyau.

• [^]Re: nombre d'or

  Posté par Beretta_Vexee (Jabber id, ) le 09/01/2005 à 21:32. (lien). Évalué à 2.

  Après se constat, ils pensent depuis ce temps à utiliser des algo d'AI pour optimiser tout ça (génétique, neurone, recuit simulé, ...). Le problème de genre d'algo est leur stabilité et la non connaissance du temps pour arrivé à un optimum acceptable.

  
  
  Ce n'est pas leur stabilité mais leur maîtrise qui pause problème, il y a des librairies toutes faites et des algo stable qui existe déjà, mais leurs utilisation demande énormément de réglage et de « tuning », ce n'est pas un remède miracle. Mais leurs gros problème c'est qu'ils ne sont pas déterministe, on ne connaît pas leurs temps de réponse, ni la réponse car celle-ci dépend de valeurs aléatoire. Donc ils n'est pas impossible que dans certaine conditions l'algo sorte un résultat complètement faux, c'est peut probable mais possible donc niveau fiabilité des perfromance ce n'est pas acceptable.
  
  

  En gros, si vous gagnez 20% de perf mais avant vous vous tapez -30% de perf pendant 1 mois, c'est peu interrescant. Vous craquerez avant.

  
  
  Le problème serait plus est tu prêt a prendre le risque que ton Kernel devienne extrêmement lent ou ais des performance qui fasse le yoyo ? En plus cela doit être un vrais cauchemar a debuger un trucs pareil.

  --
  Il relève de la responsabilité du lecteur de contrôler, par tous moyens, l'adéquation du message à ses besoins et de s'assurer qu'il ne causera pas de dommages aux personnes et aux biens.

  • [^]Re: nombre d'or

    Posté par THE_ALF_ () le 10/01/2005 à 01:28. (lien). Évalué à 3.

    
    Ce n'est pas leur stabilité mais leur maîtrise qui pause problème, il y a des librairies toutes faites et des algo stable qui existe déjà, mais leurs utilisation demande énormément de réglage et de « tuning »
    

    
    
    Ben, il suffit d'effectuer et optimiser ces réglages par algo génétiques alors, ça a l'air bien adapté du coup :-p

    --
    L'univers de propensions qui est le notre est intrinsèquement créatif (K. Popper).

Possible à mettre en place sur une machine perso ?

• [^]Re: Possible à mettre en place sur une machine perso ?

  Posté par pasBill pasGates () le 10/01/2005 à 08:03. (lien). Évalué à 3.

  Si tu l'installes sur ta machine, tu ne verras rien.
  
  Comme dit dans l'article, ca donne 1 a 3% de perfs supplementaires pour l'instant, bref c'est quasiment indetectable.
  
  Le seul type de presentation que tu pourrais faire la dessus(vu qu'il n'y a pas grand chose a montrer, pas possible de faire un "avant/apres" avec 3% de difference) serait de parler de la theorie derriere et de l'implementation, et si tu ne comprends rien a ce qui se dit plus haut, ben c'est pas d'ici au 31 que t'auras le temps de rattraper ton retard pour pouvoir faire ca.

• [^]Re: Possible à mettre en place sur une machine perso ?

  Posté par Marc (Jabber id, page perso, ) le 10/01/2005 à 12:38. (lien). Évalué à 4.

  l'avantage des panneaux solaires c'est que tu trouvera presque des TIPE cles en main, il me semble pas que ca soit super original =)
  M'enfin, bon courage quand meme

algo génétique

• [^]Re: algo génétique

  Posté par Noj Han (Jabber id, page perso, ) le 10/01/2005 à 12:29. (lien). Évalué à 3.

  Les métaheuristiques apportent au moins indéniablement une chose : elles sont simple à mettre en place... (je suis curieux de voir la méthode du gradient sur un problème NP-complet avec minima locaux non dérivable en variables réelles d'ailleurs).
  
  Rappelons que le mieux est l'ennemi du bien :)

  • [^]Re: algo génétique

    Posté par Sebastien Binet () le 10/01/2005 à 12:39. (lien). Évalué à 2.

    Je ne sais pas si on peut vraiment dire qu'elles soient si simples a mettre en place...
    Je dois bien avouer que je ne me suis pas encore attele a mettre en place le moindre algo genetique, mais j'ai commence a regarder pour les reseaux de neurones...
    Et c'est quand meme loin d'etre trivial (meme s'il existe un nombre impressionnant de bibliotheques disponible qui implementent le bouzin assez automagiquement).
    
    En plus, le biais systematique que tu introduis avec ces methodes n'est pas forcement connu a priori (enfin tu ne peux que l'estimer a posteriori).
    Donc l'interpretation du resultat est plus ardue, meme si tu peux etre relativement confiant dans le caractere optimal de ce resultat.
    
    Par contre il me semble en effet que les techniques metaheuristiques sont moins sensibles au probleme des extrema locaux.

    • [^]Re: algo génétique

      Posté par tene (page perso, ) le 10/01/2005 à 14:30. (lien). Évalué à 2.

      " Je ne sais pas si on peut vraiment dire qu'elles soient si simples a mettre en place..."
      
      Ca dépend ce qu'on appelle "mettre en place" :p
      
      En gros, c'est comme toujours, tu vas passer plein de temps à formatter les entrées/sorties pour que ça fonctionne bien, et finalement assez peu de temps à coder l'algo en lui même (vu que c'est très souvent des opérations mathématique/logique simple répétées un grand nombre de fois).
      
      Par contre ça deviendra plus coton si t 'intéresses au perf en temps et surtout en place...
      
      On a n'a pas fini de s'amuser quoi...

• [^]Re: algo génétique

  Posté par oliv () le 10/01/2005 à 14:37. (lien). Évalué à 5.

  > Les algorithmes génétiques sont surtout du succes aupres des gens
  > qui pensent que copier la nature aboutira forcément à une réussite,
  > puisque la nature est tellement belle
  
  Quand je me regarde, et quand je regarde Bush, je me dis que si c'est le résultat d'une optimisation de centaines de millions d'années, les algorithmes génétiques, c'est pas encore au point.
  
  (Bon, quand je regarde Emma de Caunes, Cécile de France, ou Nicole Kidman, je pense le contraire :) )

• [^]Re: algo génétique

  Posté par lasher () le 10/01/2005 à 18:42. (lien). Évalué à 3.

  Je peux te donner au moins un type d'exemple où les algos génétiques sont plutôt cools à utiliser : les voitures (si, si...). En fait je fais implicitement de la pub pour mon prof de logique floue, mais globalement, tu as tout plein de problèmes (du genre, "j'ai tout un tas d'équations à 400 variables à résoudre"), et si tu essaies de trouver une solution par des voies numériques, tu vas y passer un certain temps. La solution, c'est de passer par les algos génétiques (pour le côté apprentissage), auxquels on adjoint des outils de logique floue (le cas des 400 variables, c'était pour une boite qui voulait pouvoir trouver des formules chimiques pour leur produit à partir de 400 molécules différentes).
  
  Tu as aussi des applications en embarqué, pour les voitures - du genre un système de vérouillage sur la voiture devant, avec la voiture qui suit bien gentiment celle devant niveau vitesse, et qui en sus garde ses distances comme il faut, ou bien le créneau effectué automatiquement, etc.
  
  Bref, ce "pas grand chose" prend une certaine valeur lorsque tu es chargé de traiter des problèmes "mal foutus", et dont la solution est non- linéaire.

Jake Moilanen...