Algoritmos genéticos e seus casos de uso em Machine Learning

Conteúdo

Este artigo foi publicado como parte do Data Science Blogathon

Algoritmos genéticos são algoritmos de busca inspirados na teoria da evolução de Darwin na natureza..

  • Simulando o processo de seleção natural, reprodução e mutação, algoritmos genéticos podem produzir soluções de alta qualidade para vários problemas, incluindo pesquisa e otimização.

  • Através do uso efetivo da Teoria da Evolução, algoritmos genéticos podem superar os problemas enfrentados por algoritmos tradicionais.

De acordo com a teoria da evolução de Darwin, uma evolução mantém uma população de indivíduos que variam uns dos outros (variação). Aqueles que estão melhor adaptados ao seu ambiente têm mais chances de sobreviver, reproduzir e passar suas características para a próxima geração (sobrevivência do mais apto).

Como funcionam os algoritmos genéticos??

Antes de entrar na operação de um algoritmo genético, vamos mergulhar na terminologia básica dos algoritmos genéticos.

Cromossomo / individual

Um cromossomo é uma coleção de genes. Por exemplo, um cromossomo pode ser representado como uma cadeia binária onde cada bit é um gene.

644781623127595061-8406334

Fonte da imagem: algoritmo genético prático com Python, Eyal Wirsansky

população

Uma vez que um indivíduo é representado como um cromossomo, uma população é uma coleção de tais cromossomos.

779521623127686493-5364456

Fonte da imagem: algoritmo genético prático com Python, Eyal Wirsansky

Função fitness

Em cada iteração, indivíduos são avaliados com base em seus escores de aptidão que são calculados usando a função de aptidão.

As pessoas que alcançam uma melhor pontuação de condicionamento físico representam melhores soluções e são mais propensas a serem escolhidas para atravessar e passar para a próxima geração..

Por exemplo, se algoritmos genéticos são usados para seleção de recursos, então a precisão do modelo com essas características selecionadas seria a função de adequação se fosse um problema de classificação.

seleção

Após calcular a aptidão de cada indivíduo na população, um processo seletivo é usado para determinar qual dos indivíduos da população será capaz de reproduzir e criar a prole que formará a próxima geração..

Tipos de métodos de seleção disponíveis,

  • Seleção de rodas de roleta
  • Seleção de torneios
  • Seleção baseada em alcance

Transversal

Geralmente, dois indivíduos da geração atual são escolhidos e seus genes são trocados entre dois indivíduos para criar um novo indivíduo representando a prole.. Esse processo também é chamado de acasalamento ou cruzamento..

Tipos de métodos cruzados disponíveis,

  • Cruzando um ponto
  • Crossover de dois pontos
  • Travessia uniforme
505071623128127345-5633004
Cruzando um pontoFonte da imagem: algoritmos genéticos práticos com Python, Eyal Wirsansky

Mutação

Mutação é uma mudança aleatória em um cromossomo para introduzir novos padrões em um cromossomo.. Por exemplo, virar um pouco em uma sequência binária.

Tipos de métodos de mutação disponíveis,

  • Mutação de bits de lançamento
  • Mutação gaussiana
  • Mutação de troca
550041623128158975-5413371

Fluxo de trabalho geral de um simples algoritmo genético

244111623128199688-4801325

Fonte da imagem: algoritmos genéticos práticos com Python, Eyal Wirsansky

