Um algoritmo genético é um algoritmo de busca heurística adaptativo inspirado na 'teoria da evolução de Darwin na Natureza .' É usado para resolver problemas de otimização em aprendizado de máquina. É um dos algoritmos importantes, pois ajuda a resolver problemas complexos que levariam muito tempo para serem resolvidos.

Algoritmos Genéticos estão sendo amplamente utilizados em diferentes aplicações do mundo real, por exemplo, Projeto de circuitos eletrônicos, quebra de códigos, processamento de imagens e criatividade artificial.

Neste tópico, explicaremos detalhadamente o algoritmo genético, incluindo terminologias básicas usadas no algoritmo genético, como funciona, vantagens e limitações do algoritmo genético, etc.

importante

O que é um algoritmo genético?

Antes de entender o algoritmo Genético, vamos primeiro entender as terminologias básicas para entender melhor este algoritmo:

População:População é o subconjunto de todas as soluções possíveis ou prováveis ​​que podem resolver um determinado problema.Cromossomos:Um cromossomo é uma das soluções da população para um determinado problema, e a coleção de genes gera um cromossomo.Gene:Um cromossomo é dividido em um gene diferente ou é um elemento do cromossomo.Alelos:Alelo é o valor fornecido ao gene dentro de um cromossomo específico.Função de condicionamento físico:A função de aptidão é usada para determinar o nível de aptidão do indivíduo na população. Significa a capacidade de um indivíduo competir com outros indivíduos. Em cada iteração, os indivíduos são avaliados com base na sua função de aptidão.Operadores Genéticos:Em um algoritmo genético, o melhor indivíduo acasala para regenerar os descendentes melhor do que os pais. Aqui, os operadores genéticos desempenham um papel na mudança da composição genética da próxima geração.Seleção

Após calcular a aptidão de todos os existentes na população, um processo de seleção é utilizado para determinar quais das individualidades da população conseguirão se reproduzir e produzir a semente que formará a próxima geração.

Tipos de estilos de seleção disponíveis

Seleção de roleta Seleção de eventos Seleção baseada em classificação

Portanto, agora podemos definir um algoritmo genético como um algoritmo de busca heurística para resolver problemas de otimização. É um subconjunto de algoritmos evolutivos, usado em computação. Um algoritmo genético usa conceitos genéticos e de seleção natural para resolver problemas de otimização.

Como funciona o algoritmo genético?

O algoritmo genético trabalha no ciclo evolutivo geracional para gerar soluções de alta qualidade. Esses algoritmos usam diferentes operações que melhoram ou substituem a população para fornecer uma solução de ajuste melhorada.

Envolve basicamente cinco fases para resolver os complexos problemas de otimização, que são apresentados a seguir:

Inicialização Tarefa de condicionamento físico Seleção Reprodução Terminação

1. Inicialização

O processo de um algoritmo genético começa gerando o conjunto de indivíduos, que é denominado população. Aqui cada indivíduo é a solução para um determinado problema. Um indivíduo contém ou é caracterizado por um conjunto de parâmetros denominados Genes. Os genes são combinados em uma sequência e geram cromossomos, que é a solução para o problema. Uma das técnicas mais populares para inicialização é o uso de strings binárias aleatórias.

converter data em string

2. Tarefa de condicionamento físico

A função de condicionamento físico é usada para determinar o quão apto um indivíduo está? Significa a capacidade de um indivíduo competir com outros indivíduos. Em cada iteração, os indivíduos são avaliados com base na sua função de aptidão. A função de condicionamento físico fornece uma pontuação de condicionamento físico para cada indivíduo. Esta pontuação determina ainda a probabilidade de ser selecionado para reprodução. Quanto mais alta for a pontuação de aptidão, maiores serão as chances de ser selecionado para reprodução.

3. Seleção

A fase de seleção envolve a seleção de indivíduos para a reprodução da prole. Todos os indivíduos selecionados são então organizados em pares para aumentar a reprodução. Então esses indivíduos transferem seus genes para a próxima geração.

Existem três tipos de métodos de seleção disponíveis, que são:

