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 evolui em direção a melhores soluções. Cada solução candidata possui um conjunto de propriedades (seus cromossomos ou genótipos) que podem sofrer mutação e alterações. Tradicionalmente, as soluções são representadas em binário como sequências de zeros e uns, 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, sendo a população em cada iteração chamada de geração. Em cada geração, é avaliada a aptidão de cada indivíduo da população. Fitness é 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 "Recombinação (computação evolutiva)") 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 ocorre um número máximo de gerações ou quando um nível de aptidão satisfatório para a população é alcançado.

Um algoritmo genético típico requer:

1. • Uma representação genética do domínio de 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 "Matriz (matemática)") de bits. Matrizes de outros tipos e estruturas podem ser usadas 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 simples de cruzamento. Representações de comprimento variável também podem ser usadas, mas a implementação do cruzamento cromossômico é mais complexa neste caso. As representações de árvores são exploradas na programação genética e as representações semelhantes a gráficos 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 definidas a representação genética e a função de aptidão, um AG prossegue para inicializar uma população de soluções e então melhorá-la aplicando repetidamente os operadores de mutação, cruzamento, inversão e seleção.

O tamanho da população depende da natureza do problema, mas normalmente contém centenas ou milhares de soluções possíveis. Freqüentemente, a população inicial é gerada aleatoriamente, permitindo toda a gama de soluções possíveis (o espaço de busca). Ocasionalmente, as soluções podem ser “semeadas” em áreas onde é provável que sejam encontradas soluções óptimas.

Durante cada geração sucessiva, uma parte da população existente é selecionada para criar uma nova geração. As soluções individuais são selecionadas através de um processo baseado na aptidão, onde as soluções de aptidão (medidas por uma função de aptidão) têm normalmente maior probabilidade de serem selecionadas. Certos métodos de seleção avaliam a adequação de cada solução e selecionam preferencialmente as melhores soluções. Outros métodos pontuam apenas uma amostra aleatória da população, pois o processo acima pode ser demorado.

A função de aptidão é definida na representação genética e mede a qualidade da solução representada. A função de fitness sempre depende do problema. Por exemplo, no problema da mochila queremos maximizar o valor total dos objetos que podem ser colocados em uma mochila com alguma capacidade fixa. Uma representação de uma solução pode ser uma matriz 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 todas as representações são válidas, 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 da condição física. Nestes casos, a 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.

O próximo passo é gerar uma população de segunda geração, a partir de soluções selecionadas através de uma combinação de operadores genéticos: cruzamento cromossômico (também chamado de crossover ou recombinação) e mutação.

Para cada nova solução produzida, um par de soluções "pais" foi selecionado para reprodução a partir do conjunto previamente selecionado. Ao produzir uma solução de "reprodução" usando os métodos de cruzamento e mutação cromossômicos mencionados acima, é criada uma nova solução que normalmente compartilha muitas das características de seus "pais". Novos pais são selecionados para cada nova ninhada e o processo continua até que uma nova população de soluções de tamanho apropriado seja gerada. Embora os métodos de melhoramento que dependem do uso de dois pais sejam mais “inspirados na biologia”, algumas pesquisas sugerem que mais de dois “pais” podem gerar cromossomos de maior qualidade.

Em última análise, esses processos resultam na próxima geração de população cromossômica, que é diferente da geração inicial. Em geral, a aptidão média foi aumentada por este procedimento para a população, uma vez que apenas os melhores organismos da primeira geração são selecionados para reprodução, juntamente com uma pequena proporção de soluções menos adequadas. Estas soluções menos adequadas garantem a diversidade genética dentro do património genético dos pais e, portanto, asseguram a diversidade genética da próxima geração de crianças.

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

Embora cruzamento e mutação sejam conhecidos como os principais operadores genéticos, é possível utilizar outros operadores como rearranjo, extinção de colonizaçã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 ajustes razoáveis ​​para o tipo de problema em que você está trabalhando. 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 seja usada a seleção de elite.

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

• - É encontrada uma solução que satisfaz os critérios mínimos.

• - Um número fixo de gerações é atingido.

• - O orçamento atribuído é atingido (tempo de cálculo/dinheiro).

• - A adequação da solução com melhor classificação está atingindo ou atingiu um patamar tal que iterações sucessivas não produzem mais resultados melhores.

• - Inspeção manual.

• - Combinações dos itens acima.

Algoritmos genéticos são simples de implementar, mas seu comportamento é difícil de entender. Em particular, é difícil compreender porque é que estes algoritmos são frequentemente bem sucedidos na geração de soluções de elevada aptidão quando aplicados a problemas práticos. A hipótese do bloco de construção (BBH) consiste em:.

• - Uma descrição de uma heurística que realiza adaptação identificando e recombinando "blocos de construção", isto é, esquemas de definição de baixa ordem e baixo comprimento com aptidão acima da média.

• - Uma hipótese de que um algoritmo genético realiza a adaptação de forma implícita e eficiente ao implementar esta heurística.

Goldberg descreve a heurística da seguinte forma:

Esquemas curtos, de baixa ordem e de alto ajuste são amostrados, recombinados (reticulados) e reamostrados para formar cadeias 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 cadeias de alto desempenho tentando todas as combinações concebíveis, construímos cadeias cada vez melhores a partir das melhores soluções parciais das últimas amostras.

"Como esquemas altamente ajustados de baixo comprimento e baixa ordem desempenham um papel tão importante na ação dos algoritmos genéticos, já lhes demos um nome especial: blocos de construção. Assim como uma criança cria fortalezas magníficas através do arranjo de blocos de madeira simples, o mesmo acontece com um algoritmo genético que busca se aproximar do desempenho ideal através 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 do bloco de construção, ela tem sido avaliada e utilizada como referência ao longo dos anos. Muitos algoritmos de distribuição de estimativa, por exemplo, foram propostos na tentativa de fornecer um ambiente no qual a hipótese seria válida. Embora bons resultados tenham sido relatados para algumas classes de problemas, ainda permanece ceticismo em relação à generalidade e/ou praticidade da hipótese do bloco de construção como uma explicação da eficiência dos AGs. Na verdade, há uma quantidade razoável de trabalhos que tentam compreender suas limitações do ponto de vista da estimativa de algoritmos de distribuição.

Existem limitações no 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 é frequentemente o segmento mais proibitivo e limitante dos algoritmos evolutivos artificiais. Encontrar a solução ideal para problemas tridimensionais e multimodais complexos geralmente requer avaliações de funções de condicionamento muito caras. Em problemas do mundo real, como problemas de otimização estrutural, a avaliação de uma única função pode exigir de várias horas a vários dias de simulação completa. Os métodos típicos de otimização não conseguem lidar com esses tipos de problemas. Neste caso, pode ser necessário renunciar à avaliação exata e utilizar uma aptidão aproximada que seja computacionalmente eficiente. É evidente que a fusão de modelos aproximados pode ser uma das abordagens mais promissoras para usar de forma convincente a AG para resolver problemas complexos da vida real.

• - Algoritmos genéticos não se adaptam bem à complexidade. Ou seja, quando o número de elementos expostos à mutação é grande, muitas vezes ocorre 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. Para tornar tais problemas tratáveis ​​à pesquisa evolutiva, eles devem ser decompostos na representação mais simples possível. Portanto, normalmente vemos algoritmos evolutivos codificando 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 completos de aeronaves. 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 a sua avaliação de aptidão exige que se combinem bem com outras partes.

• - A “melhor” solução é apenas em comparação com outras soluções. Como resultado, o critério de parada não é claro em cada problema.

• - Em muitos problemas, os AGs podem ter uma tendência a convergir para pontos ótimos locais ou mesmo para pontos arbitrários, em vez de para o ótimo global do problema. Isto significa que eles não “sabem como” sacrificar a aptidão física a curto prazo para ganhar aptidão física a longo prazo. A probabilidade de isto ocorrer depende da forma do cenário de aptidão: certos problemas podem proporcionar uma subida fácil em direcção a um óptimo global, outros podem tornar mais fácil para a função encontrar o óptimo local. Este problema pode ser aliviado usando uma função de aptidão diferente, aumentando a taxa de mutação, ou usando técnicas de seleção que mantenham uma população diversificada de soluções [12], embora o teorema do almoço grátis [13] mostre que não existe uma solução geral para este problema. Uma técnica comum para manter a diversidade é impor uma “penalidade de nicho”, na qual qualquer grupo de indivíduos de similaridade semelhante (raio de nicho) tem uma penalidade adicional, o que reduzirá a representação desse grupo nas gerações subsequentes, permitindo que outros sejam 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 nos algoritmos genéticos (e na programação genética) porque o cruzamento de uma população homogênea não gera novas soluções. Nas estratégias de evolução e na programação evolutiva, a diversidade não é essencial devido a uma maior dependência da mutação.

