O que são bons exemplos de algoritmos genéticos/programação genética soluções?[fechado]

https://stackoverflow.com/questions/1538235

20-09-2019
|

Pergunta

Algoritmos genéticos (GA) e programação genética (GP) são áreas de interesse de investigação.

Eu gostaria de saber sobre problemas específicos que você tenha resolvido usando GA/GP e o que bibliotecas/frameworks que você usou, se não rolar o seu próprio.

Perguntas:

Quais os problemas que você tem usado GA/GP resolver?
O que as bibliotecas/frameworks que você usa?

Eu estou olhando para as primeiras experiências, então, por favor não responda a menos que você tem que.

Solução

Não trabalho de casa.

Meu primeiro emprego como programador profissional (1995) estava escrevendo um sistema de negociação automatizado baseado em algoritmo genético para futuros de S & P500. O aplicativo foi escrito no Visual Basic 3 [!] E eu não tenho idéia de como fazia nada naquela época, já que o VB3 nem tinha aulas.

O aplicativo começou com uma população de cordas de comprimento fixo gerado aleatoriamente (a parte "gene"), cada uma das quais correspondia a uma forma específica nos dados de preços minuto a minuto dos futuros de S & P500, bem como uma ordem específica (compre ou venda) e quantias de parar e interromper a fins lucrativos. Cada string (ou "gene") teve seu desempenho de lucro avaliado por uma execução através de 3 anos de dados históricos; Sempre que a "forma" especificada correspondia aos dados históricos, assumi o pedido de compra ou venda correspondente e avaliava o resultado do comércio. Adicionei a ressalva de que cada gene começou com uma quantia fixa de dinheiro e, portanto, poderia potencialmente quebrar e ser removido completamente do pool de genes.

Após cada avaliação de uma população, os sobreviventes foram cruzados aleatoriamente (apenas misturando bits de dois pais), com a probabilidade de um gene ser selecionado como pai sendo proporcional ao lucro produzido. Também adicionei a possibilidade de mutações pontuais para apimentar um pouco as coisas. Depois de algumas centenas de gerações disso, acabei com uma população de genes que poderiam transformar US $ 5000 em uma média de cerca de US $ 10000 sem chance de morte/intermediário (nos dados históricos, é claro).

Infelizmente, nunca tive a chance de usar esse sistema ao vivo, já que meu chefe perdeu cerca de US $ 100.000 em menos de 3 meses negociando da maneira tradicional e perdeu a vontade de continuar com o projeto. Em retrospecto, acho que o sistema teria obtido enormes lucros - não porque eu estava necessariamente fazendo qualquer coisa certa, mas porque a população de genes que eu produzi era tendenciosa para comprar ordens (em oposição a vender ordens) por cerca de 5: 1 proporção. E como sabemos com nossa retrospectiva 20/20, o mercado aumentou um pouco depois de 1995.

Outras dicas

Fiz algumas criaturas que viviam neste pequeno mundo. Eles tinham um cérebro de rede neural que recebeu algumas entradas do mundo e a produção era um vetor para o movimento, entre outras ações. Seus cérebros eram os "genes".

O programa começou com uma população aleatória de criaturas com cérebros aleatórios. Os insumos e os neurônios de saída eram estáticos, mas o que estava no meio não era.

O ambiente continha alimentos e perigos. Os alimentos aumentaram a energia e, quando você tem energia suficiente, pode acasalar. Os perigos reduziriam a energia e, se a energia fosse 0, eles morreram.

Eventualmente, as criaturas evoluíram para se mover pelo mundo e encontrar comida e evitar os perigos.

Decidi então fazer um pequeno experimento. Dei ao cérebro da criatura um neurônio de saída chamado "boca" e um neurônio de entrada chamado "Ear". Começou de novo e ficou surpreso ao descobrir que eles evoluíram para maximizar o espaço e cada criatura respectiva permaneceria em sua respectiva parte (a comida foi colocada aleatoriamente). Eles aprenderam a cooperar um com o outro e a não se tornarem um para o outro. Sempre houve as exceções.

Então eu tentei algo interessante. Eu morto criaturas se tornariam comida. Tente adivinhar o que aconteceu! Dois tipos de criaturas evoluíram, aqueles que atacaram como em enxames e aqueles que eram de alta evasão.

Então, qual é a lição aqui? Comunicação significa cooperação. Assim que você introduzir um elemento em que machucar outro significa que você ganha algo, a cooperação é destruída.

