Algoritmos Genéticos - Guia Rápido

Algoritmo Genético (GA) é uma técnica de otimização baseada em pesquisa baseada nos princípios de Genetics and Natural Selection. É freqüentemente usado para encontrar soluções ótimas ou quase ótimas para problemas difíceis que, de outra forma, levariam uma vida inteira para serem resolvidos. É frequentemente usado para resolver problemas de otimização, em pesquisa e em aprendizado de máquina.

Introdução à Otimização

Otimização é o processo de making something better. Em qualquer processo, temos um conjunto de entradas e um conjunto de saídas, conforme mostrado na figura a seguir.

Otimização refere-se a encontrar os valores das entradas de forma que obtenhamos os “melhores” valores de saída. A definição de “melhor” varia de problema para problema, mas em termos matemáticos, refere-se a maximizar ou minimizar uma ou mais funções objetivo, variando os parâmetros de entrada.

O conjunto de todas as soluções ou valores possíveis que as entradas podem assumir constitui o espaço de pesquisa. Neste espaço de busca, encontra-se um ponto ou um conjunto de pontos que fornece a solução ótima. O objetivo da otimização é encontrar aquele ponto ou conjunto de pontos no espaço de busca.

O que são algoritmos genéticos?

A natureza sempre foi uma grande fonte de inspiração para toda a humanidade. Algoritmos Genéticos (AGs) são algoritmos de pesquisa baseados nos conceitos de seleção natural e genética. GAs são um subconjunto de um ramo muito maior de computação conhecido comoEvolutionary Computation.

Os GAs foram desenvolvidos por John Holland e seus alunos e colegas da Universidade de Michigan, principalmente David E. Goldberg, e desde então foram testados em vários problemas de otimização com alto grau de sucesso.

Em GAs, temos um pool or a population of possible solutionspara o problema fornecido. Essas soluções então passam por recombinação e mutação (como na genética natural), produzindo novos filhos, e o processo se repete por várias gerações. Cada indivíduo (ou solução candidata) recebe um valor de aptidão (com base em seu valor de função objetivo) e os indivíduos mais aptos têm uma chance maior de acasalar e produzir indivíduos mais "aptos". Isso está de acordo com a teoria darwiniana da “sobrevivência do mais apto”.

Desta forma, continuamos “evoluindo” indivíduos ou soluções melhores ao longo das gerações, até chegarmos a um critério de parada.

Os algoritmos genéticos são suficientemente aleatórios por natureza, mas têm um desempenho muito melhor do que a pesquisa local aleatória (na qual apenas tentamos várias soluções aleatórias, acompanhando as melhores até agora), visto que também exploram informações históricas.

Vantagens dos GAs

Os AGs têm várias vantagens que os tornaram imensamente populares. Isso inclui -

  • Não requer nenhuma informação derivada (que pode não estar disponível para muitos problemas do mundo real).

  • É mais rápido e eficiente em comparação aos métodos tradicionais.

  • Possui recursos paralelos muito bons.

  • Otimiza funções contínuas e discretas e também problemas multi-objetivos.

  • Fornece uma lista de “boas” soluções e não apenas uma única solução.

  • Sempre obtém uma resposta para o problema, que fica melhor com o tempo.

  • Útil quando o espaço de pesquisa é muito grande e há um grande número de parâmetros envolvidos.

Limitações de GAs

Como qualquer técnica, os AGs também sofrem de algumas limitações. Isso inclui -

  • Os AGs não são adequados para todos os problemas, especialmente problemas que são simples e para os quais informações derivadas estão disponíveis.

  • O valor de aptidão é calculado repetidamente, o que pode ser caro do ponto de vista computacional para alguns problemas.

  • Sendo estocástico, não há garantias sobre a otimalidade ou a qualidade da solução.

  • Se não for implementado corretamente, o GA pode não convergir para a solução ideal.

GA - Motivação

Algoritmos genéticos têm a capacidade de fornecer uma solução “boa o suficiente” “rápida o suficiente”. Isso torna os algoritmos genéticos atraentes para uso na solução de problemas de otimização. Os motivos pelos quais os AGs são necessários são os seguintes -

Resolvendo problemas difíceis

Na ciência da computação, há um grande conjunto de problemas, que são NP-Hard. O que isso significa essencialmente é que, mesmo os sistemas de computação mais poderosos levam muito tempo (até anos!) Para resolver esse problema. Em tal cenário, GAs provam ser uma ferramenta eficiente para fornecerusable near-optimal solutions em um curto espaço de tempo.

Falha de métodos baseados em gradiente

Os métodos tradicionais baseados em cálculo funcionam começando em um ponto aleatório e movendo-se na direção do gradiente, até chegarmos ao topo da colina. Essa técnica é eficiente e funciona muito bem para funções objetivo de pico único, como a função de custo na regressão linear. Mas, na maioria das situações do mundo real, temos um problema muito complexo chamado de paisagens, que são feitas de muitos picos e muitos vales, o que faz com que tais métodos falhem, pois sofrem de uma tendência inerente de ficarem presos no ótimo local conforme mostrado na figura a seguir.