• - Operar em conjuntos de dados dinâmicos é difícil, pois os genomas começam a convergir precocemente para soluções que não são mais válidas para dados subsequentes. Vários métodos foram propostos para remediar esta situação, aumentando de alguma forma a diversidade genética e prevenindo a convergência precoce, seja aumentando a probabilidade de mutação quando a qualidade da solução cai (chamada hipermutação desencadeada) ou introduzindo ocasionalmente novos elementos gerados aleatoriamente no conjunto de genes (chamados 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 coma”, na qual os pais não são mantidos e os novos pais são seleccionados apenas a partir da descendência. Isso pode ser mais eficaz em problemas dinâmicos.

• - Os AGs não podem resolver problemas onde a única medida correta é uma medida certa/errada (como problemas de decisão), uma vez que não há como convergir para a solução (não há colina para subir). Nestes casos, uma busca aleatória pode encontrar uma solução tão rapidamente quanto um AG. No entanto, se a situação permitir que o teste de sucesso/fracasso seja repetido, dando (possivelmente) resultados diferentes, então a proporção de sucessos em relação aos fracassos fornece uma medida apropriada de adequação.

• - Para problemas específicos de otimização e instâncias problemáticas, outros algoritmos de otimização podem ser mais eficientes que algoritmos genéticos em termos de velocidade de convergência "Convergência (matemática)"). Algoritmos alternativos e complementares incluem estratégias de evolução, programação evolutiva, recozimento simulado, adaptação gaussiana, subida de colinas e inteligência de enxame (por exemplo: otimização 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 do conhecimento do problema; Problemas bem conhecidos geralmente têm abordagens melhores e mais especializadas.

Representação cromossômica

O algoritmo mais simples representa cada cromossomo como uma sequência de bits. Normalmente, os parâmetros numéricos podem ser representados por números 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 na verdade é um nome impróprio porque não representa realmente a teoria dos blocos de construção proposta por John Henry Holland na década de 1970. Esta teoria tem suporte, entretanto, baseada em resultados teóricos e experimentais (veja abaixo). O algoritmo básico realiza cruzamento e mutação no nível de bit. 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 feitos para 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.

Ao usar representações de números de bits de inteiros, a codificação Gray é frequentemente empregada. Desta forma, pequenas alterações no número inteiro podem ser facilmente afetadas por mutações ou cruzamentos. Descobriu-se que isso ajuda a prevenir a convergência prematura em paredes chamadas de Hamming, nas quais muitas mutações simultâneas (ou eventos de cruzamento) devem ocorrer para mudar o cromossomo para uma solução melhor.

Outras abordagens envolvem o uso de matrizes de números com valores reais em vez de sequências de bits para representar cromossomos. Os resultados da teoria dos esquemas sugerem que, em geral, quanto menor o alfabeto, melhor o desempenho, mas foi inicialmente surpreendente para os investigadores que bons resultados foram obtidos utilizando cromossomas 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 [14] [15].

Uma expansão do problema de domínio acessível do algoritmo genético pode ser obtida através da solução de codificação mais complexa de clusters por concatenação de vários tipos de genes codificados heterogeneamente em um cromossomo. [16] Esta abordagem particular permite resolver problemas de otimização que requerem domínios de definição extremamente díspares para os parâmetros do problema. Por exemplo, em problemas de ajuste de controlador em cascata, a estrutura do controlador de malha interna pode pertencer a um controlador convencional de três parâmetros, enquanto a malha externa pode implementar um controlador linguístico (como um sistema fuzzy) que possui uma descrição inerentemente diferente. Esta forma particular de codificação requer um mecanismo de cruzamento especializado que recombina o cromossomo por seção e é uma ferramenta útil para modelagem e simulação de sistemas adaptativos complexos, especialmente processos evolutivos.

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. Esta estratégia é conhecida como seleção de elite e garante que a qualidade da solução obtida pelo AG não diminuirá de uma geração para 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 de computação e migração de indivíduos entre os nós. Algoritmos genéticos paralelos assumem um indivíduo em cada nó de processamento 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 de tempo ou ruído na função de aptidão.

Algoritmo genético adaptativo

Algoritmos genéticos com parâmetros adaptativos (algoritmos genéticos adaptativos, AGAs) são outra variante significativa e promissora de algoritmos genéticos. As probabilidades de cruzamento (pc) e mutação (pm) determinam em grande parte 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 p. m., os AGs utilizam as informações populacionais em cada geração e ajustam adaptativamente pc e p. m. a fim de manter a diversidade populacional, bem como para sustentar a capacidade de convergência. No AGA (algoritmo genético adaptativo), o ajuste de pc e p. m. Depende dos valores de aptidão das soluções. No CAGA (algoritmo adaptativo baseado em clustering), através do uso de análise de cluster para julgar os estados de otimalidade da população, o ajuste de pc e p. m. depende desses estados de otimização. Pode ser muito eficaz combinar 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 a simples subida de colinas) são bastante eficientes para encontrar o ótimo absoluto em uma região limitada. Alternar GA e subida de colinas pode melhorar a eficiência da GA [carece de fontes] ao mesmo tempo em que supera a insegurança da subida de colinas.

Isto 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 cruzamento pode adicionar uma série de etapas de DNA materno adicionando uma série de etapas de DNA paterno e assim por diante. Isto é como adicionar vetores que provavelmente podem seguir uma crista na paisagem fenotípica. Portanto, a eficiência do processo pode ser aumentada em muitas ordens de grandeza. Além disso, o trader de investimento tem a oportunidade de colocar as etapas em ordem consecutiva ou em qualquer outra ordem apropriada em favor da sobrevivência ou da eficiência.

Uma variação, na qual a população como um todo se desenvolve em vez de seus membros individuais, é conhecida como recombinação de grupo genético.

Uma série de variações foram desenvolvidas para tentar melhorar o desempenho dos AGs em problemas com alto grau de epistasia de aptidão, ou seja, quando a aptidão de uma solução consiste na interação de subconjuntos de suas variáveis. Tais algoritmos visam aprender (antes de explorar) essas interações fenotípicas benéficas. Como tal, estão alinhados com a hipótese do bloco de construção na redução adaptativa da recombinação disruptiva.

Problemas que parecem ser particularmente adequados para solução usando algoritmos genéticos incluem problemas de programação, e muitos pacotes de software de programação são baseados em AGs. GAs também foram aplicados à engenharia. 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 possuem um cenário de aptidão complexo, uma vez que a mistura, isto é, a mutação em combinação com o cruzamento "Recombinação (computação evolutiva)"), é projetada para afastar a população ainda mais do ótimo local do que um algoritmo tradicional. Observe que os operadores de cruzamento 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).

Contenido

En 1950, Alan Turing propuso una "máquina de aprendizaje" que sería paralela a los principios de la evolución. La simulación por computadora de la evolución comenzó tan pronto como en 1954 con el trabajo de Nils Aall Barricelli"), que utilizaba la computadora en el instituto para el estudio avanzado en Princeton (Nueva Jersey) "Princeton (Nueva Jersey)"). Su publicación de 1954 no fue ampliamente notada. A partir de 1957, el australiano cuantitativo genetista Alex Fraser") publicó una serie de artículos sobre la simulación de la selección artificial de organismos con múltiples loci controlando un rasgo mensurable. A partir de estos comienzos, la simulación por ordenador de la evolución por los biólogos se hizo más común a principios de 1960, y los métodos fueron descritos en los libros de Fraser y Burnell (1970) y Crosby (1973) Las simulaciones de Fraser incluían todos los elementos esenciales de los algoritmos genéticos modernos. Además, Hans-Joachim Bremermann publicó una serie de artículos en los años sesenta que también adoptaron una población de solución a problemas de optimización, sometidos a recombinación, mutación y selección. La investigación de Bremermann también incluyó los elementos de los algoritmos genéticos modernos. Otros destacados primeros pioneros son Richard Friedberg"), George Friedman y Michael Conrad. Muchos de los primeros artículos han sido reimpresos por Fogel (1998).