Eu me pergunto como isso reflete sobre o sistema de livres livres e capitalismo. Quero dizer, se as empresas podem prejudicar a concorrência e fugir com isso, então está claro que eles farão tudo ao seu alcance para prejudicar a competição.

Editar:

Eu escrevi em C ++ usando nenhuma estrutura. Escreveu meu próprio código neural e GA. Eric, obrigado por dizer que é plausível. As pessoas geralmente não acreditam nos poderes do GA (embora as limitações sejam óbvias) até brincarem com ele. GA é simples, mas não simplista.

Para os que duvidam, as redes neurais provaram ser capazes de simular qualquer função se tiverem mais de uma camada. O GA é uma maneira bastante simples de navegar em um espaço de solução para encontrar um mínimo local e potencialmente global. Combine GA com redes neurais e você tem uma boa maneira de encontrar funções que encontram soluções aproximadas para problemas genéricos. Como estamos usando redes neurais, estamos otimizando a função para algumas entradas, não algumas entradas para uma função, pois outras estão usando GA

Aqui está o código de demonstração para o exemplo de sobrevivência: http://www.mempko.com/darcs/neural/demos/eaters/Construir instruções:

Instale os darcs, libboost, Liballegro, GCC, cmake,
darcs clone --lazy http://www.mempko.com/darcs/neural/
cd neural
cmake .
make
cd demos/eaters
./eaters

Eaters Screenshot

Em janeiro de 2004, fui contactado pela Philips New Display Technologies que estava criando a eletrônica para o primeiro E-TIN Comercial, o Sony Librie, que só havia sido lançado no Japão, anos antes de a Amazon Kindle e os outros chegarem ao mercado em nós em nós uma Europa.

Os engenheiros da Philips tiveram um grande problema. Alguns meses antes de o produto chegar ao mercado, eles ainda estavam ficando fantasmas na tela ao alterar as páginas. O problema foram os 200 drivers que estavam criando o campo eletrostático. Cada um desses drivers tinha uma certa tensão que precisava ser definida entre zero e 1000 mV ou algo assim. Mas se você mudasse um deles, isso mudaria tudo.

Portanto, otimizar a tensão de cada motorista individualmente estava fora de questão. O número de possíveis combinação de valores foi em bilhões e levou cerca de 1 minuto para uma câmera especial para avaliar uma única combinação. Os engenheiros tentaram muitas técnicas de otimização padrão, mas nada chegaria perto.

O engenheiro principal entrou em contato comigo porque eu havia lançado anteriormente uma biblioteca de programação genética para a comunidade de código aberto. Ele perguntou se o GP/GA ajudaria e se eu pudesse me envolver. Fiz, e por cerca de um mês trabalhamos juntos, escrevi e sintonizando a biblioteca do GA, em dados sintéticos, e ele integrando -os ao sistema deles. Então, em um fim de semana, eles o deixaram correr ao vivo com a coisa real.

Na segunda -feira seguinte, recebi esses e -mails brilhantes dele e seu designer de hardware, sobre como ninguém poderia acreditar nos resultados surpreendentes que o GA encontrou. Era isso. Mais tarde naquele ano, o produto atingiu o mercado.

Não recebi um centavo por isso, mas obtive direitos de 'me gabando'. Eles disseram que desde o início eles já estavam acima do orçamento, então eu sabia qual era o negócio antes de começar a trabalhar nisso. E é uma ótima história para aplicações de gás. :)

Usei um GA para otimizar as tarefas de assentos na minha recepção de casamento. 80 convidados mais de 10 mesas. A função de avaliação foi baseada em manter as pessoas com suas datas, colocar pessoas com algo em comum e manter as pessoas com visões opostas extremas em mesas separadas.

Eu corri várias vezes. Cada vez, eu recebia nove tabelas boas e uma com todas as bolas estranhas. No final, minha esposa fez as tarefas de assentos.

Meu vendedor ambulante Otimizador usou um novo mapeamento de cromossomo para o itinerário, o que tornou trivial criar e mutações os cromossomos sem nenhum risco de gerar passeios inválidos.

Atualizar: Porque algumas pessoas perguntaram como ...

Comece com uma variedade de convidados (ou cidades) em algum pedido arbitrário, mas consistente, por exemplo, em alfabetizado. Chame isso de solução de referência. Pense no índice de um convidado como o número do seu assento.

Em vez de tentar codificar essa ordem diretamente no cromossomo, codificamos instruções para transformar a solução de referência em uma nova solução. Especificamente, tratamos os cromossomos como listas de índices na matriz para trocar. Para decodificar um cromossomo, começamos com a solução de referência e aplicamos todos os swaps indicados pelo cromossomo. A troca de duas entradas na matriz sempre resulta em uma solução válida: todo convidado (ou cidade) ainda aparece exatamente uma vez.