Obtendo uma boa solução rapidamente

Alguns problemas difíceis, como o Problema do Vendedor Viajante (TSP), têm aplicações do mundo real, como localização de caminho e projeto VLSI. Agora imagine que você está usando seu sistema de navegação GPS e leva alguns minutos (ou mesmo algumas horas) para calcular o caminho “ideal” da origem ao destino. Atrasos em tais aplicativos do mundo real não são aceitáveis ​​e, portanto, uma solução "boa o suficiente", que é entregue "rápido" é o que é necessário.

Esta seção apresenta a terminologia básica necessária para entender os AGs. Além disso, uma estrutura genérica de GAs é apresentada em ambospseudo-code and graphical forms. O leitor é aconselhado a compreender adequadamente todos os conceitos introduzidos nesta seção e mantê-los em mente ao ler outras seções deste tutorial.

Terminologia Básica

Antes de iniciar uma discussão sobre Algoritmos Genéticos, é essencial estar familiarizado com alguma terminologia básica que será usada ao longo deste tutorial.

  • Population- É um subconjunto de todas as soluções possíveis (codificadas) para o problema fornecido. A população de um AG é análoga à população de seres humanos, exceto que, em vez de seres humanos, temos Soluções Candidatas que representam seres humanos.

  • Chromosomes - Um cromossomo é uma dessas soluções para o problema em questão.

  • Gene - Um gene é a posição de um elemento de um cromossomo.

  • Allele - É o valor que um gene assume para um cromossomo específico.

  • Genotype- Genótipo é a população no espaço de computação. No espaço de computação, as soluções são representadas de uma forma que podem ser facilmente entendidas e manipuladas por meio de um sistema de computação.

  • Phenotype - Fenótipo é a população no espaço de solução do mundo real real, no qual as soluções são representadas de uma forma que são representadas em situações do mundo real.

  • Decoding and Encoding - Para problemas simples, o phenotype and genotypeos espaços são iguais. No entanto, na maioria dos casos, o fenótipo e os espaços genotípicos são diferentes. A decodificação é um processo de transformação de uma solução do genótipo para o espaço do fenótipo, enquanto a codificação é um processo de transformação do fenótipo para o espaço do genótipo. A decodificação deve ser rápida, pois é realizada repetidamente em um GA durante o cálculo do valor de aptidão.

    Por exemplo, considere o problema da mochila 0/1. O espaço Fenótipo consiste em soluções que contêm apenas os números dos itens a serem retirados.

    No entanto, no espaço do genótipo, ele pode ser representado como uma string binária de comprimento n (onde n é o número de itens). UMA0 at position x representa isso xtho item é escolhido enquanto 1 representa o reverso. Este é um caso em que os espaços de genótipo e fenótipo são diferentes.

  • Fitness Function- Uma função de aptidão definida de forma simples é uma função que toma a solução como entrada e produz a adequação da solução como saída. Em alguns casos, a função de adequação e a função objetivo podem ser as mesmas, enquanto em outros podem ser diferentes com base no problema.

  • Genetic Operators- Alteram a composição genética da prole. Isso inclui crossover, mutação, seleção, etc.

Estrutura básica

A estrutura básica de um GA é a seguinte -

Começamos com uma população inicial (que pode ser gerada aleatoriamente ou semeada por outras heurísticas), selecionamos os pais desta população para acasalamento. Aplique operadores de crossover e mutação nos pais para gerar novos descendentes. E finalmente esses descendentes substituem os indivíduos existentes na população e o processo se repete. Desta forma, os algoritmos genéticos realmente tentam imitar a evolução humana até certo ponto.

Cada uma das etapas a seguir são abordadas como um capítulo separado posteriormente neste tutorial.

Um pseudocódigo generalizado para um GA é explicado no programa a seguir -

GA()
   initialize population
   find fitness of population
   
   while (termination criteria is reached) do
      parent selection
      crossover with probability pc
      mutation with probability pm
      decode and fitness calculation
      survivor selection
      find best
   return best

Uma das decisões mais importantes a se tomar ao implementar um algoritmo genético é decidir a representação que usaremos para representar nossas soluções. Observou-se que a representação inadequada pode levar ao mau desempenho do AG.

Portanto, a escolha de uma representação adequada, tendo uma definição adequada dos mapeamentos entre o fenótipo e os espaços genotípicos é essencial para o sucesso de um AG.

Nesta seção, apresentamos algumas das representações mais comumente usadas para algoritmos genéticos. No entanto, a representação é altamente específica para o problema e o leitor pode descobrir que outra representação ou uma mistura das representações mencionadas aqui pode se adequar melhor ao seu problema.

