Algoritmo genético - Genetic algorithm

A antena da espaçonave NASA ST5 de 2006 . Esta forma complicada foi encontrada por um programa evolutivo de design de computador para criar o melhor padrão de radiação. É conhecido como uma antena evoluída .

Em ciência da computação e pesquisa operacional , um algoritmo genético ( GA ) é uma metaheurística inspirada no processo de seleção natural que pertence à classe maior de algoritmos evolutivos (EA). Os algoritmos genéticos são comumente usados ​​para gerar soluções de alta qualidade para problemas de otimização e pesquisa, contando com operadores inspirados biologicamente, como mutação , cruzamento e seleção .

Metodologia

Problemas de otimização

Em um algoritmo genético, uma população de soluções candidatas (chamadas de indivíduos, criaturas ou fenótipos ) para um problema de otimização é desenvolvida em direção a melhores soluções. Cada solução candidata tem um conjunto de propriedades (seus cromossomos ou genótipo ) que podem sofrer mutação e alteração; tradicionalmente, as soluções são representadas em binário como strings de 0s e 1s, mas outras codificações também são possíveis.

A evolução geralmente começa a partir de uma população de indivíduos gerados aleatoriamente e é um processo iterativo , com a população em cada iteração chamada de geração . Em cada geração, a aptidão de cada indivíduo na população é avaliada; a adequação geralmente é o valor da função objetivo no problema de otimização que está sendo resolvido. Os indivíduos mais aptos são selecionados estocasticamente da população atual, e o genoma de cada indivíduo é modificado ( recombinado e possivelmente mutado aleatoriamente) para formar uma nova geração. A nova geração de soluções candidatas é então usada na próxima iteração do algoritmo . Normalmente, o algoritmo termina quando um número máximo de gerações foi produzido ou um nível de aptidão satisfatório foi alcançado para a população.

Um algoritmo genético típico requer:

  1. uma representação genética do domínio da solução,
  2. uma função de aptidão para avaliar o domínio da solução.

Uma representação padrão de cada solução candidata é como uma matriz de bits (também chamada de conjunto de bits ou sequência de bits ). Arrays de outros tipos e estruturas podem ser usados ​​essencialmente da mesma maneira. A principal propriedade que torna essas representações genéticas convenientes é que suas partes são facilmente alinhadas devido ao seu tamanho fixo, o que facilita operações de crossover simples . Representações de comprimento variável também podem ser usadas, mas a implementação de crossover é mais complexa neste caso. As representações em forma de árvore são exploradas na programação genética e as representações em forma de gráfico são exploradas na programação evolutiva ; uma mistura de cromossomos lineares e árvores é explorada na programação de expressão gênica .

Uma vez que a representação genética e a função de aptidão são definidas, um AG passa a inicializar uma população de soluções e então a melhorá-la através da aplicação repetitiva dos operadores de mutação, cruzamento, inversão e seleção.

Inicialização

O tamanho da população depende da natureza do problema, mas normalmente contém várias centenas ou milhares de soluções possíveis. Muitas vezes, a população inicial é gerada de forma aleatória, permitindo toda a gama de soluções possíveis (o espaço de busca ). Ocasionalmente, as soluções podem ser "semeadas" em áreas onde as soluções ideais podem ser encontradas.

Seleção

Durante cada geração sucessiva, uma parte da população existente é selecionada para gerar uma nova geração. Soluções individuais são seleccionados através de uma -base aptidão processo, onde ajustador soluções (como medido por uma função de fitness ) são geralmente mais susceptíveis de ser seleccionado. Certos métodos de seleção avaliam a adequação de cada solução e selecionam preferencialmente as melhores soluções. Outros métodos avaliam apenas uma amostra aleatória da população, pois o primeiro processo pode consumir muito tempo.

A função de aptidão é definida sobre a representação genética e mede a qualidade da solução representada. A função de fitness é sempre dependente do problema. Por exemplo, no problema da mochila, deseja-se maximizar o valor total dos objetos que podem ser colocados em uma mochila de alguma capacidade fixa. A representação de uma solução pode ser um array de bits, onde cada bit representa um objeto diferente, e o valor do bit (0 ou 1) representa se o objeto está ou não na mochila. Nem toda representação é válida, pois o tamanho dos objetos pode ultrapassar a capacidade da mochila. A adequação da solução é a soma dos valores de todos os objetos da mochila se a representação for válida, ou 0 caso contrário.

