Algoritmos genéticos - Guia rápido

Algoritmos Genéticos - Introdução

O algoritmo genético (GA) é uma técnica de otimização baseada em pesquisa, baseada nos princípios de genética e seleção natural . É 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. É freqüentemente usado para resolver problemas de otimização, em pesquisas e em aprendizado de máquina.

Introdução à otimização

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

Otimização

Otimização refere-se a encontrar os valores das entradas de forma a obter 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 objetivas, variando os parâmetros de entrada.

O conjunto de todas as soluções ou valores possíveis que as entradas podem assumir compõem o espaço de pesquisa. Nesse espaço de pesquisa, encontra-se um ponto ou um conjunto de pontos que fornece a solução ideal. O objetivo da otimização é encontrar esse ponto ou conjunto de pontos no espaço de pesquisa.

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 baseados em pesquisa, baseados nos conceitos de seleção natural e genética. Os GAs são um subconjunto de um ramo de computação muito maior conhecido como Computação Evolucionária .

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.

Nas AGs, temos um pool ou uma população de soluções possíveis para o problema em questão. Essas soluções passam por recombinação e mutação (como na genética natural), produzindo novos filhos, e o processo é repetido por várias gerações. Cada indivíduo (ou solução candidata) recebe um valor de adequação (com base em seu valor objetivo da função) e os indivíduos mais aptos têm uma chance maior de acasalar e produzir mais indivíduos “mais aptos”. Isso está de acordo com a teoria darwiniana de "Sobrevivência do mais apto".

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

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

Vantagens dos GAs

Os GAs têm várias vantagens que os tornaram imensamente populares. Estes incluem -

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

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

  • Tem muito boas capacidades paralelas.

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

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

  • Sempre obtém uma resposta para o problema, que melhora 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. Estes incluem -

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

  • O valor de condicionamento físico é calculado repetidamente, o que pode ser computacionalmente caro para alguns problemas.

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

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

GA - Motivação

Os algoritmos genéticos têm a capacidade de fornecer uma solução "suficientemente boa", "suficientemente rápida". 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:

Solução de 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. Nesse cenário, os AGs demonstram ser uma ferramenta eficiente para fornecer soluções utilizáveis quase ideais em um curto período de tempo.

Falha nos 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 objetivas de pico único, como a função de custo em 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 vales, o que faz com que esses métodos falhem, pois sofrem uma tendência inerente de ficarem presos nas ótimas localidades. conforme mostrado na figura a seguir.

GA Motivation

Obtendo uma boa solução rapidamente

Alguns problemas difíceis, como o Travelling Salesperson Problem (TSP), têm aplicativos do mundo real, como localização de caminhos e design VLSI. Agora imagine que você está usando o sistema de navegação GPS e leva alguns minutos (ou até algumas horas) para calcular o caminho “ideal” da origem ao destino. O atraso nessas aplicações do mundo real não é aceitável e, portanto, é necessária uma solução "suficientemente boa", que seja entregue "rapidamente".

Algoritmos Genéticos - Fundamentos

Esta seção apresenta a terminologia básica necessária para entender os GAs. Além disso, uma estrutura genérica de AGs é apresentada nas formas pseudo-código e gráfica . Recomenda-se ao leitor que compreenda adequadamente todos os conceitos introduzidos nesta seção e lembre-se deles 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.

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

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

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

  • Alelo - é o valor que um gene assume para um cromossomo específico.

Terminologia
  • Genótipo - Genótipo é a população no espaço computacional. No espaço de computação, as soluções são representadas de uma maneira que pode ser facilmente entendida e manipulada usando um sistema de computação.

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

  • Decodificação e codificação - Para problemas simples, os espaços fenótipo e genótipo são os mesmos. No entanto, na maioria dos casos, os espaços fenótipo e genótipo 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 adequaçã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 selecionados.

    No entanto, no espaço do genótipo, ele pode ser representado como uma sequência binária de comprimento n (onde n é o número de itens). Um 0 na posição x representa que x é o item escolhido, enquanto 1 representa o reverso. Este é um caso em que os espaços de genótipo e fenótipo são diferentes.

Fenótipo e espaço de genótipo
  • Função de condicionamento físico - Uma função de condicionamento físico simplesmente definida é uma função que aceita 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 de objetivo podem ser as mesmas, enquanto em outros podem ser diferentes com base no problema.

  • Operadores genéticos - 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 AG é a seguinte -