Representação Binária

Esta é uma das representações mais simples e amplamente utilizadas em AGs. Nesse tipo de representação, o genótipo consiste em cadeias de bits.

Para alguns problemas quando o espaço de solução consiste em variáveis ​​de decisão booleanas - sim ou não, a representação binária é natural. Veja, por exemplo, o problema da mochila 0/1. Se houver n itens, podemos representar uma solução por uma string binária de n elementos, onde o x- ésimo elemento diz se o item x é escolhido (1) ou não (0).

Para outros problemas, especificamente aqueles que lidam com números, podemos representar os números com sua representação binária. O problema com esse tipo de codificação é que bits diferentes têm significados diferentes e, portanto, os operadores de mutação e de cruzamento podem ter consequências indesejadas. Isso pode ser resolvido até certo ponto usandoGray Coding, já que uma mudança em um bit não tem um efeito massivo na solução.

Representação de valor real

Para problemas em que queremos definir os genes usando variáveis ​​contínuas em vez de variáveis ​​discretas, a representação com valor real é a mais natural. A precisão desses números reais de valor ou de ponto flutuante é, entretanto, limitada ao computador.

Representação Inteira

Para genes de valor discreto, nem sempre podemos limitar o espaço de solução para 'sim' ou 'não' binário. Por exemplo, se quisermos codificar as quatro distâncias - Norte, Sul, Leste e Oeste, podemos codificá-las como{0,1,2,3}. Nesses casos, a representação inteira é desejável.

Representação de Permutação

Em muitos problemas, a solução é representada por uma ordem de elementos. Em tais casos, a representação de permutação é a mais adequada.

Um exemplo clássico dessa representação é o problema do caixeiro viajante (TSP). Nela, o vendedor deve fazer um tour por todas as cidades, visitando cada cidade exatamente uma vez e voltar à cidade de origem. A distância total do passeio deve ser minimizada. A solução para este TSP é naturalmente uma ordenação ou permutação de todas as cidades e, portanto, usar uma representação de permutação faz sentido para este problema.

A população é um subconjunto de soluções na geração atual. Também pode ser definido como um conjunto de cromossomos. Há várias coisas a serem mantidas em mente ao lidar com a população GA -

  • A diversidade da população deve ser mantida, caso contrário, pode levar a uma convergência prematura.

  • O tamanho da população não deve ser mantido muito grande, pois pode causar uma desaceleração do GA, enquanto uma população menor pode não ser suficiente para um bom acasalamento. Portanto, o tamanho ideal da população precisa ser decidido por tentativa e erro.

A população é geralmente definida como uma matriz bidimensional de - size population, size x, chromosome size.

Inicialização de População

Existem dois métodos principais para inicializar uma população em um GA. Eles são -

  • Random Initialization - Preencher a população inicial com soluções completamente aleatórias.

  • Heuristic initialization - Preencher a população inicial usando uma heurística conhecida para o problema.

Observou-se que toda a população não deve ser inicializada por heurística, pois isso pode resultar na população com soluções semelhantes e muito pouca diversidade. Foi experimentalmente observado que as soluções aleatórias são as que levam a população à otimização. Portanto, com a inicialização heurística, nós apenas semeamos a população com algumas boas soluções, preenchendo o resto com soluções aleatórias ao invés de preencher toda a população com soluções baseadas em heurísticas.

Também foi observado que a inicialização heurística, em alguns casos, afeta apenas o fitness inicial da população, mas, no final, é a diversidade de soluções que leva à otimização.

Modelos de População

Existem dois modelos de população amplamente em uso -

Curso estável

No estado estacionário GA, geramos uma ou duas nascentes em cada iteração e elas substituem um ou dois indivíduos da população. Um estado estacionário GA também é conhecido comoIncremental GA.

Geracional

Em um modelo geracional, geramos 'n' descendentes, onde n é o tamanho da população, e toda a população é substituída por uma nova no final da iteração.

A função de fitness simplesmente definida é uma função que leva um candidate solution to the problem as input and produces as output quão “ajustada” ou quão “boa” é a solução com respeito ao problema em consideração.

O cálculo do valor de aptidão é feito repetidamente em um GA e, portanto, deve ser suficientemente rápido. Um cálculo lento do valor de aptidão pode afetar adversamente um GA e torná-lo excepcionalmente lento.

Na maioria dos casos, a função de aptidão e a função objetivo são iguais, pois o objetivo é maximizar ou minimizar a função objetivo dada. No entanto, para problemas mais complexos com vários objetivos e restrições, umAlgorithm Designer pode optar por ter uma função de fitness diferente.

Uma função de fitness deve possuir as seguintes características -

  • A função de aptidão deve ser suficientemente rápida para calcular.

  • Ele deve medir quantitativamente o quão adequada é uma determinada solução ou como os indivíduos adequados podem ser produzidos a partir de uma determinada solução.

