Quels sont les bons exemples d'algorithmes génétiques / solutions de programmation génétique? [fermé]

Les algorithmes génétiques (GA) et la programmation génétique (GP) sont des domaines de recherche intéressants.

J'aimerais connaître les problèmes spécifiques que vous avez résolus en utilisant GA / GP et les bibliothèques / frameworks que vous avez utilisés si vous n'avez pas lancé les vôtres.

Des questions:

• Quels problèmes avez-vous utilisé GA / GP pour résoudre?
• Quelles bibliothèques / frameworks avez-vous utilisés?

Je recherche des expériences de première main, alors ne répondez pas à moins que vous n'ayez cela.

Pas de devoirs.

Mon premier emploi en tant que programmeur professionnel (1995) a été l'écriture d'un système de trading automatisé basé sur un algorithme génétique pour les futures S & P500. L'application a été écrite en Visual Basic 3 [!] Et je n'ai aucune idée de comment j'ai fait quoi que ce soit à l'époque, car VB3 n'avait même pas de classes.

L'application a commencé avec une population de chaînes de longueur fixe générées aléatoirement (la partie "gène"), chacune correspondant à une forme spécifique dans les données de prix minute par minute des contrats à terme S & P500, ainsi qu'à un ordre spécifique (acheter ou vendre) et stop-loss et stop-profit. La performance de chaque chaîne (ou "gène") a été évaluée par une analyse de 3 ans de données historiques; chaque fois que la "forme" spécifiée correspondait aux données historiques, j'ai supposé l'ordre d'achat ou de vente correspondant et évalué le résultat de la transaction. J'ai ajouté la mise en garde que chaque gène a commencé avec un montant fixe et pourrait donc potentiellement faire faillite et être retiré du pool génétique entièrement.

Après chaque évaluation d'une population, les survivants ont été croisés de manière aléatoire (en mélangeant simplement des morceaux de deux parents), la probabilité qu'un gène étant sélectionné comme parent étant proportionnelle au profit qu'il produisait. J'ai également ajouté la possibilité de mutations ponctuelles pour pimenter un peu les choses. Après quelques centaines de générations de cela, je me suis retrouvé avec une population de gènes qui pourrait transformer 5000 $ en une moyenne d'environ 10000 $ sans risque de mort / cassure (sur les données historiques, bien sûr).

Malheureusement, je n'ai jamais eu la chance d'utiliser ce système en direct, car mon patron a perdu près de 100 000 $ en moins de 3 mois de trading de manière traditionnelle, et il a perdu sa volonté de poursuivre le projet. Rétrospectivement, je pense que le système aurait fait d'énormes profits - non pas parce que je faisais nécessairement quelque chose de bien, mais parce que la population de gènes que je produisais était biaisée vers les ordres d'achat (par opposition aux ordres de vente) d'environ 5: 1 ratio. Et comme nous le savons avec notre recul 20/20, le marché a augmenté un peu après 1995.

J'ai fait un peu de bestioles qui vivaient dans ce petit monde. Ils avaient un cerveau de réseau neuronal qui recevait certaines entrées du monde et la sortie était un vecteur de mouvement parmi d'autres actions. Leurs cerveaux étaient les "gènes".

Le programme a commencé avec une population aléatoire de bestioles au cerveau aléatoire. Les neurones d'entrée et de sortie étaient statiques mais ce qui était entre les deux ne l'était pas.

L'environnement contenait de la nourriture et des dangers. La nourriture augmente l'énergie et lorsque vous avez suffisamment d'énergie, vous pouvez vous accoupler. Les dangers réduiraient l'énergie et si l'énergie était nulle, ils mourraient.

Finalement, les créatures ont évolué pour se déplacer dans le monde et trouver de la nourriture et éviter les dangers.

J'ai alors décidé de faire une petite expérience. J'ai donné au cerveau de la créature un neurone de sortie appelé "bouche" et un neurone d'entrée appelé "oreille". Recommencé et a été surpris de constater qu'ils ont évolué pour maximiser l'espace et chaque créature respective resterait dans sa partie respective (la nourriture était placée au hasard). Ils ont appris à coopérer les uns avec les autres et à ne pas se gêner. Il y avait toujours des exceptions.

Ensuite, j'ai essayé quelque chose d'intéressant. Moi, les créatures mortes deviendraient de la nourriture. Essayez de deviner ce qui s'est passé! Deux types de créatures ont évolué, ceux qui attaquaient comme des essaims et ceux qui étaient très évitants.

Alors quelle est la leçon ici? La communication signifie la coopération. Dès que vous introduisez un élément où blesser un autre signifie que vous gagnez quelque chose, la coopération est détruite.

Je me demande comment cela se reflète sur le système des marchés libres et du capitalisme. Je veux dire, si les entreprises peuvent nuire à leur concurrence et s'en tirer , il est clair qu'elles feront tout ce qui est en leur pouvoir pour nuire à la concurrence.

Éditer:

