¿Cómo funciona la selección por torneo en un algoritmo genético?

Se toman k individuos de la población al azar y se selecciona el mejor según la función de fitness. La función selecciona_torneo repite este proceso n veces para obtener n individuos.

¿Qué hace la función de mutación en el código?

La función muta recorre cada gen del cromosoma y, con probabilidad prob, lo reemplaza por un valor elegido al azar entre los genes posibles. Trabaja sobre una copia para no modificar el original.

Algoritmos Genéticos en Python: Cruza, Mutación, Torneo y Mochila

Resumen

El documento presenta ejemplos prácticos de implementación en Python de los componentes básicos de un algoritmo genético: población inicial, cruza, mutación y selección por torneo. Incluye también la construcción de una nueva generación y la modelización del problema de la mochila como problema genético, con ejemplos de aplicación a varias instancias.

Puntos clave

La población inicial se genera eligiendo aleatoriamente genes de un conjunto de valores posibles para cada posición del cromosoma.
La cruza de un punto intercambia los segmentos de dos cromosomas padres a partir de una posición aleatoria para producir dos hijos.
La mutación cambia cada gen de un cromosoma por otro elegido al azar con una probabilidad dada.
La selección por torneo elige, de k individuos tomados al azar, el de mejor fitness.
En el problema de la mochila, la función de decodificación añade objetos en orden mientras no se supere el peso máximo, y el fitness es la suma de los valores de los objetos incluidos.

Ponte a prueba

Algoritmos Genéticos en Python: Ejemplos Prácticos

A continuación se presentan varios ejemplos de implementación de los componentes fundamentales de un algoritmo genético en Python, incluyendo la generación de la población inicial, la cruza, la mutación, la selección por torneo y la resolución del problema de la mochila.

Ej1: Población inicial, cruza y mutación

def poblacion_inicial(self, N):
    return [[random.choice(self.genes) for _ in range(self.longitud_cromosoma)]
            for _ in range(N)]

def cruza(self, c1, c2):
    pos = random.randrange(1, self.longitud_cromosoma)
    hijo1 = c1[:pos] + c2[pos:]
    hijo2 = c2[:pos] + c1[pos:]
    return [hijo1, hijo2]

def cruza_padres(self, padres):
    hijos = []
    for j in range(0, len(padres), 2):
        hijos.extend(self.cruza(padres[j], padres[j+1]))
    return hijos

def muta(self, cr, prob):
    cm = cr[:]  # una copia
    for i in range(len(cr)):
        if random.random() < prob:
            cm[i] = random.choice(self.genes)
    return cm

def muta_cromosomas(self, poblacion, prob):
    return [self.muta(cr, prob) for cr in poblacion]

Ej2: Selección por torneo

def torneo(self, poblacion, k, mejor):
    participantes = random.sample(poblacion, k)
    return mejor(participantes, key=self.fitness)

def selecciona_torneo(self, poblacion, k, mejor, n):
    return [self.torneo(poblacion, k, mejor) for _ in range(n)]

Ej3: Creación del problema genético

cuad_gen = Problema_Genetico(
    genes=[0, 1],
    longitud_cromosoma=10,
    decodifica=binario_a_decimal,
    fitness=lambda cr: binario_a_decimal(cr) ** 2
)

Ej4: Nueva generación (versión 1)

def nueva_generacion_v1(problema_genetico, poblacion, n_padres, n_directos, prob_mutar, mejor, k_torneo):
    padres_para_cruzar = problema_genetico.selecciona_torneo(poblacion, k_torneo, mejor, n_padres)
    padres_directos = problema_genetico.selecciona_torneo(poblacion, k_torneo, mejor, n_directos)
    hijos = problema_genetico.cruza_padres(padres_para_cruzar)
    hijos_mutados = problema_genetico.muta_cromosomas(hijos, prob_mutar)
    directos_mutados = problema_genetico.muta_cromosomas(padres_directos, prob_mutar)
    return hijos_mutados + directos_mutados

Ej5: Problema de la mochila

def problema_mochila(pesos, valores, peso_max):
    n = len(pesos)

    def decodifica_mochila(cromosoma):
        fenotipo = []
        peso_acumulado = 0
        parar = False
        for gen, peso in zip(cromosoma, pesos):
            if parar:
                fenotipo.append(0)
            elif gen == 1 and peso_acumulado + peso <= peso_max:
                fenotipo.append(1)
                peso_acumulado += peso
            elif gen == 1:
                fenotipo.append(0)
                parar = True
            else:
                fenotipo.append(0)
        return fenotipo

    def fitness_mochila(cromosoma):
        fenotipo = decodifica_mochila(cromosoma)
        return sum(gen * valor for gen, valor in zip(fenotipo, valores))

    return Problema_Genetico([0, 1], n, decodifica_mochila, fitness_mochila)

Ej6: Aplicación al problema de la mochila

Continuación del código del Ej6:

mochila1_gen = problema_mochila(pesos1, valores1, 165)
mochila2_gen = problema_mochila(pesos2, valores2, 750)
mochila3_gen = problema_mochila(pesos3, valores3, 6404180)

# Mochila 1 (pequeña)
solucion1, valor1 = algoritmo_genetico_v1(mochila1_gen, 150, 100, 0.7, 0.1, max, 3)
print("\nSolucion mochila 1:", solucion1, "- Valor:", valor1, "- Optimo: 309")

# Mochila 2 (mediana)
solucion2, valor2 = algoritmo_genetico_v1(mochila2_gen, 300, 200, 0.7, 0.1, max, 3)
print("\nSolucion mochila 2:", solucion2, "- Valor:", valor2, "- Optimo: 1458")