Em alguns casos, o cálculo direto da função de aptidão pode não ser possível devido às complexidades inerentes do problema em questão. Nesses casos, fazemos a aproximação de aptidão para atender às nossas necessidades.

A imagem a seguir mostra o cálculo de aptidão para uma solução da mochila 0/1. É uma função de fitness simples que apenas soma os valores de lucro dos itens que estão sendo escolhidos (que têm um 1), digitalizando os elementos da esquerda para a direita até que a mochila esteja cheia.

Seleção de pais é o processo de seleção de pais que se acasalam e se recombinam para criar descendentes para a próxima geração. A seleção dos pais é crucial para a taxa de convergência do AG, visto que bons pais conduzem os indivíduos a soluções melhores e mais adequadas.

No entanto, deve-se ter cuidado para evitar que uma solução extremamente adequada ocupe toda a população em algumas gerações, pois isso faz com que as soluções fiquem próximas umas das outras no espaço de soluções, levando a uma perda de diversidade. Maintaining good diversityna população é extremamente crucial para o sucesso de um AG. Essa ocupação de toda a população por uma solução extremamente adequada é conhecida comopremature convergence e é uma condição indesejável em um GA.

Seleção Proporcional de Fitness

A seleção proporcional de condicionamento físico é uma das formas mais populares de seleção dos pais. Nesse sentido, todo indivíduo pode se tornar um pai com uma probabilidade proporcional à sua adequação. Portanto, indivíduos mais aptos têm uma chance maior de acasalar e propagar suas características para a próxima geração. Portanto, tal estratégia de seleção aplica uma pressão de seleção aos indivíduos mais aptos da população, evoluindo os melhores indivíduos ao longo do tempo.

Considere uma roda circular. A roda é dividida emn pies, onde n é o número de indivíduos na população. Cada indivíduo recebe uma parte do círculo que é proporcional ao seu valor de aptidão.

Duas implementações de seleção proporcional de aptidão são possíveis -

Seleção de Roleta

Em uma seleção de roda de roleta, a roda circular é dividida conforme descrito anteriormente. Um ponto fixo é escolhido na circunferência da roda, conforme mostrado, e a roda é girada. A região da roda que fica na frente do ponto fixo é escolhida como pai. Para o segundo pai, o mesmo processo é repetido.

É claro que um indivíduo mais apto tem uma torta maior na roda e, portanto, uma chance maior de pousar na frente do ponto fixo quando a roda é girada. Portanto, a probabilidade de escolher um indivíduo depende diretamente de sua aptidão.

Em termos de implementação, usamos as seguintes etapas -

  • Calcule S = a soma das sutilezas.

  • Gere um número aleatório entre 0 e S.

  • Começando do topo da população, continue adicionando as sutilezas à soma parcial P, até P <S.

  • O indivíduo para o qual P excede S é o indivíduo escolhido.

Amostragem Estocástica Universal (SUS)

A Amostragem Universal Estocástica é bastante semelhante à seleção da roda da Roleta, entretanto, em vez de ter apenas um ponto fixo, temos vários pontos fixos, conforme mostrado na imagem a seguir. Portanto, todos os pais são escolhidos em apenas um giro da roda. Além disso, tal configuração incentiva os indivíduos altamente aptos a serem escolhidos pelo menos uma vez.

É de notar que os métodos de seleção proporcionais de aptidão não funcionam para casos em que a aptidão pode assumir um valor negativo.

Seleção de torneio

Na seleção do torneio K-Way, selecionamos K indivíduos da população aleatoriamente e selecionamos o melhor deles para se tornar um pai. O mesmo processo é repetido para selecionar o próximo pai. A seleção de torneio também é extremamente popular na literatura, pois pode até funcionar com valores de condicionamento físico negativos.

Seleção de Classificação

A Seleção de Classificação também funciona com valores de aptidão negativos e é usada principalmente quando os indivíduos da população têm valores de aptidão muito próximos (isso geralmente acontece no final da corrida). Isso faz com que cada indivíduo tenha uma parte quase igual do bolo (como no caso de seleção proporcional de adequação), conforme mostrado na imagem a seguir e, portanto, cada indivíduo, independentemente de quão adequado em relação ao outro, tem aproximadamente a mesma probabilidade de ser selecionado como um pai. Isso, por sua vez, leva a uma perda na pressão de seleção em relação aos indivíduos mais aptos, fazendo com que o AG faça seleções de pais ruins em tais situações.

Com isso, removemos o conceito de um valor de aptidão ao selecionar um dos pais. No entanto, cada indivíduo na população é classificado de acordo com sua aptidão. A seleção dos pais depende da classificação de cada indivíduo e não da aptidão. Os indivíduos de classificação mais alta são mais preferidos do que os de classificação inferior.

Cromossoma Valor de aptidão Classificação
UMA 8,1 1
B 8,0 4
C 8,05 2
D 7,95 6
E 8.02 3
F 7,99 5