Como os algoritmos genéticos são diferentes dos algoritmos tradicionais??

  • um espaço de pesquisa é um conjunto de todas as soluções possíveis para o problema. Algoritmos tradicionais mantêm apenas um conjunto em um espaço de pesquisa, enquanto algoritmos genéticos usam vários conjuntos em um espaço de pesquisa (seleção de recursos usando RFE versus algoritmos genéticos).

  • Algoritmos tradicionais requerem mais informações para realizar uma pesquisa, enquanto algoritmos genéticos só requerem uma função objetiva para calcular a aptidão de um indivíduo.

  • Algoritmos tradicionais não podem funcionar em paralelo, enquanto algoritmos genéticos podem funcionar em paralelo (o cálculo da aptidão dos indivíduos é independente).

  • Uma grande diferença nos algoritmos genéticos é que, em vez de operar diretamente em soluções candidatas, algoritmos genéticos operam em suas representações (ou codificação), muitas vezes referido como cromossomos.

  • Algoritmos tradicionais só podem produzir uma solução no final, enquanto em algoritmos genéticos múltiplas soluções ideais podem ser obtidas de diferentes gerações.

  • Algoritmos tradicionais não são mais propensos a produzir soluções ideais globais, algoritmos genéticos não são garantidos para produzir soluções globais ideais também, mas eles são mais propensos a produzir soluções ideais globais devido a operadores genéticos como cruzamento e mutação.

  • Algoritmos tradicionais são deterministas na natureza, enquanto algoritmos genéticos são probabilísticos e estocásticos na natureza.

  • Problemas do mundo real são multimodais (contêm múltiplas soluções ideais localmente), algoritmos tradicionais não lidam bem com esses problemas enquanto algoritmos genéticos, com as configurações corretas do parâmetro, pode lidar com esses problemas muito bem devido ao grande espaço de solução.

Vantagens dos algoritmos genéticos

  • Paralelismo

  • Otimização Global

  • Um conjunto maior de espaço para soluções

  • Requer menos informações

  • Fornece várias soluções ideais

  • Probabilística na natureza

  • Representações genéticas usando cromossomos

Desvantagens dos algoritmos genéticos

Use casos de algoritmos genéticos em aprendizado de máquina

TPOT(Otimização do gasoduto baseado em árvores) é uma estrutura Auto-ML que usa algoritmos genéticos para otimizar os pipelines de aprendizagem de máquina usando a estrutura de algoritmo genético chamada DEAP (Algoritmos evolutivos distribuídos em Python).

Seleção de recursos usando algoritmos genéticos

Usando algoritmos genéticos, vamos fazer a seleção de características em um conjunto de dados de vinho disponível em sklearn.

import random
import pandas as pd
from sklearn.base import clone
from deap.algorithms import eaSimple
from deap import base, criador, tools
from sklearn.datasets import load_wine
from sklearn.metrics import accuracy_score
from sklearn.ensemble import RandomForestClassifier
from sklearn.model_selection import train_test_split

data = load_wine()
características = pd. DataFrame(
    data.data, colunas=data.feature_names
)
alvo = pd. Série(data.target)

# split the data into train and test
x_train, x_test, y_train, y_test = train_test_split(
    recursos, alvo, test_size = 0.2, estratifique=alvo
)

modelo = RandomForestClassifier()

Divida los datos en características y destino y luego divida las características y el destino para entrenamiento y prueba.

def compute_fitness_score(individual):
    """
    Selecione os recursos do indivíduo, train
    and compute the accuracy_score.
    
    Exemplo:
    individual = [0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1]
    o 1 representa a presença de características e
    0 representa a ausência de características
    
    """
    column_support = pd. Série(individual).astype(Bool)
    x_train global, y_train, x_test, y_test, model
    
    x_train_ = x_train[x_train.colunas[column_support]]
    x_test_ = x_test[x_test.colunas[column_support]]

    model.fit(x_train_, y_train)
    y_pred = model.predict(x_test_)
    pontuação = precisão_score(y_test, y_pred)
    
    pontuação de retorno,

Defina la puntuación de fitness. compute_fitness_score toma um un individuo como entrada, por exemplo, consideremos el siguiente individuo [0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1], en esta lista, 1 representa la presencia de esa característica en particular y 0 representa a ausência dessa característica. As colunas são selecionadas de acordo com o indivíduo e, em seguida, o modelo é ajustado e o escore de precisão é calculado.. Esta pontuação de precisão é a pontuação de aptidão física de um indivíduo..

n_genes = x_train.shape[1]
n_generations = 10
n_population = 10
crossover_probability = 0.6
mutation_probability = 0.2


