Quelles sont les applications réelles des algorithmes génétiques?

13

Quels sont les problèmes du monde réel qui ont été résolus en utilisant un algorithme génétique? Quel est le problème? Quel est le test de condition physique utilisé pour résoudre ce problème?

La tour
la source
1
Il devrait s'agir d'un wiki communautaire (en supposant qu'il s'agit du sujet).
Shane
4
Je ne suis pas sûr que les algorithmes génétiques soient à portée. Nous devrions en discuter ici: meta.cstheory.stackexchange.com/questions/73/…
Suresh Venkat
7
C'est hors sujet.
Marcos Villagra
5
Une question intéressante aurait pu être: existe-t-il des scénarios qui admettent des garanties prouvables pour les AG?
Suresh Venkat
2
Mais il ne s'agit pas d'une application de la théorie. Il s'agit d'une application de la pratique.
Jeffε

Réponses:

11

L'optimiseur dans les bases de données relationnelles. Les exemples sont PostgreSQL et H2 ; d'autres bases de données utilisent très probablement également un algorithme génétique. Le problème est: sélectionner le meilleur plan de requête (celui avec le coût estimé le plus bas) est NP-difficile. Le test de fitness est le coût estimé.

Thomas Mueller
la source
8

L' algorithme génétique lamarckien est utilisé en chimio-informatique pour rechercher d'éventuels nouveaux composés médicamenteux pouvant se lier à un récepteur particulier.

Le problème de calcul est de rechercher dans une base de données chimiques des candidats capables de s'orienter correctement (par rapport aux orientations possibles de la molécule contenant le récepteur), et de combiner cela avec une recherche conformationnelle (c'est-à-dire qui considère les éventuelles torsions rotatives de la molécule , ce qui peut fortement affecter la réaction ).

Auparavant, il était possible d'effectuer une recherche d'orientation ou une recherche de conformation, mais pas les deux. LGA profite de l'accélération de l'ordinateur et combine la recherche globale d'un algorithme génétique avec une recherche locale.

Aaron Sterling
la source
6

La Nasa a créé un algorithme génétique pour la conception d'antennes .

Le test de fitness est le suivant:

La fonction de fitness utilisée pour évaluer les antennes est fonction du rapport d'ondes stationnaires (VSWR) et des valeurs de gain sur les fréquences d'émission et de réception. VSWR est un moyen de quantifier l'interférence des ondes réfléchies, et donc la quantité de décalage d'impédance à la jonction. VSWR est le rapport entre la tension la plus élevée et la tension la plus basse dans l'enveloppe du signal le long d'une ligne de transmission.

La tour
la source
6

J'ai utilisé des AG pour résoudre des problèmes de planification dans la fabrication et l'éducation. La fonction de remise en forme dans le premier cas était la quantité des articles demandés qui ont été fabriqués dans le délai imparti, tandis que dans le second cas, la remise en forme était basée sur des horaires pénalisants avec des conflits.

Si vous êtes intéressé par les applications, voici un lien vers plus de 20 000 articles sur citeseerx

Steven A. Lowe
la source
4

La conception d'antenne a déjà été mentionnée et c'est un domaine extrêmement riche. (C'est, très directement, ce qui a déclenché mon mouvement de l'électrotechnique à l'informatique (à la fin des années 90) et plus spécifiquement au calcul bio-inspiré et à l'intelligence artificielle (au cours des cinq dernières années environ).))

