Ejemplos Adicionales

La librería PySAG-UdeC incluye varios ejemplos para demostrar su uso en diferentes problemas.

Problema de la Mochila Binaria

Este ejemplo muestra cómo resolver el problema de la mochila 0/1.

examples/example_knapsack_binary.py
  1"""
  2Ejemplo de Algoritmo Genético para resolver el Problema de la Mochila Binaria (0/1).
  3
  4Objetivo: Maximizar el valor total de los ítems en la mochila sin exceder
  5          su capacidad máxima de peso.
  6Cada gen representa un ítem: 1 si se toma, 0 si no.
  7
  8El algoritmo genético se ejecutará por 200 generaciones
  9y el mejor fitness debe aproximarse a 490.
 10"""
 11
 12import sys
 13
 14import numpy as np
 15
 16try:
 17    from PySAG import GA, crossover, initialization, mutation, selection
 18except ImportError:
 19    print("Error: No se pudo importar la librería PySAG.")
 20    print("Asegúrate de que esté instalada o que la ruta a 'src' esté en PYTHONPATH.")
 21    sys.exit(1)
 22
 23# 1. Definición del Problema de la Mochila
 24# Ítems: (valor, peso)
 25items_data = {
 26    "item1": (60, 10),
 27    "item2": (100, 20),
 28    "item3": (120, 30),
 29    "item4": (80, 15),
 30    "item5": (90, 25),
 31    "item6": (70, 12),
 32    "item7": (110, 22),
 33    "item8": (50, 8),
 34    "item9": (130, 35),
 35    "item10": (75, 18),
 36}
 37item_names = list(items_data.keys())
 38item_values = np.array([items_data[name][0] for name in item_names])
 39item_weights = np.array([items_data[name][1] for name in item_names])
 40
 41KNAPSACK_CAPACITY = 100  # Capacidad máxima de peso de la mochila
 42NUM_ITEMS = len(item_names)  # Número de genes, uno por ítem
 43
 44
 45def fitness_function_knapsack(individual: np.ndarray) -> float:
 46    """
 47    Función de fitness para el problema de la mochila binaria.
 48
 49    Calcula el fitness de una solución para el problema de la mochila.
 50    El individuo es un array binario (0 o 1).
 51
 52    Args:
 53        individual: Individuo representado como un array NumPy binario.
 54
 55    Returns:
 56        float: Fitness de la solución.
 57    """
 58    if len(individual) != NUM_ITEMS:
 59        raise ValueError(f"El individuo debe tener {NUM_ITEMS} genes (ítems).")
 60    if not np.all(np.logical_or(individual == 0, individual == 1)):
 61        # Penalizar fuertemente si no es binario,
 62        # aunque la inicialización/mutación deberían manejarlo
 63        # print(f"Advertencia: Individuo no binario encontrado: {individual}")
 64        return -10000  # Penalización muy alta
 65
 66    total_value = np.sum(individual * item_values)
 67    total_weight = np.sum(individual * item_weights)
 68
 69    # Penalización si se excede la capacidad de la mochila
 70    if total_weight > KNAPSACK_CAPACITY:
 71        # Penalización proporcional al exceso de peso
 72        # Cuanto más se exceda, peor es el fitness.
 73        # Alternativamente, se puede devolver 0 o un valor muy bajo.
 74        penalty = (total_weight - KNAPSACK_CAPACITY) * 10  # Factor de penalización
 75        return max(
 76            0, total_value - penalty
 77        )  # Asegurar que el fitness no sea negativo con esta penalización
 78        # return 0 # Opción más simple: inválido si excede
 79    else:
 80        return total_value
 81
 82
 83# 2. Configurar y Instanciar la clase GA
 84population_size = 80
 85num_generations = 200
 86num_parents_mating = 15
 87crossover_prob = 0.9
 88elitism_percentage = 0.15
 89mutation_rate_bit_flip = 0.02  # Tasa de mutación por gen para bit-flip
 90
 91print("Configurando el Algoritmo Genético para el Problema de la Mochila Binaria...")
 92
 93ga_instance_knapsack = GA(
 94    fitness_func=fitness_function_knapsack,
 95    num_genes=NUM_ITEMS,
 96    population_size=population_size,
 97    num_generations=num_generations,
 98    num_parents_mating=num_parents_mating,
 99    # Inicialización: Binaria, ya que cada gen es 0 o 1
100    initial_population_func=initialization.init_random_binary,
101    initial_pop_args={},  # No necesita argumentos extra
102    # Selección: Por Rango (Rank Selection)
103    selection_func=selection.selection_rank,
104    selection_args={},  # No necesita argumentos extra
105    # Cruce: De dos puntos (Two-Point Crossover)
106    crossover_func=crossover.crossover_two_points,
107    crossover_args={},  # No necesita argumentos extra
108    crossover_probability=crossover_prob,
109    # Mutación: Bit Flip (adecuada para representaciones binarias)
110    mutation_func=mutation.mutation_bit_flip,
111    mutation_args={"mutation_rate": mutation_rate_bit_flip},
112    keep_elitism_percentage=elitism_percentage,
113    random_seed=123,  # Para reproducibilidad
114)
115
116# 3. Ejecutar el AG
117print("Ejecutando el Algoritmo Genético...")
118best_solution, best_fitness = ga_instance_knapsack.run()
119
120# 4. Mostrar Resultados
121if best_solution is not None:
122    print(f"\nMejor solución (selección de ítems): {best_solution.astype(int)}")
123    selected_items_indices = np.where(best_solution == 1)[0]
124    selected_item_names = [item_names[i] for i in selected_items_indices]
125
126    str_items = "Ítems seleccionados: "
127    str_items += f"{selected_item_names if selected_item_names else 'Ninguno'}"
128    print(str_items)
129
130    final_value = np.sum(best_solution * item_values)
131    final_weight = np.sum(best_solution * item_weights)
132    print(f"Valor total en la mochila: {final_value}")
133    print(f"Peso total en la mochila: {final_weight} (Capacidad: {KNAPSACK_CAPACITY})")
134
135    if final_weight > KNAPSACK_CAPACITY:
136        str_adv = "¡Advertencia! La solución excede la capacidad de la mochila"
137        str_adv += f"Fitness: {best_fitness}"
138        print(str_adv)
139    else:
140        print(f"Fitness de la mejor solución: {best_fitness:.2f}")
141
142    ga_instance_knapsack.plot_fitness(save_path="knapsack_binary_fitness.png")
143else:
144    print("No se encontró una solución.")
145
146print("\nEjemplo del Problema de la Mochila Binaria completado.")

