<jupyter_start><jupyter_text>A simple implementation of genetic algorithms in Python From [here](https://www.kdnuggets.com/2018/07/genetic-algorithm-implementation-python.html),<jupyter_code>import numpy as np
import pandas as pd
from itertools import product
import matplotlib.pyplot as plt
%matplotlib inline<jupyter_output><empty_output><jupyter_text>Parametrisation<jupyter_code>w = [4,-2,3.5,5,-11,-4.7] 
m = len(w) # number of features
n = 100 # population size
p = 15 # mating poopulation size

## Mutation: rate (probability of mutation at a location) and range (scale of mutation when it happens)
mutation_rate = 0.01
mutation_range = (-0.001,0.001)

n_generations = 500

## weights for the problem

pop_shape = [n,m]
pop_range = (-0.004,0.004)<jupyter_output><empty_output><jupyter_text>_Testing_: Parent population size must be sufficiently large. See explanations below<jupyter_code>assert p**2 >= n, 'p is too small for this setup, please choose a value of at least %r' % (int(np.ceil(np.sqrt(n))))<jupyter_output><empty_output><jupyter_text>A single iteration, annotated  PopulationWe start by sampling our initial "population" of weight vectors, based on the weights and ranges we defined before:<jupyter_code>new_population = \
np.random.uniform(
    low =  1.0 * min(pop_range), 
    high = 1.0 * max(pop_range), 
    size = pop_shape
)<jupyter_output><empty_output><jupyter_text>We expect to see a uniform distribution of the weights (shown here as a single long vector)<jupyter_code>pd.Series(new_population.flatten()).plot(kind = 'hist')<jupyter_output><empty_output><jupyter_text>Fitness In order to select the best parents for breeding, we have to introduce the concept of _fitness_. In biology this would be a measure (or measures) of how well do the parents fit their environments. In our case we simply want to choose the parents the perform best against our pre-defined set of weights $w$. We want to make sure that fitness is bounded (from both ends) so we use the logistic function:$$ \text{fitness}(x_i) = logit(x_i^T w) = \frac{1}{1 + exp(- x_i^T w)} $$<jupyter_code>def fitness_calc(w, pop):
    return 1 / (1 + np.exp(-1 * np.sum(pop * w, axis = 1)))<jupyter_output><empty_output><jupyter_text>And for our initial sample we can calculate the fitness score of each individual<jupyter_code>fitness = fitness_calc(w, new_population)
pd.Series(fitness).plot(kind = 'hist')<jupyter_output><empty_output><jupyter_text>ParentsAnd pick the `p` rows in our current population with the highest fitness for mating (we call them "parents"):<jupyter_code>parents = new_population[(-1*fitness).argsort(), :][range(p),:]<jupyter_output><empty_output><jupyter_text>We look at all possible pairs (excluding matching a single parent with themselves)<jupyter_code>potential_parent_pairs = np.asarray(list(product(range(p),range(p))))

potential_parent_pairs = \
potential_parent_pairs[
    np.apply_along_axis(
        func1d = lambda x: x[0] != x[1],  # only if parents are different
        axis = 1, 
        arr = potential_parent_pairs
    ),
    :
]<jupyter_output><empty_output><jupyter_text>We pick "randomly" pick `n-p` pairs of parents (seed is set here for reproducibility). _Note:_ We make an assumption here that the number of potential parent pairs $p(p-1)$ is greater or equal to the number of offsprings we need to create to re-populate the next generation (which is $n-p$, assuming we only keep the parents and some of their offsprings) so we are in fact assuming that $p^2 \geq n$ (see the `assert` clause at the beginning of the code)<jupyter_code>np.random.seed(seed=12345)
rand_index = np.random.choice(potential_parent_pairs.shape[0], n-p, replace=False) 
parent_pairs_ind = potential_parent_pairs[rand_index,:]<jupyter_output><empty_output><jupyter_text>Mating And we pair the selected parents by "splicing" their weights and adding children to the new population<jupyter_code>crossover_point = int(np.floor(m/2))
new_population = parents

for i,j in parent_pairs_ind:
    #print('this part', parents[i, 0:crossover_point])
    #print('with this part', parents[j, crossover_point:])
    #print('makes:', np.concatenate((parents[i, 0:crossover_point], parents[j, crossover_point:])))
    new_population = \
    np.vstack((
        new_population, 
        np.concatenate((parents[i, 0:crossover_point], parents[j, crossover_point:]))
    ))<jupyter_output><empty_output><jupyter_text>MutationAnd finally let's introduce some mutation: with probability `mutation_rate` we add a random fluctuation to the weight:<jupyter_code>#np.random.seed(seed=12345)
mutation_places = \
np.random.binomial(
    n = 1, 
    p = mutation_rate, 
    size = new_population.shape[0] * new_population.shape[1]
)

mutation_values = \
np.random.uniform(
    high = max(mutation_range), 
    low = min(mutation_range), 
    size = new_population.shape[0] * new_population.shape[1]
)
new_population = new_population + np.reshape(mutation_values * mutation_places, newshape = new_population.shape)<jupyter_output><empty_output><jupyter_text>Re-evaluationWe can now re-evaluate if the new population has better candidates<jupyter_code>fitness = fitness_calc(w, new_population)
pd.Series(fitness).plot(kind = 'hist')<jupyter_output><empty_output><jupyter_text>Let's iterate! We can create a simple `for` loop, but since we want to explore different mutation rates we'll wrap it in a function:<jupyter_code>def fitness_calc(w, pop):
    return 1 / (1 + np.exp(-1 * np.sum(w * pop, axis = 1)))
    
def genetic_iter(pop, w, mutation_rate = 0.01, n_generations = 20, p  = 20):
    
    ## Collect best relust from each iteration
    fitness_tracking = [np.max(fitness_calc(w, pop))]  
    #print('starting from', fitness_tracking)
    
    for g in range(n_generations):
        fitness = fitness_calc(w, pop) 
        #print(pd.Series(fitness).describe())

        ## Select parents
        parents = pop[(-1*fitness).argsort(), :][range(p),:]
        #print('parents', parents)

        ## Choose parent pairs
        potential_parent_pairs = np.asarray(list(product(range(p),range(p))))

        potential_parent_pairs = \
        potential_parent_pairs[
            np.apply_along_axis(
                func1d = lambda x: x[0] != x[1],  # only if parents are different
                axis = 1, 
                arr = potential_parent_pairs
            ),
            :
        ]

        rand_index = np.random.choice(potential_parent_pairs.shape[0], pop.shape[0]-p, replace=False) 
        parent_pairs_ind = potential_parent_pairs[rand_index,:]

        ## Mate parents
        crossover_point = int(np.floor(pop.shape[1]/2))
        pop = parents

        for i,j in parent_pairs_ind:
            #print('this part', parents[i, 0:crossover_point])
            #print('with this part', parents[j, crossover_point:])
            #print('makes:', np.concatenate((parents[i, 0:crossover_point], parents[j, crossover_point:])))
            pop = \
            np.vstack((
                pop, 
                np.concatenate((parents[i, 0:crossover_point], parents[j, crossover_point:]))
            ))

        ## Mutation
        mutation_places = np.random.binomial(
            n = 1, 
            p = mutation_rate, 
            size = pop.shape[0] * pop.shape[1]
        )

        mutation_values = np.random.uniform(
            high = max(mutation_range)+1, 
            low = min(mutation_range), 
            size = pop.shape[0] * pop.shape[1]
        )

        pop = pop + np.reshape(mutation_values * mutation_places, newshape = pop.shape)
        
        fitness_tracking.append(np.max(fitness_calc(w, pop)))
        
    return fitness_tracking<jupyter_output><empty_output><jupyter_text>We reset the population to have a fresh start and run our function:<jupyter_code>new_population = np.random.uniform(low=min(pop_range), high=max(pop_range), size=pop_shape)<jupyter_output><empty_output><jupyter_text>And explore different rates of mutation<jupyter_code>def plot_mutation_rate_progress(mr):
    return pd.Series(
        genetic_iter(
            pop = new_population, 
            w = w, 
            mutation_rate = mr, 
            p = p
        )
    ).plot(kind = 'line')
plt.subplot(3,1,1)
plot_mutation_rate_progress(0.001)
plt.subplot(3,1,2)
plot_mutation_rate_progress(0.01)
plt.subplot(3,1,3)
plot_mutation_rate_progress(0.1)<jupyter_output><empty_output><jupyter_text>Or the effect of the number of parents<jupyter_code>def plot_parent_progress(p):
    return pd.Series(
        genetic_iter(
            pop = new_population, 
            w = w, 
            mutation_rate = 0.01, 
            p = p
        )
    ).plot(kind = 'line')
plt.subplot(3,1,1)
plot_parent_progress(10)
plt.subplot(3,1,2)
plot_parent_progress(11)
plt.subplot(3,1,3)
plot_parent_progress(12)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11226799456767768, 'fraction_numerical': 0.01641014033499321, 'mean_word_length': 3.906718489727929, 'pattern_counts': {'":': 0, '<': 69, '<?xml version=': 0, '>': 70, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '17', 'dir': 'jupyter-structured-clean-dedup', 'id': '417307', 'license': 'Apache-2.0', 'n_tokens_mistral': 3073, 'n_tokens_neox': 2864, 'n_words': 717, 'path': 'genetic-algorithms/example01_basic_stuff.ipynb', 'repo_name': 'ytoren/reproduce', 'size': '8836'}