Aunque Barricelli, en el trabajo que relató en 1963, había simulado la evolución de la capacidad de jugar un juego simple, la evolución artificial se convirtió en un método de optimización ampliamente reconocido como resultado del trabajo de Ingo Rechenberg y Hans-Paul Schwefel en los años 1960 y principios de 1970 - el grupo de Rechenberg fue capaz de resolver problemas complejos de ingeniería a través de estrategias de evolución.Otro enfoque fue la técnica de programación evolutiva de Lawrence J. Fogel, que se propuso para generar inteligencia artificial. La programación evolutiva utilizó originalmente máquinas de estado finito para predecir los entornos y utilizó la variación y la selección para optimizar las lógicas predictivas. Los algoritmos genéticos, en particular, se hicieron populares a través del trabajo de John Henry Holland a principios de los años setenta, y particularmente de su libro Adaptation in Natural and Artificial Systems (1975). Su trabajo se originó con estudios de autómatas celulares, conducidos por Holland y sus estudiantes en la Universidad de Míchigan. Holland introdujo un marco formalizado para predecir la calidad de la próxima generación, conocido como el teorema del esquema de Holland. La investigación en GAs permaneció en gran parte teórica hasta mediados de los años 80, cuando la primera conferencia internacional en algoritmos genéticos fue llevada a cabo en Pittsburgh, Pensilvania.

Produtos comerciais

No final da década de 1980, a General Electric começou a vender o primeiro produto de algoritmo genético do mundo, uma caixa de ferramentas baseada em mainframe projetada para processos industriais. Em 1989, a Axcelis, Inc. lançou o Evolver, o primeiro produto comercial da AG 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 de negociação 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.

Considérese el problema de insertar signos de suma o resta entre los dígitos 9 8 7 6 5 4 3 2 1 para construir una expresión cuyo valor sea 100; no vale añadir, retirar o desordenar a los dígitos. Una solución puede ser 98+7-6+5-4+3-2-1 porque, al evaluar su valor, da exactamente 100.

Hay 9 sitios (uno antes de cada dígito) donde colocar un signo de más (+), un signo de menos (-) o nada (lo cual implicará que dos o más dígitos se unan para formar cantidades mayores; como 98 en el ejemplo anterior, donde se puso "nada" antes del 9 y antes del 8). Existen, por lo tanto, 3 a la 9 = 19683 expresiones distintas (por combinatoria) entre las cuales buscar aquellas con la suma deseada. Es posible desarrollar un algoritmo exhaustivo que las genere todas y, dada la relativa pequeñez de este ejemplo, determinar completamente todas las posibles configuraciones. Sin embargo, este reto se presta para ilustrar los pasos de un proceso genético.

Codificação

Existe uma bijeção entre as cadeias de “trits” (dígitos ternários: 0, 1, 2) de comprimento 9 e as possíveis configurações de sinais para cada soma. Por exemplo, se for adotada a convenção de que "0" representa "nada", "1" representa "menos" e "2" representa "mais", então a sequência de "trits" 002121211 corresponde à solução 98+7-6+5-4+3-2-1.

Campos pai

Algoritmos genéticos são um subcampo de:.

• - Algoritmos evolutivos.

• - Computação evolutiva.

• - Metaheurísticas.

• - Otimização estocástica.

• - Melhoria.

Campos relacionados

Algoritmos evolutivos são um subcampo da computação evolutiva.

• - As estratégias de evolução (ES, ver Rechenberg, 1994) evoluem os indivíduos através de mutação e recombinação intermediária ou discreta. Os algoritmos ES são especialmente projetados para resolver problemas no domínio do valor real. Eles usam autoadaptação para ajustar os parâmetros de controle de busca. A desrandomização da autoadaptação levou à atual Estratégia de Evolução de Adaptação da Matriz de Covariância (CMA-ES).

• - A programação evolutiva (PE) envolve populações de soluções com mutação e seleção e representações arbitrárias. Ele usa autoadaptação para ajustar parâmetros e pode incluir outras operações de variação, como combinar informações de vários pais.

• - O Algoritmo de Distribuição de Estimativa (EDA) substitui os operadores de repetição tradicionais por operadores orientados por modelo. Esses modelos são aprendidos com a população usando 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 [45] [46] ou geradas a partir de cruzamentos cromossômicos guiados [47].

• - A programação de expressão genética (GEP) também utiliza populações de programas de computador. Esses programas de computador complexos são codificados em cromossomos lineares mais simples de comprimento fixo, que são então expressos como árvores de expressão. Árvores de expressão ou programas de computador evoluem porque os cromossomos sofrem mutação e recombinação de maneira semelhante ao GA canônico. Mas graças à organização especial dos cromossomas GEP, estas modificações genéticas resultam sempre em programas de computador válidos. [48].

• - A programação genética (GP) é uma técnica relacionada popularizada por John Koza na qual programas de computador, em vez de parâmetros funcionais, são otimizados. A programação genética geralmente usa estruturas de dados internas baseadas em árvores para representar programas de computador para adaptação, em vez das estruturas de lista típicas dos algoritmos genéticos.

• - O agrupamento de algoritmos genéticos (GGA) é uma evolução do AG onde o foco muda de elementos individuais, como no AG clássico, para grupos ou subconjuntos de elementos. [49] A ideia por trás desta evolução do AG proposta por Emanuel Falkenauer é que a solução de alguns problemas complexos, como problemas de agrupamento ou partição onde um conjunto de itens deve ser dividido em um grupo de elementos disjuntos de uma forma ótima, seria melhor alcançado obtendo características de grupos de itens equivalentes a genes. Esses tipos de problemas incluem embalagem de contêineres, balanceamento de linhas, agrupamento em relação a uma medida de distância, pilhas iguais, etc., nos quais os AGs clássicos demonstraram baixo desempenho. Tornar genes equivalentes a grupos envolve cromossomos que geralmente têm comprimento variável e operadores genéticos especiais que manipulam grupos inteiros de elementos. Para embalagens de contêineres, em particular, um GGA hibridizado com o Critério de Dominância de Martello e Toth é possivelmente a melhor técnica até o momento.

• - Algoritmos evolutivos interativos são algoritmos evolutivos que utilizam avaliação humana. Eles são normalmente aplicados a domínios onde é difícil projetar uma função de aptidão computacional, por exemplo, evoluindo imagens, músicas, designs artísticos e formas para atender às preferências estéticas dos usuários.

• - A otimização de colônias de formigas (ACO) utiliza muitas formigas (ou agentes) equipadas com um modelo de feromônio para percorrer o espaço de solução e encontrar áreas produtivas locais. Uma estimativa do algoritmo de distribuição é considerada.

• - A otimização por enxame de partículas (PSO) é um método computacional para otimização multiparamétrica que também utiliza uma abordagem baseada na 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 tanto pela sua posição mais conhecida quanto pela posição global mais conhecida do enxame. Assim como os algoritmos genéticos, o método PSO depende da troca de informações entre 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.

• - O Algoritmo Memético (MA), frequentemente denominado algoritmo genético híbrido, entre outros, é um método de base populacional em que as soluções também estão sujeitas a fases de melhoria local. A ideia de algoritmos meméticos, que, diferentemente dos genes, podem se adaptar. Em algumas áreas problemáticas eles se mostram mais eficientes que os algoritmos evolutivos tradicionais.

• - Os algoritmos bacteriológicos (BA) são inspirados na ecologia evolutiva e, mais especificamente, na adaptação bacteriológica. A ecologia evolutiva é o estudo dos organismos vivos no contexto do 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 encaixe em todo o ambiente. Portanto, é preciso raciocinar no nível da população. Acredita-se também que os BAs poderiam ser aplicados com sucesso a problemas complexos de posicionamento (antenas de telefonia celular, planejamento urbano, etc.) ou mineração de dados. [52].

• - 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.

• - O algoritmo de busca diferencial (DS) é inspirado na migração de superorganismos.

• - A adaptação gaussiana (adaptação normal ou natural, abreviada como NA para evitar confusão com GA) tem como objetivo maximizar o desempenho de fabricação de sistemas de processamento de sinais. Também pode ser usado para otimização paramétrica comum. Baseia-se em um determinado teorema válido para todas as regiões de aceitabilidade e todas as distribuições gaussianas. A eficiência do 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 individual, a paisagem suaviza-se de tal forma que os vales entre os picos podem desaparecer. Portanto, tem uma certa “ambição” de evitar picos locais no cenário do fitness. NA também é bom para escalar cristas acentuadas, adaptando a matriz de momentos, porque NA pode maximizar a desordem (informação média) da Gaussiana enquanto mantém simultaneamente a aptidão média constante.