Coincidencia de Cadenas

Este ejemplo intenta evolucionar una cadena de caracteres para que coincida con una cadena objetivo.

examples/example_string_coincidence.py
  1"""
  2Ejemplo de Algoritmo Genético.
  3
  4Objetivo: Maximizar el número de caracteres coincidentes con la cadena objetivo.
  5El algoritmo genético se ejecutará por 500 generaciones
  6y el mejor fitness debe aproximarse a la longitud de la cadena objetivo.
  7"""
  8
  9import string
 10
 11import numpy as np
 12
 13from PySAG import GA, crossover, initialization, mutation, selection
 14
 15# 1. Definición del Problema: Coincidencia de Cadenas
 16TARGET_STRING = "HelloPySAG"
 17ALLOWED_CHARACTERS = (
 18    string.ascii_letters + string.digits + " _"
 19)  # Caracteres permitidos
 20# Mapeo de caracteres a enteros y viceversa
 21CHAR_TO_INT = {char: i for i, char in enumerate(ALLOWED_CHARACTERS)}
 22INT_TO_CHAR = {i: char for i, char in enumerate(ALLOWED_CHARACTERS)}
 23NUM_POSSIBLE_GENE_VALUES = len(ALLOWED_CHARACTERS)
 24
 25NUM_GENES = len(
 26    TARGET_STRING
 27)  # La longitud del cromosoma es la longitud de la cadena objetivo
 28
 29
 30def individual_to_string(individual: np.ndarray) -> str:
 31    """Convierte un individuo (array de ints) a una cadena de caracteres."""
 32    return "".join(
 33        [
 34            INT_TO_CHAR.get(int(gene_val % NUM_POSSIBLE_GENE_VALUES), "?")
 35            for gene_val in individual
 36        ]
 37    )
 38
 39
 40def fitness_function_string_match(individual: np.ndarray) -> float:
 41    """
 42    Función de fitness para el problema de coincidencia de cadenas.
 43
 44    Args:
 45        individual: Individuo representado como un array NumPy de enteros.
 46
 47    Returns:
 48        float: Fitness de la solución.
 49    """
 50    if len(individual) != NUM_GENES:
 51        raise ValueError(f"El individuo debe tener {NUM_GENES} genes.")
 52
 53    proposed_string = individual_to_string(individual)
 54
 55    matches = 0
 56    for i in range(NUM_GENES):
 57        if proposed_string[i] == TARGET_STRING[i]:
 58            matches += 1
 59    return float(matches)
 60
 61
 62# 2. Configurar y Instanciar la clase GA
 63population_size = 200  # Población más grande
 64num_generations = 500  # Más generaciones para un problema potencialmente más difícil
 65num_parents_mating = 40
 66crossover_prob = 0.7  # Probabilidad de cruce más baja
 67elitism_percentage = 0.02  # Elitismo muy bajo
 68mutation_rate_per_gene = 0.05  # Tasa de mutación por gen
 69
 70print(f"Configurando el Algoritmo Genético para encontrar la cadena: '{TARGET_STRING}'")
 71print(
 72    f"Caracteres permitidos: '{ALLOWED_CHARACTERS}' (Total: {NUM_POSSIBLE_GENE_VALUES})"
 73)
 74
 75ga_instance_string = GA(
 76    fitness_func=fitness_function_string_match,
 77    num_genes=NUM_GENES,
 78    population_size=population_size,
 79    num_generations=num_generations,
 80    num_parents_mating=num_parents_mating,
 81    initial_population_func=initialization.init_random_uniform,
 82    initial_pop_args={
 83        "low": 0,
 84        "high": NUM_POSSIBLE_GENE_VALUES - 1,
 85        "dtype": np.int_,
 86    },
 87    selection_func=selection.selection_random,
 88    selection_args={},
 89    crossover_func=crossover.crossover_single_point,
 90    crossover_args={},
 91    crossover_probability=crossover_prob,
 92    mutation_func=mutation.mutation_random_gene_uniform,
 93    mutation_args={
 94        "gene_low": 0,
 95        "gene_high": NUM_POSSIBLE_GENE_VALUES - 1,
 96        "mutation_rate": mutation_rate_per_gene,
 97        # El dtype del individuo se respetará por la función de mutación
 98    },
 99    keep_elitism_percentage=elitism_percentage,
100    random_seed=777,  # Para reproducibilidad
101)
102
103# 3. Ejecutar el AG
104print("Ejecutando el Algoritmo Genético...")
105best_solution_indices, best_fitness = ga_instance_string.run()
106
107# 4. Mostrar Resultados
108if best_solution_indices is not None:
109    best_string_found = individual_to_string(best_solution_indices)
110    print(f"\nMejor cadena encontrada: '{best_string_found}'")
111    print(f"Fitness (caracteres coincidentes): {int(best_fitness)} de {NUM_GENES}")
112
113    if best_string_found == TARGET_STRING:
114        print("¡Éxito! La cadena objetivo fue encontrada.")
115    else:
116        str_info = "La cadena objetivo no fue encontrada perfectamente,"
117        str_info += " pero esta fue la mejor aproximación."
118        print(str_info)
119
120    ga_instance_string.plot_fitness(save_path="string_matching_fitness.png")
121else:
122    print("No se encontró una solución.")
123
124print("\nEjemplo de coincidencia de cadenas completado.")