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

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

Gostaria de saber sobre problemas específicos que você resolveu usando o GA / GP e quais bibliotecas / estruturas você usou se não criou o seu próprio.

Questões:

• Quais problemas você usou o GA / GP para resolver?
• Quais bibliotecas / estruturas você usou?

Estou procurando experiências em primeira mão, por isso não responda a menos que tenha.

Não dever de casa.

Meu primeiro trabalho como programador profissional (1995) foi escrever um sistema de negociação automatizado baseado em algoritmos genéticos para futuros de S & P500. O aplicativo foi escrito em Visual Basic 3 [!] E eu não tenho ideia de como eu fazia alguma coisa naquela época, pois o VB3 nem tinha aulas.

O aplicativo começou com uma população de seqüências de comprimento fixo geradas aleatoriamente (a parte "gene"), cada uma correspondendo a uma forma específica nos dados de preços minuto a minuto dos futuros do S & P500, bem como uma ordem específica (compra ou venda) e valores de stop loss e stop profit. Cada sequência (ou "gene") teve seu desempenho de lucro avaliado por uma execução de três anos de dados históricos; sempre que a "forma" especificada correspondia aos dados históricos, assumi a ordem de compra ou venda correspondente e avaliei o resultado do negócio. Acrescentei a ressalva de que cada gene começava com uma quantia fixa de dinheiro e, portanto, poderia potencialmente quebrar e ser totalmente removido do pool genético.

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

Infelizmente, nunca tive a chance de usar esse sistema ao vivo, pois meu chefe perdeu quase US $ 100.000 em menos de três meses negociando da maneira tradicional e perdeu a vontade de continuar com o projeto. Em retrospecto, acho que o sistema teria lucros enormes - não porque eu estivesse necessariamente fazendo algo certo, mas porque a população de genes que eu produzi era tendenciosa em relação aos pedidos de compra (em oposição aos pedidos de venda) em cerca de 5: 1 proporção. E como sabemos com nossa retrospectiva 20/20, o mercado subiu um pouco depois de 1995.

Fiz algumas criaturas que viviam neste pequeno mundo. Eles tinham um cérebro de rede neural que recebeu algumas informações do mundo e a saída foi um vetor de 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 neurônios de entrada e saída eram estáticos, mas o que havia entre eles não era.

O ambiente continha comida e perigos. A comida aumentou a energia e, quando você tem energia suficiente, pode acasalar. Os perigos reduziriam a energia e, se a energia fosse 0, eles morreriam.

Eventualmente, as criaturas evoluíram para se mover pelo mundo, 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 "ouvido". Começou de novo e ficou surpreso ao descobrir que eles evoluíram para maximizar o espaço e cada criatura respectiva ficaria em sua respectiva parte (a comida era colocada aleatoriamente). Eles aprenderam a cooperar uns com os outros e a não interferir uns com os outros. Sempre havia as exceções.

Então eu tentei algo interessante. Eu criaturas mortas se tornariam comida. Tente adivinhar o que aconteceu! Dois tipos de criaturas evoluíram, as que atacavam como enxames e as que eram altas para evitar.

Então, qual é a lição aqui? Comunicação significa cooperação. Assim que você introduz um elemento em que ferir outro significa que você ganha alguma coisa, a cooperação é destruída.

Eu me pergunto como isso se reflete no sistema de livre mercado e capitalismo. Quero dizer, se as empresas podem prejudicar a concorrência e se safar , então está claro que farão tudo o que estiver ao seu alcance para prejudicar a concorrência.

Editar:

Eu escrevi em C ++ usando nenhuma estrutura. Escrevi minha própria rede neural e código GA. Eric, obrigado por dizer que é plausível. As pessoas geralmente não acreditam nos poderes da AG (embora as limitações sejam óbvias) até brincarem com ela. O GA é simples, mas não simplista.