• - O recozimento simulado (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 diminui a aptidão é aceita probabilisticamente com base na diferença na aptidão e em um parâmetro de temperatura decrescente. No jargão SA, falamos em buscar o menor nível de energia em vez do máximo de condicionamento físico. SA também pode ser usado dentro de um algoritmo GA padrão, começando com uma taxa de mutação relativamente alta e diminuindo ao longo do tempo ao longo de um determinado cronograma.

• - A busca tabu (TS) é semelhante ao recozimento simulado, pois ambos atravessam o espaço de solução testando 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 move-se para a solução com a energia mais baixa daquelas geradas. Para evitar loops e encorajar movimentos adicionais através do espaço de soluções, uma lista tabu de soluções parciais ou completas é mantida. É proibido passar para uma solução que contenha elementos da lista tabu, que é atualizada à medida que a solução atravessa o espaço de soluções.

• - A Otimização Extrema (EO), diferentemente dos AGs, que trabalham com uma população de soluções candidatas, desenvolve uma solução única e faz modificações locais nos piores componentes. Isso requer que seja selecionada uma representação apropriada que permita que componentes individuais da solução recebam uma medida de qualidade (“adequação”). O princípio que rege este algoritmo é o da melhoria emergente, removendo seletivamente componentes de baixa qualidade e substituindo-os por um componente selecionado aleatoriamente. Isto está decididamente em desacordo com um AG que seleciona boas soluções na tentativa de criar soluções melhores.

• - O método de entropia cruzada (CE) gera soluções candidatas usando uma distribuição de probabilidade parametrizada. Os parâmetros são atualizados minimizando a entropia cruzada, para gerar melhores amostras na próxima iteração.

• - A otimização de busca reativa (RSO) defende a integração de técnicas de aprendizagem subsimbólica em heurísticas de busca para resolver problemas complexos de otimização. A palavra reativo sugere uma resposta rápida a eventos durante a busca por meio de um ciclo interno de feedback on-line para autoajuste de parâmetros críticos. Metodologias de interesse para pesquisa reativa incluem aprendizado de máquina e estatística, particularmente aprendizado por reforço, aprendizado ativo ou de consulta, redes neurais e metaheurísticas.

• - Redes Neurais.

• - Lógica difusa.

• - Rede bayesiana.

• - Mínimo/máximo local.

• - Inteligência Artificial.

• - Robótica Evolutiva").

• - Emergência "Emergência (filosofia)").

• - Autômato celular.

• - Código Santillán").

• - Banzhaf, Wolfgang; Nordin, Peter; Keller, Robert; Francone, Frank (1998). Programação genética - uma introdução. São Francisco, CA: Morgan Kaufmann. ISBN 978-1558605107.

• - Bies, Robert R.; Muldoon, Matthew F.; Pollock, Bruce G.; Manuck, Steven; Smith, Gwenn; Venda, Mark E. (2006). "A abordagem de aprendizado de máquina híbrida baseada em algoritmo genético para seleção de modelos." Jornal de Farmacocinética e Farmacodinâmica. Holanda: Springer: 196-221.

• - Carmona, Enrique J.; Fernández, Severino (2020). Fundamentos da Computação Evolucionária. Marcombo. ISBN 978-8426727558.

• -Cha, Sung-Hyuk; Tappert, Charles C. (2009). "Algoritmo genético para construção de árvores de decisão binárias compactas." Jornal de pesquisa de reconhecimento de padrões. 4 (1): 1-13. doi:10.13176/11.44.

• - Eiben, Agoston; Smith, James (2003). Introdução à Computação Evolutiva. Springer. ISBN 978-3540401841.

• - Fraser, Alex S. (1957). "Simulação de Sistemas Genéticos por Computadores Digitais Automáticos, I. Introdução." Jornal Australiano de Ciências Biológicas. 10: 484-491.

• -Goldberg, David (1989). Algoritmos Genéticos em Busca, Otimização e Aprendizado de Máquina. Leitura, MA: Addison-Wesley Professional. ISBN 978-0201157673.

• -Goldberg, David (2002). O Design da Inovação: Lições de e para Algoritmos Genéticos Competentes. Norwell, MA: Kluwer Academic Publishers. ISBN 978-1402070983.

• - Fogel, David. Computação Evolucionária: Rumo à Nova Filosofia da Inteligência de Máquina (3ª ed.). Piscataway, NJ: IEEE Press. ISBN 978-0471669517.

• -Hingston, Philip; Barone, Luigi Michalewicz, Zbigniew (2008). Design by Evolution: Avanços no Design Evolucionário. Springer. ISBN 978-3540741091.

• - Holanda, John (1992). Adaptação em Sistemas Naturais e Artificiais. Cambridge, MA: MIT Press. ISBN 978-0262581110.

• - Koza, John (1992). Programação genética: sobre a programação de computadores por meio da seleção natural. Cambridge, MA: MIT Press. ISBN 978-0262111706.

• - Michalewicz, Zbigniew (1996). Algoritmos Genéticos + Estruturas de Dados = Programas de Evolução. Springer-Verlag. ISBN 978-3540606765.

• - Mitchell, Melanie (1996). Uma introdução aos algoritmos genéticos Cambridge, MA: MIT Press. ISBN 9780585030944.

• - Poli, R.; Langdon, WB; McPhee, N.F. (2008). Um guia de campo para programação genética. Lulu.com, disponível gratuitamente na internet. ISBN 978-1-4092-0073-4.

• - Rechenberg, Ingo (1994): Evolutionsstrategie '94, Stuttgart: Fromman-Holzboog.

• - Schmitt, Lothar M; Nehaniv, Cristóvão L; Fujii, Robert H (1998), Análise linear de algoritmos genéticos, Theoretical Computer Science 208: 111-148.

• - Schmitt, Lothar M (2001), Teoria dos Algoritmos Genéticos, Ciência da Computação Teórica 259: 1-61.

• - Schmitt, Lothar M (2004), Teoria de Algoritmos Genéticos II: modelos para operadores genéticos sobre a representação de populações em tensores de cordas e convergência para otimização global para funções de aptidão arbitrárias sob escalonamento, Theoretical Computer Science 310: 181-231.

• - Schwefel, Hans-Paul (1974): Numerische Optimierung von Computer-Modellen (tese de doutorado). Reimpresso por Birkhäuser (1977).

• - Vose, Michael (1999). O Algoritmo Genético Simples: Fundamentos e Teoria. Cambridge, MA: MIT Press. ISBN 978-0262220583.

• -Whitley, Darrell (1994). "Um tutorial de algoritmo genético." Estatística e Computação. 4(2): 65-85. Doi:10.1007/BF00175354.

Recursos

• - (link quebrado) Este site descreve vários algoritmos genéticos junto com seus códigos de programação e como eles podem ser usados ​​para encontrar o ponto ideal de um processo.

• - Aplicação de algoritmos genéticos na otimização de laminados de materiais compósitos.

• - Tutorial Prático de Algoritmo Genético Programando passo a passo um Algoritmo Genético.

• - Introdução aos Algoritmos Genéticos com applets Java interativos.

• - Tutorial de algoritmos genéticos Arquivado em 28 de outubro de 2005 na Wayback Machine.

• - Um tutorial simples em espanhol sobre algoritmos genéticos.

• - Introdução aos Algoritmos Genéticos.

• - Algoritmos genéticos e computação evolutiva.

• - Robô com Sistema de Navegação baseado em Algoritmos Genéticos.

• - Algoritmos genéticos em Ruby.

• - Arquimedex.com Explicação simples e prática de algoritmos genéticos.

• - Poli, R., Langdon, W. B., McPhee, N. F. (2008), A Field Guide to Genetic Programming, disponível gratuitamente em Lulu.com, ISBN 978-1-4092-0073-4.

• - Algoritmos de Otimização Global - Teoria e Aplicação Arquivado em 11 de setembro de 2008 na Wayback Machine.

• - Trabalho de Tese de Licenciatura.

• - Implementação do problema das 8 rainhas em JAVA.

Tutoriais

• - Algoritmos Genéticos - Programas de computador que "evoluem" de maneiras que se assemelham à seleção natural podem resolver problemas complexos que mesmo seus criadores não entendem completamente. Uma excelente introdução ao GA por John Holland e com uma aplicação ao Dilema do Prisioneiro.

• - Um tutorial interativo on-line do GA para um leitor praticar ou aprender como um GA funciona: Aprenda passo a passo ou observe a convergência global em lote, altere o tamanho da população, taxas/limites de cruzamento, taxas/limites de mutação e mecanismos de seleção e adicione restrições.

• - Um Tutorial de Algoritmo Genético por Darrell Whitley Departamento de Ciência da Computação Colorado State University Um excelente tutorial com muita teoria.

• - "Fundamentos de Metaheurística", 2009 (225 p). Texto aberto gratuito de Sean Luke.