Seleção aleatória

Nesta estratégia, selecionamos aleatoriamente os pais da população existente. Não há pressão de seleção para indivíduos mais aptos e, portanto, essa estratégia geralmente é evitada.

Neste capítulo, discutiremos sobre o que é um Crossover Operator junto com seus outros módulos, seus usos e benefícios.

Introdução ao Crossover

O operador de crossover é análogo à reprodução e ao crossover biológico. Neste, mais de um progenitor é selecionado e uma ou mais descendentes são produzidos usando o material genético dos progenitores. O cruzamento geralmente é aplicado em um GA com alta probabilidade -pc .

Operadores de crossover

Nesta seção, discutiremos alguns dos operadores de crossover mais usados. Deve-se notar que esses operadores de crossover são muito genéricos e o GA Designer pode escolher implementar um operador de crossover específico para o problema também.

Crossover de um ponto

Neste cruzamento de um ponto, um ponto de cruzamento aleatório é selecionado e as caudas de seus dois pais são trocadas para obter novas origens.

Crossover multiponto

O crossover multiponto é uma generalização do crossover de um ponto em que segmentos alternados são trocados para obter novas origens.

Crossover uniforme

Em um cruzamento uniforme, não dividimos o cromossomo em segmentos, mas tratamos cada gene separadamente. Nesse caso, basicamente lançamos uma moeda para cada cromossomo para decidir se ele será incluído ou não na prole. Também podemos enviesar a moeda para um dos pais, para ter mais material genético no filho desse pai.

Recombinação Aritmética Total

Isso é comumente usado para representações de inteiros e funciona tomando a média ponderada dos dois pais usando as seguintes fórmulas -

  • Criança1 = α.x + (1-α) .y
  • Criança2 = α.x + (1-α) .y

Obviamente, se α = 0,5, então os dois filhos serão idênticos, conforme mostrado na imagem a seguir.

Cruzamento da ordem de Davis (OX1)

OX1 é usado para cruzamentos baseados em permutação com a intenção de transmitir informações sobre a ordenação relativa às nascentes. Funciona da seguinte maneira -

  • Crie dois pontos de cruzamento aleatórios no pai e copie o segmento entre eles do primeiro pai para o primeiro filho.

  • Agora, começando do segundo ponto de cruzamento no segundo pai, copie os números não usados ​​restantes do segundo pai para o primeiro filho, envolvendo a lista.

  • Repita para o segundo filho com o papel do pai invertido.

Existem muitos outros cruzamentos, como Crossover parcialmente mapeado (PMX), crossover baseado em ordem (OX2), Crossover aleatório, Crossover de anel, etc.

Introdução à mutação

Em termos simples, a mutação pode ser definida como um pequeno ajuste aleatório no cromossomo, para obter uma nova solução. É usado para manter e introduzir diversidade na população genética e geralmente é aplicado com baixa probabilidade -pm. Se a probabilidade for muito alta, o AG fica reduzido a uma busca aleatória.

Mutação é a parte do GA que está relacionada à “exploração” do espaço de busca. Foi observado que a mutação é essencial para a convergência do GA, enquanto o crossover não é.

Operadores de mutação

Nesta seção, descrevemos alguns dos operadores de mutação mais comumente usados. Como os operadores de crossover, esta não é uma lista exaustiva e o designer do GA pode achar uma combinação dessas abordagens ou um operador de mutação específico do problema mais útil.

Bit Flip Mutation

Nessa mutação de bit flip, selecionamos um ou mais bits aleatórios e os invertemos. Isso é usado para GAs codificados em binários.

Reinicialização aleatória

Random Resetting é uma extensão do bit flip para a representação inteira. Nesse caso, um valor aleatório do conjunto de valores permitidos é atribuído a um gene escolhido aleatoriamente.

Troca de mutação

Na mutação de troca, selecionamos duas posições no cromossomo aleatoriamente e trocamos os valores. Isso é comum em codificações baseadas em permutação.

Mutação Scramble

A mutação Scramble também é popular com representações de permutação. Neste, de todo o cromossomo, um subconjunto de genes é escolhido e seus valores são embaralhados ou embaralhados aleatoriamente.

Mutação de Inversão

Na mutação de inversão, selecionamos um subconjunto de genes como na mutação de embaralhamento, mas em vez de embaralhar o subconjunto, meramente invertemos a string inteira no subconjunto.

A Política de Seleção de Sobreviventes determina quais indivíduos devem ser expulsos e quais devem ser mantidos na próxima geração. É crucial, pois deve garantir que os indivíduos mais aptos não sejam expulsos da população, ao mesmo tempo que a diversidade deve ser mantida na população.

Alguns GAs empregam Elitism. Em termos simples, significa que o membro mais apto da população atual é sempre propagado para a próxima geração. Portanto, em nenhuma circunstância o membro mais apto da população atual pode ser substituído.