Assim, os cromossomos podem ser gerados aleatoriamente, mutados e cruzados com outros e sempre produzirão uma solução válida.

Usei algoritmos genéticos (bem como algumas técnicas relacionadas) para determinar as melhores configurações para um sistema de gerenciamento de riscos que tentou impedir que os agricultores de ouro usassem cartões de crédito roubados para pagar pelo MMOS. O sistema receberia vários milhares de transações com valores "conhecidos" (fraude ou não) e descobriria qual a melhor combinação de configurações era identificar adequadamente as transações fraudulentas sem ter muitos falsos positivos.

Tínhamos dados sobre várias dezenas de características (booleanas) de uma transação, cada uma das quais recebeu um valor e totalizou. Se o total fosse maior que um limiar, a transação foi fraude. O GA criaria um grande número de conjuntos aleatórios de valores, avaliaria -os em relação a um corpus de dados conhecidos, selecionou os que obtiveram o melhor (na detecção de fraudes e limitando o número de falsos positivos) e depois atravessa os melhores poucos de cada geração para produzir uma nova geração de candidatos. Após um certo número de gerações, o melhor conjunto de valores de pontuação foi considerado o vencedor.

Criar o corpus de dados conhecidos contra testar foi o calcanhar do sistema de Aquiles. Se você esperasse os estornos, ficou atrasado vários meses ao tentar responder aos fraudadores, para que alguém tenha que revisar manualmente um grande número de transações para construir esse corpus de dados sem ter que esperar muito tempo.

Isso acabou identificando a grande maioria da fraude que entrou, mas não conseguiu obter abaixo de 1% nos itens mais propensos a fraudes (dado que 90% das transações de entrada poderiam ser fraudes, o que estava indo muito bem).

Eu fiz tudo isso usando Perl. Uma execução do software em uma caixa Linux bastante antiga levaria de 1 a 2 horas para ser executada (20 minutos para carregar dados sobre um link WAN, o restante do tempo gasto na trituração). O tamanho de qualquer geração foi limitado pela RAM disponível. Eu o executaria repetidamente com pequenas alterações nos parâmetros, procurando um conjunto de resultados especialmente bom.

No geral, evitou algumas das gafes que vieram com a tentativa manualmente de ajustar os valores relativos de dezenas de indicadores de fraude e criaram consistentemente soluções melhores do que eu poderia criar manualmente. Afaik, ainda está em uso (cerca de 3 anos depois que eu escrevi).

Gorjeta de futebol. Eu construí um sistema de GA para prever o resultado da semana a semana de jogos na AFL (futebol do australiano Regras).

Alguns anos atrás, fiquei entediado com a piscina de futebol de trabalho padrão, todo mundo estava indo online e pegando as escolhas de algum especialista na imprensa. Então, achei que não poderia ser muito difícil vencer um monte de cursos de jornalismo de transmissão, certo? Meu primeiro pensamento foi tirar os resultados de Classificações de Massey E então revele no final da temporada minha estratégia depois de ganhar fama e glória. No entanto, por razões que nunca descobri que Massey não rastreia a AFL. O cínico em mim acredita que é porque o resultado de cada jogo da AFL basicamente se tornou chance aleatória, mas minhas queixas de mudanças recentes de regras pertencem a um fórum diferente.

O sistema basicamente considerou a força ofensiva, a força defensiva, a vantagem do campo em casa, a melhoria semana a semana (ou a falta dela) e a velocidade das mudanças em cada uma delas. Isso criou um conjunto de equações polinomiais para cada equipe durante a temporada. O vencedor e a pontuação para cada partida para uma determinada data podem ser calculados. O objetivo era encontrar o conjunto de coeficientes que mais correspondiam ao resultado de todos os jogos anteriores e usam que definidos para prever o próximo jogo das semanas.

Na prática, o sistema encontraria soluções que previam com precisão mais de 90% dos resultados do jogo passado. Em seguida, escolheria com sucesso cerca de 60 a 80% dos jogos na próxima semana (essa é a semana que não está no conjunto de treinamento).

O resultado: logo acima do meio do pacote. Nenhum grande prêmio em dinheiro nem um sistema que eu poderia usar para vencer Vegas. Foi divertido.

Eu construí tudo a partir do zero, nenhuma estrutura usada.