Em alguns problemas, é difícil ou mesmo impossível definir a expressão de aptidão; nestes casos, uma simulação pode ser usada para determinar o valor da função de aptidão de um fenótipo (por exemplo, a dinâmica de fluidos computacional é usada para determinar a resistência do ar de um veículo cuja forma é codificada como o fenótipo), ou mesmo algoritmos genéticos interativos são usados.

Operadores genéticos

A próxima etapa é gerar uma população de segunda geração de soluções daqueles selecionados por meio de uma combinação de operadores genéticos : crossover (também chamado de recombinação) e mutação .

Para cada nova solução a ser produzida, um par de soluções "pai" é selecionado para reprodução a partir do pool selecionado anteriormente. Ao produzir uma solução "filha" usando os métodos acima de crossover e mutação, uma nova solução é criada que normalmente compartilha muitas das características de seus "pais". Novos pais são selecionados para cada novo filho e o processo continua até que uma nova população de soluções de tamanho apropriado seja gerada. Embora os métodos de reprodução baseados no uso de dois pais sejam mais "inspirados na biologia", algumas pesquisas sugerem que mais de dois "pais" geram cromossomos de melhor qualidade.

Em última análise, esses processos resultam na população de cromossomos de próxima geração que é diferente da geração inicial. Geralmente, a aptidão média terá aumentado por este procedimento para a população, uma vez que apenas os melhores organismos da primeira geração são selecionados para reprodução, junto com uma pequena proporção de soluções menos adequadas. Essas soluções menos adequadas garantem a diversidade genética dentro do pool genético dos pais e, portanto, garantem a diversidade genética da geração subsequente de filhos.

As opiniões estão divididas sobre a importância do cruzamento versus mutação. Existem muitas referências em Fogel (2006) que suportam a importância da pesquisa baseada em mutação.

Embora o cruzamento e a mutação sejam conhecidos como os principais operadores genéticos, é possível usar outros operadores, como reagrupamento, colonização-extinção ou migração em algoritmos genéticos.

Vale a pena ajustar parâmetros como probabilidade de mutação , probabilidade de cruzamento e tamanho da população para encontrar configurações razoáveis ​​para a classe do problema que está sendo trabalhada. Uma taxa de mutação muito pequena pode levar à deriva genética (que é de natureza não ergódica ). Uma taxa de recombinação muito alta pode levar à convergência prematura do algoritmo genético. Uma taxa de mutação muito alta pode levar à perda de boas soluções, a menos que a seleção elitista seja empregada. Um tamanho populacional adequado garante diversidade genética suficiente para o problema em questão, mas pode levar ao desperdício de recursos computacionais se definido com um valor maior do que o necessário.

Heurísticas

Além dos operadores principais acima, outras heurísticas podem ser empregadas para tornar o cálculo mais rápido ou robusto. A heurística de especiação penaliza o cruzamento entre soluções candidatas que são muito semelhantes; isso incentiva a diversidade da população e ajuda a prevenir a convergência prematura para uma solução menos ideal.

Terminação

Este processo geracional é repetido até que uma condição de término seja alcançada. As condições de rescisão comuns são:

  • Foi encontrada uma solução que satisfaz os critérios mínimos
  • Número fixo de gerações alcançadas
  • Orçamento alocado (tempo de computação / dinheiro) atingido
  • A adequação da solução de classificação mais alta está atingindo ou atingiu um patamar tal que as iterações sucessivas não produzem mais resultados melhores
  • Inspeção manual
  • Combinações das opções acima

A hipótese do bloco de construção

Os algoritmos genéticos são simples de implementar, mas seu comportamento é difícil de entender. Em particular, é difícil entender por que esses algoritmos freqüentemente têm sucesso na geração de soluções de alta adequação quando aplicados a problemas práticos. A hipótese do bloco de construção (BBH) consiste em:

  1. Uma descrição de uma heurística que realiza a adaptação ao identificar e recombinar "blocos de construção", ou seja, esquemas de ordem baixa e comprimento de definição baixo com aptidão acima da média.
  2. Uma hipótese de que um algoritmo genético realiza a adaptação implementando implícita e eficientemente esta heurística.

Goldberg descreve a heurística da seguinte forma:

"Esquemas curtos, de baixa ordem e altamente ajustados são amostrados, recombinados [cruzados] e reamostrados para formar strings de aptidão potencialmente mais alta. De certa forma, ao trabalhar com esses esquemas específicos [os blocos de construção], reduzimos a complexidade do nosso problema; em vez de construir strings de alto desempenho tentando todas as combinações concebíveis, construímos strings cada vez melhores a partir das melhores soluções parciais de amostragens anteriores.
"Como os esquemas altamente ajustados de comprimento de definição baixa e ordem inferior desempenham um papel tão importante na ação dos algoritmos genéticos, já demos a eles um nome especial: blocos de construção. Assim como uma criança cria fortalezas magníficas por meio do arranjo de blocos simples de madeira, o mesmo ocorre com um algoritmo genético que busca um desempenho próximo ao ótimo por meio da justaposição de esquemas ou blocos de construção curtos, de baixa ordem e alto desempenho. "