Je l'ai écrit en C ++ sans utiliser de frameworks. A écrit mon propre réseau neuronal et mon code GA. Eric, merci d'avoir dit que c'était plausible. Les gens ne croient généralement pas aux pouvoirs de GA (bien que les limites soient évidentes) jusqu'à ce qu'ils jouent avec. GA est simple mais pas simpliste.

Pour les sceptiques, les réseaux de neurones se sont avérés capables de simuler n'importe quelle fonction s'ils ont plus d'une couche. GA est un moyen assez simple de naviguer dans un espace de solution pour trouver un minimum local et potentiellement global. Combinez GA avec des réseaux neuronaux et vous avez un très bon moyen de trouver des fonctions qui trouvent des solutions approximatives à des problèmes génériques. Parce que nous utilisons des réseaux neuronaux, nous optimisons la fonction pour certaines entrées, pas certaines entrées d'une fonction, car d'autres utilisent GA

Voici le code de démonstration de l'exemple de survie: http://www.mempko.com/darcs/neural/demos/eaters/ Instructions de construction:

• Installer darcs, libboost, liballegro, gcc, cmake, make
• darcs clone --lazy http://www.mempko.com/darcs/neural/
• cd neural
• cmake .
• make
• cd demos/eaters
• ./eaters

En janvier 2004, j'ai été contacté par Philips New Display Technologies qui créait l'électronique pour la toute première encre électronique commerciale, la Sony Librie, qui n'était sortie qu'au Japon, des années avant qu'Amazon Kindle et les autres arrivent sur le marché américain. une Europe.

Les ingénieurs Philips ont eu un problème majeur. Quelques mois avant que le produit ne soit censé arriver sur le marché, ils se faisaient toujours fantômes à l'écran lors du changement de page. Le problème était les 200 pilotes qui créaient le champ électrostatique. Chacun de ces pilotes avait une certaine tension qui devait être réglée correctement entre zéro et 1000 mV ou quelque chose comme ça. Mais si vous en changiez un, cela changerait tout.

Il n'était donc pas question d'optimiser la tension de chaque conducteur individuellement. Le nombre de combinaisons possibles de valeurs était en milliards, et il a fallu environ 1 minute à une caméra spéciale pour évaluer une seule combinaison. Les ingénieurs ont essayé de nombreuses techniques d'optimisation standard, mais rien ne s'en rapproche.

L'ingénieur en chef m'a contacté parce que j'avais précédemment publié une bibliothèque de programmation génétique pour la communauté open-source. Il a demandé si les GP / GA aideraient et si je pouvais m'impliquer. Je l'ai fait, et pendant environ un mois, nous avons travaillé ensemble, moi à écrire et à régler la bibliothèque GA, sur des données synthétiques, et lui à l'intégrer dans leur système. Puis, un week-end, ils l'ont laissé vivre avec la vraie chose.

Le lundi suivant, j'ai reçu ces courriels courriels de sa part et de leur concepteur de matériel, sur la façon dont personne ne pouvait croire les résultats incroyables trouvés par l'AG. C'était ça. Plus tard cette année-là, le produit est arrivé sur le marché.

Je n'ai pas été payé un cent pour cela, mais j'ai eu le droit de me vanter. Ils ont dit dès le début qu'ils avaient déjà dépassé leur budget, donc je savais quel était l'accord avant de commencer à y travailler. Et c'est une belle histoire pour les applications des AG. :)

J'ai utilisé une AG pour optimiser l'attribution des sièges lors de ma réception de mariage. 80 invités sur 10 tables. La fonction d'évaluation était basée sur le fait de garder les gens avec leurs dates, de rassembler les gens avec quelque chose en commun et de garder les gens avec des opinions opposées extrêmes à des tables séparées.

Je l'ai couru plusieurs fois. Chaque fois, j'ai eu neuf bonnes tables et une avec toutes les boules bizarres. En fin de compte, ma femme a fait les attributions de sièges.

Mon optimiseur de vendeur itinérant a utilisé une nouvelle cartographie des chromosomes pour l'itinéraire, ce qui a rendu trivial la reproduction et la mutation des chromosomes sans risque de générer des visites invalides.

Mise à jour : Parce que quelques personnes ont demandé comment ...

Commencez avec un tableau d'invités (ou de villes) dans un ordre arbitraire mais cohérent, par exemple alphabétique. Appelez cela la solution de référence. Considérez l'index d'un invité comme son numéro de siège.

Au lieu d'essayer de coder cet ordre directement dans le chromosome, nous codons des instructions pour transformer la solution de référence en une nouvelle solution. Plus précisément, nous traitons les chromosomes comme des listes d'index dans le tableau à échanger. Pour obtenir le décodage d'un chromosome, nous commençons par la solution de référence et appliquons tous les swaps indiqués par le chromosome. L'échange de deux entrées dans le tableau donne toujours une solution valide: chaque invité (ou ville) apparaît toujours exactement une fois.

