Visão geral do algoritmo genético

Técnicas de otimização são as técnicas usadas para descobrir a melhor solução dentre todas as soluções possíveis disponíveis sob as restrições presentes. Portanto, o algoritmo genético é um desses algoritmos de otimização, construído com base no processo evolutivo natural de nossa natureza. A idéia de Seleção Natural e Herança Genética é usada aqui. Ele usa a pesquisa aleatória guiada, diferentemente de outros algoritmos, ou seja, encontrando a solução ideal iniciando com uma função de custo inicial aleatória e pesquisando apenas no espaço que teve o menor custo (na direção guiada). Adequado quando você está trabalhando com conjuntos de dados enormes e complexos.

O que é um algoritmo genético?

O algoritmo genético é baseado na estrutura genética e no comportamento do cromossomo da população. O seguinte é a base dos algoritmos genéticos.

  • Cada cromossomo indica uma possível solução. Assim, a população é uma coleção de cromossomos.
  • Cada indivíduo da população é caracterizado por uma função de condicionamento físico. Maior aptidão melhor é a solução.
  • Dos indivíduos disponíveis na população, os melhores indivíduos são usados ​​para a reprodução dos filhotes da próxima geração.
  • A prole produzida terá características de ambos os pais e é resultado de mutação. Uma mutação é uma pequena mudança na estrutura do gene.

Fases do algoritmo genético

Abaixo estão as diferentes fases do algoritmo genético:

1. Inicialização da população (codificação)

  • Todo gene representa um parâmetro (variáveis) na solução. Essa coleção de parâmetros que forma a solução é o cromossomo. A população é uma coleção de cromossomos.
  • A ordem dos genes no cromossomo é importante.
  • Na maioria das vezes, os cromossomos são representados em binário como zeros e zeros, mas também existem outras codificações possíveis.

2. Função de condicionamento físico

  • Dos cromossomos disponíveis, temos que selecionar os melhores para a reprodução dos filhotes, para que cada cromossomo receba um valor de condicionamento físico.
  • A pontuação de condicionamento físico ajuda a selecionar os indivíduos que serão utilizados para a reprodução.

3. Seleção

  • O principal objetivo desta fase é encontrar a região onde as chances de obter a melhor solução são maiores.
  • A inspiração para isso é a sobrevivência do mais apto.
  • Deve haver um equilíbrio entre a exploração e a exploração do espaço de pesquisa.
  • O GA tenta mover o genótipo para uma melhor adequação no espaço de pesquisa.
  • Um viés de seleção de aptidão muito forte pode levar a soluções abaixo do ideal.
  • Pouca seleção de viés de condicionamento físico resulta em pesquisa sem foco.
  • Assim, a seleção proporcional de Fitness é usada, também conhecida como seleção de roleta, é um operador genético usado em algoritmos genéticos para selecionar soluções potencialmente úteis para recombinação.

4. Reprodução

A geração de filhotes acontece de duas maneiras:

  • Crossover
  • Mutação

a) Crossover

O cruzamento é o estágio mais vital do algoritmo genético. Durante o cruzamento, um ponto aleatório é selecionado ao acasalar um par de pais para gerar filhos.

Existem 3 tipos principais de crossover.

  • Cruzamento de ponto único: um ponto nos cromossomos de ambos os pais é escolhido aleatoriamente e designado como 'ponto de cruzamento'. Os bits à direita desse ponto são trocados entre os dois cromossomos progenitores.
  • Crossover de dois pontos : dois pontos de crossover são selecionados aleatoriamente nos cromossomos principais. Os bits entre os dois pontos são trocados entre os organismos progenitores.
  • Crossover uniforme: em um crossover uniforme, normalmente, cada bit é escolhido de qualquer um dos pais com igual probabilidade.

Os novos filhos são adicionados à população.

b) Mutação

Em algumas novas crias formadas, alguns de seus genes podem ser submetidos a uma mutação com baixa probabilidade aleatória. Isso indica que alguns dos bits no cromossomo dos bits podem ser invertidos. A mutação trata da diversidade da população e impede a convergência prematura.

5. Convergência (quando parar)

Poucas regras seguidas que informam quando parar são as seguintes:

  • Quando não há melhoria na qualidade da solução após a conclusão de um certo número de gerações definidas anteriormente.
  • Quando é atingido um intervalo de gerações e tempo difícil e rápido.
  • Até que uma solução aceitável seja obtida.

Aplicação de Algoritmo Genético

Nesta seção, discutiremos algumas das áreas nas quais o Algoritmo Genético é freqüentemente aplicado.

1. Roteiro de viagem e embarque

O problema do vendedor ambulante é uma das principais aplicações do algoritmo genético. Por exemplo, quando um planejador de viagem é solicitado a planejar uma viagem, ele recebe a ajuda de um algoritmo genético que não apenas ajuda a reduzir o custo total da viagem, mas também na redução do tempo. A GE também é usada para planejar a entrega de produtos de um lugar para outro da melhor maneira eficiente.

2. Robótica

O algoritmo genético é amplamente utilizado no campo da robótica. Os robôs diferem um do outro pelo propósito para o qual foram criados. Por exemplo, poucos são criados para uma tarefa de cozinhar, poucos são criados para tarefas de ensino etc.

  • Seleção de recursos importantes no conjunto de dados fornecido.
  • No método tradicional, os recursos importantes no conjunto de dados são selecionados usando o método a seguir. ou seja, se você observar a importância desse modelo, definirá um valor limite para os recursos e, se o recurso tiver um valor mais importante que um limite, ele será considerado.
  • Mas aqui usamos um método chamado problema de mochila.
  • Começaremos novamente com a população de um cromossomo, onde cada cromossomo será uma sequência binária. 1 denotará a "inclusão" de recurso no modelo e 0 denotará a "exclusão" de recurso no modelo.
  • A função de condicionamento físico aqui será nossa métrica de precisão da competição. Quanto mais preciso for o nosso conjunto de cromossomos na previsão de valor, mais adequado será.
  • Existem muitas outras aplicações de algoritmos genéticos, como análise de DNA, aplicativos de agendamento e projeto de engenharia.

Conclusão

No cenário atual, a GE está sendo usada em grandes empresas de manufatura, como aeronaves etc., a fim de otimizar o tempo e o uso de recursos. Outros cientistas estão trabalhando para encontrar novas maneiras de combinar algoritmos genéticos com outras técnicas de otimização.

Artigos recomendados

Este é um guia para O que é o algoritmo genético? Aqui discutimos a introdução, fases e aplicações do algoritmo genético. Você também pode consultar nossos outros artigos sugeridos -

  1. Algoritmos de roteamento
  2. Tipos de algoritmos
  3. Algoritmos de redes neurais
  4. Algoritmos de mineração de dados
  5. Guia de exemplos de algoritmo C ++

Categoria:

Big Data