Algorithmes génétiques et leurs cas d'utilisation en Machine Learning

Contenu

Cet article a été publié dans le cadre du Blogathon sur la science des données

Les algorithmes génétiques sont des algorithmes de recherche inspirés de la théorie de l'évolution de la nature de Darwin.

  • En simulant le processus de sélection naturelle, reproduction et mutation, les algorithmes génétiques peuvent produire des solutions de haute qualité à divers problèmes, y compris la recherche et l'optimisation.

  • Grâce à l'utilisation efficace de la théorie de l'évolution, les algorithmes génétiques peuvent surmonter les problèmes auxquels les algorithmes traditionnels sont confrontés.

Selon la théorie de l'évolution de Darwin, une évolution maintient une population d'individus qui varient les uns des autres (variation). Ceux qui sont mieux adaptés à leur environnement ont de meilleures chances de survie, reproduire et transmettre leurs traits à la génération suivante (la survie du plus fort).

Comment fonctionnent les algorithmes génétiques?

Avant d'entrer dans le fonctionnement d'un algorithme génétique, Plongeons dans la terminologie de base des algorithmes génétiques.

Chromosome / individu

Un chromosome est un ensemble de gènes. Par exemple, un chromosome peut être représenté comme une chaîne binaire où chaque bit est un gène.

644781623127595061-8406334

Source de l'image: algorithme génétique pratique avec Python, Eyal Wirsansky

Ville

Étant donné qu'un individu est représenté comme un chromosome, une population est une collection de tels chromosomes.

779521623127686493-5364456

Source de l'image: algorithme génétique pratique avec Python, Eyal Wirsansky

Fonction de remise en forme

A chaque itération, les individus sont évalués en fonction de leurs scores de fitness qui sont calculés à l'aide de la fonction de fitness.

Les personnes qui obtiennent un meilleur score de condition physique représentent de meilleures solutions et sont plus susceptibles d'être choisies pour passer et transmettre à la génération suivante.

Par exemple, si des algorithmes génétiques sont utilisés pour la sélection des caractères, alors la précision du modèle avec ces caractéristiques sélectionnées serait la fonction d'adéquation s'il s'agissait d'un problème de classification.

sélection

Après avoir calculé la fitness de chaque individu de la population, un processus de sélection est utilisé pour déterminer lequel des individus de la population sera capable de se reproduire et de créer la progéniture qui formera la prochaine génération.

Types de méthodes de sélection disponibles,

  • Sélection de roue de roulette
  • Sélection du tournoi
  • Sélection basée sur la plage

Transversale

Généralement, deux individus de la génération actuelle sont choisis et leurs gènes sont échangés entre deux individus pour créer un nouvel individu qui représente la progéniture. Ce processus est également appelé accouplement ou croisement..

Types de méthodes croisées disponibles,

  • Traverser un point
  • Croisement à deux points
  • Croisement uniforme
505071623128127345-5633004
Traverser un pointSource de l'image: algorithmes génétiques pratiques avec Python, Eyal Wirsansky

Mutation

La mutation est un changement aléatoire sur un chromosome pour introduire de nouveaux motifs sur un chromosome. Par exemple, retourner un peu dans une chaîne binaire.

Types de méthodes de mutation disponibles,

  • Mutation flip bit
  • Mutation gaussienne
  • Mutation d'échange
550041623128158975-5413371

Workflow général d'un algorithme génétique simple

244111623128199688-4801325

Source de l'image: algorithmes génétiques pratiques avec Python, Eyal Wirsansky