Bem como alguns dos problemas comuns, como o Caixeiro-viajante e de uma variação Roger Alsing Mona Lisa de programa, Eu também escrito evolução Sudoku solver (o que exigia um pouco mais de pensamento original de minha parte, ao invés de incluir somente a re-execução de outra pessoa uma idéia).Há mais confiável algoritmos para resolver Sudokus mas a abordagem evolutiva funciona bastante bem.

Nos últimos dias, eu fui brincar com um programa evolutivo para encontrar "a frio de pavimentos" do poker depois de ver este artigo no Reddit.Não é bastante satisfatório no momento, mas eu acho que eu posso melhorar.

Eu meu próprio framework que eu uso de algoritmos evolutivos.

Desenvolvi uma cerveja doméstica GA para um sistema de perfil de superfície a laser em 3D que minha empresa desenvolveu para a indústria de frete em 1992. O sistema se baseava em triangulação tridimensional e usava um scanner de linha a laser personalizado, uma câmera de 512x512 (com captura personalizada HW). A distância entre a câmera e o laser nunca seria mais precisa e o ponto focal das câmeras não foi encontrado na posição 256.256 que você esperava que fosse!

Foi um pesadelo tentar descobrir os parâmetros de calibração usando a geometria padrão e a solução simulada de equações de estilo de recozimento.

O algoritmo genético foi preparado em uma noite e eu criei um cubo de calibração para testá -lo. Eu conhecia as dimensões do cubo com alta precisão e, portanto, a idéia era que meu GA pudesse desenvolver um conjunto de parâmetros de triangulação personalizados para cada unidade de varredura que superaria as variações de produção.

O truque funcionou um deleite. Fiquei ficado para dizer o mínimo! Em cerca de 10 gerações, meu cubo 'virtual' (gerado a partir da varredura bruta e recriado a partir dos parâmetros de calibração) parecia um cubo! Depois de cerca de 50 gerações, eu tinha a calibração de que precisava.

Muitas vezes, é difícil obter uma combinação exata de cores quando você planeja pintar sua casa. Muitas vezes, você tem alguma cor em mente, mas não é uma das cores, o fornecedor mostra a você.

Ontem, meu Prof. que é pesquisador da GA mencionado sobre uma história verdadeira na Alemanha (desculpe, não tenho mais referências, sim, posso descobrir se alguém solicita). Esse cara (vamos chamá -lo de cor de cor) costumava ir da porta da porta para ajudar as pessoas a encontrar o código de cores exato (em Rgb) Esse seria o armário do que o cliente tinha em mente. Aqui está como ele faria isso:

o cor de cor Usado para carregar consigo um programa de software que usava a GA. Ele costumava começar com 4 cores diferentes- cada uma codificada como um cromossomo codificado (cujo valor decodificado seria um valor RGB). O consumidor escolhe 1 das 4 cores (que é a mais próxima da qual ele/ela tem em mente). O programa atribuiria o máximo ginástica para isso Individual e passe para o próximo geração usando mutação/crossover. As etapas acima seriam repetidas até que o consumidor encontrasse a cor exata e depois cor de cor Costumava dizer a ele a combinação RGB!

Ao atribuir adequação máxima à cor, fecha o que o consumidor tem em mente, o cor de corO programa está aumentando as chances de convergir para a cor, o consumidor tem em mente exatamente. Eu achei muito divertido!

Agora que tenho um -1, se você está planejando mais -1, pls. elucidar o motivo para fazê -lo!

Como parte do meu diploma de graduação da CompSci, recebemos o problema de encontrar sinalizadores ideais de JVM para a máquina virtual de pesquisa Jikes. Isso foi avaliado usando o DiCAPPO Benchmark Suite, que retorna um tempo ao console. Eu escrevi um alogirthm distribuído que trocou essas bandeiras para melhorar o tempo de execução da suíte de benchmark, embora levasse dias para correr para compensar o jitter de hardware que afeta os resultados. O único problema era que não aprendi corretamente sobre a teoria do compilador (que era a intenção da tarefa).

Eu poderia ter semeado a população inicial com os sinalizadores padrão existentes, mas o interessante era que o algoritmo encontrou uma configuração muito semelhante ao nível de otimização de O3 (mas na verdade foi mais rápido em muitos testes).

EDIT: Também escrevi minha própria estrutura de algoritmo genético em Python para a tarefa e apenas usei os comandos Popen para executar os vários benchmarks, embora se não fosse uma tarefa avaliada, eu teria analisado o PyEvolve.