A política mais fácil é expulsar membros aleatórios da população, mas tal abordagem freqüentemente apresenta problemas de convergência, portanto, as seguintes estratégias são amplamente utilizadas.

Seleção baseada na idade

Na seleção com base na idade, não temos noção de aptidão. Parte-se da premissa de que cada indivíduo tem permissão para entrar na população por uma geração finita onde é permitido se reproduzir, após isso, é expulso da população por melhor que seja sua aptidão.

Por exemplo, no exemplo a seguir, a idade é o número de gerações pelas quais o indivíduo esteve na população. Os membros mais velhos da população, ou seja, P4 e P7, são expulsos da população e as idades do restante dos membros são aumentadas em um.

Seleção Baseada em Fitness

Nessa seleção baseada em aptidão, as crianças tendem a substituir os indivíduos menos aptos da população. A seleção dos indivíduos menos aptos pode ser feita usando uma variação de qualquer uma das políticas de seleção descritas antes - seleção de torneio, seleção proporcional de aptidão, etc.

Por exemplo, na imagem a seguir, os filhos substituem os indivíduos menos aptos P1 e P10 da população. Deve-se notar que, uma vez que P1 e P9 têm o mesmo valor de aptidão, a decisão de remover qual indivíduo da população é arbitrária.

A condição de término de um Algoritmo Genético é importante para determinar quando uma execução de GA terminará. Foi observado que, inicialmente, o GA progride muito rápido com melhores soluções surgindo a cada poucas iterações, mas isso tende a saturar nos estágios posteriores, onde as melhorias são muito pequenas. Normalmente queremos uma condição de término de forma que nossa solução esteja próxima do ótimo, no final da execução.

Normalmente, mantemos uma das seguintes condições de rescisão -

  • Quando não houve melhoria na população para X iterações.
  • Quando atingimos um número absoluto de gerações.
  • Quando o valor da função objetivo atinge um determinado valor pré-definido.

Por exemplo, em um algoritmo genético, mantemos um contador que registra as gerações para as quais não houve melhoria na população. Inicialmente, definimos esse contador como zero. Cada vez que não geramos descendentes melhores do que os indivíduos da população, incrementamos o contador.

No entanto, se a aptidão de qualquer uma das molas descendentes for melhor, então zeramos o contador. O algoritmo termina quando o contador atinge um valor predeterminado.

Como outros parâmetros de um GA, a condição de terminação também é altamente específica para o problema e o projetista do GA deve tentar várias opções para ver o que melhor se adapta ao seu problema específico.

Até agora neste tutorial, tudo o que discutimos corresponde ao modelo darwiniano de evolução - seleção natural e variação genética por meio de recombinação e mutação. Na natureza, apenas as informações contidas no genótipo do indivíduo podem ser transmitidas para a próxima geração. Esta é a abordagem que temos seguido no tutorial até agora.

No entanto, outros modelos de adaptação para a vida - Lamarckian Model e Baldwinian Modeltambém existem. É de notar que qualquer modelo que seja o melhor, está aberto para debate e os resultados obtidos pelos pesquisadores mostram que a escolha da adaptação ao longo da vida é altamente específica para o problema.

Freqüentemente, hibridizamos um GA com pesquisa local - como em Algoritmos Meméticos. Em tais casos, pode-se escolher ir com o modelo lamarckiano ou baldwiniano para decidir o que fazer com os indivíduos gerados após a busca local.

Modelo Lamarckiano

O modelo lamarckiano diz essencialmente que as características que um indivíduo adquire durante a vida podem ser transmitidas à sua descendência. Recebeu o nome do biólogo francês Jean-Baptiste Lamarck.

Mesmo assim, a biologia natural desconsiderou completamente o lamarckismo, pois todos sabemos que apenas a informação do genótipo pode ser transmitida. No entanto, do ponto de vista da computação, foi demonstrado que a adoção do modelo Lamarckiano dá bons resultados para alguns dos problemas.

No modelo lamarckiano, um operador de busca local examina a vizinhança (adquirindo novas características) e, se um cromossomo melhor for encontrado, ele se torna o descendente.

Modelo Baldwiniano

O modelo baldwiniano é uma ideia intermediária que leva o nome de James Mark Baldwin (1896). No modelo Baldwin, os cromossomos podem codificar uma tendência de aprendizado de comportamentos benéficos. Isso significa que, ao contrário do modelo lamarckiano, não transmitimos os traços adquiridos para a próxima geração, e também não ignoramos completamente os traços adquiridos como no modelo darwiniano.

O Modelo Baldwin está no meio desses dois extremos, em que a tendência de um indivíduo de adquirir certas características é codificada, e não as próprias características.