Apesar da falta de consenso quanto à validade da hipótese de construção, ela tem sido avaliada de forma consistente e usada como referência ao longo dos anos. Muitos algoritmos de estimativa de distribuição , por exemplo, foram propostos na tentativa de fornecer um ambiente no qual a hipótese se sustentaria. Embora bons resultados tenham sido relatados para algumas classes de problemas, o ceticismo em relação à generalidade e / ou praticidade da hipótese do bloco de construção como uma explicação para a eficiência dos AGs ainda permanece. Na verdade, há uma quantidade razoável de trabalho que tenta entender suas limitações do ponto de vista da estimativa de algoritmos de distribuição.

Limitações

Existem limitações do uso de um algoritmo genético em comparação com algoritmos de otimização alternativos:

  • A avaliação repetida da função de aptidão para problemas complexos costuma ser o segmento mais proibitivo e limitante dos algoritmos evolutivos artificiais. Encontrar a solução ideal para problemas complexos multimodais de alta dimensão geralmente requer avaliações de função de aptidão muito caras . Em problemas do mundo real, como problemas de otimização estrutural, a avaliação de uma única função pode exigir várias horas a vários dias de simulação completa. Os métodos de otimização típicos não podem lidar com esses tipos de problemas. Nesse caso, pode ser necessário renunciar a uma avaliação exata e usar uma adequação aproximada que seja computacionalmente eficiente. É evidente que o amálgama de modelos aproximados pode ser uma das abordagens mais promissoras para usar o AG de forma convincente para resolver problemas complexos da vida real.
  • Algoritmos genéticos não se adaptam bem à complexidade. Ou seja, onde o número de elementos expostos à mutação é grande, geralmente há um aumento exponencial no tamanho do espaço de busca. Isso torna extremamente difícil o uso da técnica em problemas como o projeto de um motor, uma casa ou um avião. A fim de tornar esses problemas tratáveis ​​à pesquisa evolucionária, eles devem ser divididos na representação mais simples possível. Portanto, normalmente vemos algoritmos evolutivos que codificam projetos para pás de ventiladores em vez de motores, formas de construção em vez de planos de construção detalhados e aerofólios em vez de projetos de aeronaves inteiras. O segundo problema de complexidade é a questão de como proteger as partes que evoluíram para representar boas soluções de futuras mutações destrutivas, particularmente quando sua avaliação de aptidão exige que combinem bem com outras partes.
  • A solução "melhor" é apenas em comparação com outras soluções. Como resultado, o critério de parada não é claro em todos os problemas.
  • Em muitos problemas, os AGs tendem a convergir para ótimos locais ou mesmo pontos arbitrários, em vez do ótimo global do problema. Isso significa que ele não "sabe" sacrificar a aptidão de curto prazo para obter aptidão de longo prazo. A probabilidade de isso ocorrer depende da forma do cenário de aptidão : certos problemas podem fornecer uma ascensão fácil em direção a um ótimo global, outros podem tornar mais fácil para a função encontrar o ótimo local. Este problema pode ser atenuado usando uma função de aptidão diferente, aumentando a taxa de mutação, ou usando técnicas de seleção que mantêm uma população diversificada de soluções, embora o teorema No Free Lunch prove que não há uma solução geral para este problema. Uma técnica comum para manter a diversidade é impor uma "penalidade de nicho", em que, qualquer grupo de indivíduos de similaridade suficiente (raio de nicho) terá uma penalidade adicionada, o que reduzirá a representação daquele grupo nas gerações subsequentes, permitindo outros (menos semelhantes ) indivíduos a serem mantidos na população. Esse truque, entretanto, pode não ser eficaz, dependendo do cenário do problema. Outra técnica possível seria simplesmente substituir parte da população por indivíduos gerados aleatoriamente, quando a maioria da população é muito semelhante entre si. A diversidade é importante em algoritmos genéticos (e programação genética ) porque cruzar uma população homogênea não produz novas soluções. Em estratégias de evolução e programação evolutiva , a diversidade não é essencial por causa de uma maior dependência de mutação.
  • Operar em conjuntos de dados dinâmicos é difícil, pois os genomas começam a convergir cedo para soluções que podem não ser mais válidas para dados posteriores. Vários métodos foram propostos para remediar isso aumentando a diversidade genética de alguma forma e evitando a convergência precoce, seja aumentando a probabilidade de mutação quando a qualidade da solução cai (chamada de hipermutação desencadeada ), ou introduzindo ocasionalmente elementos inteiramente novos gerados aleatoriamente no pool genético (chamados de imigrantes aleatórios ). Mais uma vez, as estratégias de evolução e a programação evolutiva podem ser implementadas com a chamada "estratégia de vírgula", na qual os pais não são mantidos e os novos pais são selecionados apenas na descendência. Isso pode ser mais eficaz em problemas dinâmicos.
  • Os AGs não podem resolver com eficácia problemas nos quais a única medida de aptidão é uma única medida certa / errada (como problemas de decisão ), pois não há como convergir para a solução (sem colina para subir). Nestes casos, uma busca aleatória pode encontrar uma solução tão rapidamente quanto um GA. No entanto, se a situação permitir que a tentativa de sucesso / fracasso seja repetida, dando (possivelmente) resultados diferentes, então a proporção de sucessos para fracassos fornece uma medida de aptidão adequada.
  • Para problemas de otimização específicos e instâncias de problemas, outros algoritmos de otimização podem ser mais eficientes do que algoritmos genéticos em termos de velocidade de convergência. Algoritmos alternativos e complementares incluem estratégias de evolução , programação evolutiva , recozimento simulado , adaptação Gaussiana , escalada e inteligência de enxame (por exemplo: otimização de colônia de formigas , otimização de enxame de partículas ) e métodos baseados em programação linear inteira . A adequação dos algoritmos genéticos depende da quantidade de conhecimento do problema; problemas bem conhecidos geralmente têm abordagens melhores e mais especializadas.