def setup_toolbox():
    # container for individuals
    creator.create('FitnessMax', base. Aptidão, pesos =(1.0,))
    criador.criar('Individual', Lista, fitness=criador. FitnessMax)

    caixa de ferramentas = base. Toolbox()
    caixa de ferramentas.registre-se(
        'individual_generator_function',
        random.randint, 0, 1
    )
    # method to populate individual
    toolbox.register(
        'individual_generator',
        ferramentas.initRepeat,
        criador. Individual,
        toolbox.individual_generator_function,
        n_genes
    )
    # method to create population
    toolbox.register(
        'population_generator',
        ferramentas.initRepeat,
        Lista,
        toolbox.individual_generator
    )
    # fitness calculation
    toolbox.register(
        'avaliar', compute_fitness_score
    )
    # selection
    toolbox.register(
        'selecionar', tools.selTournament, tournsize=3
    )
    # crossover
    toolbox.register('companheiro', ferramentas.cxOnePoint)
    # mutation
    toolbox.register(
        'mutado',
        ferramentas.mutFlipBit,
        indpb=mutation_probability
    )
    caixa de ferramentas de retorno

n_genes representam o número de genes em um indivíduo que é igual ao número de características, n_generations representa o número de gerações que é igual a 10 e também n_population representado pelo número populacional. A probabilidade de travessia é definida para 0,6 e a probabilidade de mutação é definida em 0,2.

Toolbox é uma classe em uma estrutura de deap que nos fornece os utilitários necessários para definir indivíduos, populações e muito mais.

As etapas realizadas no método setup_toolbox são,

  • Primeiro, definimos um indivíduo que tem uma pontuação de aptidão associada a ele
  • A seguir, definimos uma função que gera genes de um indivíduo, no nosso caso 0 o 1 em um indivíduo
  • Definimos uma função que gera indivíduos de uma população, por exemplo, [0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1] é um indivíduo em uma população.
  • A seguir, definimos uma função que gera uma população, por exemplo, [[0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1],

    [0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1]]é um tamanho populacional 2.

  • A seguir, definimos uma função para avaliação, no nosso caso usamos a função compute_fitness_score.

  • Escolhemos o método de seleção do torneio para o processo seletivo, um ponto de travessia para o processo de travessia e uma mutação bit mudar para o processo de mutação.

# setup deap toolbox
toolbox = setup_toolbox()

# create a population
population = toolbox.population_generator(n_population)

# A simple evolutionary algorithm
final_population, diário de bordo = eaSimple(
    população, 
    Toolbox, 
    crossover_probability, 
    mutation_probability, 
    n_generations
)

Primeiro geramos uma população de indivíduos de tamanho 10. Então chamamos o método eaSimple em profundidade, que executa um algoritmo genético simples.

Os argumentos da função eaSimple,

  • O primeiro argumento é a população
  • caixa de ferramentas é a instância da classe caixa de ferramentas de deap
  • A probabilidade de atravessar denota a probabilidade de que um par de indivíduos atravessará
  • A probabilidade de mutação denota a probabilidade de que um indivíduo irá sofrer mutação
  • n_generations denota o número de gerações para evoluir.

O algoritmo eaSimple funciona da seguinte forma,

  1. A aptidão dos indivíduos em uma população é calculada
  2. Selecione o indivíduo mais apto usando o método de seleção do torneio.
  3. Cruzar indivíduos usando o método de cruzar um ponto
  4. Mutar indivíduos usando a mutação de bits de lançamento
  5. Recalcular a aptidão dos indivíduos.
  6. Siga os passos 2 uma 5 até atingir o número desejado de gerações.

Desta forma, pode realizar seleção de recursos usando um algoritmo genético.

Referências

[1] Algoritmos genéticos práticos com Python, Eyal Wirsansky

Obrigado!

A mídia mostrada neste artigo não é propriedade da DataPeaker e é usada a critério do autor.

Assine a nossa newsletter

Nós não enviaremos SPAM para você. Nós odiamos isso tanto quanto você.