Dans le même ordre d'idées, j'ajouterai l' optimisation du réseau d' antennes , en particulier pour l'optimisation des réseaux phasés, qui est tout le casse-tête de la conception d'antennes, et plus encore. Il y a des opportunités dans tout le domaine de la conception d'appareils électromagnétiques, en fait: antennes, réseaux d'antennes, filtres micro-ondes, réseaux optiques, conception d'appareils métamatériaux, tout cela du haut de ma tête. Une étude datée est l' optimisation électromagnétique par des algorithmes génétiques , et une enquête plus récente est des algorithmes génétiques en électromagnétique . (Je devrais vraiment acheter ce deuxième.

J'ai également vu beaucoup de bons articles sur la conception de circuits non électromagnétiques: les GA proposent des amplificateurs opérationnels compétitifs ou d'autres conceptions de circuits intégrés, les GA "apprennent" à tirer parti des imperfections analogiques des FPGA pour implémenter des fonctions analogiques comme horloges, etc. Même quelque chose d'aussi simple que la conception de filtre d'élément discret peut être une cible pour les GA: j'en ai vu un qui prend en compte les facteurs q, les tolérances, les valeurs discrètes et les modèles parasites de soudure pour obtenir de bons filtres manufacturables à partir du les pièces que vous avez sous la main.

Celles-ci impliquent souvent de nouvelles représentations de circuits (pour moi, en tout cas) pour amener les opérateurs génétiques à s'adapter au paradigme, ainsi que des chromosomes de taille variable.

Novak
la source
oui, il a été démontré que l'exemple de conception de circuits redécouvre, voire surpasse les conceptions brevetées. Voici un premier article dans ce sens, des recherches beaucoup plus tardives. Conception d'un amplificateur opérationnel à gain élevé et d'autres circuits au moyen de la programmation génétique par Koza et al 1997
vzn
3

récemment, il y avait une question sur l'utilisation des AG pour faire évoluer les conceptions de pales d'éoliennes en utilisant des simulations de dynamique des fluides de la puissance physique générée comme fonction de fitness. [1]

Cette vidéo montre l'utilisation d'un algorithme génétique pour développer des pales d'éoliennes VAWT. L'une des lames résultantes est assez différente et semble bien simuler. Le logiciel d'élevage a été écrit en Perl, le logiciel d'affichage Java et le logiciel CFD était OpenFoam. Plus de 672 heures CPU ont été nécessaires à la réalisation de cette vidéo. Remarque: J'ai découvert depuis que j'avais utilisé la mauvaise viscosité pour l'air lors de cette expérience, donc les résultats ne sont pas valables pour une utilisation sur terre. (Peut-être Jupiter.)

[1] "Pales d'éoliennes en évolution" sur youtube par "sjh7132". cité par / de la question TCS.se: Dans quelle mesure est-il possible d'utiliser des algorithmes génétiques pour rendre les pales d'éoliennes plus efficaces?

vzn
la source
3

il existe des recherches sur l'utilisation des AG pour la classification des vins. il classe avec précision la variété de vin et le lieu de production ("dénomination d'origine"). [1] il s'agit d'un sous-ensemble d'utilisation des AG dans les systèmes agricoles dont les applications sont nombreuses. [2]

[1] Algorithmes de sélection des fonctionnalités utilisant des chromatogrammes de vin chiliens comme exemples par NHBeltran et al

[2] État de l'art des algorithmes génétiques pour les systèmes agricoles par Bolboaca et al

vzn
la source
1

il existe de nombreux articles sur l'utilisation des GA pour le contrôle de vol dans le domaine aérospatial. beaucoup d'entre eux sont publiés ou consultables par l' explorateur IEEE . la fonction fitness mesure généralement la façon dont l'algorithme contrôle bien / efficacement le vol.

[1] Conception et optimisation d'un système de commandes de vol avec un algorithme génétique par Fantinutto et al

[2] Application d'algorithmes génétiques au contrôle de vol hypersonique. Austin, Jacobs.

[3] Implémentation multicœur du système de contrôle de surface de vol F-16 utilisant l'algorithme de contrôle adaptatif basé sur l'algorithme génétique, Xiaoru Wang

[4] Contrôle de logique floue basé sur un algorithme génétique pour un contrôle de vol intégré pour les véhicules hypersoniques. par Wang Jian

vzn
la source
1

une utilisation remarquable, même extraordinaire ou changeante de paradigme des AG, très citée dans des enquêtes ultérieures, a été lancée par Koza pour résoudre un "problème" de jeu vidéo - à savoir Pac Man pour une preuve de principe, mais le concept peut probablement être appliqué à peut-être presque n'importe quel jeu vidéo, et les résultats sont définitivement loin d'être triviaux ou "jouets".

c'est-à-dire qu'il a développé des algorithmes qui implémentent un comportement réel pour gagner à jouer au jeu pendant de longues périodes. les résultats sont au niveau des performances d'amateur ou même avancé des joueurs humains . une fonction de remise en forme peut être soit des points marqués par l'algorithme ou la durée de jeu (le dernier évoluera vraisemblablement des algorithmes qui survivent sans marquer de points, comme un cas classique de «chasse» de vaisseaux spatiaux dans le jeu Asteroids). le comportement est mis en œuvre avec des «primitives» (par exemple, détecter les monstres / agir en tournant, etc.) et des arbres qui représentent les combinaisons de stratégies primitives.

[1] Divers agents évoluant Mme Pac-Man utilisant la programmation génétique par Atif M. Alhejali et Simon M. Lucas

[2] Apprendre à jouer à Pac-Man: une approche évolutive basée sur des règles par Gallagher et Ryan

[3] Apprendre à jouer en utilisant des politiques basées sur des règles de faible complexité: illustrations par Mme Pac-Man par István Szita András L ~ orincz

vzn
la source
Pour être très pointilleux, je ferais une distinction entre la programmation génétique et les algorithmes génétiques. Mais ils sont certainement étroitement liés.
Novak
@novak a accepté & thx pour avoir fait la distinction qui était floue ici. à peu près, GP est l'utilisation des GA pour découvrir des algorithmes, vrai? oui le comportement trouvé / construit est fondamentalement équivalent à un algorithme .. & bien sûr la technique est probablement largement applicable en dehors des jeux vidéo bien qu'elle ne connaisse pas beaucoup d'exemples jusqu'à présent .. son utilisation très avancée .. (bien que je me souvienne d'un autre exemple de koza qui utilise toujours les arbres de manière intelligente!
vzn
1

La conférence annuelle GECCO (à peu près le premier lieu de recherche en calcul évolutif) a une piste «Real World Applications».

Voir aussi cette récente présentation:

NietzscheanAI
la source