Variantes

Representação cromossômica

O algoritmo mais simples representa cada cromossomo como uma string de bits . Normalmente, os parâmetros numéricos podem ser representados por inteiros , embora seja possível usar representações de ponto flutuante . A representação de ponto flutuante é natural para estratégias de evolução e programação evolutiva . A noção de algoritmos genéticos de valor real foi oferecida, mas é realmente um nome impróprio porque não representa realmente a teoria dos blocos de construção que foi proposta por John Henry Holland nos anos 1970. No entanto, esta teoria tem suporte, com base em resultados teóricos e experimentais (ver abaixo). O algoritmo básico realiza crossover e mutação no nível de bits. Outras variantes tratam o cromossomo como uma lista de números que são índices em uma tabela de instruções, nós em uma lista encadeada , hashes , objetos ou qualquer outra estrutura de dados imaginável . O cruzamento e a mutação são executados de forma a respeitar os limites dos elementos de dados. Para a maioria dos tipos de dados, operadores de variação específicos podem ser projetados. Diferentes tipos de dados cromossômicos parecem funcionar melhor ou pior para diferentes domínios de problemas específicos.

Quando as representações de cadeia de bits de inteiros são usadas, a codificação Gray é frequentemente empregada. Desta forma, pequenas mudanças no número inteiro podem ser prontamente afetadas por meio de mutações ou cruzamentos. Descobriu-se que isso ajuda a prevenir a convergência prematura nas chamadas paredes de Hamming , nas quais muitas mutações simultâneas (ou eventos de crossover) devem ocorrer para mudar o cromossomo para uma solução melhor.

Outras abordagens envolvem o uso de matrizes de números com valor real em vez de sequências de bits para representar os cromossomos. Os resultados da teoria dos esquemas sugerem que, em geral, quanto menor o alfabeto, melhor o desempenho, mas foi inicialmente surpreendente para os pesquisadores que bons resultados foram obtidos com o uso de cromossomos de valor real. Isso foi explicado como o conjunto de valores reais em uma população finita de cromossomos formando um alfabeto virtual (quando a seleção e a recombinação são dominantes) com uma cardinalidade muito menor do que seria esperado de uma representação de ponto flutuante.

Uma expansão do domínio do problema acessível do Algoritmo Genético pode ser obtida por meio de uma codificação mais complexa dos pools de solução, concatenando vários tipos de genes codificados de forma heterogênea em um cromossomo. Essa abordagem específica permite resolver problemas de otimização que requerem domínios de definição amplamente díspares para os parâmetros do problema. Por exemplo, em problemas de sintonia do controlador em cascata, a estrutura do controlador de loop interno pode pertencer a um regulador convencional de três parâmetros, enquanto o loop externo pode implementar um controlador linguístico (como um sistema fuzzy) que tem uma descrição inerentemente diferente. Esta forma particular de codificação requer um mecanismo de crossover especializado que recombina o cromossomo por seção, e é uma ferramenta útil para a modelagem e simulação de sistemas adaptativos complexos, especialmente processos de evolução.