• - Algoritmos de Otimização Global – Teoria e Aplicação Arquivado em 11 de setembro de 2008 na Wayback Machine.

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 evolui em direção a melhores soluções. Cada solução candidata possui um conjunto de propriedades (seus cromossomos ou genótipos) que podem sofrer mutação e alterações. Tradicionalmente, as soluções são representadas em binário como sequências de zeros e uns, 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, sendo a população em cada iteração chamada de geração. Em cada geração, é avaliada a aptidão de cada indivíduo da população. Fitness é 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 "Recombinação (computação evolutiva)") 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 ocorre um número máximo de gerações ou quando um nível de aptidão satisfatório para a população é alcançado.

Um algoritmo genético típico requer:

1. • Uma representação genética do domínio de 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 "Matriz (matemática)") de bits. Matrizes de outros tipos e estruturas podem ser usadas 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 simples de cruzamento. Representações de comprimento variável também podem ser usadas, mas a implementação do cruzamento cromossômico é mais complexa neste caso. As representações de árvores são exploradas na programação genética e as representações semelhantes a gráficos 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 definidas a representação genética e a função de aptidão, um AG prossegue para inicializar uma população de soluções e então melhorá-la aplicando repetidamente os operadores de mutação, cruzamento, inversão e seleção.

O tamanho da população depende da natureza do problema, mas normalmente contém centenas ou milhares de soluções possíveis. Freqüentemente, a população inicial é gerada aleatoriamente, permitindo toda a gama de soluções possíveis (o espaço de busca). Ocasionalmente, as soluções podem ser “semeadas” em áreas onde é provável que sejam encontradas soluções óptimas.

Durante cada geração sucessiva, uma parte da população existente é selecionada para criar uma nova geração. As soluções individuais são selecionadas através de um processo baseado na aptidão, onde as soluções de aptidão (medidas por uma função de aptidão) têm normalmente maior probabilidade de serem selecionadas. Certos métodos de seleção avaliam a adequação de cada solução e selecionam preferencialmente as melhores soluções. Outros métodos pontuam apenas uma amostra aleatória da população, pois o processo acima pode ser demorado.

A função de aptidão é definida na representação genética e mede a qualidade da solução representada. A função de fitness sempre depende do problema. Por exemplo, no problema da mochila queremos maximizar o valor total dos objetos que podem ser colocados em uma mochila com alguma capacidade fixa. Uma representação de uma solução pode ser uma matriz 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 todas as representações são válidas, 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 da condição física. Nestes casos, a 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.

O próximo passo é gerar uma população de segunda geração, a partir de soluções selecionadas através de uma combinação de operadores genéticos: cruzamento cromossômico (também chamado de crossover ou recombinação) e mutação.

Para cada nova solução produzida, um par de soluções "pais" foi selecionado para reprodução a partir do conjunto previamente selecionado. Ao produzir uma solução de "reprodução" usando os métodos de cruzamento e mutação cromossômicos mencionados acima, é criada uma nova solução que normalmente compartilha muitas das características de seus "pais". Novos pais são selecionados para cada nova ninhada e o processo continua até que uma nova população de soluções de tamanho apropriado seja gerada. Embora os métodos de melhoramento que dependem do uso de dois pais sejam mais “inspirados na biologia”, algumas pesquisas sugerem que mais de dois “pais” podem gerar cromossomos de maior qualidade.

Em última análise, esses processos resultam na próxima geração de população cromossômica, que é diferente da geração inicial. Em geral, a aptidão média foi aumentada por este procedimento para a população, uma vez que apenas os melhores organismos da primeira geração são selecionados para reprodução, juntamente com uma pequena proporção de soluções menos adequadas. Estas soluções menos adequadas garantem a diversidade genética dentro do património genético dos pais e, portanto, asseguram a diversidade genética da próxima geração de crianças.

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

Embora cruzamento e mutação sejam conhecidos como os principais operadores genéticos, é possível utilizar outros operadores como rearranjo, extinção de colonizaçã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 ajustes razoáveis ​​para o tipo de problema em que você está trabalhando. 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 seja usada a seleção de elite.

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

• - É encontrada uma solução que satisfaz os critérios mínimos.

• - Um número fixo de gerações é atingido.

• - O orçamento atribuído é atingido (tempo de cálculo/dinheiro).

• - A adequação da solução com melhor classificação está atingindo ou atingiu um patamar tal que iterações sucessivas não produzem mais resultados melhores.

• - Inspeção manual.

• - Combinações dos itens acima.

Algoritmos genéticos são simples de implementar, mas seu comportamento é difícil de entender. Em particular, é difícil compreender porque é que estes algoritmos são frequentemente bem sucedidos na geração de soluções de elevada aptidão quando aplicados a problemas práticos. A hipótese do bloco de construção (BBH) consiste em:.

• - Uma descrição de uma heurística que realiza adaptação identificando e recombinando "blocos de construção", isto é, esquemas de definição de baixa ordem e baixo comprimento com aptidão acima da média.

• - Uma hipótese de que um algoritmo genético realiza a adaptação de forma implícita e eficiente ao implementar esta heurística.

Goldberg descreve a heurística da seguinte forma:

Esquemas curtos, de baixa ordem e de alto ajuste são amostrados, recombinados (reticulados) e reamostrados para formar cadeias 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 cadeias de alto desempenho tentando todas as combinações concebíveis, construímos cadeias cada vez melhores a partir das melhores soluções parciais das últimas amostras.

"Como esquemas altamente ajustados de baixo comprimento e baixa ordem desempenham um papel tão importante na ação dos algoritmos genéticos, já lhes demos um nome especial: blocos de construção. Assim como uma criança cria fortalezas magníficas através do arranjo de blocos de madeira simples, o mesmo acontece com um algoritmo genético que busca se aproximar do desempenho ideal através 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 do bloco de construção, ela tem sido avaliada e utilizada como referência ao longo dos anos. Muitos algoritmos de distribuição de estimativa, por exemplo, foram propostos na tentativa de fornecer um ambiente no qual a hipótese seria válida. Embora bons resultados tenham sido relatados para algumas classes de problemas, ainda permanece ceticismo em relação à generalidade e/ou praticidade da hipótese do bloco de construção como uma explicação da eficiência dos AGs. Na verdade, há uma quantidade razoável de trabalhos que tentam compreender suas limitações do ponto de vista da estimativa de algoritmos de distribuição.

Existem limitações no 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 é frequentemente o segmento mais proibitivo e limitante dos algoritmos evolutivos artificiais. Encontrar a solução ideal para problemas tridimensionais e multimodais complexos geralmente requer avaliações de funções de condicionamento muito caras. Em problemas do mundo real, como problemas de otimização estrutural, a avaliação de uma única função pode exigir de várias horas a vários dias de simulação completa. Os métodos típicos de otimização não conseguem lidar com esses tipos de problemas. Neste caso, pode ser necessário renunciar à avaliação exata e utilizar uma aptidão aproximada que seja computacionalmente eficiente. É evidente que a fusão de modelos aproximados pode ser uma das abordagens mais promissoras para usar de forma convincente a AG para resolver problemas complexos da vida real.

• - Algoritmos genéticos não se adaptam bem à complexidade. Ou seja, quando o número de elementos expostos à mutação é grande, muitas vezes ocorre 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. Para tornar tais problemas tratáveis ​​à pesquisa evolutiva, eles devem ser decompostos na representação mais simples possível. Portanto, normalmente vemos algoritmos evolutivos codificando 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 completos de aeronaves. 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 a sua avaliação de aptidão exige que se combinem bem com outras partes.

• - A “melhor” solução é apenas em comparação com outras soluções. Como resultado, o critério de parada não é claro em cada problema.

• - Em muitos problemas, os AGs podem ter uma tendência a convergir para pontos ótimos locais ou mesmo para pontos arbitrários, em vez de para o ótimo global do problema. Isto significa que eles não “sabem como” sacrificar a aptidão física a curto prazo para ganhar aptidão física a longo prazo. A probabilidade de isto ocorrer depende da forma do cenário de aptidão: certos problemas podem proporcionar uma subida fácil em direcção a um óptimo global, outros podem tornar mais fácil para a função encontrar o óptimo local. Este problema pode ser aliviado usando uma função de aptidão diferente, aumentando a taxa de mutação, ou usando técnicas de seleção que mantenham uma população diversificada de soluções [12], embora o teorema do almoço grátis [13] mostre que não existe uma solução geral para este problema. Uma técnica comum para manter a diversidade é impor uma “penalidade de nicho”, na qual qualquer grupo de indivíduos de similaridade semelhante (raio de nicho) tem uma penalidade adicional, o que reduzirá a representação desse grupo nas gerações subsequentes, permitindo que outros sejam 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 nos algoritmos genéticos (e na programação genética) porque o cruzamento de uma população homogênea não gera novas soluções. Nas estratégias de evolução e na programação evolutiva, a diversidade não é essencial devido a uma maior dependência da mutação.

