Introdução aos algoritmos genéticos em aprendizado de máquina

introduction genetic algorithms machine learning

lista de adjacência de grafos c ++

Este tutorial de algoritmo genético explica o que são algoritmos genéticos e sua função no aprendizado de máquina em detalhes :

No Tutorial anterior , aprendemos sobre Modelos de Redes Neurais Artificiais - Perceptron Multicamadas, Backpropagation, Radial Bias e Mapas Auto Organizáveis ​​de Kohonen, incluindo sua arquitetura.

Vamos nos concentrar em Algoritmos Genéticos que vieram muito antes das Redes Neurais, mas agora o GA foi assumido pela NN. Embora o GA ainda tenha aplicações na vida real, como problemas de otimização como agendamento, jogos, robótica, design de hardware, problemas de caixeiro viajante, etc.

Algoritmos genéticos são algoritmos baseados na ideia evolucionária de seleção natural e genética. GAs são algoritmos de busca heurística adaptativos, ou seja, os algoritmos seguem um padrão iterativo que muda com o tempo. É um tipo de aprendizagem por reforço em que o feedback é necessário sem dizer o caminho correto a seguir. O feedback pode ser positivo ou negativo.

=> Leia a série completa de treinamento em aprendizado de máquina

O que você aprenderá:

• Por que usar algoritmos genéticos
  • Antecedentes Biológicos de Algoritmos Genéticos
• O que são algoritmos genéticos
  • Correlação de um cromossomo com GA
  • Terminologia importante em GA
  • Um Algoritmo Genético Simples
  • Método de seleção da roda de roleta
  • Outros Métodos de Seleção
  • Crossover
  • Mutação
  • Quando parar o algoritmo genético
• Vantagens e desvantagens do algoritmo genético
• Aplicações de Algoritmos Genéticos
• Conclusão
  • Leitura recomendada

Por que usar algoritmos genéticos

GAs são algoritmos mais robustos que podem ser usados ​​para vários problemas de otimização. Esses algoritmos não se desviam facilmente na presença de ruído, ao contrário de outros algoritmos de IA. Os AGs podem ser usados ​​na busca de grande espaço ou espaço multimodal.

Antecedentes Biológicos de Algoritmos Genéticos

Genética é derivada da palavra grega “gênese” que significa crescer. A genética decide os fatores de hereditariedade, semelhanças e diferenças entre os descendentes no processo de evolução. Algoritmos genéticos também são derivados da evolução natural.

Algumas terminologias em um cromossomo biológico

• Cromossomos: Todas as informações genéticas de uma espécie são cromossomos armazenados.
• Genes: Os cromossomos são divididos em várias partes chamadas Genes.
• Alelos: Os genes identificam as características de um indivíduo. A possibilidade de uma combinação de genes para formar propriedades é chamada de alelos. Um gene pode ter alelos diferentes.
• Pool Gene: Todas as combinações possíveis de genes que são todos alelos em um pool de população são chamadas de pool de genes.
• Genoma: O conjunto de genes de uma espécie é denominado genoma.
• Locus: Cada gene tem uma posição em um genoma que é chamado de locus.
• Genótipo: Uma combinação completa de genes em um indivíduo é chamada de genótipo.
• Fenótipo: Um conjunto de genótipos em uma forma decodificada é chamado de fenótipo.

O que são algoritmos genéticos

Os Algoritmos Genéticos estimulam o processo como nos sistemas naturais para a evolução. Charles Darwin afirmou a teoria da evolução que na evolução natural, os seres biológicos evoluem de acordo com o princípio da “sobrevivência do mais apto”. A busca GA é projetada para encorajar a teoria da “sobrevivência do mais apto”.

Os GAs realizam uma busca aleatória para resolver problemas de otimização. O GA usa técnicas que usam as informações históricas anteriores para direcionar sua pesquisa para a otimização no novo espaço de pesquisa.

Correlação de um cromossomo com GA

O corpo humano possui cromossomos que são feitos de genes. Um conjunto de todos os genes de uma espécie específica é denominado genoma. Nos seres vivos, os genomas são armazenados em vários cromossomos, enquanto no GA todos os genes são armazenados no mesmo cromossomo.

Comparação entre a evolução natural e a terminologia do algoritmo genético

Terminologia importante em GA