Elitismo

Uma variante prática do processo geral de construção de uma nova população é permitir que os melhores organismos da geração atual sejam transferidos para a próxima, inalterados. Essa estratégia é conhecida como seleção elitista e garante que a qualidade da solução obtida pelo AG não diminuirá de uma geração para a outra.

Implementações paralelas

Implementações paralelas de algoritmos genéticos vêm em dois sabores. Algoritmos genéticos paralelos de granulação grossa assumem uma população em cada um dos nós do computador e a migração de indivíduos entre os nós. Algoritmos genéticos paralelos refinados assumem um indivíduo em cada nó processador que atua com indivíduos vizinhos para seleção e reprodução. Outras variantes, como algoritmos genéticos para problemas de otimização online , introduzem dependência do tempo ou ruído na função de aptidão.

GAs adaptativos

Algoritmos genéticos com parâmetros adaptativos (algoritmos genéticos adaptativos, AGAs) é outra variante significativa e promissora dos algoritmos genéticos. As probabilidades de cruzamento (pc) e mutação (pm) determinam muito o grau de precisão da solução e a velocidade de convergência que os algoritmos genéticos podem obter. Em vez de usar valores fixos de pc e pm , os AGAs utilizam as informações da população em cada geração e ajustam de forma adaptativa o pc e pm para manter a diversidade populacional e também sustentar a capacidade de convergência. No AGA (algoritmo genético adaptativo), o ajuste de pc e pm depende dos valores de aptidão das soluções. No CAGA (algoritmo genético adaptativo baseado em agrupamento), através do uso da análise de agrupamento para julgar os estados de otimização da população, o ajuste de pc e pm depende desses estados de otimização. Pode ser bastante eficaz combinar o GA com outros métodos de otimização. GA tende a ser muito bom em encontrar soluções globais geralmente boas, mas bastante ineficiente em encontrar as últimas mutações para encontrar o ótimo absoluto. Outras técnicas (como escalada simples ) são bastante eficientes para encontrar o ótimo absoluto em uma região limitada. Alternar o GA e o hill climbing pode melhorar a eficiência do GA enquanto supera a falta de robustez do hill climbing.

Isso significa que as regras de variação genética podem ter um significado diferente no caso natural. Por exemplo - desde que as etapas sejam armazenadas em ordem consecutiva - o crossing over pode somar uma série de etapas do DNA materno, adicionar uma série de etapas do DNA paterno e assim por diante. Isso é como adicionar vetores que provavelmente podem seguir uma crista na paisagem fenotípica. Assim, a eficiência do processo pode ser aumentada em muitas ordens de magnitude. Além disso, o operador de inversão tem a oportunidade de colocar etapas em ordem consecutiva ou qualquer outra ordem adequada em favor da sobrevivência ou eficiência.

Uma variação, em que a população como um todo evolui, e não seus membros individuais, é conhecida como recombinação do pool genético.

Uma série de variações foram desenvolvidas para tentar melhorar o desempenho dos AGs em problemas com um alto grau de epistasia de aptidão, ou seja, onde a aptidão de uma solução consiste em subconjuntos interativos de suas variáveis. Esses algoritmos visam aprender (antes de explorar) essas interações fenotípicas benéficas. Como tal, eles estão alinhados com a Hipótese do Bloco de Construção na redução adaptativa da recombinação disruptiva. Exemplos proeminentes dessa abordagem incluem o mGA, GEMGA e LLGA.

Domínios de problema

Os problemas que parecem ser particularmente apropriados para solução por algoritmos genéticos incluem problemas de cronograma e agendamento, e muitos pacotes de software de agendamento são baseados em AGs. Os AGs também foram aplicados à engenharia . Os algoritmos genéticos são frequentemente aplicados como uma abordagem para resolver problemas de otimização global .

Como regra geral, algoritmos genéticos podem ser úteis em domínios de problemas que têm um cenário de fitness complexo, já que a mistura, ou seja, mutação em combinação com cruzamento , é projetada para mover a população para longe dos ótimos locais que um algoritmo de escalada tradicional pode travar in. Observe que os operadores de crossover comumente usados ​​não podem alterar nenhuma população uniforme. A mutação por si só pode fornecer ergodicidade ao processo geral do algoritmo genético (visto como uma cadeia de Markov ).

