Este proyecto implementa algoritmos de optimización metaheurísticos para resolver el problema del viajante en un laberinto con múltiples tesoros. El objetivo principal es encontrar el orden óptimo de recolección de tesoros que minimice la distancia total recorrida desde el punto de inicio (S) hasta la salida (E), pasando por todos los tesoros exactamente una vez.
- Implementar Recocido Simulado (SA): Algoritmo de búsqueda local con capacidad de escape de óptimos locales mediante aceptación probabilística de soluciones peores.
- Implementar Algoritmo Genético (GA): Algoritmo poblacional que evoluciona soluciones a través de selección, cruce y mutación.
- Comparación de Algoritmos: Análisis empírico del rendimiento de ambos algoritmos en términos de calidad de solución, tiempo de ejecución y recursos utilizados.
- Interfaz Interactiva: Menú principal que permite experimentar con diferentes configuraciones de laberintos y parámetros de algoritmos.
Para n tesoros, existen n! permutaciones posibles, lo que hace inviable la búsqueda exhaustiva para valores moderados de n. Los algoritmos metaheurísticos ofrecen soluciones aproximadas eficientes.
La clase LaberintoTesoros representa el entorno de navegación y gestiona las operaciones básicas:
class LaberintoTesoros:
def __init__(self, grid: List[List[str]]):
self.grid = grid
self.filas = len(grid)
self.cols = len(grid[0]) if grid else 0
self.inicio = None
self.salida = None
self.tesoros = {} # {nombre_tesoro: (fila, col)}
self._extraer_posiciones()Elementos del laberinto:
- S: Punto de inicio
- E: Punto de salida
- T1, T2, ...: Tesoros a recolectar
- X: Paredes/obstáculos
- ' ': Espacios transitables
Métodos principales:
es_valida(pos): Verifica si una posición es transitableobtener_vecinos(pos): Retorna posiciones adyacentes válidas (4 direcciones)__str__(): Representación visual del laberinto
El algoritmo A* encuentra el camino óptimo entre dos puntos considerando obstáculos:
def encontrar_camino_minimo(inicio, fin, laberinto):
# Inicialización
heap = [(0, contador, inicio, [inicio])] # (f_score, contador, pos, camino)
visitados = {inicio: 0}
while heap:
f_score, _, pos_actual, camino_actual = heapq.heappop(heap)
if pos_actual == fin:
return camino_actual, len(camino_actual) - 1
# Explorar vecinos
for vecino in laberinto.obtener_vecinos(pos_actual):
nuevo_g = len(camino_actual)
if vecino not in visitados or nuevo_g < visitados[vecino]:
visitados[vecino] = nuevo_g
h = heuristica_manhattan(vecino, fin)
f = nuevo_g + h
heapq.heappush(heap, (f, contador, vecino, camino_actual + [vecino]))Características:
- Heurística: Distancia Manhattan (|dx| + |dy|)
- Complejidad: O(b^d) donde b es el factor de ramificación
- Admisibilidad: La heurística nunca sobreestima el costo real
Pre-calcula distancias entre todos los nodos importantes (S, E, T1, T2, ...) usando A*:
def construir_matriz_distancias(laberinto):
nodos = {'S': laberinto.inicio, 'E': laberinto.salida}
nodos.update(laberinto.tesoros)
matriz = {}
cache = {}
for i, nombre1 in enumerate(nombres_nodos):
for nombre2 in nombres_nodos[i+1:]:
camino, distancia = encontrar_camino_minimo(pos1, pos2, laberinto)
matriz[(nombre1, nombre2)] = distancia
matriz[(nombre2, nombre1)] = distancia
if camino:
cache[(pos1, pos2)] = (camino, distancia)
cache[(pos2, pos1)] = (camino[::-1], distancia)
return matriz, cacheCalcula la distancia total para un orden específico de tesoros:
def calcular_distancia_total(orden_tesoros, laberinto, cache):
puntos = [laberinto.inicio]
for tesoro in orden_tesoros:
puntos.append(laberinto.tesoros[tesoro])
puntos.append(laberinto.salida)
distancia_total = 0
camino_completo = []
for i in range(len(puntos) - 1):
origen, destino = puntos[i], puntos[i + 1]
camino_segmento, distancia = cache[(origen, destino)]
distancia_total += distancia
if i == 0:
camino_completo.extend(camino_segmento)
else:
camino_completo.extend(camino_segmento[1:])
return distancia_total, camino_completoclass SolucionRecocido:
def __init__(self, orden_tesoros: List[str]):
self.orden = orden_tesoros[:]
self.costo = float('inf')
self.camino = []
def evaluar(self, laberinto, cache):
self.costo, self.camino = calcular_distancia_total(self.orden, laberinto, cache)class RecocidoSimuladoTesoros:
def __init__(self, laberinto, temp_inicial=1000.0, temp_final=1.0, alpha=0.95, max_iteraciones=1000):
# Inicialización...
def ejecutar(self):
# Inicializar solución
self.solucion_actual = self.generar_solucion_inicial()
self.mejor_solucion = SolucionRecocido(self.solucion_actual.orden[:])
while self.temperatura > self.temp_final:
for _ in range(self.max_iteraciones):
# Generar vecino (perturbar)
vecino = self.perturbar_solucion(self.solucion_actual)
# Calcular delta costo
delta_costo = vecino.costo - self.solucion_actual.costo
# Aceptar según probabilidad
if random.random() < self.probabilidad_aceptacion(delta_costo, self.temperatura):
self.solucion_actual = vecino
# Actualizar mejor solución
if self.solucion_actual.costo < self.mejor_solucion.costo:
self.mejor_solucion = SolucionRecocido(self.solucion_actual.orden[:])
# Enfriar temperatura
self.enfriar_temperatura()
return self.mejor_solucionParámetros clave:
temp_inicial: Temperatura alta para explorar inicialmentetemp_final: Criterio de paradaalpha: Factor de enfriamiento (0 < α < 1)max_iteraciones: Iteraciones por nivel de temperatura
Perturbación: Intercambio aleatorio de dos tesoros (swap mutation)
Probabilidad de aceptación: P(ΔE, T) = e^(-ΔE/T) si ΔE > 0, 1 si ΔE ≤ 0
class Cromosoma:
def __init__(self, orden_tesoros: List[str]):
self.orden = orden_tesoros[:]
self.fitness = 0.0
self.distancia = float('inf')
self.camino = []
def evaluar(self, laberinto, cache):
self.distancia, self.camino = calcular_distancia_total(self.orden, laberinto, cache)
self.fitness = 1.0 / (1.0 + self.distancia) if self.distancia != float('inf') else 0.0Selección por Torneo:
def seleccion_torneo(self, k=3):
participantes = random.sample(self.poblacion, k)
return max(participantes, key=lambda x: x.fitness)Cruce Order Crossover (OX):
def cruce_orden(self, padre1, padre2):
n = len(padre1.orden)
punto1, punto2 = sorted(random.sample(range(n), 2))
hijo1_orden = [None] * n
hijo1_orden[punto1:punto2] = padre1.orden[punto1:punto2]
# Llenar con elementos de padre2 en orden
pos = punto2
for elemento in padre2.orden:
if elemento not in hijo1_orden:
hijo1_orden[pos % n] = elemento
pos += 1
return Cromosoma(hijo1_orden), Cromosoma(hijo2_orden)Mutación por Swap:
def mutacion_swap(self, cromosoma):
if random.random() < self.tasa_mutacion and len(cromosoma.orden) > 1:
i, j = random.sample(range(len(cromosoma.orden)), 2)
cromosoma.orden[i], cromosoma.orden[j] = cromosoma.orden[j], cromosoma.orden[i]def evolucionar(self):
if not self.poblacion:
self.inicializar_poblacion()
num_elite = max(1, int(self.tam_poblacion * self.tasa_elitismo))
for gen in range(self.generaciones):
nueva_poblacion = []
# Elitismo
nueva_poblacion.extend(self.poblacion[:num_elite])
# Generar descendencia
while len(nueva_poblacion) < self.tam_poblacion:
padre1 = self.seleccion_torneo()
padre2 = self.seleccion_torneo()
if random.random() < self.tasa_cruce:
hijo1, hijo2 = self.cruce_orden(padre1, padre2)
else:
hijo1 = Cromosoma(padre1.orden[:])
hijo2 = Cromosoma(padre2.orden[:])
self.mutacion_swap(hijo1)
self.mutacion_swap(hijo2)
hijo1.evaluar(self.laberinto, self.cache_distancias)
hijo2.evaluar(self.laberinto, self.cache_distancias)
nueva_poblacion.extend([hijo1, hijo2])
# Reemplazo generacional
self.poblacion = nueva_poblacion[:self.tam_poblacion]
self.poblacion.sort(reverse=True) # Mejor fitness primero
# Actualizar mejor histórico
if self.poblacion[0].fitness > self.mejor_historico.fitness:
self.mejor_historico = self.poblacion[0]
return self.mejor_historicoEl archivo principal es Recocido Simulado.py que contiene el menú interactivo:
python "Recocido Simulado.py"- Usar laberinto predefinido: Utiliza el laberinto incluido en
get_mi_laberinto() - Crear laberinto aleatorio: Genera laberintos con parámetros personalizables
- Salir
from Recocido_Simulado import RecocidoSimuladoTesoros
from laberinto import LaberintoTesoros, get_mi_laberinto
# Crear laberinto
laberinto_grid = get_mi_laberinto()
laberinto = LaberintoTesoros(laberinto_grid)
# Ejecutar SA
sa = RecocidoSimuladoTesoros(laberinto=laberinto)
mejor_solucion = sa.ejecutar()
print(f"Mejor orden: {mejor_solucion.orden}")
print(f"Distancia: {mejor_solucion.costo}")from algoritmoGenetico import AlgoritmoGeneticoTesoros
ag = AlgoritmoGeneticoTesoros(laberinto=laberinto)
mejor_cromosoma = ag.evolucionar()
print(f"Mejor orden: {mejor_cromosoma.orden}")
print(f"Distancia: {mejor_cromosoma.distancia}")# Ejecutar comparación automática
resultados = sa.comparar_con_genetico(generaciones_ga=100, tam_poblacion_ga=50)from Recocido_Simulado import crear_laberinto_aleatorio
grid_aleatorio = crear_laberinto_aleatorio(
filas=6,
cols=8,
num_tesoros=5,
densidad_paredes=0.3
)
laberinto = LaberintoTesoros(grid_aleatorio)Recocido Simulado:
temp_inicial: 1000.0temp_final: 1.0alpha: 0.95max_iteraciones: 1000
Algoritmo Genético:
tam_poblacion: 50generaciones: 100tasa_mutacion: 0.2tasa_cruce: 0.7tasa_elitismo: 0.1
- Python 3.7+
- random: Generación de números aleatorios
- math: Funciones matemáticas (exp, log)
- time: Medición de tiempos de ejecución
- heapq: Cola de prioridad para A*
- psutil: Monitoreo de recursos del sistema
- itertools: Generación de permutaciones
- collections: Estructuras de datos (deque)
- typing: Anotaciones de tipos
Proyecto IA laberinto.pdf: Documentación detallada del sistema de laberinto y algoritmo A*Proyecto Recocido Simulado.md: Documentación específica del Recocido Simulado
Recocido Simulado.py: Implementación principal con menú interactivolaberinto.py: Clase LaberintoTesoros y algoritmos de navegaciónalgoritmoGenetico.py: Implementación del Algoritmo Genético
- A Search*: Búsqueda de caminos óptimos con heurística admisible
- Simulated Annealing: Optimización metaheurística con enfriamiento controlado
- Genetic Algorithm: Evolución poblacional con operadores genéticos
- Distance Matrix Precomputation: Optimización mediante cache de distancias
| Algoritmo | Tiempo | Espacio |
|---|---|---|
| A* | O(b^d) | O(b^d) |
| SA | O(iter × temp_steps) | O(1) |
| GA | O(gen × pop × eval) | O(pop) |
Donde:
- b: factor de ramificación
- d: profundidad máxima
- iter: iteraciones por temperatura
- temp_steps: número de niveles de temperatura
- gen: generaciones
- pop: tamaño de población
- eval: costo de evaluación de una solución
Proyecto desarrollado como parte del curso de Inteligencia Artificial Implementación: Python 3.x Última actualización: 2024