Nesse modelo baldwiniano, um operador de busca local examina a vizinhança (adquirindo novas características) e, se um cromossomo melhor for encontrado, ele apenas atribui a aptidão aprimorada ao cromossomo e não modifica o próprio cromossomo. A mudança no fitness significa a capacidade dos cromossomos de “adquirir o traço”, mesmo que não seja passado diretamente para as gerações futuras.

Os AGs são muito gerais por natureza e apenas aplicá-los a qualquer problema de otimização não daria bons resultados. Nesta seção, descrevemos alguns pontos que ajudariam e auxiliariam um designer ou implementador de GA em seu trabalho.

Apresente conhecimento de domínio específico para problemas

Foi observado que quanto mais conhecimento de domínio específico do problema incorporamos ao AG; os melhores valores objetivos que obtemos. Adicionar informações específicas do problema pode ser feito usando crossover específico do problema ou operadores de mutação, representações personalizadas, etc.

A imagem a seguir mostra a visão de Michalewicz (1990) da EA -

Reduzir a aglomeração

A aglomeração ocorre quando um cromossomo altamente apto consegue se reproduzir muito e, em algumas gerações, toda a população é preenchida com soluções semelhantes com aptidão semelhante. Isso reduz a diversidade, que é um elemento crucial para garantir o sucesso de um AG. Existem várias maneiras de limitar a aglomeração. Alguns deles são -

  • Mutation para introduzir diversidade.

  • Mudando para rank selection e tournament selection que têm mais pressão de seleção do que seleção proporcional de aptidão para indivíduos com aptidão semelhante.

  • Fitness Sharing - Nesse caso, a aptidão de um indivíduo é reduzida se a população já contém indivíduos semelhantes.

A randomização ajuda!

Foi observado experimentalmente que as melhores soluções são impulsionadas por cromossomos randomizados, uma vez que conferem diversidade à população. O implementador do GA deve ter o cuidado de manter uma quantidade suficiente de randomização e diversidade na população para obter os melhores resultados.

Hibridize GA com pesquisa local

A busca local refere-se a verificar as soluções na vizinhança de uma determinada solução para buscar melhores valores objetivos.

Às vezes, pode ser útil hibridizar o GA com a pesquisa local. A imagem a seguir mostra os vários lugares nos quais a pesquisa local pode ser introduzida em um GA.

Variação de parâmetros e técnicas

Em algoritmos genéticos, não existe um “tamanho único” ou uma fórmula mágica que funcione para todos os problemas. Mesmo depois que o AG inicial está pronto, leva muito tempo e esforço para brincar com os parâmetros como tamanho da população, mutação e probabilidade de cruzamento, etc. para encontrar aqueles que se adequam ao problema específico.

Nesta seção, apresentamos alguns tópicos avançados em Algoritmos Genéticos. Um leitor que procura apenas uma introdução aos AGs pode optar por pular esta seção.

Problemas de otimização restrita

Problemas de otimização restrita são aqueles problemas de otimização em que temos que maximizar ou minimizar um determinado valor de função objetivo que está sujeito a certas restrições. Portanto, nem todos os resultados no espaço da solução são viáveis, e o espaço da solução contém regiões viáveis, conforme mostrado na imagem a seguir.

Em tal cenário, os operadores de crossover e mutação podem nos dar soluções que são inviáveis. Portanto, mecanismos adicionais devem ser empregados no AG ao lidar com problemas de otimização restritos.

Alguns dos métodos mais comuns são -

  • Usando penalty functions o que reduz a adequação de soluções inviáveis, de preferência de forma que a adequação seja reduzida na proporção do número de restrições violadas ou da distância da região viável.

  • Usando repair functions que pegam uma solução inviável e a modificam para que as restrições violadas sejam satisfeitas.

  • Not allowing infeasible solutions para entrar na população em tudo.

  • Use um special representation or decoder functions que garante a viabilidade das soluções.

Antecedentes Teóricos Básicos

Nesta seção, discutiremos sobre o esquema e o teorema da NFL, juntamente com a hipótese do bloco de construção.

Teorema do Esquema

Os pesquisadores têm tentado descobrir a matemática por trás do funcionamento dos algoritmos genéticos, e o Teorema do Esquema de Holland é um passo nessa direção. Ao longo do ano, várias melhorias e sugestões foram feitas ao Teorema do Esquema para torná-lo mais geral.

Nesta seção, não nos aprofundamos na matemática do Teorema do Esquema, em vez disso, tentamos desenvolver uma compreensão básica do que é o Teorema do Esquema. A terminologia básica a saber é a seguinte -

  • UMA Schemaé um “modelo”. Formalmente, é uma string sobre o alfabeto = {0,1, *},

    onde * é não importa e pode assumir qualquer valor.

    Portanto, * 10 * 1 pode significar 01001, 01011, 11001 ou 11011

    Geometricamente, um esquema é um hiperplano no espaço de busca de soluções.

  • Order de um esquema é o número de posições fixas especificadas em um gene.

  • Defining length é a distância entre os dois símbolos fixos mais distantes no gene.