• População: É um grupo de indivíduos. A população inclui o número de indivíduos sendo testados, informações do espaço de pesquisa e os parâmetros do fenótipo. Geralmente, a população é inicializada aleatoriamente.
• Indivíduos: Os indivíduos são uma solução única na população. Um indivíduo possui um conjunto de parâmetros chamados genes. Genes combinados para formar cromossomos.
• Genes: Genes são blocos de construção de Algoritmos Genéticos. Um cromossomo é composto de genes. Os genes podem determinar a solução para o problema. Eles são representados por uma sequência de bits (0 ou 1) de comprimento aleatório.
• Ginástica: A aptidão diz o valor do fenótipo do problema. A função de fitness informa o quão perto a solução está da solução ideal. A função de aptidão é determinada de várias maneiras, como a soma de todos os parâmetros relacionados ao problema - distância euclidiana, etc. Não há regra para avaliar a função de aptidão.

Um Algoritmo Genético Simples

Um GA simples tem uma população de cromossomos individuais. Esses cromossomos representam soluções possíveis. Operadores de reprodução são aplicados sobre esses conjuntos de cromossomos para realizar mutações e recombinações. Assim, é importante encontrar operadores de reprodução adequados, pois o comportamento de GA depende dele.

Um algoritmo genético simples é o seguinte:

# 1) Comece com a população criada aleatoriamente.

#dois) Calcule a função de aptidão de cada cromossomo.

# 3) Repita os passos até que n descendentes sejam criados. Os descendentes são criados conforme mostrado abaixo.

• Selecione um par de cromossomos da população.
• Cruze o par com probabilidade p_cpara formar descendentes.
• Transformar o cruzamento com probabilidade p_m.

# 4) Substitua a população original pela nova população e vá para a etapa 2.

Vamos ver as etapas seguidas neste processo de iteração. A população inicial de cromossomos é gerada. A população inicial deve conter genes suficientes para que qualquer solução possa ser gerada. O primeiro pool de população é gerado aleatoriamente.

• Seleção: O melhor conjunto de genes é selecionado dependendo da função de aptidão. A corda com a melhor função de fitness é escolhida.
• Reprodução: Novos descendentes são gerados por recombinação e mutação.
• Avaliação: Os novos cromossomos gerados são avaliados por sua adequação.
• Substituição: Nesta etapa, a população antiga é substituída pela população recém-gerada.

Método de seleção da roda de roleta

A seleção da roda da roleta é o método de seleção amplamente utilizado.

O processo de seleção é curto, conforme mostrado abaixo:

Nesse método, uma busca linear é feita por meio da roda da roleta. As ranhuras da roda são pesadas de acordo com o valor de aptidão individual. O valor alvo é definido aleatoriamente de acordo com a proporção da soma da aptidão na população.

A população é então pesquisada até que o valor alvo seja alcançado. Este método não garante o mais apto dos indivíduos, mas tem a probabilidade de ser o mais apto.

Vamos ver as etapas envolvidas na seleção da roda de roleta.

O valor esperado de um indivíduo = aptidão individual / aptidão da população. Os slots de roda são atribuídos a indivíduos com base em sua aptidão. A roda é girada N vezes, onde N é o número total de indivíduos na população. Quando uma rotação termina, o indivíduo selecionado é colocado em um grupo de pais.

1. Seja o valor total esperado de um número de indivíduos na população S.
2. Repita as etapas de 3 a 5 n vezes.
3. Selecione um número inteiro s entre 0 e S.
4. Percorra os indivíduos da população, some os valores esperados até que a soma seja maior do que s.
5. O indivíduo cujo valor esperado coloca a soma acima do limite s é selecionado.

Desvantagens da seleção da roda de roleta:

1. Se a aptidão difere muito, então a circunferência da roda da Roleta será tomada ao máximo pelo cromossomo da função de aptidão mais alta, então as outras têm muito pouca chance de serem selecionadas.
2. É barulhento.
3. A evolução depende da variação na aptidão da população.

Outros Métodos de Seleção

Existem muitos outros métodos de seleção usados ​​no 'Seleção' etapa do Algoritmo Genético.

Discutiremos os outros 2 métodos amplamente utilizados:

# 1) Seleção de classificação: Neste método, cada cromossomo recebe um valor de aptidão da classificação. O pior ajuste é 1 e o melhor ajuste é N. É um método de convergência lenta. Neste método, a diversidade é preservada levando a uma busca bem-sucedida.

