Genetic Algorithm Operators in Python

Genetic Algorithm Implementation Functions

The following Python functions demonstrate key components of Genetic Algorithms, including crossover, selection, and population initialization.

Four-Point Crossover Method

This function performs a four-point crossover using four parents to generate offspring.

def four_point_cross(parent1, parent2, parent3, parent4):
    pos_alea = sorted(list(np.random.choice(range(1, parent1), 4, replace=False)))
    hijo1 = parent1[:pos_alea[0]] + parent2[pos_alea[0]:pos_alea[1]], parent1[:pos_alea[1:2]], parent2[pos_alea[2]:pos_alea[3]], parent1[:pos_alea[3:]]
    hijo2 = parent2[:pos_alea[0]] + parent3[pos_alea[0]:pos_alea[1]], parent2[:pos_alea[1:2]], parent3[pos_alea[2]:pos_alea[3]], parent2[:pos_alea[3:]]
    hijo3 = parent3[:pos_alea[0]] + parent4[pos_alea[0]:pos_alea[1]], parent3[:pos_alea[1:2]], parent4[pos_alea[2]:pos_alea[3]], parent3[:pos_alea[3:]]
    hijo4 = parent4[:pos_alea[0]] + parent1[pos_alea[0]:pos_alea[1]], parent4[:pos_alea[1:2]], parent1[pos_alea[2]:pos_alea[3]], parent4[:pos_alea[3:]]
    return [hijo1, hijo2, hijo3, hijo4]

Selection Strategies

Roulette Wheel Selection

Implements Roulette Wheel Selection based on fitness probability distribution.

def roulette_wheel_selection(ranked_population, ranked_fitness):
    probabilidad = [ranked_fitness[i] / sum(ranked_fitness) for i in range(len(ranked_fitness))]
    distribu_prop = list(np.cumsum(probabilidad))
    alpha = random.random()
    seleccion = np.argmin([alpha > distribu_prop[i] for i in range(len(distribu_prop))])
    return distribu_prop[seleccion]

Rank Selection

This method utilizes Rank Selection to choose individuals from the population.

def rank_selection(ranked_population, ranked_fitness):
    division = np.cumsum(range(len(ranked_population) + 1))[-1]
    asignacion_tickets = sorted([x for x in range(1, len(ranked_population) + 1)], reverse=True)
    probabilidades = [x / division for x in asignacion_tickets]
    return ranked_population[np.random.choice(range(len(ranked_population)), p=probabilidades)]

Tournament Selection

A Tournament Selection approach that selects parents based on a specified percentile.

def tournament_selection(population, population_fitness, percentile=10):
    tournament_size = int(len(population) * percentile / 100)
    pos = random.sample(len(population[0]), tournament_size)
    padres = []
    fitness = []
    for i in pos:
        ind = population[i]
        padres.append(ind)
        ind_fit = population_fitness[i]
        fitness.append(ind_fit)
    padres_r = rank_population(padres, fitness)
    return padres_r

Population Initialization

Individual Creation

Generates a single individual with specific constraints regarding multiples of five.

def create_individual(size=50):
    multiplos = [x for x in range(size) if (x % 5 == 0) & (x != 0)]
    lista_numeros_no_multiplos = [x for x in range(size) if (x % 5 != 0) | (x == 0)]
    posicion = np.random.choice(range(size))
    lista = list(np.random.choice(lista_numeros_no_multiplos, len(lista_numeros_no_multiplos), replace=False))
    return lista[:posicion] + multiplos + lista[posicion:]

Population Generation

Creates a full population of individuals for the genetic algorithm.

def create_population(population_size, size):
    return [create_individual(size) for x in range(population_size)]