Para os que duvidam, foi comprovado que as redes neurais são capazes de simular qualquer função se elas tiverem mais de uma camada. O GA é uma maneira bastante simples de navegar em um espaço de solução, encontrando o mínimo local e potencialmente global. Combine o GA com redes neurais e você terá uma ótima maneira de encontrar funções que encontrem soluções aproximadas para problemas genéricos. Como estamos usando redes neurais, otimizamos a função para algumas entradas, não algumas para uma função, enquanto outras estão usando o GA

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

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

Em janeiro de 2004, fui contactado pela Philips New Display Technologies, que criava os eletrônicos para a primeira tinta eletrônica comercial, a Sony Librie, lançada apenas no Japão, anos antes de o Amazon Kindle e os outros chegarem ao mercado nos EUA. uma Europa.

Os engenheiros da Philips tiveram um grande problema. Alguns meses antes do produto chegar ao mercado, eles ainda estavam aparecendo na tela ao trocar de página. 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 ajustada entre zero e 1000 mV ou algo assim. Mas se você mudasse um deles, tudo mudaria.

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

O engenheiro chefe entrou em contato comigo porque eu havia lançado uma biblioteca de programação genética para a comunidade de código aberto. Ele perguntou se os GPs / GAs ajudariam e se eu poderia me envolver. Eu fiz, e por cerca de um mês nós trabalhamos juntos, eu escrevendo e ajustando a biblioteca do GA, em dados sintéticos, e ele integrando-o ao sistema deles. Então, em um fim de semana, eles o deixaram viver com a coisa real.

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

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

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

Eu corri várias vezes. Cada vez, tenho nove boas mesas e uma com todas as bolas estranhas. No final, minha esposa fez as designações de assentos.

Meu otimizador de vendedor ambulante usou um novo mapeamento do cromossomo para o itinerário, o que tornou trivial criar e alterar os cromossomos sem nenhum risco de gerar visitas inválidas.

Atualização : porque algumas pessoas perguntaram como ...