En quoi les algorithmes génétiques sont-ils différents des algorithmes traditionnels?

  • Un espace de recherche est un ensemble de toutes les solutions possibles au problème. Les algorithmes traditionnels ne conservent qu'un seul ensemble dans un espace de recherche, alors que les algorithmes génétiques utilisent plusieurs ensembles dans un espace de recherche (sélection de caractéristiques utilisant RFE par rapport aux algorithmes génétiques).

  • Les algorithmes traditionnels nécessitent plus d'informations pour effectuer une recherche, alors que les algorithmes génétiques ne nécessitent qu'une fonction objective pour calculer l'aptitude d'un individu.

  • Les algorithmes traditionnels ne peuvent pas fonctionner en parallèle, tandis que les algorithmes génétiques peuvent fonctionner en parallèle (le calcul de l'aptitude des individus est indépendant).

  • Une grande différence dans les algorithmes génétiques est qu'au lieu d'opérer directement sur des solutions candidates, les algorithmes génétiques opèrent sur leurs représentations (ou encodage), souvent appelés chromosomes.

  • Les algorithmes traditionnels ne peuvent produire qu'une solution à la fin, tandis que dans les algorithmes génétiques, plusieurs solutions optimales de différentes générations peuvent être obtenues.

  • ‌Les algorithmes traditionnels ne sont plus susceptibles de produire des solutions optimales globales, les algorithmes génétiques ne sont pas garantis pour produire également des solutions optimales globales, mais ils sont plus susceptibles de produire des solutions optimales globales en raison d'opérateurs génétiques tels que le croisement et la mutation.

  • Les algorithmes traditionnels sont de nature déterministe, tandis que les algorithmes génétiques sont de nature probabiliste et stochastique.

  • Les problèmes du monde réel sont multimodaux (contenir plusieurs solutions optimales localement), les algorithmes traditionnels ne gèrent pas bien ces problèmes tandis que les algorithmes génétiques, avec des réglages de paramètres corrects, peut très bien gérer ces problèmes en raison du grand espace de solution.

Avantages des algorithmes génétiques

  • Parallélisme

  • Optimisation globale

  • Un plus grand espace pour les solutions

  • Nécessite moins d'informations

  • Fournit plusieurs solutions optimales

  • De nature probabiliste

  • Représentations génétiques utilisant des chromosomes

Inconvénients des algorithmes génétiques

Cas d'utilisation d'algorithmes génétiques en machine learning

TPOT(Optimisation du pipeline basée sur l'arborescence) est un framework Auto-ML qui utilise des algorithmes génétiques pour optimiser les pipelines d'apprentissage automatique à l'aide du framework d'algorithmes génétiques appelé DEAP (Algorithmes évolutifs distribués en Python).

Sélection de caractéristiques à l'aide d'algorithmes génétiques

Utiliser des algorithmes génétiques, effectuons une sélection de caractéristiques sur un ensemble de données de vin disponible dans sklearn.

importer au hasard
importer des pandas au format pd
à partir du clone d'importation sklearn.base
à partir de deap.algorithms importer eaSimple
de la base d'importation profonde, créateur, outils
à partir de sklearn.datasets importer load_wine
de sklearn.metrics importer precision_score
de sklearn.ensemble importer RandomForestClassifier
de sklearn.model_selection importer train_test_split

données = load_wine()
fonctionnalités = pd.DataFrame(
    données.données, column=data.feature_names
)
cible = pd.Série(data.target)

# diviser les données en train et tester
x_train, x_test, y_train, y_test = train_test_split(
    caractéristiques, cible, taille_test=0.2, stratifier=cible
)

modèle = RandomForestClassifier()

Divisez les données en caractéristiques et cible, puis divisez les caractéristiques et la cible pour l'entraînement et les tests.

def compute_fitness_score(individuel):
    """
    Sélectionnez les fonctionnalités de l'individu, former
    et calculer le precision_score.
    
    Exemple:
    individu = [0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1]
    Les 1 représente la présence de caractéristiques et
    0 représente l'absence de caractéristiques
    
    """
    support_colonne = pd.Série(individuel).astype(bool)
    x_train global, y_train, x_test, y_test, maquette
    
    x_train_ = x_train[x_train.columns[colonne_support]]
    x_test_ = x_test[x_test.columns[colonne_support]]

    model.fit(x_train_, y_train)
    y_pred = model.predict(x_test_)
    score = precision_score(y_test, y_pred)
    
    note de retour,

Définir le score de forme physique. compute_fitness_score prend un individu en entrée, par exemple, considérons l'individu suivant [0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1], sur cette liste, 1 représente la présence de cette caractéristique particulière et 0 représente l'absence de cette caractéristique. Les colonnes sont sélectionnées en fonction de l'individu, puis le modèle est ajusté et le score de précision est calculé. Ce score de précision est le score de condition physique d'un individu.

n_genes = x_train.shape[1]
n_générations = 10
n_population = 10
crossover_probability = 0.6
mutation_probabilité = 0.2


def setup_toolbox():
    # conteneur pour les particuliers
    créateur.créer('Fitness Max', base.Fitness, poids=(1.0,))
    créateur.créer('Individuel', liste, fitness=créateur.FitnessMax)

    boîte à outils = base.Boîte à outils()
    toolbox.register(
        'individual_generator_function',
        random.randint, 0, 1
    )
    # méthode pour peupler l'individu
    toolbox.register(
        'générateur_individuel',
        tools.initRepeat,
        créateur.Individu,
        toolbox.individual_generator_function,
        n_gènes
    )
    # méthode pour créer une population
    toolbox.register(
        'population_generator',
        tools.initRepeat,
        liste,
        toolbox.individual_generator
    )
    # calcul de la condition physique
    toolbox.register(
        'évaluer', calculate_fitness_score
    )
    # sélection
    toolbox.register(
        'sélectionner', tools.selTournoi, tournize=3
    )
    # croisement
    toolbox.register('camarade', outils.cxOnePoint)
    # mutation
    toolbox.register(
        'subir une mutation',
        tools.mutFlipBit,
        indpb=probabilité_mutation
    )
    boîte à outils de retour

n_genes représente le nombre de gènes chez un individu qui est égal au nombre de caractéristiques, n_generations représente le nombre de générations égal à 10 et aussi n_population qui représente le nombre de population. La probabilité de croisement est fixée à 0,6 et la probabilité de mutation est fixée à 0,2.

Toolbox est une classe dans un framework profond qui nous fournit les utilitaires nécessaires pour définir les individus, populations et bien plus.

Les étapes effectuées dans la méthode setup_toolbox sont,

  • Premier, on définit un individu auquel est associé un score d'aptitude
  • Ensuite, nous définissons une fonction qui génère les gènes d'un individu, dans notre cas 0 O 1 chez un individu
  • On définit une fonction qui génère des individus à partir d'une population, par exemple, [0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1] est un individu dans une population.
  • Ensuite, on définit une fonction qui génère une population, par exemple, [[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]]est une population de taille 2.

  • Ensuite, on définit une fonction d'évaluation, dans notre cas, nous utilisons la fonction compute_fitness_score.

  • Nous choisissons la méthode de sélection du tournoi pour le processus de sélection, un point de croisement pour le processus de croisement et une mutation de bit de décalage pour le processus de mutation.

# configuration de la boîte à outils profonde
boîte à outils = setup_toolbox()

# créer une population
population = toolbox.population_generator(n_population)

# Un algorithme évolutif simple
population_finale, journal de bord = eaSimple(
    population, 
    boîte à outils, 
    crossover_probability, 
    mutation_probabilité, 
    n_générations
)

Nous générons d'abord une population d'individus de taille 10. Ensuite, nous appelons la méthode eaSimple en profondeur, qui exécute un algorithme génétique simple.

Les arguments de la fonction eaSimple,

  • Le premier argument est la population
  • toolbox est l'instance de la classe Toolbox de deap
  • La probabilité de croisement désigne la probabilité qu'une paire d'individus se croise
  • La probabilité de mutation désigne la probabilité qu'un individu mute
  • n_generations désigne le nombre de générations à évoluer.

L'algorithme eaSimple fonctionne comme suit,

  1. La fitness des individus dans une population est calculée
  2. Sélectionnez l'individu le plus apte à l'aide de la méthode de sélection du tournoi.
  3. Croisement d'individus selon la méthode de croisement en un point
  4. Mutation d'individus à l'aide de la mutation flip bit
  5. Recalculer la forme physique des individus.
  6. Suis les étapes 2 une 5 jusqu'à atteindre le nombre de générations souhaité.

De cette façon, peut effectuer une sélection de caractéristiques à l'aide d'un algorithme génétique.

Les références

[1] Algorithmes génétiques pratiques avec Python, Eyal Wirsansky

Merci!

Les médias présentés dans cet article ne sont pas la propriété de DataPeaker et sont utilisés à la discrétion de l'auteur.

Abonnez-vous à notre newsletter

Nous ne vous enverrons pas de courrier SPAM. Nous le détestons autant que vous.