Começamos com uma população inicial (que pode ser gerada aleatoriamente ou gerada por outras heurísticas), e selecionamos os pais dessa população para acasalar. Aplique operadores de crossover e mutação nos pais para gerar novas fontes. E, finalmente, essas fontes substituem os indivíduos existentes na população e o processo se repete. Dessa maneira, algoritmos genéticos realmente tentam imitar a evolução humana até certo ponto.

Cada uma das etapas a seguir é abordada como um capítulo separado posteriormente neste tutorial.

Estrutura básica

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

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

Representação de Genótipo

Uma das decisões mais importantes a serem tomadas ao implementar um algoritmo genético é decidir a representação que usaremos para representar nossas soluções. Foi observado que uma representação inadequada pode levar a um desempenho ruim da AG.

Portanto, escolher uma representação adequada, ter uma definição adequada dos mapeamentos entre os espaços fenótipo e genótipo é essencial para o sucesso de um AG.

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

Representação binária

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

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

Representação binária

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 significado diferente e, portanto, operadores de mutação e crossover podem ter consequências indesejadas. Isso pode ser resolvido em certa medida usando o Gray Coding, pois uma alteração em um bit não afeta enormemente a solução.

Representação com Valor Real

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

Representação com Valor Real

Representação Inteira

Para genes de valor discreto, nem sempre podemos limitar o espaço da solução ao binário 'yes' ou 'no'. Por exemplo, se queremos 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 Inteira

Representação de Permutação

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

Um exemplo clássico dessa representação é o problema do vendedor ambulante (TSP). Nisso, o vendedor precisa fazer um tour por todas as cidades, visitando cada cidade exatamente uma vez e retornando à cidade inicial. 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, o uso de uma representação de permutação faz sentido para esse problema.

Representação de Permutação

Algoritmos Genéticos - População

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 lembradas ao lidar com a população do GA -

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

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

A população é geralmente definida como uma matriz bidimensional de tamanho populacional, tamanho x, tamanho do cromossomo .

Inicialização da população

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

  • Inicialização aleatória - preencha a população inicial com soluções completamente aleatórias.

  • Inicialização heurística - preencha a população inicial usando uma heurística conhecida para o problema.

Observou-se que toda a população não deve ser inicializada usando uma heurística, pois isso pode resultar na população com soluções semelhantes e com pouca diversidade. Observou-se experimentalmente que as soluções aleatórias são as que levam a população à otimização. Portanto, com a inicialização heurística, apenas propomos à população algumas boas soluções, preenchendo o restante com soluções aleatórias, em vez de preencher toda a população com soluções baseadas em heurística.

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

Modelos de População

Existem dois modelos populacionais amplamente utilizados -

Curso estável

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

Geracional

Em um modelo geracional, geramos 'n' sub-fontes, em que n é o tamanho da população e toda a população é substituída pela nova no final da iteração.

Algoritmos Genéticos - Função Fitness

A função de adequação simplesmente definida é uma função que leva uma solução candidata ao problema como entrada e produz como saída quão "adequado" é o quão "boa" é a solução em relação ao problema em consideração.

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

Na maioria dos casos, a função de adequação e a função objetivo são as mesmas que o objetivo é maximizar ou minimizar a função objetivo fornecida. No entanto, para problemas mais complexos com vários objetivos e restrições, um designer de algoritmos pode optar por ter uma função de condicionamento diferente.

Uma função de condicionamento físico deve possuir as seguintes características -

  • A função de condicionamento físico deve ser suficientemente rápida para calcular.

  • Ele deve medir quantitativamente a adequação de uma determinada solução ou a adequação dos indivíduos a partir da solução.

Em alguns casos, o cálculo direto da função de adequação pode não ser possível devido às complexidades inerentes ao problema em questão. Nesses casos, fazemos uma aproximação de adequação à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 simples de condicionamento físico que apenas soma os valores de lucro dos itens que estão sendo selecionados (que têm 1), digitalizando os elementos da esquerda para a direita até a mochila estar cheia.

Representação binária

Algoritmos Genéticos - Seleção dos Pais

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

No entanto, deve-se tomar cuidado para evitar que uma solução extremamente adequada domine toda a população em poucas gerações, pois isso leva as soluções a se aproximarem no espaço da solução, levando a uma perda de diversidade. Manter uma boa diversidade na população é extremamente crucial para o sucesso de uma AG. Essa ocupação de toda a população por uma solução extremamente adequada é conhecida como convergência prematura e é uma condição indesejável em um AG.

Seleção Proporcional de Fitness

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

Considere uma roda circular. A roda é dividida em n tortas , 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 condicionamento físico.

São possíveis duas implementações da seleção proporcional da adequação -

Seleção de roleta

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

Seleção de roleta

