Quais são algumas aplicações do mundo real para algoritmos genéticos?

13

Quais são alguns problemas do mundo real que foram resolvidos usando um algoritmo genético? Qual é o problema? Qual é o teste de aptidão utilizado para resolver este problema?

The Rook
fonte
1
Este deve ser um wiki da comunidade (assumindo que esteja no tópico).
Shane
4
Não sei se algoritmos genéticos estão dentro do escopo. Devemos discuti-lo aqui: meta.cstheory.stackexchange.com/questions/73/…
Suresh Venkat
7
Isso está fora de tópico.
Marcos Villagra
5
Uma questão interessante seria: existem cenários que admitem garantias comprováveis ​​para as AGs?
Suresh Venkat
2
Mas não se trata de uma aplicação da teoria. É sobre uma aplicação da prática.
Jeffε

Respostas:

11

O otimizador em bancos de dados relacionais. Exemplos são PostgreSQL e H2 ; outros bancos de dados provavelmente também usam um algoritmo genético. O problema é: selecionar o melhor plano de consulta (aquele com o menor custo estimado) é difícil para o NP. O teste de aptidão é o custo estimado.

Thomas Mueller
fonte
8

O algoritmo genético lamarckiano é usado na quimioinformática para rastrear possíveis novos compostos de drogas que podem se ligar a um receptor específico.

O problema computacional é procurar em um banco de dados químico candidatos que possam orientar corretamente (escrever as orientações possíveis da molécula que contém o receptor) e combiná-lo com uma pesquisa conformacional (isto é, uma que considere as possíveis torções rotativas da molécula) , o que pode afetar fortemente a reação ).

Anteriormente, era possível realizar uma pesquisa de orientação ou uma pesquisa de conformação, mas não as duas. A LGA aproveita a aceleração do computador e combina a pesquisa global de um algoritmo genético com uma pesquisa local.

Aaron Sterling
fonte
6

A Nasa criou um algoritmo genético para o Design de Antenas .

O teste de aptidão é o seguinte:

A função de adequação usada para avaliar antenas é uma função da relação da onda estacionária de tensão (VSWR) e dos valores de ganho nas frequências de transmissão e recepção. O VSWR é uma maneira de quantificar a interferência das ondas refletidas e, portanto, a quantidade de incompatibilidade de impedância na junção. VSWR é a razão entre a tensão mais alta e a mais baixa no envelope de sinal ao longo de uma linha de transmissão.

The Rook
fonte
6

Eles são frequentemente usados ​​em finanças, especialmente para problemas de otimização de portfólio. Existem muitos trabalhos sobre esse assunto, mas veja, por exemplo, Algoritmos Genéticos em Otimização de Portfólio .

Shane
fonte
6

Eu usei os GAs para resolver problemas de agendamento na fabricação e educação. A função de adequação no primeiro caso foi o quanto dos itens solicitados foram fabricados no período de tempo especificado, enquanto no segundo caso a adequação foi baseada em penalizações de cronogramas com conflitos.

Se você estiver interessado em candidaturas, aqui está um link para mais de 20 mil artigos sobre citeseerx

Steven A. Lowe
fonte
4