Ainsi, les chromosomes peuvent être générés au hasard, mutés et croisés avec d'autres et produiront toujours une solution valide.

J'ai utilisé des algorithmes génétiques (ainsi que certaines techniques connexes) pour déterminer les meilleurs paramètres pour un système de gestion des risques qui tentait d'empêcher les producteurs d'or d'utiliser des cartes de crédit volées pour payer les MMO. Le système prendrait en compte plusieurs milliers de transactions avec des valeurs "connues" (fraude ou non) et déterminerait la meilleure combinaison de paramètres pour identifier correctement les transactions frauduleuses sans trop de faux positifs.

Nous avions des données sur plusieurs dizaines (booléennes) de caractéristiques d'une transaction, chacune ayant reçu une valeur et totalisée. Si le total était supérieur à un seuil, la transaction était une fraude. L'AG créerait un grand nombre d'ensembles de valeurs aléatoires, les évaluerait par rapport à un corpus de données connues, sélectionnerait celles qui obtiendraient les meilleurs résultats (à la fois pour la détection de la fraude et la limitation du nombre de faux positifs), puis pour croiser les meilleurs parmi chaque génération pour produire une nouvelle génération de candidats. Après un certain nombre de générations, l'ensemble de valeurs ayant obtenu le meilleur score a été jugé vainqueur.

La création du corpus de données connues à tester était le talon d'Achille du système. Si vous attendiez des rétrofacturations, vous aviez plusieurs mois de retard lorsque vous tentiez de répondre aux fraudeurs, de sorte que quelqu'un devrait examiner manuellement un grand nombre de transactions pour constituer ce corpus de données sans avoir à attendre trop longtemps.

Cela a fini par identifier la grande majorité des fraudes qui se sont produites, mais n'a pas pu le faire descendre en dessous de 1% sur les articles les plus sujets à la fraude (étant donné que 90% des transactions entrantes pouvaient être des fraudes, cela se passait plutôt bien).

J'ai fait tout cela en utilisant perl. Une exécution du logiciel sur une boîte Linux assez ancienne prendrait de 1 à 2 heures (20 minutes pour charger les données sur une liaison WAN, le reste du temps étant consacré à l'analyse). La taille d'une génération donnée était limitée par la RAM disponible. Je l'exécutais encore et encore avec de légères modifications des paramètres, à la recherche d'un ensemble de résultats particulièrement bon.