É claro que um indivíduo mais apto tem uma torta maior na roda e, portanto, uma maior chance de aterrissar 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 de uma fineza.

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

  • Começando pelo topo da população, continue adicionando os detalhes à 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 de roleta, no entanto, 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, essa configuração incentiva os indivíduos altamente aptos a serem escolhidos pelo menos uma vez.

SUS

Deve-se notar que os métodos de seleção proporcional à adequação não funcionam nos casos em que a adequação pode ter um valor negativo.

Seleção de Torneios

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

Seleção de Torneios

Seleção de classificação

A seleção de classificação também funciona com valores negativos de condicionamento físico e é usada principalmente quando os indivíduos da população têm valores de condicionamento muito próximos (isso geralmente ocorre no final da corrida). Isso faz com que cada indivíduo tenha uma parcela quase igual da torta (como no caso de seleção proporcional à adequação), como mostrado na imagem a seguir e, portanto, cada indivíduo, independentemente do ajuste em relação ao outro, tem aproximadamente a mesma probabilidade de ser selecionado como um pai. Por sua vez, isso leva a uma perda na pressão de seleção em relação a indivíduos mais aptos, fazendo com que a AG faça más seleções de pais nessas situações.

Seleção de classificação

Nesse caso, removemos o conceito de um valor de adequação ao selecionar um pai. No entanto, todos os indivíduos da população são classificados 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 com classificação mais alta são os preferidos mais do que os indivíduos com classificação mais baixa.

Cromossoma Valor da 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.

Algoritmos Genéticos - Crossover

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

Introdução ao Crossover

O operador de cruzamento é análogo à reprodução e cruzamento biológico. Nisto, mais de um pai é selecionado e uma ou mais nascentes são produzidas usando o material genético dos pais. O crossover é geralmente aplicado em um GA com uma alta probabilidade - p c .

Operadores de crossover

Nesta seção, discutiremos alguns dos operadores de crossover mais populares. É importante observar que esses operadores de crossover são muito genéricos e o GA Designer também pode optar por implementar um operador de crossover específico ao problema.

One Point Crossover

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

One Point Crossover

Multi Point Crossover

Crossover de múltiplos pontos é uma generalização do crossover de um ponto em que segmentos alternados são trocados para obter novas fontes.

Multi Point Crossover

Passagem uniforme

Em um cruzamento uniforme, não dividimos o cromossomo em segmentos, mas tratamos cada gene separadamente. Nesse sentido, basicamente jogamos uma moeda para cada cromossomo para decidir se ela será ou não incluída na primavera. Também podemos influenciar a moeda para um dos pais, para ter mais material genético na criança desse pai.

Passagem uniforme

Recombinação Aritmética Inteira

Isso geralmente é usado para representações inteiras e funciona calculando 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, as duas crianças serão idênticas, como mostrado na imagem a seguir.

Recombinação Aritmética Inteira

Passagem de pedidos de Davis (OX1)

OX1 é usado para cruzamentos baseados em permutações com a intenção de transmitir informações sobre pedidos relativos às fontes externas. 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 no segundo ponto de cruzamento no segundo pai, copie os números restantes não utilizados do segundo pai para o primeiro filho, agrupando a lista.

  • Repita o procedimento para o segundo filho com a função dos pais invertida.

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

Algoritmos Genéticos - Mutação

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 uma baixa probabilidade - p m . Se a probabilidade for muito alta, o GA será reduzido a uma pesquisa aleatória.

Mutação é a parte do AG relacionada à "exploração" do espaço de pesquisa. Observou-se que a mutação é essencial para a convergência do AG enquanto o crossover não é.

Operadores de mutação

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

Bit Flip Mutation

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

Bit Flip Mutation

Reinicialização aleatória

A redefinição aleatória é uma extensão do bit flip para a representação inteira. Neste, um valor aleatório do conjunto de valores permitidos é atribuído a um gene escolhido aleatoriamente.

Mutação de swap

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

Mutação de swap

Mutação Scramble

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

Mutação Scramble

Mutação por 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, apenas invertemos toda a cadeia de caracteres no subconjunto.

Mutação por Inversão

Algoritmos Genéticos - Seleção de Sobreviventes

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

Alguns AGs empregam elitismo . Em termos simples, significa que o atual membro mais apto da população é sempre propagado para a próxima geração. Portanto, sob 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 essa abordagem freqüentemente apresenta problemas de convergência; portanto, as estratégias a seguir são amplamente utilizadas.

Seleção por Idade