Exemplos de problemas resolvidos por algoritmos genéticos incluem: espelhos projetados para canalizar a luz do sol para um coletor solar, antenas projetadas para captar sinais de rádio no espaço, métodos de caminhada para figuras de computador, design ideal de corpos aerodinâmicos em campos de fluxo complexos

Em seu Manual de Projeto de Algoritmo , Skiena desaconselha algoritmos genéticos para qualquer tarefa:

Não é natural modelar aplicativos em termos de operadores genéticos, como mutação e cruzamento em strings de bits. A pseudobiologia adiciona outro nível de complexidade entre você e seu problema. Em segundo lugar, os algoritmos genéticos demoram muito em problemas não triviais. [...] [A] analogia com a evolução - onde um progresso significativo requer [sic] milhões de anos - pode ser bastante apropriada.

[...]

Nunca encontrei nenhum problema em que algoritmos genéticos parecessem a maneira certa de atacá-lo. Além disso, nunca vi nenhum resultado computacional relatado usando algoritmos genéticos que tenha me impressionado favoravelmente. Limite-se ao recozimento simulado para suas necessidades de vodu de pesquisa heurística.

-  Steven Skiena

História

Em 1950, Alan Turing propôs uma "máquina de aprendizado" que seria semelhante aos princípios da evolução. A simulação da evolução por computador começou já em 1954 com o trabalho de Nils Aall Barricelli , que estava usando o computador no Institute for Advanced Study em Princeton, New Jersey . Sua publicação de 1954 não foi amplamente notada. A partir de 1957, o geneticista quantitativo australiano Alex Fraser publicou uma série de artigos sobre simulação de seleção artificial de organismos com múltiplos loci controlando uma característica mensurável. A partir desse início, a simulação computacional da evolução por biólogos se tornou mais comum no início dos anos 1960, e os métodos foram descritos nos livros de Fraser e Burnell (1970) e Crosby (1973). As simulações de Fraser incluíram todos os elementos essenciais dos algoritmos genéticos modernos. Além disso, Hans-Joachim Bremermann publicou uma série de artigos na década de 1960 que também adotou uma população de soluções para problemas de otimização, passando por recombinação, mutação e seleção. A pesquisa de Bremermann também incluiu os elementos de algoritmos genéticos modernos. Outros pioneiros notáveis ​​incluem Richard Friedberg, George Friedman e Michael Conrad. Muitos dos primeiros artigos foram reimpressos por Fogel (1998).

Embora Barricelli, em um trabalho que relatou em 1963, tenha simulado a evolução da habilidade de jogar um jogo simples, a evolução artificial só se tornou um método de otimização amplamente reconhecido como resultado do trabalho de Ingo Rechenberg e Hans-Paul Schwefel na década de 1960 e no início Década de 1970 - o grupo de Rechenberg conseguiu resolver problemas complexos de engenharia por meio de estratégias de evolução . Outra abordagem foi a técnica de programação evolutiva de Lawrence J. Fogel , que foi proposta para gerar inteligência artificial. A programação evolucionária originalmente usava máquinas de estado finito para prever ambientes e usava variação e seleção para otimizar a lógica preditiva. Os algoritmos genéticos, em particular, tornaram-se populares através do trabalho de John Holland no início dos anos 1970, e particularmente de seu livro Adaptation in Natural and Artificial Systems (1975). Seu trabalho teve origem nos estudos de autômatos celulares , conduzidos por Holland e seus alunos na Universidade de Michigan . A Holanda introduziu uma estrutura formalizada para prever a qualidade da próxima geração, conhecida como Teorema do Esquema de Holanda . A pesquisa em GAs permaneceu amplamente teórica até meados da década de 1980, quando a Primeira Conferência Internacional sobre Algoritmos Genéticos foi realizada em Pittsburgh, Pensilvânia .

Produtos comerciais

No final dos anos 1980, a General Electric começou a vender o primeiro produto de algoritmo genético do mundo, um kit de ferramentas baseado em mainframe projetado para processos industriais. Em 1989, a Axcelis, Inc. lançou o Evolver , o primeiro produto GA comercial do mundo para computadores desktop. O redator de tecnologia do New York Times , John Markoff, escreveu sobre o Evolver em 1990 e ele permaneceu como o único algoritmo genético comercial interativo até 1995. O Evolver foi vendido para a Palisade em 1997, traduzido para vários idiomas e atualmente está em sua sexta versão. Desde a década de 1990, o MATLAB construiu três algoritmos heurísticos de otimização livres de derivadas (recozimento simulado, otimização por enxame de partículas, algoritmo genético) e dois algoritmos de pesquisa direta (pesquisa simplex, pesquisa de padrão).

Técnicas relacionadas

Campos pai