Os pais em potencial são selecionados e, em seguida, um torneio é realizado para decidir qual dos indivíduos será o pai.

# 2) Seleção do torneio: Nesse método, uma estratégia de pressão seletiva é aplicada à população. O melhor indivíduo é aquele com maior aptidão. Este indivíduo é o vencedor da competição do torneio entre indivíduos Nu na população.

A população do torneio junto com o vencedor é novamente adicionada ao pool para gerar novos descendentes. A diferença nos valores de aptidão do vencedor e dos indivíduos no pool de acasalamento fornece uma pressão seletiva para resultados ideais.

Crossover

É um processo de pegar 2 indivíduos e produzir um filho deles. O processo de reprodução após a seleção produz clones das picadas boas. O operador crossover é aplicado sobre as cordas para produzir uma prole melhor.

A implementação do operador de crossover é a seguinte:

1. Dois indivíduos são selecionados aleatoriamente na população para produzir descendentes.
2. Um site cruzado é selecionado aleatoriamente ao longo do comprimento da string.
3. Os valores no site são trocados.

O crossover executado pode ser um crossover de ponto único, crossover de dois pontos, crossover multiponto, etc. O crossover de ponto único tem um site de crossover, enquanto um site de crossover de dois pontos tem 2 sites onde os valores são trocados.

Podemos ver isso no exemplo abaixo:

Crossover de Ponto Único

Crossover de dois pontos

Probabilidade de cruzamento

P_c, a probabilidade de cruzamento é o termo que descreve a frequência com que o cruzamento será executado. 0% de probabilidade significa que os novos cromossomos serão uma cópia exata dos cromossomos antigos, enquanto 100% de probabilidade significa que todos os novos cromossomos são feitos por cruzamento.

Mutação

A mutação é feita após o Crossover. Enquanto o crossover se concentra apenas na solução atual, a operação de mutação pesquisa todo o espaço de pesquisa. Este método serve para recuperar a informação genética perdida e distribuir a informação genética.

Este operador ajuda a manter a diversidade genética na população. Ajuda a prevenir mínimos locais e impede a geração de soluções inúteis por parte de qualquer população.

A mutação é realizada de várias maneiras, como inverter o valor de cada gene com uma pequena probabilidade ou realizar mutação apenas se melhorar a qualidade da solução.

Algumas das formas de mutação são:

• Lançando: Mudando de 0 a 1 ou 1 a 0.
• Intercambiando: Duas posições aleatórias são escolhidas e os valores são trocados.
• Invertendo: A posição aleatória é escolhida e os bits próximos a ela são invertidos.

Vamos ver alguns exemplos de cada um:

Lançando

Intercambiando

Invertendo

Probabilidade de mutação

P_m, a probabilidade de mutação é um termo que decide com que frequência os cromossomos sofrerão mutação. Se a probabilidade de mutação for 100%, significa que todo o cromossomo foi alterado. Se uma mutação não for realizada, uma nova descendência será gerada diretamente após o cruzamento.

Um exemplo de um algoritmo genético geral Probabilidade de mutação: P_m, a probabilidade de mutação é um termo que decide com que frequência os cromossomos sofrerão mutação. Se a probabilidade de mutação for 100%, significa que todo o cromossomo foi alterado.

Se uma mutação não for realizada, os novos descendentes serão gerados diretamente após o cruzamento. A população inicial de cromossomos é dada como A, B, C, D. O tamanho da população é 4.

A função de fitness é considerada como um número de 1 na sequência.

A soma da aptidão é 12, o que implica, a função de aptidão média seria ~ 12/4 = 3

Probabilidade de cruzamento = 0,7

Probabilidade de mutação = 0,001

# 1) Se B e C forem selecionados, o cruzamento não será realizado porque o valor de adequação de C está abaixo da adequação média.

#dois) B é mutado => B: 11101110 -> B^': 01101110 para preservar a diversidade populacional

# 3) B e D são selecionados, o crossover é executado.

B: 11101110 E: 10110100 -> D: 00110100 F: 01101110

# 4) Se E for mutado, então

E: 10110100 -> E^': 10110000

Os cromossomos correspondentes são mostrados na tabela abaixo. O pedido é colocado aleatoriamente.