• Seleção de roleta
• Seleção de torneio
• Seleção baseada em classificação

4. Reprodução

Após o processo seletivo, a criação de um filho ocorre na etapa de reprodução. Nesta etapa, o algoritmo genético utiliza dois operadores de variação que são aplicados à população parental. Os dois operadores envolvidos na fase de reprodução são apresentados a seguir:

Cruzamento:O cruzamento desempenha um papel mais significativo na fase de reprodução do algoritmo genético. Neste processo, um ponto de cruzamento é selecionado aleatoriamente dentro dos genes. Em seguida, o operador de cruzamento troca informações genéticas de dois pais da geração atual para produzir um novo indivíduo representando a prole.

Os genes dos pais são trocados entre si até que o ponto de cruzamento seja atingido. Esses descendentes recém-gerados são adicionados à população. Este processo também é chamado de crossover. Tipos de estilos de crossover disponíveis:
• Cruzamento de um ponto
• Cruzamento de dois pontos
• Crossover de libré
• Cruzamento de algoritmos herdáveis
Mutação
O operador de mutação insere genes aleatórios na prole (novo filho) para manter a diversidade na população. Isso pode ser feito invertendo alguns bits nos cromossomos.
A mutação ajuda a resolver o problema da convergência prematura e aumenta a diversificação. A imagem abaixo mostra o processo de mutação:
Tipos de estilos de mutação disponíveis,

como exibir aplicativo no android

Mutação de flip bit Mutação gaussiana Mutação de troca/troca

5. Rescisão

Após a fase de reprodução, um critério de parada é aplicado como base para a terminação. O algoritmo termina depois que a solução de aptidão limite é atingida. Irá identificar a solução final como a melhor solução na população.

Fluxo de trabalho geral de um algoritmo genético simples

Vantagens do Algoritmo Genético

• As capacidades paralelas dos algoritmos genéticos são as melhores.
• Ajuda na otimização de vários problemas, como funções discretas, problemas multiobjetivo e funções contínuas.
• Ele fornece uma solução para um problema que melhora com o tempo.
• Um algoritmo genético não precisa de informações derivadas.

Limitações dos Algoritmos Genéticos

• Algoritmos genéticos não são algoritmos eficientes para resolver problemas simples.
• Não garante a qualidade da solução final de um problema.
• O cálculo repetitivo dos valores de aptidão pode gerar alguns desafios computacionais.

Diferença entre Algoritmos Genéticos e Algoritmos Tradicionais

• Um espaço de busca é o conjunto de todas as soluções possíveis para o problema. No algoritmo tradicional, apenas um conjunto de soluções é mantido, enquanto, em um algoritmo genético, vários conjuntos de soluções no espaço de busca podem ser utilizados.
• Os algoritmos tradicionais precisam de mais informações para realizar uma pesquisa, enquanto os algoritmos genéticos precisam apenas de uma função objetivo para calcular a aptidão de um indivíduo.
• Os algoritmos tradicionais não podem funcionar paralelamente, enquanto os algoritmos genéticos podem funcionar paralelamente (o cálculo da aptidão das individualidades é independente).
• Uma grande diferença nos algoritmos genéticos é que, em vez de operar diretamente nos resultados do buscador, os algoritmos herdáveis ​​operam em suas representações (ou renderização), frequentemente chamadas de cromossomos.
• Uma das grandes diferenças entre o algoritmo tradicional e o algoritmo genético é que ele não opera diretamente nas soluções candidatas.
• Os algoritmos tradicionais podem gerar apenas um resultado no final, enquanto os algoritmos genéticos podem gerar vários resultados ótimos de diferentes gerações.
• O algoritmo tradicional não tem maior probabilidade de gerar resultados ótimos, enquanto os algoritmos genéticos não garantem a geração de resultados globais ótimos, mas também há uma grande possibilidade de obter o resultado ótimo para um problema, pois utiliza operadores genéticos como Crossover e Mutação.
• Os algoritmos tradicionais são de natureza determinística, enquanto os algoritmos genéticos são probabilísticos e estocásticos por natureza.