Aprende Selección, Cruce y Mutación

Estrategias de selección

La selección es un proceso crucial en los algoritmos genéticos, determina qué individuos contribuyen a la siguiente generación, equilibrando aptitud y diversidad. Existen varias estrategias de selección ampliamente utilizadas:

Selección por ruleta: Asigna una probabilidad de selección a cada individuo proporcional a su aptitud. Imagine una ruleta donde el tamaño de cada segmento corresponde a la aptitud; los individuos con mayor aptitud tienen una mayor probabilidad de ser seleccionados;
Selección por torneo: Selecciona aleatoriamente un grupo (torneo) de individuos y elige al mejor entre ellos como progenitor. Este método es simple y efectivo, y el tamaño del torneo puede controlar la presión de selección;
Selección basada en ranking: Ordena a los individuos por aptitud y asigna probabilidades de selección en función de su posición en el ranking en lugar de su aptitud absoluta. Esto ayuda a evitar la dominación por unos pocos individuos de alta aptitud, especialmente en problemas con grandes diferencias de aptitud.


              1234567891011121314151617
            
import random

def tournament_selection(population, fitnesses, tournament_size=3):
    """
    Selects one individual from the population using tournament selection.
    """
    # Randomly pick tournament_size individuals
    selected_indices = random.sample(range(len(population)), tournament_size)
    # Find the one with the highest fitness
    best_index = max(selected_indices, key=lambda idx: fitnesses[idx])
    return population[best_index]

# Example usage
population = [[0,1,1,0], [1,0,0,1], [1,1,0,0], [0,0,1,1]]
fitnesses = [3, 2, 5, 4]
parent = tournament_selection(population, fitnesses, tournament_size=2)
print("Selected parent:", parent)

Operadores de cruce

Después de la selección, los algoritmos genéticos utilizan el cruce para crear nuevos individuos combinando información de dos progenitores. El cruce introduce variación y permite que el algoritmo explore nuevas combinaciones de características dentro de la población.

Tipos comunes de cruce:

Cruce de un punto: Se elige aleatoriamente un punto de cruce. La primera parte de un progenitor se combina con la parte restante del otro.
Cruce de dos puntos: Se seleccionan aleatoriamente dos puntos. El segmento entre ellos se intercambia entre los progenitores para producir descendencia.
Cruce uniforme: Cada gen de la descendencia se elige aleatoriamente de uno de los dos progenitores con igual probabilidad.


              12345678910111213141516171819
            
import random

def single_point_crossover(parent1, parent2):
    """
    Performs single-point crossover between two parents.
    """
    if len(parent1) != len(parent2):
        raise ValueError("Parents must be of the same length")
    point = random.randint(1, len(parent1) - 1)
    child1 = parent1[:point] + parent2[point:]
    child2 = parent2[:point] + parent1[point:]
    return child1, child2

# Example usage
p1 = [1, 0, 1, 0, 1]
p2 = [0, 1, 0, 1, 0]
offspring1, offspring2 = single_point_crossover(p1, p2)
print("Offspring 1:", offspring1)
print("Offspring 2:", offspring2)

Papel de la Mutación

La mutación es uno de los mecanismos clave en los algoritmos genéticos. Introduce nuevo material genético en la población, ayudando al algoritmo a evitar el estancamiento y continuar explorando nuevas soluciones. Sin mutación, la población puede volverse demasiado similar, lo que provoca que la búsqueda se estanque en óptimos locales.

Por qué la Mutación es Importante

Prevención de convergencia prematura: la mutación asegura que la población no se vuelva demasiado uniforme, evitando una convergencia subóptima;
Mantenimiento de la diversidad: al introducir alteraciones aleatorias, la mutación mantiene una amplia gama de variación genética disponible para generaciones futuras;
Permite escapar de óptimos locales: pequeños cambios aleatorios permiten que el algoritmo explore nuevas áreas del espacio de búsqueda que podrían conducir a mejores soluciones;
Equilibrio con el cruce: mientras que el cruce combina rasgos existentes, la mutación introduce nuevos, asegurando que el algoritmo siga generando posibilidades novedosas.

En conjunto, estas propiedades hacen que la mutación sea esencial para un proceso de búsqueda robusto y adaptativo.

Operadores de Mutación Comunes

Diferentes representaciones de problemas requieren distintas técnicas de mutación. Los dos operadores más utilizados son:

Mutación por cambio de bit: para representaciones binarias — cambia un bit de 0 a 1 o de 1 a 0, introduciendo cambios pequeños y controlados;
Mutación por intercambio: para representaciones basadas en permutaciones (por ejemplo, problemas de ordenamiento) — intercambia dos elementos dentro de un individuo para generar una nueva configuración.


              1234567891011121314151617181920
            
import random

def bit_flip_mutation(individual, mutation_rate=0.1):
    """
    Performs bit-flip mutation on a binary list.
    """
    mutated = []
    for gene in individual:
        if random.random() < mutation_rate:
            mutated.append(1 - gene)  # Flip bit
        else:
            mutated.append(gene)
    return mutated

# Example usage
original = [1, 0, 1, 1, 0]
mutated = bit_flip_mutation(original, mutation_rate=0.5)
print("Original:", original)
print("Mutated:", mutated)

¿Todo estuvo claro?

¡Gracias por tus comentarios!

Sección 2. Capítulo 2

Pregunte a AI

Pregunte lo que quiera o pruebe una de las preguntas sugeridas para comenzar nuestra charla

Awesome!

Completion rate improved to 6.25

Desliza para mostrar el menú