• - Operar em conjuntos de dados dinâmicos é difícil, pois os genomas começam a convergir precocemente para soluções que não são mais válidas para dados subsequentes. Vários métodos foram propostos para remediar esta situação, aumentando de alguma forma a diversidade genética e prevenindo a convergência precoce, seja aumentando a probabilidade de mutação quando a qualidade da solução cai (chamada hipermutação desencadeada) ou introduzindo ocasionalmente novos elementos gerados aleatoriamente no conjunto de genes (chamados 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 coma”, na qual os pais não são mantidos e os novos pais são seleccionados apenas a partir da descendência. Isso pode ser mais eficaz em problemas dinâmicos.

• - Os AGs não podem resolver problemas onde a única medida correta é uma medida certa/errada (como problemas de decisão), uma vez que não há como convergir para a solução (não há colina para subir). Nestes casos, uma busca aleatória pode encontrar uma solução tão rapidamente quanto um AG. No entanto, se a situação permitir que o teste de sucesso/fracasso seja repetido, dando (possivelmente) resultados diferentes, então a proporção de sucessos em relação aos fracassos fornece uma medida apropriada de adequação.

• - Para problemas específicos de otimização e instâncias problemáticas, outros algoritmos de otimização podem ser mais eficientes que algoritmos genéticos em termos de velocidade de convergência "Convergência (matemática)"). Algoritmos alternativos e complementares incluem estratégias de evolução, programação evolutiva, recozimento simulado, adaptação gaussiana, subida de colinas e inteligência de enxame (por exemplo: otimização 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 do conhecimento do problema; Problemas bem conhecidos geralmente têm abordagens melhores e mais especializadas.

Representação cromossômica

O algoritmo mais simples representa cada cromossomo como uma sequência de bits. Normalmente, os parâmetros numéricos podem ser representados por números 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 na verdade é um nome impróprio porque não representa realmente a teoria dos blocos de construção proposta por John Henry Holland na década de 1970. Esta teoria tem suporte, entretanto, baseada em resultados teóricos e experimentais (veja abaixo). O algoritmo básico realiza cruzamento e mutação no nível de bit. 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 feitos para 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.

Ao usar representações de números de bits de inteiros, a codificação Gray é frequentemente empregada. Desta forma, pequenas alterações no número inteiro podem ser facilmente afetadas por mutações ou cruzamentos. Descobriu-se que isso ajuda a prevenir a convergência prematura em paredes chamadas de Hamming, nas quais muitas mutações simultâneas (ou eventos de cruzamento) devem ocorrer para mudar o cromossomo para uma solução melhor.

Outras abordagens envolvem o uso de matrizes de números com valores reais em vez de sequências de bits para representar cromossomos. Os resultados da teoria dos esquemas sugerem que, em geral, quanto menor o alfabeto, melhor o desempenho, mas foi inicialmente surpreendente para os investigadores que bons resultados foram obtidos utilizando cromossomas 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 [14] [15].

Uma expansão do problema de domínio acessível do algoritmo genético pode ser obtida através da solução de codificação mais complexa de clusters por concatenação de vários tipos de genes codificados heterogeneamente em um cromossomo. [16] Esta abordagem particular permite resolver problemas de otimização que requerem domínios de definição extremamente díspares para os parâmetros do problema. Por exemplo, em problemas de ajuste de controlador em cascata, a estrutura do controlador de malha interna pode pertencer a um controlador convencional de três parâmetros, enquanto a malha externa pode implementar um controlador linguístico (como um sistema fuzzy) que possui uma descrição inerentemente diferente. Esta forma particular de codificação requer um mecanismo de cruzamento especializado que recombina o cromossomo por seção e é uma ferramenta útil para modelagem e simulação de sistemas adaptativos complexos, especialmente processos evolutivos.

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. Esta estratégia é conhecida como seleção de elite e garante que a qualidade da solução obtida pelo AG não diminuirá de uma geração para 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 de computação e migração de indivíduos entre os nós. Algoritmos genéticos paralelos assumem um indivíduo em cada nó de processamento 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 de tempo ou ruído na função de aptidão.

Algoritmo genético adaptativo

Algoritmos genéticos com parâmetros adaptativos (algoritmos genéticos adaptativos, AGAs) são outra variante significativa e promissora de algoritmos genéticos. As probabilidades de cruzamento (pc) e mutação (pm) determinam em grande parte 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 p. m., os AGs utilizam as informações populacionais em cada geração e ajustam adaptativamente pc e p. m. a fim de manter a diversidade populacional, bem como para sustentar a capacidade de convergência. No AGA (algoritmo genético adaptativo), o ajuste de pc e p. m. Depende dos valores de aptidão das soluções. No CAGA (algoritmo adaptativo baseado em clustering), através do uso de análise de cluster para julgar os estados de otimalidade da população, o ajuste de pc e p. m. depende desses estados de otimização. Pode ser muito eficaz combinar 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 a simples subida de colinas) são bastante eficientes para encontrar o ótimo absoluto em uma região limitada. Alternar GA e subida de colinas pode melhorar a eficiência da GA [carece de fontes] ao mesmo tempo em que supera a insegurança da subida de colinas.

Isto 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 cruzamento pode adicionar uma série de etapas de DNA materno adicionando uma série de etapas de DNA paterno e assim por diante. Isto é como adicionar vetores que provavelmente podem seguir uma crista na paisagem fenotípica. Portanto, a eficiência do processo pode ser aumentada em muitas ordens de grandeza. Além disso, o trader de investimento tem a oportunidade de colocar as etapas em ordem consecutiva ou em qualquer outra ordem apropriada em favor da sobrevivência ou da eficiência.

Uma variação, na qual a população como um todo se desenvolve em vez de seus membros individuais, é conhecida como recombinação de grupo genético.

Uma série de variações foram desenvolvidas para tentar melhorar o desempenho dos AGs em problemas com alto grau de epistasia de aptidão, ou seja, quando a aptidão de uma solução consiste na interação de subconjuntos de suas variáveis. Tais algoritmos visam aprender (antes de explorar) essas interações fenotípicas benéficas. Como tal, estão alinhados com a hipótese do bloco de construção na redução adaptativa da recombinação disruptiva.

Problemas que parecem ser particularmente adequados para solução usando algoritmos genéticos incluem problemas de programação, e muitos pacotes de software de programação são baseados em AGs. GAs também foram aplicados à engenharia. 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 possuem um cenário de aptidão complexo, uma vez que a mistura, isto é, a mutação em combinação com o cruzamento "Recombinação (computação evolutiva)"), é projetada para afastar a população ainda mais do ótimo local do que um algoritmo tradicional. Observe que os operadores de cruzamento 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).

Contenido

En 1950, Alan Turing propuso una "máquina de aprendizaje" que sería paralela a los principios de la evolución. La simulación por computadora de la evolución comenzó tan pronto como en 1954 con el trabajo de Nils Aall Barricelli"), que utilizaba la computadora en el instituto para el estudio avanzado en Princeton (Nueva Jersey) "Princeton (Nueva Jersey)"). Su publicación de 1954 no fue ampliamente notada. A partir de 1957, el australiano cuantitativo genetista Alex Fraser") publicó una serie de artículos sobre la simulación de la selección artificial de organismos con múltiples loci controlando un rasgo mensurable. A partir de estos comienzos, la simulación por ordenador de la evolución por los biólogos se hizo más común a principios de 1960, y los métodos fueron descritos en los libros de Fraser y Burnell (1970) y Crosby (1973) Las simulaciones de Fraser incluían todos los elementos esenciales de los algoritmos genéticos modernos. Además, Hans-Joachim Bremermann publicó una serie de artículos en los años sesenta que también adoptaron una población de solución a problemas de optimización, sometidos a recombinación, mutación y selección. La investigación de Bremermann también incluyó los elementos de los algoritmos genéticos modernos. Otros destacados primeros pioneros son Richard Friedberg"), George Friedman y Michael Conrad. Muchos de los primeros artículos han sido reimpresos por Fogel (1998).