Algoritmos genéticos são um subcampo:

Campos relacionados

Algoritmos evolutivos

Algoritmos evolutivos é um subcampo da computação evolucionária .

  • As estratégias de evolução (ES, ver Rechenberg, 1994) evoluem os indivíduos por meio de mutação e recombinação intermediária ou discreta. Os algoritmos ES são projetados especialmente para resolver problemas no domínio do valor real. Eles usam auto-adaptação para ajustar os parâmetros de controle da pesquisa. A desaleatização da auto-adaptação levou à estratégia contemporânea de evolução da adaptação da matriz de covariância ( CMA-ES ).
  • A programação evolutiva (EP) envolve populações de soluções principalmente com mutação e seleção e representações arbitrárias. Eles usam auto-adaptação para ajustar parâmetros e podem incluir outras operações de variação, como combinar informações de vários pais.
  • O Algoritmo de Estimativa de Distribuição (EDA) substitui os operadores tradicionais de reprodução por operadores guiados por modelos. Tais modelos são aprendidos com a população, empregando técnicas de aprendizado de máquina e representados como Modelos Gráficos Probabilísticos, a partir dos quais novas soluções podem ser amostradas ou geradas a partir de crossover guiado.
  • A programação genética (GP) é uma técnica relacionada popularizada por John Koza em que programas de computador, ao invés de parâmetros de função, são otimizados. A programação genética geralmente usa estruturas de dados internas baseadas em árvore para representar os programas de computador para adaptação, em vez das estruturas de lista típicas dos algoritmos genéticos. Existem muitas variantes de programação genética, incluindo programação genética cartesiana , programação de expressão gênica , evolução gramatical , programação genética linear , programação de expressão múltipla , etc.
  • O algoritmo genético de agrupamento (GGA) é uma evolução do GA onde o foco é mudado de itens individuais, como nos GAs clássicos, para grupos ou subconjuntos de itens. A ideia por trás dessa evolução do GA proposta por Emanuel Falkenauer é que resolver alguns problemas complexos, também conhecidos como problemas de agrupamento ou particionamento , onde um conjunto de itens deve ser dividido em grupos disjuntos de itens de maneira ideal, seria melhor alcançado criando características dos grupos de itens equivalentes a genes. Esses tipos de problemas incluem empacotamento de caixas, balanceamento de linha, agrupamento em relação a uma medida de distância, pilhas iguais, etc., nos quais os GAs clássicos provaram ter um desempenho ruim. Tornar genes equivalentes a grupos implica cromossomos que, em geral, são de comprimento variável e operadores genéticos especiais que manipulam grupos inteiros de itens. Para embalagem de lixo em particular, um GGA hibridizado com o Critério de Dominância de Martello e Toth, é indiscutivelmente a melhor técnica até o momento.
  • Algoritmos evolutivos interativos são algoritmos evolutivos que usam avaliação humana. Eles geralmente são aplicados a domínios onde é difícil projetar uma função de aptidão computacional, por exemplo, imagens em evolução, música, designs artísticos e formas para atender às preferências estéticas dos usuários.

Inteligência de enxame

A inteligência de enxame é um subcampo da computação evolucionária .

  • A otimização da colônia de formigas ( ACO ) usa muitas formigas (ou agentes) equipadas com um modelo de feromônio para atravessar o espaço de solução e encontrar áreas produtivas localmente.
  • Embora seja considerado um algoritmo de estimativa de distribuição , a otimização por enxame de partículas (PSO) é um método computacional para otimização multiparâmetros que também usa uma abordagem baseada em população. Uma população (enxame) de soluções candidatas (partículas) se move no espaço de busca, e o movimento das partículas é influenciado por sua própria posição mais conhecida e pela posição global mais conhecida do enxame. Como os algoritmos genéticos, o método PSO depende do compartilhamento de informações entre os membros da população. Em alguns problemas, o PSO é frequentemente mais eficiente computacionalmente do que os AGs, especialmente em problemas irrestritos com variáveis ​​contínuas.

Algoritmos evolutivos combinados com inteligência Swarm

Outros algoritmos de computação evolucionária