O teorema do esquema afirma que este esquema com aptidão acima da média, comprimento de definição curto e ordem inferior tem mais probabilidade de sobreviver a crossover e mutação.

Hipótese do Bloco de Construção

Os blocos de construção são esquemas de baixa definição e ordem inferior com a adequação média fornecida acima. A hipótese dos blocos de construção diz que tais blocos de construção servem como base para o sucesso e adaptação dos AGs em AGs à medida que progride identificando e recombinando sucessivamente esses “blocos de construção”.

Teorema Sem Almoço Grátis (NFL)

Wolpert e Macready publicaram em 1997 um artigo intitulado "Nenhum Teorema do Almoço Gratuito para Otimização". Essencialmente, afirma que, se calcularmos a média do espaço de todos os problemas possíveis, todos os algoritmos de caixa preta que não revisam exibirão o mesmo desempenho.

Isso significa que quanto mais entendemos um problema, nosso GA se torna mais específico para o problema e oferece melhor desempenho, mas compensa isso apresentando um desempenho insatisfatório para outros problemas.

Aprendizado de máquina baseado em GA

Algoritmos genéticos também encontram aplicação no aprendizado de máquina. Classifier systems são uma forma de genetics-based machine learning(GBML) que são frequentemente usados ​​na área de aprendizado de máquina. Os métodos GBML são uma abordagem de nicho para o aprendizado de máquina.

Existem duas categorias de sistemas GBML -

  • The Pittsburg Approach - Nesta abordagem, um cromossomo codifica uma solução e, portanto, a adequação é atribuída às soluções.

  • The Michigan Approach - uma solução é normalmente representada por muitos cromossomos e, portanto, a aptidão é atribuída a soluções parciais.

Deve-se ter em mente que o problema padrão como crossover, mutação, Lamarckiano ou Darwiniano, etc. também estão presentes nos sistemas GBML.

Os algoritmos genéticos são usados ​​principalmente em problemas de otimização de vários tipos, mas também são frequentemente usados ​​em outras áreas de aplicação.

Nesta seção, listamos algumas das áreas nas quais os algoritmos genéticos são usados ​​com frequência. Estes são -

  • Optimization- Algoritmos genéticos são mais comumente usados ​​em problemas de otimização em que temos que maximizar ou minimizar um determinado valor de função objetivo sob um determinado conjunto de restrições. A abordagem para resolver problemas de otimização foi destacada ao longo do tutorial.

  • Economics - Os AGs também são usados ​​para caracterizar vários modelos econômicos, como o modelo da teia de aranha, a resolução de equilíbrio da teoria dos jogos, precificação de ativos, etc.

  • Neural Networks - GAs também são usados ​​para treinar redes neurais, particularmente redes neurais recorrentes.

  • Parallelization - Os AGs também têm capacidades paralelas muito boas e provam ser um meio muito eficaz na resolução de certos problemas, além de fornecer uma boa área para pesquisa.

  • Image Processing - GAs são usados ​​para várias tarefas de processamento de imagem digital (DIP), bem como correspondência de pixel denso.

  • Vehicle routing problems - Com múltiplas janelas soft time, múltiplos depósitos e uma frota heterogênea.

  • Scheduling applications - Os AGs também são usados ​​para resolver vários problemas de agendamento, particularmente o problema de cronograma.

  • Machine Learning - como já discutido, o aprendizado de máquina baseado em genética (GBML) é uma área de nicho no aprendizado de máquina.

  • Robot Trajectory Generation - GAs têm sido usados ​​para planejar o caminho que um braço de robô faz ao se mover de um ponto a outro.

  • Parametric Design of Aircraft - GAs têm sido usados ​​para projetar aeronaves variando os parâmetros e desenvolvendo soluções melhores.

  • DNA Analysis - GAs foram usados ​​para determinar a estrutura do DNA usando dados espectrométricos sobre a amostra.

  • Multimodal Optimization - AGs são obviamente abordagens muito boas para otimização multimodal em que temos que encontrar várias soluções ótimas.

  • Traveling salesman problem and its applications - GAs têm sido usados ​​para resolver o TSP, que é um problema combinatório bem conhecido usando novas estratégias de crossover e empacotamento.

Os livros a seguir podem ser consultados para aprimorar ainda mais o conhecimento do leitor de Algoritmos Genéticos e Computação Evolutiva em geral -

  • Algoritmos genéticos em pesquisa, otimização e aprendizado de máquina por David E. Goldberg.

  • Algoritmos Genéticos + Estruturas de Dados = Programas Evolucionários por Zbigniew Michalewicz.

  • Algoritmos Genéticos Práticos por Randy L. Haupt e Sue Ellen Haupt.

  • Otimização Multi-Objetivo usando Algoritmos Evolucionários por Kalyanmoy Deb.