Aunque Barricelli, en el trabajo que relató en 1963, había simulado la evolución de la capacidad de jugar un juego simple, la evolución artificial se convirtió en un método de optimización ampliamente reconocido como resultado del trabajo de Ingo Rechenberg y Hans-Paul Schwefel en los años 1960 y principios de 1970 - el grupo de Rechenberg fue capaz de resolver problemas complejos de ingeniería a través de estrategias de evolución.Otro enfoque fue la técnica de programación evolutiva de Lawrence J. Fogel, que se propuso para generar inteligencia artificial. La programación evolutiva utilizó originalmente máquinas de estado finito para predecir los entornos y utilizó la variación y la selección para optimizar las lógicas predictivas. Los algoritmos genéticos, en particular, se hicieron populares a través del trabajo de John Henry Holland a principios de los años setenta, y particularmente de su libro Adaptation in Natural and Artificial Systems (1975). Su trabajo se originó con estudios de autómatas celulares, conducidos por Holland y sus estudiantes en la Universidad de Míchigan. Holland introdujo un marco formalizado para predecir la calidad de la próxima generación, conocido como el teorema del esquema de Holland. La investigación en GAs permaneció en gran parte teórica hasta mediados de los años 80, cuando la primera conferencia internacional en algoritmos genéticos fue llevada a cabo en Pittsburgh, Pensilvania.

Produtos comerciais

No final da década de 1980, a General Electric começou a vender o primeiro produto de algoritmo genético do mundo, uma caixa de ferramentas baseada em mainframe projetada para processos industriais. Em 1989, a Axcelis, Inc. lançou o Evolver, o primeiro produto comercial da AG 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 de negociação 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.

Considérese el problema de insertar signos de suma o resta entre los dígitos 9 8 7 6 5 4 3 2 1 para construir una expresión cuyo valor sea 100; no vale añadir, retirar o desordenar a los dígitos. Una solución puede ser 98+7-6+5-4+3-2-1 porque, al evaluar su valor, da exactamente 100.

Hay 9 sitios (uno antes de cada dígito) donde colocar un signo de más (+), un signo de menos (-) o nada (lo cual implicará que dos o más dígitos se unan para formar cantidades mayores; como 98 en el ejemplo anterior, donde se puso "nada" antes del 9 y antes del 8). Existen, por lo tanto, 3 a la 9 = 19683 expresiones distintas (por combinatoria) entre las cuales buscar aquellas con la suma deseada. Es posible desarrollar un algoritmo exhaustivo que las genere todas y, dada la relativa pequeñez de este ejemplo, determinar completamente todas las posibles configuraciones. Sin embargo, este reto se presta para ilustrar los pasos de un proceso genético.

Codificação

Existe uma bijeção entre as cadeias de “trits” (dígitos ternários: 0, 1, 2) de comprimento 9 e as possíveis configurações de sinais para cada soma. Por exemplo, se for adotada a convenção de que "0" representa "nada", "1" representa "menos" e "2" representa "mais", então a sequência de "trits" 002121211 corresponde à solução 98+7-6+5-4+3-2-1.

Campos pai

Algoritmos genéticos são um subcampo de:.

• - Algoritmos evolutivos.

• - Computação evolutiva.

• - Metaheurísticas.

• - Otimização estocástica.

• - Melhoria.

Campos relacionados

Algoritmos evolutivos são um subcampo da computação evolutiva.

• - As estratégias de evolução (ES, ver Rechenberg, 1994) evoluem os indivíduos através de mutação e recombinação intermediária ou discreta. Os algoritmos ES são especialmente projetados para resolver problemas no domínio do valor real. Eles usam autoadaptação para ajustar os parâmetros de controle de busca. A desrandomização da autoadaptação levou à atual Estratégia de Evolução de Adaptação da Matriz de Covariância (CMA-ES).

• - A programação evolutiva (PE) envolve populações de soluções com mutação e seleção e representações arbitrárias. Ele usa autoadaptação para ajustar parâmetros e pode incluir outras operações de variação, como combinar informações de vários pais.

• - O Algoritmo de Distribuição de Estimativa (EDA) substitui os operadores de repetição tradicionais por operadores orientados por modelo. Esses modelos são aprendidos com a população usando 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 [45] [46] ou geradas a partir de cruzamentos cromossômicos guiados [47].

• - A programação de expressão genética (GEP) também utiliza populações de programas de computador. Esses programas de computador complexos são codificados em cromossomos lineares mais simples de comprimento fixo, que são então expressos como árvores de expressão. Árvores de expressão ou programas de computador evoluem porque os cromossomos sofrem mutação e recombinação de maneira semelhante ao GA canônico. Mas graças à organização especial dos cromossomas GEP, estas modificações genéticas resultam sempre em programas de computador válidos. [48].

• - A programação genética (GP) é uma técnica relacionada popularizada por John Koza na qual programas de computador, em vez de parâmetros funcionais, são otimizados. A programação genética geralmente usa estruturas de dados internas baseadas em árvores para representar programas de computador para adaptação, em vez das estruturas de lista típicas dos algoritmos genéticos.

• - O agrupamento de algoritmos genéticos (GGA) é uma evolução do AG onde o foco muda de elementos individuais, como no AG clássico, para grupos ou subconjuntos de elementos. [49] A ideia por trás desta evolução do AG proposta por Emanuel Falkenauer é que a solução de alguns problemas complexos, como problemas de agrupamento ou partição onde um conjunto de itens deve ser dividido em um grupo de elementos disjuntos de uma forma ótima, seria melhor alcançado obtendo características de grupos de itens equivalentes a genes. Esses tipos de problemas incluem embalagem de contêineres, balanceamento de linhas, agrupamento em relação a uma medida de distância, pilhas iguais, etc., nos quais os AGs clássicos demonstraram baixo desempenho. Tornar genes equivalentes a grupos envolve cromossomos que geralmente têm comprimento variável e operadores genéticos especiais que manipulam grupos inteiros de elementos. Para embalagens de contêineres, em particular, um GGA hibridizado com o Critério de Dominância de Martello e Toth é possivelmente a melhor técnica até o momento.

• - Algoritmos evolutivos interativos são algoritmos evolutivos que utilizam avaliação humana. Eles são normalmente aplicados a domínios onde é difícil projetar uma função de aptidão computacional, por exemplo, evoluindo imagens, músicas, designs artísticos e formas para atender às preferências estéticas dos usuários.

• - A otimização de colônias de formigas (ACO) utiliza muitas formigas (ou agentes) equipadas com um modelo de feromônio para percorrer o espaço de solução e encontrar áreas produtivas locais. Uma estimativa do algoritmo de distribuição é considerada.

• - A otimização por enxame de partículas (PSO) é um método computacional para otimização multiparamétrica que também utiliza uma abordagem baseada na 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 tanto pela sua posição mais conhecida quanto pela posição global mais conhecida do enxame. Assim como os algoritmos genéticos, o método PSO depende da troca de informações entre 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.

• - O Algoritmo Memético (MA), frequentemente denominado algoritmo genético híbrido, entre outros, é um método de base populacional em que as soluções também estão sujeitas a fases de melhoria local. A ideia de algoritmos meméticos, que, diferentemente dos genes, podem se adaptar. Em algumas áreas problemáticas eles se mostram mais eficientes que os algoritmos evolutivos tradicionais.

• - Os algoritmos bacteriológicos (BA) são inspirados na ecologia evolutiva e, mais especificamente, na adaptação bacteriológica. A ecologia evolutiva é o estudo dos organismos vivos no contexto do 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 encaixe em todo o ambiente. Portanto, é preciso raciocinar no nível da população. Acredita-se também que os BAs poderiam ser aplicados com sucesso a problemas complexos de posicionamento (antenas de telefonia celular, planejamento urbano, etc.) ou mineração de dados. [52].

• - 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.

• - O algoritmo de busca diferencial (DS) é inspirado na migração de superorganismos.

• - A adaptação gaussiana (adaptação normal ou natural, abreviada como NA para evitar confusão com GA) tem como objetivo maximizar o desempenho de fabricação de sistemas de processamento de sinais. Também pode ser usado para otimização paramétrica comum. Baseia-se em um determinado teorema válido para todas as regiões de aceitabilidade e todas as distribuições gaussianas. A eficiência do 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 individual, a paisagem suaviza-se de tal forma que os vales entre os picos podem desaparecer. Portanto, tem uma certa “ambição” de evitar picos locais no cenário do fitness. NA também é bom para escalar cristas acentuadas, adaptando a matriz de momentos, porque NA pode maximizar a desordem (informação média) da Gaussiana enquanto mantém simultaneamente a aptidão média constante.