Primeiro, "Programação Genética", de Jonathan Koza (na Amazon) é praticamente o livro sobre técnicas genéticas e evolutivas de algoritmo/programação, com muitos exemplos. Eu sugiro verificá -lo.

Quanto ao meu próprio uso de um algoritmo genético, usei um algoritmo genético (cultivado em casa) para desenvolver um algoritmo de enxame para um cenário de coleta/destruição de objetos (o objetivo prático poderia estar limpando um campo minado). Aqui está um link para o papel. A parte mais interessante do que eu fiz foi a função de condicionamento físico com vários estágios, o que era uma necessidade, pois as funções simples de condicionamento físico não forneceram informações suficientes para o algoritmo genético para diferenciar suficientemente entre os membros da população.

Algumas semanas atrás, sugeri um solução em So Usando algoritmos genéticos para resolver um problema de layout do gráfico. É um exemplo de um problema de otimização restrito.

Também na área de aprendizado de máquina, implementei uma estrutura de regras de classificação baseada no GA em C/C ++ do zero.
Eu também usei GA em um projeto de amostra para treinamento redes neurais artificiais (Ann) em vez de usar o famoso Algoritmo de backpropagação.

Além disso, e como parte da minha pesquisa de pós -graduação, usei o GA no treinamento Modelos Hidden Markov como uma abordagem adicional para o EM baseado Baum-Welch Algoritmo (em C/C ++ novamente).

Faço parte de uma equipe que investiga o uso da computação evolutiva (CE) para corrigir automaticamente bugs nos programas existentes. Reparamos com sucesso uma série de bugs reais em projetos de software do mundo real (ver a página inicial deste projeto).

Temos duas aplicações dessa técnica de reparo da CE.

O primeiro (Informações de código e reprodução disponíveis na página do projeto) Evolui as árvores de sintaxe abstrata analisadas dos programas C existentes e é implementado no OCAML usando nosso próprio mecanismo CE personalizado.
O segundo (Informações de código e reprodução disponíveis na página do projeto), minha contribuição pessoal para o projeto, evolui o código de montagem X86 ou Java Byte compilado a partir de programas escritos em várias linguagens de programação. Este aplicativo é implementado no Clojure e também usa seu próprio mecanismo CE personalizado.

Um aspecto agradável da computação evolutiva é a simplicidade da técnica, torna possível escrever suas próprias implementações personalizadas sem muita dificuldade. Para um bom texto introdutório disponível gratuitamente sobre programação genética, consulte o Guia de campo para programação genética.

Um colega de trabalho e eu estamos trabalhando em uma solução para carregar frete em caminhões usando os vários critérios que nossa empresa exige. Eu tenho trabalhado em uma solução de algoritmo genético enquanto ele usa um ramo e ligado à poda agressiva. Ainda estamos no processo de implementação dessa solução, mas até agora estamos obtendo bons resultados.

Vários anos atrás, usei GA's para otimizar as gramáticas ASR (reconhecimento automático de fala) para obter melhores taxas de reconhecimento. Comecei com listas de opções bastante simples (onde o GA estava testando combinações de termos possíveis para cada slot) e trabalhei para gramáticas mais abertas e complexas. A aptidão foi determinada medindo a separação entre termos/seqüências sob uma espécie de função de distância fonética. Também experimentei fazer variações fracamente equivalentes a uma gramática para encontrar uma que compilou uma representação mais compacta (no final, fui com um algoritmo direto e aumentou drasticamente o tamanho da "linguagem" que poderíamos usar em aplicativos) .

Mais recentemente, eu os usei como uma hipótese padrão contra a qual testar a qualidade das soluções geradas a partir de vários algoritmos. Isso envolveu amplamente a categorização e diferentes tipos de problemas de ajuste (ou seja, crie uma "regra" que explique um conjunto de opções feitas pelos revisores sobre um (s) conjunto (s)).

Fiz uma estrutura completa do GA chamada "Galab", para resolver muitos problemas:

Localizando as formigas GSM (BTS) para diminuir a sobreposição e os locais em branco.
A programação do projeto de restrição de recursos.
Criação evolutiva da imagem. (Evópico)
Problema de vendedor ambulante.
Problemas N-Queen & N-Color.
Problemas de turnê e mochila de Knight.
Magic Square e sudoku quebra -cabeças.
compactação de string, com base no problema da superestramento.
Problema de embalagem 2D.
Pequeno aplicativo de vida artificial.
Rubik Puzzle.