Embora o indivíduo mais apto com valor de aptidão de 6 seja perdido, a aptidão média geral da população aumenta e seria: 14/4 = 3,5

Quando parar o algoritmo genético

Um algoritmo genético é interrompido quando algumas condições listadas abaixo são atendidas:

# 1) Melhor Convergência Individual: Quando o nível mínimo de aptidão cai abaixo do valor de convergência, o algoritmo é interrompido. Isso leva a uma convergência mais rápida.

# 2) Pior Convergência Individual: Quando os indivíduos menos ajustados na população atingem o valor mínimo de aptidão abaixo da convergência, o algoritmo é interrompido. Nesse método, o padrão mínimo de aptidão é mantido na população. Isso significa que o melhor indivíduo não é garantido, mas indivíduos com valor mínimo de aptidão estarão presentes.

# 3) Soma de aptidão: Neste método, se a soma da adequação for menor ou igual ao valor de convergência, a busca é interrompida. Garante que toda a população está dentro da faixa de aptidão.

# 4) Aptidão mediana: Nesse método, pelo menos metade dos indivíduos da população será melhor ou igual ao valor de convergência.

Alguns critérios de convergência ou condição de parada podem ser:

• Quando um determinado número de gerações evoluiu.
• Quando o tempo especificado para executar o algoritmo for atingido.
• Quando o valor de aptidão da população não muda mais com as iterações.

Vantagens e desvantagens do algoritmo genético

As vantagens de um algoritmo genético são:

1. Tem um espaço de solução mais amplo.
2. É mais fácil descobrir o ótimo global.
3. Paralelismo: Vários GAs podem ser executados juntos usando a mesma CPU sem interferir uns com os outros. Eles funcionam paralelamente de forma isolada.

Limitações do GA:

1. A identificação da função de fitness é uma limitação.
2. A convergência dos algoritmos pode ser muito rápida ou muito lenta.
3. Há uma limitação de seleção de parâmetros como cruzamento, probabilidade de mutação, tamanho da população etc.

Aplicações de Algoritmos Genéticos

GA é eficaz para resolver problemas dimensionais elevados. Um GA é efetivamente usado quando o espaço de busca é muito grande, não há técnicas de resolução de problemas matemáticos disponíveis e outros algoritmos de busca tradicionais não funcionam.

Alguns aplicativos onde o GA é usado:

• Problema de otimização: Um dos melhores exemplos de problemas de otimização é o problema do caixeiro de viagens que usa o GA. Outros problemas de otimização, como agendamento de trabalho, GAs de otimização de qualidade de som são amplamente utilizados.
• Modelo de sistema imunológico: GAs são usados ​​para modelar vários aspectos do sistema imunológico para genes individuais e famílias multigênicas durante o tempo evolutivo.
• Aprendizado de máquina: Os AGs têm sido usados ​​para resolver problemas relacionados à classificação, previsão, criar regras para aprendizagem e classificação .

Conclusão

Algoritmos genéticos são baseados no método da evolução natural. Esses algoritmos são diferentes dos outros algoritmos de classificação porque usam parâmetros codificados (0 ou 1), há vários números de indivíduos em uma população e usam o método probabilístico para convergência.

Com o processo de crossover e mutação, os GAs convergem em gerações sucessivas. A execução de um algoritmo GA nem sempre garante uma solução de sucesso. Os algoritmos genéticos são altamente eficientes na otimização - problemas de agendamento de tarefas.

Espero que este tutorial tenha enriquecido seu conhecimento sobre o conceito de Algoritmos Genéticos !!

=> Visite aqui para a série exclusiva de aprendizado de máquina

Leitura recomendada

• Teste Baseado em Modelo Usando Algoritmo Genético
• Data Mining Vs Machine Learning Vs Artificial Intelligence Vs Deep Learning
• Tutorial de aprendizado de máquina: introdução ao ML e seus aplicativos
• Tipos de aprendizado de máquina: aprendizado supervisionado versus aprendizado não supervisionado
• Um guia completo para redes neurais artificiais em aprendizado de máquina
• 11 ferramentas de software de aprendizado de máquina mais populares em 2021
• As 13 MELHORES empresas de aprendizado de máquina (Lista atualizada de 2021)
• O que é Support Vector Machine (SVM) no aprendizado de máquina