Na Seleção por Idade, não temos noção de aptidão. É baseado na premissa de que cada indivíduo é permitido na população por uma geração finita, onde é permitido reproduzir; depois disso, é expulso da população, independentemente da qualidade de 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 antigos da população, ou seja, P4 e P7, são expulsos da população e as idades do restante dos membros são incrementadas em um.

Seleção por Idade

Seleção Baseada em Fitness

Nesta seleção baseada em condicionamento físico, 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 torneios, seleção proporcional de condicionamento físico etc.

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

Seleção Baseada em Fitness

Algoritmos Genéticos - Condição de Terminação

A condição de terminação de um algoritmo genético é importante para determinar quando uma execução do GA terminará. Observou-se 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. Geralmente, queremos uma condição de término de forma que nossa solução esteja próxima da ideal no final da execução.

Normalmente, mantemos uma das seguintes condições de término -

  • Quando não houve melhora na população para X iterações.
  • Quando atingimos um número absoluto de gerações.
  • Quando o valor da função objetivo atingir um determinado valor predefinido.

Por exemplo, em um algoritmo genético, mantemos um contador que acompanha 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 fontes melhores que os indivíduos da população, aumentamos o contador.

No entanto, se a adequação de qualquer uma das molas for melhor, redefinimos o contador para zero. O algoritmo termina quando o contador atinge um valor predeterminado.

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

Modelos de adaptação ao longo da vida

Até agora neste tutorial, tudo o que discutimos corresponde ao modelo darwiniano de evolução - seleção natural e variação genética através 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. Essa é a abordagem que temos seguido no tutorial até agora.

No entanto, outros modelos de adaptação ao longo da vida - Modelo Lamarckiano e Modelo Baldwiniano também existem. Deve-se notar que, qualquer que seja o melhor, está aberto ao 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. Nesses casos, pode-se optar pelo modelo lamarckiano ou baldwiniano para decidir o que fazer com os indivíduos gerados após a pesquisa local.

Modelo Lamarckiano

O Modelo Lamarckiano diz essencialmente que as características que um indivíduo adquire durante a vida podem ser passadas para a prole. É nomeado após o biólogo francês Jean-Baptiste Lamarck.

Mesmo assim, a biologia natural desconsiderou completamente o lamarckismo, pois todos sabemos que apenas as informações no genótipo podem ser transmitidas. No entanto, do ponto de vista da computação, foi demonstrado que a adoção do modelo lamarckiano fornece 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 tornará um descendente.

Modelo Baldwiniano

O modelo baldwiniano é uma idéia intermediária em homenagem a James Mark Baldwin (1896). No modelo de Baldwin, os cromossomos podem codificar uma tendência de aprender comportamentos benéficos. Isso significa que, diferentemente do modelo lamarckiano, não transmitimos as características adquiridas para a próxima geração, nem ignoramos completamente as características adquiridas, como no modelo darwiniano.

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

Neste Modelo Baldwiniano, um operador de pesquisa local examina a vizinhança (adquirindo novas características) e, se um cromossomo melhor for encontrado, ele atribui apenas a melhor aptidão ao cromossomo e não modifica o próprio cromossomo. A mudança no condicionamento físico significa a capacidade dos cromossomos de "adquirir a característica", mesmo que não seja passada diretamente para as gerações futuras.

Implementação eficaz

Os GAs são de natureza muito geral 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 do GA em seu trabalho.

Introduzir conhecimento de domínio específico do problema

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

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

Implementação eficaz

Reduzir a aglomeração

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

  • Mutação para introduzir diversidade.

  • Mudar para seleção de rank e seleção de torneio que têm mais pressão de seleção do que a seleção proporcional de aptidão para indivíduos com aptidão semelhante

  • Compartilhamento de condicionamento físico - Nesse caso, o condicionamento físico de um indivíduo é reduzido se a população já contiver indivíduos semelhantes.

Randomização ajuda!

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

Hibridar o GA com a pesquisa local

A pesquisa local se refere à verificação das soluções na vizinhança de uma determinada solução para buscar melhores valores objetivos.

Às vezes, pode ser útil hibridar o GA com a pesquisa local. A imagem a seguir mostra os vários locais em que a pesquisa local pode ser introduzida em um GA.

Hibridar GA

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

Nos algoritmos genéticos, não existe um tamanho único ou uma fórmula mágica que funcione para todos os problemas. Mesmo após o GA inicial estar pronto, é preciso muito tempo e esforço para analisar parâmetros como tamanho populacional, probabilidade de mutação e cruzamento, etc., para encontrar os que se adequam ao problema específico.

Algoritmos Genéticos - Tópicos Avançados

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

Problemas de otimização restrita