Comece com uma variedade de convidados (ou cidades) em alguma ordem arbitrária, mas consistente, por exemplo, em ordem alfabética. Chame isso de solução de referência. Pense no índice de um hóspede como seu número de 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 a serem trocados. 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 hóspede (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 tentava impedir os fazendeiros de ouro de usar cartões de crédito roubados para pagar MMOs. O sistema realizaria vários milhares de transações com valores "conhecidos" (fraude ou não) e descobriria qual era a melhor combinação de configurações para identificar corretamente 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 superior a um limite, a transação era fraudulenta. O GA criaria um grande número de conjuntos aleatórios de valores, os avaliaria em relação a um corpus de dados conhecidos, selecionaria aqueles que obtiveram a melhor pontuação (tanto na detecção de fraudes quanto na limitação do número de falsos positivos) e cruzaria os melhores 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 foi considerado o vencedor.

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

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

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

No fim das contas, evitou algumas das gafes que surgiram com a tentativa de ajustar manualmente os valores relativos de dezenas de indicadores de fraude, e sempre surgiram 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. Criei um sistema de GA para prever o resultado semanal dos jogos na AFL (Aussie Rules Football).

Alguns anos atrás, eu estava entediado com o pool de futebol profissional padrão, todo mundo estava entrando na internet e fazendo escolhas de algum especialista na imprensa. Então, achei que não seria muito difícil derrotar um monte de especialistas em jornalismo de transmissão, certo? Meu primeiro pensamento foi pegar os resultados da Massey Ratings e depois revelar no final da temporada minha estratégia depois de ganhar fama e glória. No entanto, por razões que nunca descobri, Massey não rastreia o AFL. O cínico em mim acredita que é porque o resultado de cada jogo da AFL se tornou basicamente uma chance aleatória, mas minhas queixas de mudanças recentes nas regras pertencem a um fórum diferente.

O sistema considerou basicamente 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 ao longo da temporada. O vencedor e a pontuação de cada partida em uma determinada data podem ser computados. O objetivo era encontrar o conjunto de coeficientes que mais se aproximasse do resultado de todos os jogos anteriores e usá-lo para prever o jogo das próximas semanas.

Na prática, o sistema encontraria soluções que previssem com precisão mais de 90% dos resultados de jogos anteriores. Em seguida, ele selecionava com sucesso de 60 a 80% dos jogos para a próxima semana (que é 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 pudesse usar para vencer Las Vegas. Foi divertido.

Eu construí tudo do zero, sem estrutura usada.

Além de alguns problemas comuns, como o Vendedor ambulante e uma variação do programa Mona Lisa de Roger Alsing , também escrevi um solucionador evolutivo de Sudoku (que exigia um pouco mais de originalidade da minha parte, em vez de apenas reimplementar idéia de outra pessoa). Existem algoritmos mais confiáveis ​​para resolver o Sudokus, mas a abordagem evolutiva funciona bastante bem.

Nos últimos dias, tenho brincado com um programa evolutivo para encontrar "decks frios" para poker depois de ver este artigo no Reddit. Não é muito satisfatório no momento, mas acho que posso melhorá-lo.

Eu tenho minha própria estrutura que eu uso para algoritmos evolutivos.

Desenvolvi um GA caseiro para um sistema de perfil de superfície a laser 3D que minha empresa desenvolveu para o setor de frete em 1992. O sistema contava com 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 precisa e o ponto focal das câmeras não seria encontrado na posição 256.256 que você esperava!

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

O algoritmo genético foi criado 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 ideia era que meu GA pudesse desenvolver um conjunto de parâmetros de triangulação personalizados para cada unidade de digitalização que superasse as variações de produção.

O truque funcionou. Fiquei pasmo por 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! Após cerca de 50 gerações, tive a calibração necessária.

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, mostra o fornecedor.

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

O cara da cor costumava levar consigo um programa de software que usava o 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 uma das quatro cores (qual é a mais próxima da qual ele / ela tem em mente). O programa atribuiria a máxima aptidão a esse indivíduo e passaria para a próxima geração usando mutação / cruzamento . As etapas acima seriam repetidas até que o consumidor encontrasse a cor exata e o cara da cor costumava dizer a ele a combinação RGB!

Ao atribuir o máximo de adequação à cor, aproxima-se do que o consumidor tem em mente, o programa do profissional de cores está aumentando as chances de convergir para a cor, e o consumidor tem exatamente em mente. Achei muito divertido!

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

Há algumas semanas, sugeri uma solução em SO usando algoritmos genéticos para resolver um problema de layout de 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 em GA em c / c ++ do zero.
Também usei o GA em um projeto de amostra para treinar redes neurais artificiais (RNA), em vez de usar o famoso algoritmo de retropropagação .

Além disso, e como parte de minha pesquisa de graduação, usei o GA no treinamento de Modelos Hidden Markov como uma abordagem adicional ao algoritmo Baum-Welch baseado em EM (novamente em c / c ++).

Como parte do meu curso de graduação em CompSci, recebemos o problema de encontrar sinalizadores de jvm ideais para a máquina virtual de pesquisa da Jikes. Isso foi avaliado usando o conjunto de benchmarks Dicappo, que retorna um tempo para o console. Escrevi um alogirthm gentic distribuído que alternava esses sinalizadores para melhorar o tempo de execução do conjunto de benchmarks, embora demorasse dias para compensar a instabilidade do hardware que afetava os resultados. O único problema foi que eu não aprendi adequadamente sobre a teoria do compilador (que era a intenção da tarefa).

Eu poderia ter propagado a população inicial com os sinalizadores padrão existentes, mas o interessante foi que o algoritmo encontrou uma configuração muito semelhante ao nível de otimização do 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 atribuição e apenas usei os comandos popen para executar os vários benchmarks, embora, se não fosse uma atribuição avaliada, eu teria examinado o pyEvolve.

Primeiro, "Genetic Programming", de Jonathan Koza ( na amazônia ), é praticamente o livro sobre técnicas de algoritmos / programação genéticos e evolutivos, com muitos exemplos. Eu sugiro verificá-lo.

Quanto ao meu próprio uso de um algoritmo genético, usei um algoritmo genético (produzido em casa) para desenvolver um algoritmo de enxame para um cenário de coleta / destruição de objetos (o objetivo prático poderia ter sido limpar um campo minado). Aqui está um link para o artigo . A parte mais interessante do que eu fiz foi a função de condicionamento físico de várias etapas, que era uma necessidade, uma vez que as funções simples de condicionamento físico não forneciam informações suficientes para que o algoritmo genético se diferenciasse suficientemente entre os membros da população.

Faço parte de uma equipe que investiga o uso da Computação Evolutiva (EC) para corrigir automaticamente erros nos programas existentes. Consertamos com êxito vários bugs reais em projetos de software do mundo real (consulte a página inicial deste projeto ).

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

• O primeiro ( informações de código e reprodução disponíveis na página do projeto ) desenvolve as árvores de sintaxe abstrata analisadas dos programas C existentes e é implementado no Ocaml usando nosso próprio mecanismo de EC personalizado.

• O segundo ( informações de código e reprodução disponíveis na página do projeto ), minha contribuição pessoal ao projeto, evolui o assembly x86 ou o código de byte Java compilado a partir de programas escritos em várias linguagens de programação. Esse aplicativo é implementado no Clojure e também usa seu próprio mecanismo EC personalizado.

Um aspecto interessante da Computação Evolucionária é a simplicidade da técnica, que permite 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 .

Eu e um colega de trabalho estamos trabalhando em uma solução para carregar mercadorias em caminhões usando os vários critérios exigidos por nossa empresa. Eu tenho trabalhado em uma solução de algoritmo genético enquanto ele está usando um Branch And Bound com poda agressiva. Ainda estamos no processo de implementação desta solução, mas até agora estamos obtendo bons resultados.

Vários anos atrás, usei ga's para otimizar 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 até gramáticas mais abertas e complexas. O condicionamento físico foi determinado medindo a separação entre termos / sequências sob um tipo de função de distância fonética. Também experimentei fazer variações fracamente equivalentes em uma gramática para encontrar uma que fosse compilada para uma representação mais compacta (no final, eu fui com um algoritmo direto, e aumentou drasticamente o tamanho da "linguagem" que poderíamos usar nos aplicativos) .

Mais recentemente, eu as 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 (por exemplo, crie uma "regra" que explique um conjunto de escolhas feitas pelos revisores sobre um (s) conjunto (s) de dados).

Eu criei uma estrutura completa do GA chamada "GALAB", para resolver muitos problemas:

• localizando GSM ANTs (BTS) para diminuir a sobreposição e os locais em branco.
• Planejamento de projeto de restrição de recurso.
• Criação de imagem evolutiva. ( Evopic )
• Problema de vendedor ambulante.
• Problemas com N-Queen e N-Color.
• Turnê de Knight e problemas de mochila.
• Quadrado mágico e quebra-cabeças de Sudoku.
• compactação de string, com base no problema de supercorda.
• Problema de empacotamento 2D.
• Pequena vida artificial APP.
• Quebra-cabeça Rubik.

Uma vez eu 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, portanto, eles mostraram alguma previsibilidade no padrão de bits do endereço (bits menos significativos todos zero; bits do meio incrementando regularmente etc.) A função hash original era "robusta" - tendia a obter hits do cluster em cada terceiro balde de hash. O algoritmo aprimorado tinha uma distribuição quase perfeita.

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

Durante meus estudos, desenvolvemos nosso próprio programa para resolver o problema do Vendedor ambulante.

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

Funcionou muito bem, mas demorou um pouco para entender como executar 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, pois também nos envolvemos com redes neurais e similares.

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

Criei um GA simples para extrair padrões úteis do espectro de frequência da música enquanto ela estava sendo tocada. A saída foi usada para gerar efeitos gráficos em um plugin do winamp.

• Entrada: alguns quadros FFT (imagine uma matriz 2D de flutuadores)
• Saída: valor flutuante único (soma ponderada de entradas), com limite de 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 GAs sintonizados em diferentes partes do espectro, bem como em diferentes limites de BPM, para que eles não tendessem a convergir para o mesmo padrão. As saídas das 4 principais de cada população foram enviadas para o mecanismo de renderização.

Um efeito colateral interessante foi que o condicionamento físico médio em toda a população era um bom indicador de 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 multiobjetivo mPOEMS (otimização de protótipo multiobjetivo com etapas de aprimoramento evoluídas), que é um AG usando conceitos evolutivos. É genérico de uma maneira que todas as partes independentes do problema foram separadas das partes dependentes do problema e uma interface é oferecida para usar a estrutura, adicionando apenas as partes dependentes do problema. Portanto, quem deseja usar o algoritmo não precisa começar do 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 ponta SPEA-2 e NSGA, e ficou provado que o algoritmo tem desempenho comparável ou até melhor, dependendo das métricas que você tome para medir o desempenho e, principalmente, dependendo do problema de otimização que você está procurando.

Você pode encontrá-lo aqui .

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

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

Depois disso, trabalhei em um departamento de gerenciamento de portfólio em uma das empresas listadas na Fortune 500, onde eles usaram um software comercial que também aplicava um AG ao problema de seleção de projetos / otimização de portfólio.

Mais recursos:

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

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

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

No trabalho, tive o seguinte problema: dadas tarefas M e N DSPs, qual era a melhor maneira de atribuir tarefas aos DSPs? "Melhor" 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 elas foram atribuídas, por isso codifiquei o conjunto de atribuições de trabalho para DSP como uma "sequência de DNA" e depois usei um algoritmo genético para "reproduzir" a melhor sequência de tarefas que pude.

Funcionou razoavelmente bem (muito melhor que o meu método anterior, que era avaliar todas as combinações possíveis ... em tamanhos de problemas não triviais, levaria anos para ser concluído!), O único problema era que não havia como saber se a solução ideal foi alcançada ou não. Você só pode decidir se o "melhor esforço" atual é bom o suficiente ou deixá-lo demorar mais para ver se poderia fazer melhor.

Havia uma competição no codechef.com (a propósito, um ótimo site, competições de programação mensais) em que se deveria resolver um sudoku insolúvel (deve-se chegar o mais próximo possível com o mínimo de colunas / linhas / etc erradas possível).

O que eu faria era primeiro gerar um sudoku perfeito e depois substituir os campos que foram fornecidos. A partir dessa base bastante boa, usei a 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 de 300x300 e a pesquisa levaria muito tempo.

Usei um algoritmo genético simples para otimizar a relação sinal / ruído de uma onda representada como uma sequência binária. Ao inverter os bits de várias maneiras ao longo de vários milhões de gerações, pude produzir uma transformação que resultou em uma maior relação sinal / ruído dessa onda. O algoritmo também poderia ter sido "Simulated Annealing", mas não foi usado neste caso. Basicamente, os algoritmos genéticos são simples, e esse foi o caso de uso mais simples que eu já vi, então não usei uma estrutura para criação e seleção de geração - apenas uma semente aleatória e a Relação Sinal-Ruído. função na mão.

Em um seminário na escola, desenvolvemos um aplicativo para gerar música com base no modo musical. O programa foi construído em Java e a saída era um arquivo midi com a música. Estamos usando distinções de GA para gerar a música. Eu acho que esse 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 a tomar decisões inteligentes. Foi bem legal.

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

Desde então, desenvolvi ainda mais o comportamento do jogo. Um exemplo de aplicativo que criei recentemente para mim foi um algoritmo genético para resolver o problema do vendedor ambulante na localização de rotas no Reino Unido, levando em consideração os estados de início e objetivo, além de um / vários pontos de conexão, atrasos, cancelamentos, obras, hora do rush, greves públicas, consideração entre as rotas mais rápidas e as mais baratas. Em seguida, forneça uma recomendação equilibrada para a rota seguir em um determinado dia.

Geralmente, minha estratégia é usar a representação de genes com base em POJO, depois 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 condicionamento físico se torna basicamente bastante complexa com base na estratégia e nos critérios que preciso aplicar como medida heurística.

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

Geralmente, acho que estratégias evolutivas, como a maioria das estratégias metaheurísticas / de otimização global, são lentas para aprender no início, mas começam a se intensificar à medida que as soluções se aproximam cada vez mais do estado da meta e desde que sua função e heurísticas de aptidão estejam bem alinhadas para produzir essa convergência dentro do seu espaço de pesquisa.

Certa vez, tentei criar um player de computador para o jogo Go, baseado exclusivamente em 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 reduzida.

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

Depois de ler O relojoeiro cego , fiquei interessado no programa pascal que Dawkins disse que havia desenvolvido para criar modelos de organismos que poderiam evoluir ao longo do tempo. Eu estava interessado o suficiente para escrever meu próprio usando o Swarm . Eu não fiz todos os gráficos criativos de fantasia que ele fez, mas meus traços controlados pelos 'cromossomos' que afetavam a capacidade de sobrevivência dos organismos. Eles viviam em um mundo simples e podiam lutar um contra o outro e contra o meio ambiente.

Os organismos viveram ou morreram em parte devido ao acaso, mas também com base na eficácia com que se adaptaram ao ambiente local, na qualidade de consumo de nutrientes e no sucesso com a reprodução. Foi divertido, mas também mais uma prova para minha esposa de que sou um nerd.

Foi há um tempo atrás, mas eu criei um GA para evoluir o que estava em efeito kernels de processamento de imagem para remover traços de raios cósmicos das imagens do Hubble Space Telescope (HST). A abordagem padrão é fazer várias exposições com o Hubble e manter apenas as coisas iguais em todas as imagens. Como o tempo de HST é tão valioso, sou um fã de astronomia e recentemente participei do Congresso sobre Computação Evolucionária, pensei em usar um AG para limpar exposições únicas.

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

Na verdade, meio que funcionou, mas não o suficiente para justificar a abordagem original. Se eu não estivesse com o tempo limitado pela minha tese, poderia ter expandido a lista de peças genéticas disponível 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ômica e E / S.

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

Os genes codificaram os pesos de uma rede neural.

As entradas da rede neural eram "antenas" que detectavam toques. Valores mais altos significavam muito próximos e 0 significava não tocar.

As saídas foram para duas "rodas". Se as duas rodas avançavam, o cara avançava. Se as rodas estivessem em direções opostas, o sujeito girava. A força da saída determinou a velocidade do giro da roda.

Um labirinto simples foi gerado. Era realmente simples - até estúpido. 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 bugs) no início. Assim que um cara alcançou a meta, ou um limite de tempo foi atingido, a aptidão foi calculada. Era inversamente proporcional à distância da meta naquele momento.

Eu então os emparelhei e os "criei" para criar a próxima geração. A probabilidade de ser escolhido para ser criado foi proporcional à sua adequação. Às vezes, isso significava que alguém era criado repetidamente se possuía uma aptidão relativa muito alta.

Eu pensei que eles desenvolveriam um comportamento de "abraço na parede esquerda", mas eles sempre pareciam seguir algo menos ideal. Em todos os experimentos, os bugs convergiam para um padrão espiral. Eles espiralariam para fora até tocarem uma parede à direita. Eles seguiriam isso e, quando chegassem à brecha, iriam espiralar para baixo (longe da brecha) e dar a volta. Eles faziam uma curva de 270 graus para a esquerda e geralmente entravam na brecha. Isso os levaria através da maioria dos muros, e freqüentemente até o objetivo.

Uma característica que eu adicionei foi colocar um vetor de cor nos genes para rastrear a relação entre indivíduos. Depois de algumas gerações, todos teriam a mesma cor, o que me diz que eu deveria ter uma melhor estratégia de criação.

Eu tentei fazê-los desenvolver uma estratégia melhor. Eu compliquei a rede neural - adicionando uma memória e tudo. Isso não ajudou. Eu sempre vi a mesma estratégia.

Tentei várias coisas, como ter conjuntos de genes separados que só 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 definidos, como o máximo de condicionamento físico antes de subir. Eu nunca vi um livro de evolução falar sobre essa possibilidade.