O design da antena já foi mencionado e é um domínio extremamente rico. (Foi, diretamente, o que iniciou meu movimento da engenharia elétrica para a ciência da computação (no final dos anos 90) e, mais especificamente, para a computação inspirada em biologia e inteligência artificial (nos últimos cinco anos).

Na mesma linha, adicionarei a otimização do arranjo da antena , especialmente para a otimização do arranjo em fases, que são todas as dores de cabeça do design da antena e muito mais. Na verdade, existem oportunidades em todo o campo do design de dispositivos eletromagnéticos: antenas, conjuntos de antenas, filtros de microondas, grades ópticas, design de dispositivos metamateriais, tudo em cima da minha cabeça. Uma pesquisa datada é a Otimização Eletromagnética por Algoritmos Genéticos , e uma pesquisa mais recente é Algoritmos Genéticos em Eletromagnetismo . (Eu realmente deveria comprar esse segundo.

Também já vi muitos artigos bons sobre o design de circuitos não eletromagnéticos: os GAs criaram amplificadores operacionais competitivos ou outros projetos de circuitos integrados; os GAs "aprendem" a tirar proveito das imperfeições analógicas nos FPGAs para implementar funções analógicas como relógios, etc. Mesmo algo tão simples quanto o design de filtro de elemento discreto e burro pode ser um alvo para os GAs: eu vi um que leva em consideração fatores q, tolerâncias, valores discretos e modelos parasitas de solda para obter bons filtros fabricáveis ​​a partir do peças que você tem em mãos.

Isso geralmente envolve algumas representações de circuitos novos (para mim, pelo menos) para fazer com que os operadores genéticos se ajustem ao paradigma, bem como cromossomos de tamanho variável.

Novak
fonte
sim, o exemplo do projeto de circuitos mostrou redescobrir ou até superar os projetos patenteados. aqui está um artigo inicial, muito mais tarde. Projeto de um amplificador operacional de alta Ganho e outros circuitos por Meio da Programação Genética por Koza et al 1997
vzn
3

recentemente, houve uma pergunta sobre o uso de GAs para desenvolver projetos de pás de turbinas eólicas usando simulações de dinâmica de fluidos de energia física gerada como função de condicionamento físico.

Este vídeo mostra o uso de um algoritmo genético para desenvolver pás de turbinas eólicas VAWT. Uma das lâminas resultantes é bem diferente e parece simular bem. O software de criação foi escrito em Perl, o software de exibição Java e o software CFD foi o OpenFoam. Mais de 672 horas de CPU foram usadas para a criação deste vídeo. Nota: Desde então, descobri que usei a viscosidade errada para o ar nesta experiência, portanto, os resultados não são válidos para uso na Terra. (Talvez Júpiter.)

[1] "Lâminas de turbinas eólicas em evolução" no youtube por "sjh7132". citado pela / da pergunta TCS.se: Até que ponto é possível usar algoritmos genéticos para tornar as pás das turbinas eólicas mais eficientes?

vzn
fonte
1

existem muitos artigos sobre o uso de GAs para controle de vôo no campo aeroespacial. muitos deles são publicados ou pesquisáveis ​​pelo IEEE explorer . a função fitness geralmente mede o quão bem / efetivamente o algoritmo controla o voo.

[1] Projeto e otimização de sistemas de controle de vôo com algoritmo genético de Fantinutto et al.

[2] Aplicação de algoritmos genéticos ao controle de vôo hipersônico. Austin, Jacobs.

[3] Implementação multinúcleo do sistema de controle de superfície de vôo F-16 usando o algoritmo de controle adaptativo baseado em algoritmo genético, Xiaoru Wang.

[4] Controle lógico difuso baseado em algoritmo genético para controle de vôo integrado para veículos hipersônicos. por Wang Jian

vzn
fonte
1

um uso notável, até extraordinário ou de mudança de paradigma, de AGs, altamente citado em pesquisas posteriores, foi pioneiro por Koza para resolver um "problema" de videogame - ou seja, Pac Man para uma prova de princípio, mas o conceito provavelmente pode ser aplicado a possivelmente quase qualquer jogo de vídeo, e os resultados estão definitivamente longe de ser triviais ou "brinquedos".

isto é, ele desenvolveu algoritmos que implementam o comportamento real para vencer jogando o jogo por longos períodos de tempo. os resultados estão no nível de desempenho de jogadores humanos amadores ou mesmo avançados . uma função de condicionamento físico pode ser pontos pontuados pelo algoritmo ou período de tempo jogado (o mais recente provavelmente evoluirá algoritmos que sobreviverão sem pontos de pontuação, como um caso clássico de naves espaciais de "caça" no jogo Asteróides). o comportamento é implementado com "primitivas" (por exemplo, monstros dos sentidos / agindo girando etc) e árvores que representam as combinações de estratégias primitivas.

[1] Evoluindo diversos agentes que jogam Pac-Man usando programação genética de Atif M. Alhejali e Simon M. Lucas

[2] Aprendendo a jogar Pac-Man: uma abordagem evolutiva baseada em regras de Gallagher e Ryan

[3] Aprendendo a tocar usando políticas baseadas em regras de baixa complexidade: ilustrações através da Sra. Pac-Man de István Szita András Lincin

vzn
fonte
Para ser muito exigente, eu faria uma distinção entre programação genética e algoritmos genéticos. Certamente eles estão intimamente relacionados, no entanto.
Novak
A @novak concordou & thx por traçar a distinção que ficou embaçada aqui. aproximadamente, GP é o uso de GAs para descobrir algoritmos, verdade? sim, o comportamento encontrado / construído é basicamente equivalente a um algoritmo .. & é claro que a técnica provavelmente é amplamente aplicável fora dos videogames, embora não esteja ciente de muitos exemplos até agora .. seu uso muito avançado .. (embora me lembre de outro exemplo dos koza's que ainda usam árvores de maneira inteligente!
vzn
1

A conferência anual da GECCO (praticamente o principal local para pesquisas em computação evolutiva) tem uma faixa de 'Aplicações do mundo real'.

Veja também esta apresentação recente:

NietzscheanAI
fonte