Learning: implementation of genetic algorithm and python deap package genetic algorithm

1, Genetic algorithm

An optimal solution search algorithm is designed based on the concept of species genetics in nature. Genetic algorithm takes all individuals in a species as objects, and uses randomization technology to search an encoded parameter space efficiently. Among them, selection, crossover and mutation constitute the genetic operation of genetic algorithm; Parameter coding, initial population setting, fitness function design, genetic operation design and control parameter setting constitute the core content of genetic algorithm.

An easy to understand example of genetic algorithm, the author explains genetic algorithm with knapsack problem. Simple examples to understand genetic algorithm

Algorithm pseudocode:

        i = 0;           //Evolutionary population algebra
        Initialize P(i);    //Initialize population 
        Fitness P(i);     //Calculate appropriate value
        While(not Terminate-Condition) //When the termination conditions are not met, the loop
            i ++;              //loop
            GA-Operation P(i);  //Crossover and mutation operation
            Fitness P(i);        //Calculate appropriate value
 END  //End algorithm

Description of algorithm steps:
Initialization: population size P, genetic algebra N, crossover probability pc, mutation probability pm, count variable i=0;
(1) Generate the initial population.
(2) The suitable value of each chromosome in the initial population was calculated.
(3) i=i+1; If I < = n, generate a gambling wheel and turn to step 4; Otherwise, go to step 9.
(4) The number of chromosomes in the gene pool is the population size P.
(5) The crossover operation is performed according to the crossover probability pc, and the gene pool without crossover operation is directly copied to the next generation.
(6) The mutation operation is carried out according to the mutation probability pm.
(7) The suitable value of each chromosome in the offspring population was calculated.
(8) The offspring population replaces the parent population, and go to step 3.
(9) The network delay, error rate and network cost of the number of routes corresponding to each chromosome in the population are calculated. According to the suitable value, the chromosome with the smallest suitable value is the obtained solution.

2, deap

Github link for deap

1.deap function

Various genetic algorithms
Genetic programming
Evolutionary strategy
Multi objective optimization
Cooperation and competition among multiple groups
Parallel computing
Set checkpoints during calculation
Set the benchmark module to test the algorithm capability
Support particle swarm optimization algorithm, differential evolution algorithm, etc

2.deap example

The code is as follows (example): give an example and explanation of deap

import random
from deap import creator, base, tools, algorithms

creator.create("FitnessMax", base.Fitness, weights=(1.0,))//Optimization objectives
creator.create("Individual", list, fitness=creator.FitnessMax)//Individual generation

toolbox = base.Toolbox()//Toolbox: register parameter information: crossover, mutation, reserved individual, evaluation function

toolbox.register("attr_bool", random.randint, 0, 1)//Individual coding method
toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_bool, n=100)//Individual coding
toolbox.register("population", tools.initRepeat, list, toolbox.individual)//Create initial population

def evalOneMax(individual):
    return sum(individual),

toolbox.register("evaluate", evalOneMax)//Evaluation setting
toolbox.register("mate", tools.cxTwoPoint)//Individual crossover
toolbox.register("mutate", tools.mutFlipBit, indpb=0.05)//Individual compilation
toolbox.register("select", tools.selTournament, tournsize=3)//Select a new generation of population

population = toolbox.population(n=300)//Initial group

NGEN=40//Genetic search
for gen in range(NGEN):
    offspring = algorithms.varAnd(population, toolbox, cxpb=0.5, mutpb=0.1)
    fits = toolbox.map(toolbox.evaluate, offspring)
    for fit, ind in zip(fits, offspring):
        ind.fitness.values = fit
    population = toolbox.select(offspring, k=len(population))
top10 = tools.selBest(population, k=10)

A detailed explanation example of the use of deap

Python evolutionary algorithm based on DEAP library from entry to penetration – (I) basic operation and implementation of evolutionary algorithm


This paper is a learning record of how to use deap to use genetic algorithm. Genetic algorithm needs to be used in project practice, so I study.

Reference link

[1]: Python evolutionary algorithm based on DEAP library from entry to penetration – (I) basic operation and implementation of evolutionary algorithm
[2]: Github documentation for Deap
[3]: Simple examples to understand genetic algorithm

Keywords: Python Algorithm Machine Learning

Added by adammc on Fri, 19 Nov 2021 08:00:02 +0200