Problemas de otimização restrita são aqueles problemas de otimização nos quais temos que maximizar ou minimizar um determinado valor objetivo da função 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.

Otimização restrita

Nesse cenário, os operadores de crossover e mutação podem nos fornecer soluções inviáveis. Portanto, mecanismos adicionais devem ser empregados no GA ao lidar com problemas de otimização restritos.

Alguns dos métodos mais comuns são -

  • Utilizar funções de penalidade que reduzam a adequação de soluções inviáveis, de preferência para que a adequação seja reduzida proporcionalmente ao número de restrições violadas ou à distância da região viável.

  • Usando funções de reparo que tomam uma solução inviável e modificam-na para que as restrições violadas sejam satisfeitas.

  • Não permitindo que soluções inviáveis entrem na população.

  • Use uma representação especial ou funções de decodificador que garantam a viabilidade das soluções.

Fundamentos Teóricos Básicos

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

Teorema do Esquema

Os pesquisadores tentam 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, mas tentamos desenvolver um entendimento básico do que é o Teorema do Esquema. A terminologia básica a saber é a seguinte -

  • Um esquema é um "modelo". Formalmente, é uma string sobre o alfabeto = {0,1, *},

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

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

    Geometricamente, um esquema é um hiperplano no espaço de pesquisa da solução.

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

Ordem do esquema
  • Definir comprimento é a distância entre os dois símbolos fixos mais distantes no gene.

Esquema Definindo o comprimento

O teorema do esquema afirma que este esquema com aptidão acima da média, comprimento de definição curto e ordem inferior é mais provável que sobreviva ao cruzamento e mutação.

Hipótese do bloco de construção

Os Blocos de Construção são esquemas de ordem baixa e comprimento baixo que definem a aptidão média fornecida acima. A hipótese do bloco de construção diz que esses blocos de construção servem como base para o sucesso e a adaptação das AGs nas AGs à medida que progridem, identificando e recombinando sucessivamente esses "blocos de construção".

Teorema Sem Almoço Gratuito (NFL)

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

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

Aprendizado de máquina baseado no GA

Algoritmos genéticos também encontram aplicação no Machine Learning. Os sistemas classificadores são uma forma de sistema de aprendizado de máquina baseado em genética (GBML) que é frequentemente usado no campo 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 -

  • A abordagem de Pittsburg - nessa abordagem, um cromossomo codifica uma solução e, portanto, a aptidão é atribuída às soluções.

  • A abordagem de Michigan - 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 a questão padrão como crossover, mutação, lamarckiana ou darwiniana etc. também está presente nos sistemas GBML.

Algoritmos Genéticos - Áreas de Aplicação

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 -

  • Otimização - Algoritmos genéticos são mais comumente usados em problemas de otimização, nos quais 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.

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

  • Redes neurais - os GAs também são usados para treinar redes neurais, particularmente redes neurais recorrentes.

  • Paralelização - os AGs também têm recursos paralelos muito bons e provam ser meios muito eficazes para resolver certos problemas, além de fornecer uma boa área para pesquisa.

  • Processamento de imagem - Os GAs são usados para várias tarefas de processamento de imagem digital (DIP), bem como para correspondência densa de pixels.

  • Problemas de roteamento de veículos - com várias janelas flexíveis, vários depósitos e uma frota heterogênea.

  • Aplicativos de agendamento - os GAs também são usados para resolver vários problemas de agendamento, principalmente o problema de contagem de horas.

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

  • Geração de trajetória de robô - GAs foram usados para planejar o caminho que um braço de robô percorre, movendo-se de um ponto para outro.

  • Projeto paramétrico de aeronaves - GAs têm sido utilizados para projetar aeronaves variando os parâmetros e desenvolvendo melhores soluções.

  • Análise de DNA - Os GAs foram utilizados para determinar a estrutura do DNA usando dados espectrométricos sobre a amostra.

  • Otimização multimodal - os AGs são obviamente muito boas abordagens para otimização multimodal, nas quais temos que encontrar várias soluções ótimas.

  • Problema do vendedor ambulante e suas aplicações - os GAs foram usados para resolver o TSP, que é um problema combinatório bem conhecido usando novas estratégias de cruzamento e empacotamento.

Algoritmos Genéticos - Outras Leituras

Os livros a seguir podem ser consultados para aprimorar ainda mais o conhecimento do leitor sobre 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 Evolutivos por Zbigniew Michalewicz .

  • Algoritmos genéticos práticos de Randy L. Haupt e Sue Ellen Haupt .

  • Otimização Multi-Objetiva usando Algoritmos Evolutivos por Kalyanmoy Deb .