Dans l'ensemble, cela a évité certaines des gaffes qui venaient avec manuellement essayer de modifier les valeurs relatives de dizaines d'indicateurs de fraude, et a toujours trouvé de meilleures solutions que je ne pouvais créer à la main. AFAIK, il est toujours utilisé (environ 3 ans après l'avoir écrit).

Pourboire de football. J'ai construit un système GA pour prédire l'issue d'une semaine à l'autre des matchs de l'AFL (Aussie Rules Football).

Il y a quelques années, je me suis ennuyé de la piscine de football de travail standard, tout le monde se connectait et prenait les choix d'un expert dans la presse. Donc, je pensais que ça ne pouvait pas être trop difficile de battre un tas de majors du journalisme de diffusion, non? Ma première pensée a été de prendre les résultats de Massey Ratings puis de révéler à la fin de la saison ma stratégie après avoir gagné la gloire et la gloire. Cependant, pour des raisons que je n'ai jamais découvert, Massey ne suit pas l'AFL. Le cynique en moi pense que c'est parce que le résultat de chaque match de l'AFL est fondamentalement devenu un hasard, mais mes plaintes concernant les récents changements de règles appartiennent à un forum différent.

Le système tenait essentiellement compte de la force offensive, de la force défensive, de l'avantage sur le terrain, de l'amélioration d'une semaine à l'autre (ou de son absence) et de la vitesse des changements dans chacun d'eux. Cela a créé un ensemble d'équations polynomiales pour chaque équipe au cours de la saison. Le gagnant et le score de chaque match pour une date donnée peuvent être calculés. Le but était de trouver l'ensemble de coefficients qui correspondait le mieux au résultat de tous les jeux précédents et d'utiliser cet ensemble pour prédire le match des semaines à venir.

Dans la pratique, le système trouverait des solutions qui permettaient de prédire avec précision plus de 90% des résultats de matchs antérieurs. Il choisirait ensuite avec succès environ 60 à 80% des jeux pour la semaine à venir (c'est-à-dire la semaine qui ne fait pas partie de l'ensemble d'entraînement).

Le résultat: juste au-dessus du milieu du peloton. Pas de gros prix ni de système que je pourrais utiliser pour battre Vegas. C'était amusant cependant.

J'ai tout construit à partir de zéro, aucun cadre utilisé.

En plus de certains des problèmes courants, comme le voyageur de commerce et une variante du programme Mona Lisa de Roger Alsing , j'ai également écrit un solveur évolutif de Sudoku (qui nécessitait un peu plus de réflexion originale de ma part, plutôt que de simplement réimplémenter idée de quelqu'un d'autre). Il existe des algorithmes plus fiables pour résoudre Sudokus mais l'approche évolutive fonctionne assez bien.

Ces derniers jours, j'ai joué avec un programme évolutif pour trouver des "decks froids" pour le poker après avoir vu cet article sur Reddit. Ce n'est pas tout à fait satisfaisant pour le moment mais je pense que je peux l'améliorer.

J'ai mon propre framework que j'utilise pour les algorithmes évolutionnaires.

J'ai développé un GA de brassage à domicile pour un système de profil de surface laser 3D développé par mon entreprise pour l'industrie du fret en 1992. Le système reposait sur une triangulation tridimensionnelle et utilisait un scanner de ligne laser personnalisé, un appareil photo 512x512 (avec capture personnalisée hw). La distance entre la caméra et le laser n'allait jamais être précise et le point focal des caméras ne se trouvait pas dans la position 256 256 que vous attendiez!

C'était un cauchemar d'essayer de déterminer les paramètres d'étalonnage en utilisant la géométrie standard et la résolution d'équations de style de recuit simulé.

L'algorithme génétique a été fouetté en une soirée et j'ai créé un cube d'étalonnage pour le tester. Je connaissais les dimensions du cube avec une grande précision et donc l'idée était que mon GA pourrait faire évoluer un ensemble de paramètres de triangulation personnalisés pour chaque unité de numérisation qui permettrait de surmonter les variations de production.

L'astuce a fonctionné un régal. J'ai été sidéré pour le moins! En environ 10 générations, mon cube «virtuel» (généré à partir du scan brut et recréé à partir des paramètres d'étalonnage) ressemblait en fait à un cube! Après environ 50 générations, j'ai eu l'étalonnage dont j'avais besoin.

Il est souvent difficile d'obtenir une combinaison de couleurs exacte lorsque vous envisagez de peindre votre maison. Souvent, vous avez un peu de couleur en tête, mais ce n'est pas une des couleurs, le vendeur vous le montre.

Hier, mon professeur qui est un chercheur de l'AG a parlé d'une histoire vraie en Allemagne (désolé, je n'ai pas d'autres références, oui, je peux le savoir si quelqu'un le demande). Ce gars (appelons-le le gars de la couleur ) allait de porte en porte pour aider les gens à trouver le code de couleur exact (en RVB ) qui serait le placard de ce que le client avait en tête. Voici comment il le ferait:

Le gars de couleur portait avec lui un logiciel qui utilisait GA. Il avait l'habitude de commencer avec 4 couleurs différentes - chacune codée comme un chromosome codé (dont la valeur décodée serait une valeur RVB). Le consommateur choisit 1 des 4 couleurs (qui est la plus proche de laquelle il / elle a en tête). Le programme attribuerait alors la forme physique maximale à cet individu et passerait à la génération suivante à l' aide d'une mutation / croisement . Les étapes ci-dessus seraient répétées jusqu'à ce que le consommateur ait trouvé la couleur exacte, puis le gars de couleur utilisé pour lui dire la combinaison RVB!

En attribuant une forme physique maximale à la couleur se rapproche de ce que le consommateur a à l'esprit, le programme du gars de la couleur augmente les chances de converger vers la couleur, le consommateur a exactement à l'esprit. Je l'ai trouvé assez amusant!

Maintenant que j'ai un -1, si vous prévoyez plus de -1, pls. élucider la raison de le faire!

Il y a quelques semaines, j'ai proposé une solution sur SO en utilisant des algorithmes génétiques pour résoudre un problème de mise en page des graphes. C'est un exemple d'un problème d'optimisation contraint.

Toujours dans le domaine de l'apprentissage automatique, j'ai implémenté un cadre de règles de classification basé sur GA en c / c ++ à partir de zéro.
J'ai également utilisé GA dans un exemple de projet pour former des réseaux de neurones artificiels (ANN) au lieu d'utiliser le célèbre algorithme de rétropropagation .

De plus, et dans le cadre de mes recherches de troisième cycle, j'ai utilisé GA dans la formation de modèles de Markov cachés comme approche supplémentaire de l' algorithme Baum-Welch basé sur EM (à nouveau en c / c ++).

Dans le cadre de mon diplôme de premier cycle CompSci, nous avons été confrontés au problème de trouver des indicateurs jvm optimaux pour la machine virtuelle de recherche Jikes. Cela a été évalué à l'aide de la suite de référence Dicappo qui renvoie un temps à la console. J'ai écrit un alogirthm gentic distribué qui a changé ces drapeaux pour améliorer le temps d'exécution de la suite de benchmark, bien qu'il ait fallu des jours pour s'exécuter pour compenser la gigue matérielle affectant les résultats. Le seul problème était que je ne connaissais pas bien la théorie du compilateur (ce qui était l'intention de l'affectation).

J'aurais pu amorcer la population initiale avec les indicateurs par défaut existants, mais ce qui était intéressant, c'est que l'algorithme a trouvé une configuration très similaire au niveau d'optimisation O3 (mais était en fait plus rapide dans de nombreux tests).

Edit: J'ai également écrit mon propre cadre d'algorithme génétique en Python pour l'affectation, et j'ai juste utilisé les commandes popen pour exécuter les différents tests de référence, bien que si ce n'était pas une affectation évaluée, j'aurais regardé pyEvolve.

Tout d'abord, "Genetic Programming" de Jonathan Koza ( sur amazon ) est à peu près LE livre sur les techniques de programmation / algorithme génétique et évolutif, avec de nombreux exemples. Je suggère fortement de le vérifier.

Quant à ma propre utilisation d'un algorithme génétique, j'ai utilisé un algorithme génétique (fait maison) pour développer un algorithme d'essaim pour un scénario de collecte / destruction d'objets (le but pratique aurait pu être de nettoyer un champ de mines). Voici un lien vers l'article . La partie la plus intéressante de ce que j'ai fait était la fonction de fitness à plusieurs niveaux, qui était une nécessité car les fonctions de fitness simples ne fournissaient pas suffisamment d'informations pour que l'algorithme génétique différencie suffisamment les membres de la population.

Je fais partie d'une équipe qui étudie l'utilisation du calcul évolutif (EC) pour corriger automatiquement les bogues dans les programmes existants. Nous avons réussi à réparer un certain nombre de bogues réels dans des projets logiciels réels (voir la page d'accueil de ce projet ).

Nous avons deux applications de cette technique de réparation EC.

• Le premier ( code et informations de reproduction disponibles sur la page du projet ) fait évoluer les arbres de syntaxe abstraite analysés à partir des programmes C existants et est implémenté dans Ocaml en utilisant notre propre moteur EC personnalisé.

• Le second ( code et informations de reproduction disponibles sur la page du projet ), ma contribution personnelle au projet, fait évoluer l'assemblage x86 ou le code d'octet Java compilé à partir de programmes écrits dans un certain nombre de langages de programmation. Cette application est implémentée dans Clojure et utilise également son propre moteur EC personnalisé.

Un aspect agréable du calcul évolutif est la simplicité de la technique qui permet d'écrire vos propres implémentations personnalisées sans trop de difficulté. Pour un bon texte d'introduction disponible gratuitement sur la programmation génétique, voir le Field Guide to Genetic Programming .

Un collègue et moi travaillons sur une solution pour le chargement de fret sur des camions en utilisant les différents critères requis par notre entreprise. J'ai travaillé sur une solution d'algorithme génétique alors qu'il utilise une branche et lié avec une taille agressive. Nous sommes toujours en train de mettre en œuvre cette solution mais jusqu'à présent, nous avons obtenu de bons résultats.

Il y a plusieurs années, j'ai utilisé les ga pour optimiser les grammaires asr (reconnaissance automatique de la parole) pour de meilleurs taux de reconnaissance. J'ai commencé avec des listes de choix assez simples (où le ga testait des combinaisons de termes possibles pour chaque emplacement) et j'ai progressé vers des grammaires plus ouvertes et complexes. L'aptitude a été déterminée en mesurant la séparation entre les termes / séquences sous une sorte de fonction de distance phonétique. J'ai également expérimenté avec des variations faiblement équivalentes sur une grammaire pour en trouver une compilée en une représentation plus compacte (à la fin j'ai opté pour un algorithme direct, et cela a considérablement augmenté la taille du "langage" que nous pourrions utiliser dans les applications) .

Plus récemment, je les ai utilisées comme hypothèse par défaut pour tester la qualité des solutions générées à partir de divers algorithmes. Cela a impliqué en grande partie la catégorisation et différents types de problèmes d'adaptation (c'est-à-dire créer une "règle" qui explique un ensemble de choix faits par les examinateurs sur un ou des ensembles de données).

J'ai fait un framework GA complet nommé "GALAB", pour résoudre de nombreux problèmes:

• localiser les ANT GSM (BTS) pour réduire le chevauchement et les emplacements vides.
• Planification de projet de contrainte de ressources.
• Création d'images évolutives. ( Evopic )
• Problème de vendeur itinérant.
• Problèmes N-Queen et N-Color.
• Tour de chevalier et problèmes de sac à dos.
• Casse-tête Magic Square et Sudoku.
• compression de chaîne, basée sur un problème de Superstring.
• Problème d'emballage 2D.
• Petite vie artificielle APP.
• Puzzle Rubik.

J'ai déjà utilisé un GA pour optimiser une fonction de hachage pour les adresses mémoire. Les adresses étaient des tailles de page 4K ou 8K, donc elles montraient une certaine prévisibilité dans le modèle de bits de l'adresse (bits les moins significatifs tous à zéro; les bits du milieu incrémentent régulièrement, etc.) La fonction de hachage d'origine était "grossière" - elle avait tendance à regrouper les hits sur chaque troisième seau de hachage. L'algorithme amélioré avait une distribution presque parfaite.

Je ne sais pas si les devoirs comptent ...

Au cours de mes études, nous avons lancé notre propre programme pour résoudre le problème du voyageur de commerce.

L'idée était de faire une comparaison sur plusieurs critères (difficulté à cartographier le problème, performances, etc.) et nous avons également utilisé d'autres techniques comme le recuit simulé .

Cela a plutôt bien fonctionné, mais il nous a fallu un certain temps pour comprendre comment faire correctement la phase de `` reproduction '': la modélisation du problème en quelque chose de approprié pour la programmation génétique m'a vraiment semblé la partie la plus difficile ...

Ce fut un cours intéressant car nous avons également essayé les réseaux de neurones et autres.

Je voudrais savoir si quelqu'un a utilisé ce type de programmation en code de «production».

J'ai construit un GA simple pour extraire des motifs utiles du spectre de fréquences de la musique pendant qu'elle était jouée. La sortie a été utilisée pour piloter des effets graphiques dans un plugin Winamp.

• Entrée: quelques images FFT (imaginez un tableau 2D de flotteurs)
• Sortie: valeur flottante unique (somme pondérée des entrées), seuil à 0,0 ou 1,0
• Gènes: poids d'entrée
• Fonction fitness: combinaison du rapport cyclique, de la largeur d'impulsion et du BPM dans une plage sensible.

J'ai eu quelques GA réglés sur différentes parties du spectre ainsi que sur différentes limites de BPM, donc ils n'ont pas eu tendance à converger vers le même schéma. Les sorties des 4 premiers de chaque population ont été envoyées au moteur de rendu.

Un effet secondaire intéressant était que la forme physique moyenne dans la population était un bon indicateur des changements dans la musique, bien qu'il ait généralement fallu 4 à 5 secondes pour le comprendre.

Dans le cadre de ma thèse, j'ai écrit un framework Java générique pour l'algorithme d'optimisation multi-objectif mPOEMS (Optimisation de prototype multi-objectif avec étapes d'amélioration évoluées), qui est une AG utilisant des concepts évolutifs. Il est générique de manière à ce que toutes les parties indépendantes du problème aient été séparées des parties dépendantes du problème, et une interface est fournie pour utiliser le cadre en ajoutant uniquement les parties dépendantes du problème. Ainsi, celui qui veut utiliser l'algorithme n'a pas à partir de zéro, et cela facilite beaucoup le travail.

Vous pouvez trouver le code ici .

Les solutions que vous pouvez trouver avec cet algorithme ont été comparées dans un travail scientifique avec les algorithmes de pointe SPEA-2 et NSGA, et il a été prouvé que l'algorithme fonctionne de manière comparable ou même meilleure, selon les mesures que vous prendre pour mesurer les performances, et surtout en fonction du problème d'optimisation que vous recherchez.

Vous pouvez le trouver ici .

Également dans le cadre de ma thèse et de la preuve de travail, j'ai appliqué ce cadre au problème de sélection de projet trouvé dans la gestion de portefeuille. Il s'agit de sélectionner les projets qui ajoutent le plus de valeur à l'entreprise, soutiennent le plus la stratégie de l'entreprise ou soutiennent tout autre objectif arbitraire. Ex: sélection d'un certain nombre de projets dans une catégorie spécifique, ou maximisation des synergies de projets, ...

Ma thèse qui applique ce cadre au problème de sélection de projet: http://www.ub.tuwien.ac.at/dipl/2008/AC05038968.pdf

Après cela, j'ai travaillé dans un département de gestion de portefeuille dans l'un des Fortune 500, où ils ont utilisé un logiciel commercial qui a également appliqué une AG au problème de sélection de projet / optimisation de portefeuille.

Autres ressources:

La documentation du framework: http://thomaskremmel.com/mpoems/mpoems_in_java_documentation.pdf

Document de présentation mPOEMS: http://portal.acm.org/citation.cfm?id=1792634.1792653

En fait, avec un peu d'enthousiasme, tout le monde pouvait facilement adapter le code du cadre générique à un problème d'optimisation arbitraire à objectifs multiples.

Au travail, j'ai eu le problème suivant: étant donné les tâches M et les N DSP, quelle était la meilleure façon d'affecter des tâches aux DSP? "Meilleur" a été défini comme "minimisant la charge du DSP le plus chargé". Il y avait différents types de tâches, et divers types de tâches avaient diverses ramifications de performances selon l'endroit où elles étaient affectées, j'ai donc codé l'ensemble des affectations de travail à DSP en tant que «chaîne d'ADN», puis j'ai utilisé un algorithme génétique pour «se reproduire» la meilleure chaîne d'affectation que je pouvais.

Cela fonctionnait assez bien (bien mieux que ma méthode précédente, qui consistait à évaluer toutes les combinaisons possibles ... sur des tailles de problème non triviales, cela aurait pris des années à terminer!), Le seul problème était qu'il n'y avait aucun moyen de le savoir si la solution optimale a été atteinte ou non. Vous ne pouviez que décider si le "meilleur effort" actuel était assez bon, ou le laisser courir plus longtemps pour voir s'il pouvait faire mieux.

Il y avait un concours sur codechef.com (grand site au fait, concours de programmation mensuels) où l'on était censé résoudre un sudoku insoluble (on devrait s'approcher le plus près possible avec le moins de colonnes / lignes / etc erronées possible).

Ce que je ferais, c'était de générer d'abord un sudoku parfait puis de remplacer les champs qui ont été donnés. À partir de cette très bonne base, j'ai utilisé la programmation génétique pour améliorer ma solution.

Je ne pouvais pas penser à une approche déterministe dans ce cas, car le sudoku était 300x300 et la recherche aurait pris trop de temps.

J'ai utilisé un algorithme génétique simple pour optimiser le rapport signal / bruit d'une onde qui était représentée comme une chaîne binaire. En retournant les bits de certaines façons sur plusieurs millions de générations, j'ai pu produire une transformation qui a entraîné un rapport signal / bruit plus élevé de cette onde. L'algorithme aurait également pu être "recuit simulé" mais n'a pas été utilisé dans ce cas. À la base, les algorithmes génétiques sont simples, et c'était à peu près aussi simple qu'un cas d'utilisation que j'ai vu, donc je n'ai pas utilisé de cadre pour la création et la sélection de génération - seulement une graine aléatoire et le rapport signal / bruit fonction à portée de main.

Dans un séminaire à l'école, nous développons une application pour générer de la musique basée sur le mode musical. Le programme a été construit en Java et la sortie était un fichier midi avec la chanson. Nous utilisons des approches distinctes de GA pour générer la musique. Je pense que ce programme peut être utile pour explorer de nouvelles compositions.

au premier cycle, nous avons utilisé NERO (une combinaison de réseau neuronal et d'algorithme génétique) pour enseigner aux robots du jeu à prendre des décisions intelligentes. C'était plutôt cool.

J'ai développé une simulation swing multithread de la navigation par robot à travers un ensemble de terrain de grille aléatoire de sources de nourriture et de mines et développé une stratégie basée sur un algorithme génétique pour explorer l'optimisation du comportement robotique et la survie des gènes les plus aptes pour un chromosome robotique. Cela a été fait en utilisant la cartographie et la cartographie de chaque cycle d'itération.

Depuis, j'ai développé encore plus de comportements de jeu. Un exemple d'application que j'ai construit récemment pour moi-même était un algorithme génétique pour résoudre le problème des vendeurs ambulants dans la recherche d'itinéraire au Royaume-Uni en tenant compte des états de départ et d'objectif ainsi que d'un / plusieurs points de connexion, retards, annulations, travaux de construction, heure de pointe, grèves publiques, considération entre les itinéraires les plus rapides et les moins chers. Fournir ensuite une recommandation équilibrée pour l'itinéraire à suivre un jour donné.

Généralement, ma stratégie consiste à utiliser la représentation des gènes basée sur POJO, puis j'applique des implémentations d'interface spécifiques pour la sélection, la mutation, les stratégies de croisement et le point de critères. Ma fonction de fitness devient alors assez complexe en fonction de la stratégie et des critères que je dois appliquer comme mesure heuristique.

J'ai également cherché à appliquer un algorithme génétique à des tests automatisés dans le code en utilisant des cycles de mutation systématiques où l'algorithme comprend la logique et essaie de vérifier un rapport de bogue avec des recommandations pour les corrections de code. Fondamentalement, un moyen d'optimiser mon code et de fournir des recommandations d'amélioration ainsi qu'un moyen d'automatiser la découverte de nouveau code programmatique. J'ai également essayé d'appliquer des algorithmes génétiques à la production musicale, entre autres applications.

En général, je trouve que les stratégies évolutives comme la plupart des stratégies d'optimisation métaheuristique / globale, elles sont lentes à apprendre au début, mais commencent à prendre de l'ampleur à mesure que les solutions se rapprochent de plus en plus de l'état de l'objectif et tant que votre fonction de fitness et l'heuristique sont bien alignées pour produire cette convergence dans votre espace de recherche.

J'ai essayé une fois de créer un ordinateur pour le jeu de Go, exclusivement basé sur la programmation génétique. Chaque programme serait traité comme une fonction d'évaluation d'une séquence de mouvements. Les programmes produits n'étaient cependant pas très bons, même sur une carte 3x4 plutôt réduite.

J'ai utilisé Perl et j'ai tout codé moi-même. Je ferais les choses différemment aujourd'hui.

Après avoir lu The Blind Watchmaker , j'ai été intéressé par le programme pascal que Dawkins a dit qu'il avait développé pour créer des modèles d'organismes qui pourraient évoluer avec le temps. J'étais assez intéressé pour écrire le mien en utilisant Swarm . Je n'ai pas fait tous les graphiques créatures fantaisistes qu'il a faits, mais mes «chromosomes» contrôlaient les traits qui affectaient la capacité des organismes à survivre. Ils vivaient dans un monde simple et pouvaient se battre les uns contre les autres et leur environnement.

Les organismes ont vécu ou sont morts en partie à cause du hasard, mais aussi en fonction de leur efficacité d'adaptation à leur environnement local, de la façon dont ils ont consommé des nutriments et de leur succès de reproduction. C'était amusant, mais aussi une preuve supplémentaire pour ma femme que je suis un geek.

C'était il y a un certain temps, mais j'ai lancé un GA pour faire évoluer ce qui était en fait des noyaux de traitement d'image pour supprimer les traces de rayons cosmiques des images du télescope spatial Hubble (HST). L'approche standard consiste à prendre plusieurs expositions avec le Hubble et à ne conserver que les éléments identiques sur toutes les images. Étant donné que le temps HST est si précieux, je suis un passionné d'astronomie et j'avais récemment assisté au Congrès sur le calcul évolutif, j'ai pensé à utiliser un GA pour nettoyer les expositions uniques.

Les individus étaient sous la forme d'arbres qui prenaient une zone de 3x3 pixels en entrée, effectuaient des calculs et produisaient une décision quant à savoir si et comment modifier le pixel central. L'aptitude a été jugée en comparant la sortie avec une image nettoyée de manière traditionnelle (c'est-à-dire en empilant les expositions).

En fait, cela a en quelque sorte fonctionné, mais pas suffisamment pour justifier de renoncer à l'approche originale. Si ma thèse ne m'avait pas contraint dans le temps, j'aurais peut-être élargi le bac de pièces génétiques disponible pour l'algorithme. Je suis presque sûr que j'aurais pu l'améliorer considérablement.

Bibliothèques utilisées: Si je me souviens bien, IRAF et cfitsio pour le traitement des données d'images astronomiques et les E / S.

J'ai expérimenté avec GA dans ma jeunesse. J'ai écrit un simulateur en Python qui fonctionnait comme suit.

Les gènes codaient les poids d'un réseau neuronal.

Les entrées du réseau neuronal étaient des "antennes" qui détectaient les contacts. Des valeurs plus élevées signifiaient très proches et 0 signifiait ne pas toucher.

Les sorties étaient à deux "roues". Si les deux roues avancent, le gars avance. Si les roues étaient dans des directions opposées, le gars a tourné. La force de la sortie a déterminé la vitesse de rotation des roues.

Un labyrinthe simple a été généré. C'était vraiment simple - stupide même. Il y avait le début en bas de l'écran et un but en haut, avec quatre murs entre les deux. Chaque mur avait un espace retiré au hasard, donc il y avait toujours un chemin.

J'ai commencé des gars au hasard (je les considérais comme des bugs) au début. Dès qu'un gars a atteint l'objectif, ou qu'une limite de temps a été atteinte, la condition physique a été calculée. Il était inversement proportionnel à la distance du but à ce moment-là.

Je les ai ensuite jumelés et «élevés» pour créer la prochaine génération. La probabilité d'être choisi pour être reproduit était proportionnelle à son aptitude. Parfois, cela signifiait que l'on était élevé avec lui-même à plusieurs reprises s'il avait une très bonne condition physique relative.

Je pensais qu'ils développeraient un comportement "étreignant le mur gauche", mais ils semblaient toujours suivre quelque chose de moins optimal. Dans chaque expérience, les bugs ont convergé vers un motif en spirale. Ils tournaient en spirale vers l'extérieur jusqu'à ce qu'ils touchent un mur à droite. Ils suivaient cela, puis lorsqu'ils arrivaient à l'écart, ils descendaient en spirale (loin de l'écart) et autour. Ils faisaient un virage de 270 degrés vers la gauche, puis entraient généralement dans l'écart. Cela leur permettrait de franchir la majorité des murs et souvent d'atteindre le but.

Une caractéristique que j'ai ajoutée était de mettre un vecteur de couleur dans les gènes pour suivre la parenté entre les individus. Après quelques générations, ils seraient tous de la même couleur, ce qui me dit que je devrais avoir une meilleure stratégie d'élevage.

J'ai essayé de les amener à développer une meilleure stratégie. J'ai compliqué le réseau neuronal - en ajoutant une mémoire et tout. Ça n'a pas aidé. J'ai toujours vu la même stratégie.

J'ai essayé différentes choses comme avoir des pools de gènes séparés qui ne se sont recombinés qu'après 100 générations. Mais rien ne les pousserait vers une meilleure stratégie. C'était peut-être impossible.

Une autre chose intéressante est de représenter graphiquement la forme physique au fil du temps. Il y avait des schémas définis, comme la forme physique maximale qui descendait avant de monter. Je n'ai jamais vu un livre sur l'évolution parler de cette possibilité.