Uma vez usei um GA para otimizar uma função de hash para endereços de memória. Os endereços eram tamanhos de página de 4k ou 8k, por isso mostraram alguma previsibilidade no padrão de bit do endereço (bits menos significativos todos zero; bits médios que incrementam regularmente etc.) A função de hash original era "robusta" - tendia a acertos em cluster Em cada terceiro balde de hash. O algoritmo aprimorado teve uma distribuição quase perfeita.

Não sei se a lição de casa conta ...

Durante meus estudos, lançamos nosso próprio programa para resolver o problema do vendedor ambulante.

A idéia era fazer uma comparação em vários critérios (dificuldade para mapear o problema, desempenho etc.) e também usamos outras técnicas, como Recozimento simulado.

Funcionou muito bem, mas demoramos um pouco para entender como fazer a fase de 'reprodução' corretamente: modelar o problema em questão em algo adequado para a programação genética realmente me pareceu a parte mais difícil ...

Foi um curso interessante, já que também discutimos com redes neurais e coisas do gênero.

Eu gostaria de saber se alguém usou esse tipo de programação no código de 'produção'.

Eu construí um GA simples para extrair padrões úteis do espectro de frequência da música enquanto estava sendo tocado. A saída foi usada para direcionar efeitos gráficos em um plug -in do Winamp.

Entrada: alguns quadros de FFT (imagine uma variedade 2D de carros alegóricos)
Saída: Valor de flutuação única (soma ponderada de entradas), limite para 0,0 ou 1.0
Genes: pesos de entrada
Função de condicionamento físico: combinação de ciclo de trabalho, largura de pulso e BPM dentro da faixa sensata.

Eu tinha alguns gás sintonizados em diferentes partes do espectro, bem como diferentes limites de BPM, para que eles não tendem a convergir para o mesmo padrão. As saídas do top 4 de cada população foram enviadas para o mecanismo de renderização.

Um efeito colateral interessante foi que a aptidão média em toda a população era um bom indicador para mudanças na música, embora geralmente levasse 4-5 segundos para descobrir.