A computação evolutiva é um subcampo dos métodos metaheurísticos .

  • O algoritmo memético (MA), frequentemente denominado algoritmo genético híbrido entre outros, é um método baseado em população em que as soluções também estão sujeitas a fases de melhoramento local. A ideia de algoritmos meméticos vem de memes , que, ao contrário dos genes, podem se adaptar. Em algumas áreas problemáticas, eles se mostram mais eficientes do que os algoritmos evolucionários tradicionais.
  • Algoritmos bacteriológicos (BA) inspirados na ecologia evolutiva e, mais particularmente, na adaptação bacteriológica. A ecologia evolutiva é o estudo dos organismos vivos no contexto de seu ambiente, com o objetivo de descobrir como eles se adaptam. Seu conceito básico é que em um ambiente heterogêneo, não existe um indivíduo que se adapte a todo o ambiente. Portanto, é preciso raciocinar no nível da população. Também se acredita que os BAs podem ser aplicados com sucesso a problemas de posicionamento complexos (antenas para telefones celulares, planejamento urbano e assim por diante) ou mineração de dados.
  • O algoritmo cultural (CA) consiste no componente populacional quase idêntico ao do algoritmo genético e, além disso, um componente de conhecimento denominado espaço de crenças.
  • Evolução diferencial (DS) inspirada na migração de superorganismos.
  • A adaptação gaussiana ( adaptação normal ou natural, abreviada como NA para evitar confusão com GA) é destinada à maximização do rendimento da fabricação de sistemas de processamento de sinal. Também pode ser usado para otimização paramétrica comum. Ele se baseia em um certo teorema válido para todas as regiões de aceitabilidade e todas as distribuições gaussianas. A eficiência de NA depende da teoria da informação e de um certo teorema da eficiência. Sua eficiência é definida como informação dividida pelo trabalho necessário para obtê-la. Como NA maximiza a aptidão média em vez da aptidão do indivíduo, a paisagem é suavizada de forma que os vales entre os picos podem desaparecer. Portanto, tem uma certa "ambição" de evitar picos locais no cenário de fitness. NA também é bom em escalar cristas agudas por adaptação da matriz de momento, porque NA pode maximizar a desordem ( informação média ) do Gaussiano simultaneamente mantendo a aptidão média constante.

Outros métodos metaheurísticos

Os métodos metaheurísticos geralmente se enquadram nos métodos de otimização estocástica .

  • Simulated annealing (SA) é uma técnica de otimização global relacionada que atravessa o espaço de busca testando mutações aleatórias em uma solução individual. Uma mutação que aumenta a aptidão é sempre aceita. Uma mutação que reduz a aptidão é aceita probabilisticamente com base na diferença na aptidão e em um parâmetro de temperatura decrescente. Na linguagem SA, fala-se em buscar a energia mais baixa em vez da aptidão máxima. SA também pode ser usado dentro de um algoritmo GA padrão, começando com uma taxa relativamente alta de mutação e diminuindo ao longo do tempo ao longo de um determinado cronograma.
  • A pesquisa tabu (TS) é semelhante ao recozimento simulado em que ambos atravessam o espaço da solução testando as mutações de uma solução individual. Enquanto o recozimento simulado gera apenas uma solução mutada, a busca tabu gera muitas soluções mutadas e se move para a solução com a energia mais baixa daquelas geradas. Para evitar ciclos e estimular um maior movimento no espaço de solução, é mantida uma lista tabu de soluções parciais ou completas. É proibido mover para uma solução que contenha elementos da lista tabu, que é atualizada conforme a solução atravessa o espaço da solução.
  • Otimização externa (EO) Ao contrário dos GAs, que trabalham com uma população de soluções candidatas, a EO desenvolve uma única solução e faz modificações locais nos piores componentes. Isso requer que uma representação adequada seja selecionada que permita aos componentes individuais da solução serem atribuídos a uma medida de qualidade ("adequação"). O princípio governante por trás desse algoritmo é o da melhoria emergente por meio da remoção seletiva de componentes de baixa qualidade e da sua substituição por um componente selecionado aleatoriamente. Isso está decididamente em desacordo com um GA que seleciona boas soluções na tentativa de fazer melhores soluções.

Outros métodos de otimização estocástica

  • O método de entropia cruzada (CE) gera soluções candidatas por meio de uma distribuição de probabilidade parametrizada. Os parâmetros são atualizados via minimização de entropia cruzada, de forma a gerar melhores amostras na próxima iteração.
  • A otimização de pesquisa reativa (RSO) defende a integração de técnicas de aprendizado de máquina sub-simbólicas em heurísticas de pesquisa para resolver problemas de otimização complexos. A palavra reativa sugere uma resposta pronta aos eventos durante a busca por meio de um loop interno de feedback online para o autoajuste de parâmetros críticos. Metodologias de interesse para Pesquisa reativa incluem aprendizado de máquina e estatística, em particular aprendizado por reforço , aprendizado ativo ou por consulta , redes neurais e metaheurísticas .

Veja também

Referências

Bibliografia

links externos

Recursos

Tutoriais