Aplicar los principios de los algoritmos genéticos para resolver el problema del agente viajero, observando cómo el aprendizaje emergente puede llevar a soluciones óptimas mediante evolución simulada.

Un agente (vendedor) debe visitar una lista de ciudades una sola vez y regresar a la ciudad de origen. El desafío es encontrar la ruta más corta posible entre todas las combinaciones posibles.

Crea una lista de 6 a 10 ciudades imaginarias o reales. Puedes dibujar un mapa o simplemente escribirlas en papel o una tabla. Ejemplo:

• A: Alfa

• B: Beta

• C: Ceres

• D: Delta

• E: Epsilon

• F: Fobos

Dibuja los nodos y conéctalos como puntos en un mapa. Agrega distancias estimadas entre cada par.

Crea al menos 5 rutas diferentes (cromosomas), donde cada ruta representa un orden en el que el agente viaja por las ciudades.

Escribe estas rutas en una tabla. Cada fila es un individuo (ruta posible).

Suma las distancias de cada ruta completa. Mientras menor sea la distancia total, mayor es la aptitud del individuo.

Crea una columna "Distancia total" y ordénalas de mejor (menor distancia) a peor.

Elige las dos mejores rutas con menor distancia total para que se crucen. Este proceso se llama selección natural, como en la biología.

Marca las dos mejores y llama a estos “padres”.

Combina partes de cada padre para crear nuevas rutas (hijos).Puedes usar la técnica "Order Crossover", en la que se toma una parte del primer padre y se completa con el orden del segundo padre.

Ejemplo:

Padre 1: A → C → B → E → D → F

Padre 2: A → F → D → C → B → E

→ Hijo: C → B → E + (orden de Padre 2 sin repetir) = C → B → E → F → D → A

Crea al menos 2 hijos nuevos.

Introduce un pequeño cambio aleatorio en las rutas (por ejemplo, intercambiar dos ciudades de lugar). Esto ayuda a descubrir nuevas soluciones.

Ejemplo de mutación:

C → B → E → F → D → A → C → E → B → F → D → A

Aplica una mutación a uno o más hijos.

Sustituye las rutas más largas de la población original con los nuevos hijos. Repite los pasos 3 a 6 durante 3 generaciones o más.

Observa cómo las rutas evolucionan y mejoran.

Al final, deberías tener una ruta mucho más eficiente que la inicial. Habrá surgido como resultado de selección, cruzamiento y mutación: la base de los algoritmos genéticos.

Después de comprender el proceso, se procede a codificar el algoritmo

Implementar un algoritmo genético básico en Python para encontrar una solución eficiente al problema del agente viajero, comprendiendo los principios de selección, cruzamiento, mutación y evaluación de fitness.

Primero, instalamos y/o importamos las librerías necesarias:

import random
import numpy as np
import matplotlib.pyplot as plt

# Crear un conjunto de ciudades con coordenadas aleatorias (ejemplo con 10 ciudades)
num_ciudades = 10
ciudades = np.random.rand(num_ciudades, 2)  # Coordenadas x, y entre 0 y 1

def distancia(ciudad1, ciudad2):
    return np.linalg.norm(ciudad1 - ciudad2)

# Crear una matriz de distancias
matriz_distancia = np.zeros((num_ciudades, num_ciudades))
for i in range(num_ciudades):
    for j in range(num_ciudades):
        if i != j:
            matriz_distancia[i][j] = distancia(ciudades[i], ciudades[j])

# Calcular distancia total de una ruta
def calcular_distancia(ruta):
    return sum(matriz_distancia[ruta[i]][ruta[i + 1]] for i in range(len(ruta) - 1)) + \
           matriz_distancia[ruta[-1]][ruta[0]]  # regreso al origen

# Crear una ruta aleatoria
def crear_ruta():
    ruta = list(range(num_ciudades))
    random.shuffle(ruta)
    return ruta

# Crear población inicial
def crear_poblacion(tamano):
    return [crear_ruta() for _ in range(tamano)]

# Selección (las mejores rutas)
def seleccionar(poblacion, k=4):
    puntuadas = sorted(poblacion, key=lambda ruta: calcular_distancia(ruta))
    return puntuadas[:k]

# Cruzamiento (Order Crossover simple)
def cruzar(padre1, padre2):
    a, b = sorted(random.sample(range(len(padre1)), 2))
    hijo = [None] * len(padre1)
    hijo[a:b] = padre1[a:b]
    rellenar = [ciudad for ciudad in padre2 if ciudad not in hijo]
    idx = 0
    for i in range(len(hijo)):
        if hijo[i] is None:
            hijo[i] = rellenar[idx]
            idx += 1
    return hijo

# Mutación (intercambio de dos ciudades)
def mutar(ruta, tasa_mutacion=0.1):
    nueva_ruta = ruta[:]
    if random.random() < tasa_mutacion:
        i, j = random.sample(range(len(ruta)), 2)
        nueva_ruta[i], nueva_ruta[j] = nueva_ruta[j], nueva_ruta[i]
    return nueva_ruta

def evolucionar(poblacion, generaciones=100, mutacion=0.1):
    mejores_distancias = []
    for _ in range(generaciones):
        seleccionados = seleccionar(poblacion)
        hijos = []
        while len(hijos) < len(poblacion):
            padre1, padre2 = random.sample(seleccionados, 2)
            hijo = cruzar(padre1, padre2)
            hijo = mutar(hijo, tasa_mutacion=mutacion)
            hijos.append(hijo)
        poblacion = hijos
        mejor = min(poblacion, key=lambda r: calcular_distancia(r))
        mejores_distancias.append(calcular_distancia(mejor))
    return mejor, mejores_distancias

# Ejecutar
poblacion = crear_poblacion(20)
mejor_ruta, historial = evolucionar(poblacion, generaciones=100)

# Mostrar ruta final
plt.figure(figsize=(6,6))
ruta_coords = np.array([ciudades[i] for i in mejor_ruta] + [ciudades[mejor_ruta[0]]])
plt.plot(ruta_coords[:,0], ruta_coords[:,1], marker='o')
for i, ciudad in enumerate(mejor_ruta):
    plt.text(ciudades[ciudad][0], ciudades[ciudad][1], str(ciudad), fontsize=12)
plt.title("Ruta más corta encontrada")
plt.show()

# Evolución de la distancia
plt.figure()
plt.plot(historial)
plt.title("Evolución de la distancia total")
plt.xlabel("Generación")
plt.ylabel("Distancia")
plt.show()

Al ejecutar el algoritmo:

• Se encontrará una ruta eficiente entre las ciudades.

• Se visualizará la ruta final y cómo la distancia total fue mejorando con cada generación.

Para más info:

https://www.frexus.dev/post/inteligencia-artificial/