Como parte da minha tese, escrevi uma estrutura Java genérica para o algoritmo de otimização multi-objetiva (MPOEMS (otimização de protótipo multiobjetivo com etapas de melhoria evoluídas), que é um GA usando conceitos evolutivos. É genérico de uma maneira que todas as partes independentes de problemas tenham sido separadas das partes dependentes do problema, e uma interface é fornecida para usar a estrutura com apenas a adição das partes dependentes do problema. Assim, quem deseja usar o algoritmo não precisa começar de zero e facilita muito o trabalho.

Você pode encontrar o código aqui.

As soluções que você pode encontrar com esse algoritmo foram comparadas em um trabalho científico com os algoritmos de última geração Spea-2 e NSGA, e foi comprovado que o algoritmo tem desempenho comparável ou ainda melhor, dependendo das métricas que você Pegue para medir o desempenho e, especialmente, dependendo do problema da otimização que você está olhando.

Você pode encontrá lo aqui.

Também como parte da minha tese e prova de trabalho, apliquei essa estrutura ao problema de seleção do projeto encontrado no gerenciamento de portfólio. Trata -se de selecionar os projetos que agregam mais valor à empresa, apoiam a maioria da estratégia da empresa ou apoiam qualquer outra meta arbitrária. Por exemplo, seleção de um certo número de projetos de uma categoria específica, ou maximização de sinergias do projeto, ...

Minha tese que aplica essa estrutura ao problema de seleção do projeto:http://www.ub.tuwien.ac.at/dipl/2008/ac05038968.pdf

Depois disso, trabalhei em um departamento de gerenciamento de portfólio em um dos 500 da Fortune, onde eles usaram um software comercial que também aplicou um GA ao problema de seleção de projetos / otimização do portfólio.

Outros recursos:

A documentação da estrutura:http://thomaskremmel.com/mpoems/mpoems_in_java_documentation.pdf

Documento de apresentação de MPOEMS:http://portal.acm.org/citation.cfm?id=1792634.1792653

Na verdade, com um pouco de entusiasmo, todos poderiam adaptar facilmente o código da estrutura genérica a um problema arbitrário de otimização multi-objetiva.

No trabalho, tive o seguinte problema: dadas m tarefas e n dsps, qual era a melhor maneira de atribuir tarefas aos DSPs? "Best" foi definido como "minimizar a carga do DSP mais carregado". Havia diferentes tipos de tarefas, e vários tipos de tarefas tinham várias ramificações de desempenho, dependendo de onde foram atribuídas, então codifiquei o conjunto de atribuições de trabalho a DSP como uma "string de DNA" e depois usei um algoritmo genético para "raça" A melhor string de atribuição que eu pude.

Funcionou razoavelmente bem (muito melhor do que o meu método anterior, que era para avaliar todas as combinações possíveis ... em tamanhos de problemas não triviais, levaria anos para concluir!), O único problema era que não havia como contar Se a solução ideal tivesse sido alcançada ou não. Você só poderia decidir se o "melhor esforço" atual era bom o suficiente ou deixou que ele funcione mais para ver se poderia fazer melhor.

Houve uma competição no Codechef.com (excelente site, a propósito, competições mensais de programação), onde deveria resolver um sudoku insoluto (alguém deveria chegar o mais próximo possível com o menor número possível de columns/linhas/etc).

O que eu faria foi gerar primeiro um sudoku perfeito e depois substituir os campos, que foram dados. A partir dessa base, usei programação genética para melhorar minha solução.

Eu não conseguia pensar em uma abordagem determinística neste caso, porque o Sudoku era 300x300 e a pesquisa demoraria muito.

Usei um algoritmo genético simples para otimizar a relação sinal / ruído de uma onda que foi representada como uma corda binária. Ao virar os bits de certas maneiras de mais de vários milhões de gerações, pude produzir uma transformação que resultou em uma relação sinal / ruído mais alta dessa onda. O algoritmo também poderia ter sido "recozimento simulado", mas não foi usado neste caso. Na essência deles, os algoritmos genéticos são simples, e isso foi tão simples de um caso de uso que eu vi, então não usei uma estrutura para criação e seleção de geração-apenas uma semente aleatória e a proporção de sinal / ruído função à mão.

Em um seminário na escola, desenvolvemos um aplicativo para gerar músicas baseadas no modo musical. O programa foi construído em Java e a saída foi um arquivo MIDI com a música. Usando distintos abritos do GA para gerar a música. Eu acho que este programa pode ser útil para explorar novas composições.

Na graduação, usamos o Nero (uma combinação de rede neural e algoritmo genético) para ensinar robôs no jogo para tomar decisões inteligentes. Foi muito legal.

Desenvolvi uma simulação baseada em swing multithread da navegação por robôs através de um conjunto de terrenos randomizados de fontes e minas alimentares e desenvolvi uma estratégia baseada em algoritmo genético de explorar a otimização do comportamento robótico e a sobrevivência de genes mais aptos para um cromossomo robótico. Isso foi feito usando o gráfico e o mapeamento de cada ciclo de iteração.

Desde então, desenvolvi ainda mais comportamento de jogo. Um exemplo de aplicativo que eu construí recentemente para mim foi um algoritmo genético para resolver o problema de vendas que viajam em busca de rota no Reino Unido, levando em consideração os estados de início e metas, bem como um/múltiplo de conexão, atrasos, cancelamentos, obras, hora do rush, Greves públicas, consideração entre rotas mais rápidas versus mais baratas. Em seguida, fornecendo uma recomendação equilibrada para a rota seguir um determinado dia.

Geralmente, minha estratégia é usar a representação de genes baseada em POJO, então aplico implementações específicas de interface para seleção, mutação, estratégias de cruzamento e o ponto de critério. Minha função de aptidão então basicamente se torna um bastante complexo, com base na estratégia e nos critérios que preciso aplicar como uma medida heurística.

Também procurei a aplicação do algoritmo genético em testes automatizados no código usando ciclos de mutação sistemática em que o algoritmo entende a lógica e tenta verificar um relatório de bug com recomendações para correções de código. Basicamente, uma maneira de otimizar meu código e fornecer recomendações para melhoria, bem como uma maneira de automatizar a descoberta de um novo código programático. Também tentei aplicar algoritmos genéticos à produção musical, entre outras aplicações.

Geralmente, acho estratégias evolutivas como a maioria das estratégias de otimização metaheurística/global, elas demoram a aprender no começo, mas começam a captar à medida que as soluções se tornam cada vez mais próximas do estado do objetivo e desde que sua função de condicionamento físico e heurísticas estejam bem alinhadas para produzir Essa convergência em seu espaço de pesquisa.

Uma vez tentei fazer um player de computador para o jogo de Go, com base exclusivamente com base na programação genética. Cada programa seria tratado como uma função de avaliação para uma sequência de movimentos. Os programas produzidos não foram muito bons, mesmo em uma placa 3x4 bastante diminutiva.

Eu usei Perl e codifiquei tudo sozinho. Eu faria as coisas de maneira diferente hoje.

Depois de ler O relojoeiro cego, Eu estava interessado no programa Pascal, Dawkins disse que havia desenvolvido para criar modelos de organismos que poderiam evoluir com o tempo. Eu estava interessado o suficiente para escrever o meu usando Enxame. Eu não fiz todos os gráficos chiques que ele fez, mas meus traços controlados dos 'cromossomos afetavam a capacidade dos organismos de sobreviver. Eles viviam em um mundo simples e podiam lidar um contra o outro e seu ambiente.

Os organismos viviam ou morreram em parte devido ao acaso, mas também com base na eficácia de se adaptaram aos seus ambientes locais, quão bem eles consumiram nutrientes e com que se reproduziram com sucesso. Foi divertido, mas também mais provas para minha esposa de que eu sou um nerd.

Faz há um tempo atrás, mas eu rolei um GA para evoluir o que estava na verdade, os kernels de processamento de imagens para remover rastreios de raios cósmicos das imagens do Telescópio Espacial Hubble (HST). A abordagem padrão é adotar várias exposições com o Hubble e manter apenas as coisas que são as mesmas em todas as imagens. Como o HST é tão valioso, sou um fã de astronomia e recentemente participou do Congresso sobre computação evolutiva, pensei em usar um GA para limpar as exposições únicas.

Os indivíduos estavam na forma de árvores que adotaram uma área de 3x3 pixels como entrada, realizaram alguns cálculos e produziram uma decisão sobre se e como modificar o pixel central. A aptidão foi julgada comparando a saída com uma imagem limpa da maneira tradicional (ou seja, as exposições de empilhamento).

Na verdade, ele meio que funcionou, mas não o suficiente para justificar a abordagem original. Se eu não tivesse sido restrito ao tempo da minha tese, poderia ter expandido a caixa de peças genéticas disponíveis para o algoritmo. Tenho certeza de que poderia ter melhorado significativamente.

Bibliotecas usadas: Se bem me lembro, IRAF e CFITSIO para processamento de dados de imagem astronômicos e E/S.

Eu experimentei GA na minha juventude. Eu escrevi um simulador em Python que funcionou da seguinte maneira.

Os genes codificaram os pesos de uma rede neural.

Os insumos da rede neural eram "antenas" que detectaram toques. Valores mais altos significavam muito perto e 0 significava não tocar.

As saídas foram para duas "rodas". Se as duas rodas fossem avançadas, o cara avançava. Se as rodas estavam em direções opostas, o cara se virou. A força da saída determinou a velocidade da roda girando.

Um labirinto simples foi gerado. Era muito simples-até mesmo. Houve o início na parte inferior da tela e um gol no topo, com quatro paredes no meio. Cada parede tinha um espaço retirado aleatoriamente, então sempre havia um caminho.

Comecei caras aleatórios (pensei neles como insetos) no início. Assim que um cara atingiu o gol, ou foi alcançado um limite de tempo, a aptidão foi calculada. Era inversamente proporcional à distância da meta naquela época.

Em seguida, eu os combinei e os "criei" para criar a próxima geração. A probabilidade de ser escolhida para ser criada foi proporcional à sua aptidão. Às vezes, isso significava que alguém era criado sozinho repetidamente se tivesse uma aptidão relativa muito alta.

Eu pensei que eles desenvolveriam um comportamento de "parede esquerda", mas sempre pareciam seguir algo menos ideal. Em todos os experimentos, os insetos convergiram para um padrão em espiral. Eles espiralavam para fora até tocarem uma parede à direita. Eles seguiam isso, então, quando chegaram à brecha, se afastariam (longe da lacuna) e ao redor. Eles dariam uma volta de 270 graus para a esquerda e geralmente entrava na lacuna. Isso os levaria através da maioria das paredes e, muitas vezes, ao objetivo.

Um recurso que acrescentei foi colocar um vetor de cores nos genes para rastrear a relação entre os indivíduos. Depois de algumas gerações, todas elas seriam da mesma cor, o que me diz que eu deveria ter uma estratégia de melhoramento melhor.

Tentei fazê -los desenvolver uma estratégia melhor. Complicei a rede neural-adquirindo uma memória e tudo mais. Não ajudou. Eu sempre vi a mesma estratégia.

Eu tentei várias coisas como ter pools de genes separados que apenas se recombinaram após 100 gerações. Mas nada os levaria a uma estratégia melhor. Talvez fosse impossível.

Outra coisa interessante é representar graficamente a aptidão ao longo do tempo. Havia padrões definitivos, como a aptidão máxima que cai antes de subir. Eu nunca vi um livro de evolução falar sobre essa possibilidade.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow