Ce patch propose de modifier dynamiquement les paramètres de différents éléments du noyau en fonction des performances mesurées de celui-ci. L'originalité vient du fait que les nouveaux paramètres sont obtenus grâce à un algorithme génétique, qui doit permettre, théoriquement, d'arriver aux paramètres optimaux.
À l'heure actuelle, Jake a modifié l'ordonnanceur de processus et l'ordonnanceur d'entrées/sorties pour qu'ils utilisent ce mécanisme. Il annonce des gains de performance de l'ordre de 1 à 3% avec des benchmarks classiques, mais suppose qu'un expert des ordonnanceurs pourra faire mieux.
Au delà de l'aspect "performance" pure, c'est également le défi technique relevé par ce patch qui est particulièrement intéressant !
Aller plus loin
- Annonce sur KernelTrap (8 clics)
- Annonce sur la LKML (5 clics)
- Algorithme génétique (37 clics)
# L'idée..
Posté par ploum (site web personnel, Mastodon) . Évalué à 10.
Mais 1-3%, même si on arrive à 5%, pour Mr tout le monde sur son Pentium 2GHz, il ne verra pas franchement de différence..
Et puis, est-ce que ça entraîne des quelconques défauts qqparts ? Comme une possible légère perte de performances lors d'un changement d'utilisation ou qqch du genre ?
Mes livres CC By-SA : https://ploum.net/livres.html
[^] # Re: L'idée..
Posté par Mickaël Sibelle (site web personnel) . Évalué à 6.
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 . Évalué à 6.
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 . Évalué à 7.
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 . Évalué à 10.
Ou alors, DNA/Linux "Genetic patents inside" :P
[^] # Re: L'idée..
Posté par XHTML/CSS inside (site web personnel) . Évalué à 0.
Merde, c'est déjà pris : TIGER...
J'y file ======>[]
[^] # Re: L'idée..
Posté par Antoine J. . Évalué à 10.
# Algorithme génétique ?
Posté par Xavier Teyssier (site web personnel) . Évalué à 1.
[^] # Re: Algorithme génétique ?
Posté par Julien Duponchelle (site web personnel) . Évalué à 4.
[^] # Re: Algorithme génétique ?
Posté par Mickaël Sibelle (site web personnel) . Évalué à 5.
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 (Mastodon) . Évalué à 2.
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 . Évalué à 2.
[^] # Re: Algorithme génétique ?
Posté par Black Fox . Évalué à 3.
[^] # Re: Algorithme génétique ?
Posté par Sylvain Sauvage . Évalué à 2.
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 . Évalué à 6.
[^] # Re: Algorithme génétique ?
Posté par liberforce (site web personnel) . Évalué à 8.
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 . Évalué à 8.
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 . Évalué à 10.
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.
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.
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.
[^] # Re: Algorithme génétique ?
Posté par pifou . Évalué à 5.
[^] # Re: Algorithme génétique ?
Posté par Beretta_Vexee . Évalué à 2.
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.
[^] # Re: Algorithme génétique ?
Posté par Sebastien . Évalué à 2.
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 . Évalué à 2.
[^] # Re: Algorithme génétique ?
Posté par Besnard Jerome . Évalué à 7.
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 . Évalué à 7.
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 . Évalué à 3.
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 . Évalué à 2.
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 . Évalué à 3.
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 . Évalué à 1.
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 . Évalué à 2.
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 (site web personnel) . Évalué à 4.
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 ecyrbe . Évalué à 5.
[^] # Re: Algorithme génétique ?
Posté par nojhan (site web personnel, Mastodon) . Évalué à 2.
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 . Évalué à 4.
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 . Évalué à 2.
[^] # Re: Algorithme génétique ?
Posté par Merlin (site web personnel) . Évalué à 4.
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 (site web personnel) . Évalué à 3.
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 . Évalué à 4.
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 (site web personnel) . Évalué à 5.
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...)
[^] # Re: Algorithme génétique ?
Posté par fmaz fmaz . Évalué à 4.
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 . Évalué à 7.
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 (site web personnel) . Évalué à 2.
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.
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 . Évalué à 6.
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 nojhan (site web personnel, Mastodon) . Évalué à 4.
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 . Évalué à 3.
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 nojhan (site web personnel, Mastodon) . Évalué à 3.
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 . Évalué à 3.
http://www.ingber.com/(...) (pas les fichiers "karate" mais les fichiers "ASA" ;) )
# qualité de l'article sur wikipedia
Posté par Ludovic Gasc . Évalué à 10.
Ça fait plaisir de voir que wikipedia devienne une référence utilisable depuis un moment, dans le sens où on a de bonnes chances de trouver un article bien fait pour pouvoir se cultiver ou qui peut servir comme base pour un exposé.
Parlez de wikipedia autour de vous, ma petite soeur s'en sert souvent pour ses exposés ou questions qu'elle se pose.
# .
Posté par MsK` . Évalué à 0.
[^] # Re: .
Posté par Sebastien . Évalué à 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é ?
Posté par domi . Évalué à 8.
Ah non, halte aux OGM, qui tentent maintenant de s'infiltrer même dans notre beau et pur monde GNU/libre !
[^] # Re: Qu'en pense José ?
Posté par Mickaël Sibelle (site web personnel) . Évalué à -1.
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 (site web personnel) . Évalué à -2.
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 (site web personnel) . Évalué à 7.
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
Posté par Nicolas Boulay (site web personnel) . Évalué à 7.
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.
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.
"La première sécurité est la liberté"
[^] # Re: nombre d'or
Posté par Antoine . Évalué à 6.
[^] # Re: nombre d'or
Posté par Nicolas Boulay (site web personnel) . Évalué à 3.
"La première sécurité est la liberté"
[^] # Re: nombre d'or
Posté par tene . Évalué à 1.
[^] # Re: nombre d'or
Posté par Tony Flow . Évalué à 3.
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 . Évalué à 1.
[^] # Re: nombre d'or
Posté par Beretta_Vexee . Évalué à 2.
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.
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.
[^] # Re: nombre d'or
Posté par THE_ALF_ . Évalué à 3.
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
# Possible à mettre en place sur une machine perso ?
Posté par Sufflope (site web personnel) . Évalué à 2.
J'aimerais savoir si c'est immédiatement utilisable (pas forcément utile ni efficace) par un païen de mon espèce qui n'a ni les connaissances en algorithmique des auteurs de certains commentaires ardus plus haut, ni de grandes compétences en programmation ou quoi que ce soit...
Je m'explique.
Je ne veux absolument pas faire le geek en soirée parce que j'ai un noyau qui utilise un "algo G" :D
Je suis en 2ème année de classe prépa, et pour ceux qui connaissent, je dois donc présenter un TIPE aux concours. Pour les autres : Travaux d'Initiative Personnelle Encadrés. Autrement dit : préparer un dossier et un exposé oral sur un sujet précis, en apportant une touche personnelle, comme une rencontre avc un professionnel, une expérience menée soi-même ...
Et ceci me paraît un sujet parfaitement utilisable, et bien plus passionnant à mon goût que celui que j'ai pris :)
Il serait même limite mieux que l'actuel qui me passionne bien moins (et qui n'a rien à voir) : ça cause de panneaux solaires...
- il m'intéresse plus donc je serais plus motivé
- a moins de construire un panneau solaire moi-même, un truc accessible comme une visite de labo aura moins de gueule que de dire "bah vous voyez, j'ai utilisé ça sur mn PC à moi dans ma piaule pendant 6 mois, et je peux vous dire que... etc"
Sauf que je dois me dépêcher de me décider si je change ... C'est même tres coton, les sujets devaient être fixés avant les dernières vacances, les inscriptions aux concours se font samedi prochain au plus tard, et je dois présenter un début de TIPE a mes profs le 31 !!!
Donc j'aimerais vos conseils avisés ... :)
[^] # Re: Possible à mettre en place sur une machine perso ?
Posté par pasBill pasGates . Évalué à 3.
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 (site web personnel) . Évalué à 4.
M'enfin, bon courage quand meme
# algo génétique
Posté par celastus . Évalué à 4.
En fait, ce sont des programmes dit heuristiques, c'est à dire qu'ils étudient beaucoup de solutions au problemes, et gardent la meilleure qu'ils ont trouvée. Les différence entre les algorithmes heuristiques sont surtout issues de la façon de generer les soutions étudiées.
Dans un algorithme génétiques, on a plein de solutions, on en prends deux et on en fait une troisieme, qui hérite du "patrimoine génétique" des deux précédentes... et on ne garde que les meilleures, à la darwin.
Comme il l'a été dit plus haut, les heuristiques sont nécéssaires pour trouver des solutions à peu pres correctes aux problemes NP-complets, pour lesquels il n'est pas possible de trouver la solution optimale en un temps raisonnable.
Maintenant l'algorithme génétique n'apporte pas grand chose aux autres méthodes plus "traditionnelles" et généralement issues de la programmation mathématique ou de l'intelligence artificielle orienté mathématique, comme les algorithmes min-max, la méthode du gradient...
[^] # Re: algo génétique
Posté par nojhan (site web personnel, Mastodon) . Évalué à 3.
Rappelons que le mieux est l'ennemi du bien :)
[^] # Re: algo génétique
Posté par Sebastien . Évalué à 2.
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 . Évalué à 2.
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 . Évalué à 5.
> 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 . Évalué à 3.
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...
Posté par Matafan . Évalué à 6.
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.