• - O recozimento simulado (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 diminui a aptidão é aceita probabilisticamente com base na diferença na aptidão e em um parâmetro de temperatura decrescente. No jargão SA, falamos em buscar o menor nível de energia em vez do máximo de condicionamento físico. SA também pode ser usado dentro de um algoritmo GA padrão, começando com uma taxa de mutação relativamente alta e diminuindo ao longo do tempo ao longo de um determinado cronograma.

• - A busca tabu (TS) é semelhante ao recozimento simulado, pois ambos atravessam o espaço de solução testando 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 move-se para a solução com a energia mais baixa daquelas geradas. Para evitar loops e encorajar movimentos adicionais através do espaço de soluções, uma lista tabu de soluções parciais ou completas é mantida. É proibido passar para uma solução que contenha elementos da lista tabu, que é atualizada à medida que a solução atravessa o espaço de soluções.

• - A Otimização Extrema (EO), diferentemente dos AGs, que trabalham com uma população de soluções candidatas, desenvolve uma solução única e faz modificações locais nos piores componentes. Isso requer que seja selecionada uma representação apropriada que permita que componentes individuais da solução recebam uma medida de qualidade (“adequação”). O princípio que rege este algoritmo é o da melhoria emergente, removendo seletivamente componentes de baixa qualidade e substituindo-os por um componente selecionado aleatoriamente. Isto está decididamente em desacordo com um AG que seleciona boas soluções na tentativa de criar soluções melhores.

• - O método de entropia cruzada (CE) gera soluções candidatas usando uma distribuição de probabilidade parametrizada. Os parâmetros são atualizados minimizando a entropia cruzada, para gerar melhores amostras na próxima iteração.

• - A otimização de busca reativa (RSO) defende a integração de técnicas de aprendizagem subsimbólica em heurísticas de busca para resolver problemas complexos de otimização. A palavra reativo sugere uma resposta rápida a eventos durante a busca por meio de um ciclo interno de feedback on-line para autoajuste de parâmetros críticos. Metodologias de interesse para pesquisa reativa incluem aprendizado de máquina e estatística, particularmente aprendizado por reforço, aprendizado ativo ou de consulta, redes neurais e metaheurísticas.

• - Redes Neurais.

• - Lógica difusa.

• - Rede bayesiana.

• - Mínimo/máximo local.

• - Inteligência Artificial.

• - Robótica Evolutiva").

• - Emergência "Emergência (filosofia)").

• - Autômato celular.

• - Código Santillán").

• - Banzhaf, Wolfgang; Nordin, Peter; Keller, Robert; Francone, Frank (1998). Programação genética - uma introdução. São Francisco, CA: Morgan Kaufmann. ISBN 978-1558605107.

• - Bies, Robert R.; Muldoon, Matthew F.; Pollock, Bruce G.; Manuck, Steven; Smith, Gwenn; Venda, Mark E. (2006). "A abordagem de aprendizado de máquina híbrida baseada em algoritmo genético para seleção de modelos." Jornal de Farmacocinética e Farmacodinâmica. Holanda: Springer: 196-221.

• - Carmona, Enrique J.; Fernández, Severino (2020). Fundamentos da Computação Evolucionária. Marcombo. ISBN 978-8426727558.

• -Cha, Sung-Hyuk; Tappert, Charles C. (2009). "Algoritmo genético para construção de árvores de decisão binárias compactas." Jornal de pesquisa de reconhecimento de padrões. 4 (1): 1-13. doi:10.13176/11.44.

• - Eiben, Agoston; Smith, James (2003). Introdução à Computação Evolutiva. Springer. ISBN 978-3540401841.

• - Fraser, Alex S. (1957). "Simulação de Sistemas Genéticos por Computadores Digitais Automáticos, I. Introdução." Jornal Australiano de Ciências Biológicas. 10: 484-491.

• -Goldberg, David (1989). Algoritmos Genéticos em Busca, Otimização e Aprendizado de Máquina. Leitura, MA: Addison-Wesley Professional. ISBN 978-0201157673.

• -Goldberg, David (2002). O Design da Inovação: Lições de e para Algoritmos Genéticos Competentes. Norwell, MA: Kluwer Academic Publishers. ISBN 978-1402070983.

• - Fogel, David. Computação Evolucionária: Rumo à Nova Filosofia da Inteligência de Máquina (3ª ed.). Piscataway, NJ: IEEE Press. ISBN 978-0471669517.

• -Hingston, Philip; Barone, Luigi Michalewicz, Zbigniew (2008). Design by Evolution: Avanços no Design Evolucionário. Springer. ISBN 978-3540741091.

• - Holanda, John (1992). Adaptação em Sistemas Naturais e Artificiais. Cambridge, MA: MIT Press. ISBN 978-0262581110.

• - Koza, John (1992). Programação genética: sobre a programação de computadores por meio da seleção natural. Cambridge, MA: MIT Press. ISBN 978-0262111706.

• - Michalewicz, Zbigniew (1996). Algoritmos Genéticos + Estruturas de Dados = Programas de Evolução. Springer-Verlag. ISBN 978-3540606765.

• - Mitchell, Melanie (1996). Uma introdução aos algoritmos genéticos Cambridge, MA: MIT Press. ISBN 9780585030944.

• - Poli, R.; Langdon, WB; McPhee, N.F. (2008). Um guia de campo para programação genética. Lulu.com, disponível gratuitamente na internet. ISBN 978-1-4092-0073-4.

• - Rechenberg, Ingo (1994): Evolutionsstrategie '94, Stuttgart: Fromman-Holzboog.

• - Schmitt, Lothar M; Nehaniv, Cristóvão L; Fujii, Robert H (1998), Análise linear de algoritmos genéticos, Theoretical Computer Science 208: 111-148.

• - Schmitt, Lothar M (2001), Teoria dos Algoritmos Genéticos, Ciência da Computação Teórica 259: 1-61.

• - Schmitt, Lothar M (2004), Teoria de Algoritmos Genéticos II: modelos para operadores genéticos sobre a representação de populações em tensores de cordas e convergência para otimização global para funções de aptidão arbitrárias sob escalonamento, Theoretical Computer Science 310: 181-231.

• - Schwefel, Hans-Paul (1974): Numerische Optimierung von Computer-Modellen (tese de doutorado). Reimpresso por Birkhäuser (1977).

• - Vose, Michael (1999). O Algoritmo Genético Simples: Fundamentos e Teoria. Cambridge, MA: MIT Press. ISBN 978-0262220583.

• -Whitley, Darrell (1994). "Um tutorial de algoritmo genético." Estatística e Computação. 4(2): 65-85. Doi:10.1007/BF00175354.

Recursos

• - (link quebrado) Este site descreve vários algoritmos genéticos junto com seus códigos de programação e como eles podem ser usados ​​para encontrar o ponto ideal de um processo.

• - Aplicação de algoritmos genéticos na otimização de laminados de materiais compósitos.

• - Tutorial Prático de Algoritmo Genético Programando passo a passo um Algoritmo Genético.

• - Introdução aos Algoritmos Genéticos com applets Java interativos.

• - Tutorial de algoritmos genéticos Arquivado em 28 de outubro de 2005 na Wayback Machine.

• - Um tutorial simples em espanhol sobre algoritmos genéticos.

• - Introdução aos Algoritmos Genéticos.

• - Algoritmos genéticos e computação evolutiva.

• - Robô com Sistema de Navegação baseado em Algoritmos Genéticos.

• - Algoritmos genéticos em Ruby.

• - Arquimedex.com Explicação simples e prática de algoritmos genéticos.

• - Poli, R., Langdon, W. B., McPhee, N. F. (2008), A Field Guide to Genetic Programming, disponível gratuitamente em Lulu.com, ISBN 978-1-4092-0073-4.

• - Algoritmos de Otimização Global - Teoria e Aplicação Arquivado em 11 de setembro de 2008 na Wayback Machine.

• - Trabalho de Tese de Licenciatura.

• - Implementação do problema das 8 rainhas em JAVA.

Tutoriais

• - Algoritmos Genéticos - Programas de computador que "evoluem" de maneiras que se assemelham à seleção natural podem resolver problemas complexos que mesmo seus criadores não entendem completamente. Uma excelente introdução ao GA por John Holland e com uma aplicação ao Dilema do Prisioneiro.

• - Um tutorial interativo on-line do GA para um leitor praticar ou aprender como um GA funciona: Aprenda passo a passo ou observe a convergência global em lote, altere o tamanho da população, taxas/limites de cruzamento, taxas/limites de mutação e mecanismos de seleção e adicione restrições.

• - Um Tutorial de Algoritmo Genético por Darrell Whitley Departamento de Ciência da Computação Colorado State University Um excelente tutorial com muita teoria.

• - "Fundamentos de Metaheurística", 2009 (225 p). Texto aberto gratuito de Sean Luke.

• - Algoritmos de Otimização Global – Teoria e Aplicação Arquivado em 11 de setembro de 2008 na Wayback Machine.