pages/AG_2D.py

import streamlit as st
import random
import plotly.graph_objects as go
import pandas as pd

# Se debe tener instalado plotly, streamlit y matplotlib

st.set_page_config(layout="centered", page_title="AG for TSP 2D", page_icon="🧬")


# Función para generar una población inicial aleatoria
def generar_poblacion(num_individuos, num_ciudades):
    poblacion = []
    for _ in range(num_individuos):
        individuo = list(range(num_ciudades))
        random.shuffle(individuo)
        poblacion.append(individuo)
    return poblacion


# Función para evaluar la aptitud de un individuo (distancia total del recorrido)
def calcular_aptitud(individuo, distancias, coordenadas):
    distancia_total = 0
    coordenadas_iguales = all(coord == coordenadas[0] for coord in coordenadas)

    if not coordenadas_iguales:
        for i in range(len(individuo) - 1):
            ciudad_actual = individuo[i]
            siguiente_ciudad = individuo[i + 1]
            distancia_total += distancias[ciudad_actual][siguiente_ciudad]

        distancia_total += distancias[individuo[-1]][individuo[0]]

    return distancia_total


# Función para seleccionar individuos para la reproducción (torneo binario)
def seleccion_torneo(poblacion, distancias, coordenadas):
    seleccionados = []
    for _ in range(len(poblacion)):
        torneo = random.sample(poblacion, 2)
        aptitud_torneo = [
            calcular_aptitud(individuo, distancias, coordenadas) for individuo in torneo
        ]
        seleccionado = torneo[aptitud_torneo.index(min(aptitud_torneo))]
        seleccionados.append(seleccionado)
    return seleccionados

checkboxCruce = st.sidebar.checkbox("Sin cruce de caminos")

# Función para realizar el cruce de dos padres para producir un hijo
def cruzar(padre1, padre2):
    punto_cruce = random.randint(0, len(padre1) - 1)
    hijo = padre1[:punto_cruce] + [
        gen for gen in padre2 if gen not in padre1[:punto_cruce]
    ]
    if checkboxCruce:
        hijo = corregir_camino(hijo, distancias)
    return hijo

# Función para corregir el camino y evitar cruces no deseados
def corregir_camino(camino, distancias):
    n = len(camino)
    for i in range(n):
        for j in range(i + 2, n - 1):
            if distancias[camino[i]][camino[i + 1]] + distancias[camino[j]][camino[j + 1]] > distancias[camino[i]][camino[j]] + distancias[camino[i + 1]][camino[j + 1]]:
                # Intercambiar las conexiones para corregir el cruce
                camino[i + 1], camino[j] = camino[j], camino[i + 1]
    return camino

# Función para aplicar mutaciones en la población
def mutar(individuo, probabilidad_mutacion):
    if random.random() < probabilidad_mutacion:
        indices = random.sample(range(len(individuo)), 2)
        individuo[indices[0]], individuo[indices[1]] = (
            individuo[indices[1]],
            individuo[indices[0]],
        )
    return individuo


# Función para generar distancias aleatorias entre ciudades y sus coordenadas bidimensionales
def generar_distancias(num_ciudades):
    distancias = [[0] * num_ciudades for _ in range(num_ciudades)]
    coordenadas = [
        (random.uniform(0, 100), random.uniform(0, 100)) for _ in range(num_ciudades)
    ]

    for i in range(num_ciudades):
        for j in range(i + 1, num_ciudades):
            distancias[i][j] = distancias[j][i] = (
                sum((x - y) ** 2 for x, y in zip(coordenadas[i], coordenadas[j])) ** 0.5
            )

    return distancias, coordenadas


# Función para visualizar el camino en 2D
def visualizar_camino(camino, coordenadas, mejor_distancia):
    fig = go.Figure()

    # Añadir el camino como un trazado 2D interactivo
    x = [coordenadas[i][0] for i in camino]
    y = [coordenadas[i][1] for i in camino]

    fig.add_trace(go.Scatter(x=x, y=y, mode="lines+markers", name="Camino"))

    # Añadir el punto de inicio
    fig.add_trace(
        go.Scatter(
            x=[x[0]],
            y=[y[0]],
            mode="markers",
            marker=dict(color="green", size=10),
            name="Inicio",
        )
    )

    # Añadir el punto de fin
    fig.add_trace(
        go.Scatter(
            x=[x[-1]],
            y=[y[-1]],
            mode="markers",
            marker=dict(color="red", size=10),
            name="Fin",
        )
    )

    # Configuraciones adicionales
    fig.update_layout(
        title=f"Mejor Camino Encontrado\nDistancia: {mejor_distancia:.2f}"
    )

    # Mostrar el gráfico interactivo en Streamlit
    st.plotly_chart(fig)


def visualizar_camino_streamlit(camino, coordenadas, mejor_distancia):
    fig_camino = go.Figure()

    # Ordenar las coordenadas de acuerdo con el camino
    ordenado_x = [coordenadas[i][0] for i in camino]
    ordenado_y = [coordenadas[i][1] for i in camino]

    # Añadir el camino como un trazado 2D interactivo sin markers
    fig_camino.add_trace(
        go.Scatter(
            x=ordenado_x,
            y=ordenado_y,
            mode="lines",
            name="Camino",
        )
    )

    # Añadir los puntos de inicio y fin con etiquetas
    fig_camino.add_trace(
        go.Scatter(
            x=[ordenado_x[0]],
            y=[ordenado_y[0]],
            mode="markers+text",
            marker=dict(color="green", size=15),
            name="Inicio",
            text=[str(camino[0])],
            textposition="top center",
        )
    )

    fig_camino.add_trace(
        go.Scatter(
            x=[ordenado_x[-1]],
            y=[ordenado_y[-1]],
            mode="markers+text",
            marker=dict(color="red", size=15),
            name="Fin",
            text=[str(camino[-1])],
            textposition="top center",
        )
    )

    # Añadir etiquetas a los puntos intermedios
    for i, (xi, yi) in enumerate(zip(ordenado_x[1:-1], ordenado_y[1:-1])):
        fig_camino.add_trace(
            go.Scatter(
                x=[xi],
                y=[yi],
                mode="markers+text",
                marker=dict(size=3),
                text=[str(camino[i + 1])],
                textposition="top center",
                showlegend=False,
            )
        )

    # Configuraciones adicionales
    fig_camino.update_layout(
        title=f"Mejor Camino Encontrado\nDistancia: {mejor_distancia:.2f}"
    )

    # Mostrar el gráfico interactivo en Streamlit
    st.plotly_chart(fig_camino)


# funcion para fitness
def fitness(distancia, maxima_distancia, tamCromosoma):
    return (
        0
        if distancia * tamCromosoma == 0
        else 1 - ((distancia) / (maxima_distancia * tamCromosoma))
    )


def algoritmo_genetico(
    num_generaciones,
    num_ciudades,
    num_individuos,
    probabilidad_mutacion,
    distancias,
    coordenadas,
    probabilidad_cruce,
):
    poblacion = generar_poblacion(num_individuos, num_ciudades)
    mejor_solucion_historial = []
    mejor_distancia_historial = []
    peor = 0
    fitness_historial = []
    for _ in range(num_generaciones):
        poblacion = sorted(
            poblacion, key=lambda x: calcular_aptitud(x, distancias, coordenadas)
        )
        mejor_individuo = poblacion[0]
        mejor_distancia = calcular_aptitud(mejor_individuo, distancias, coordenadas)
        mejor_solucion_historial.append(mejor_individuo)
        mejor_distancia_historial.append(mejor_distancia)
        seleccionados = seleccion_torneo(poblacion, distancias, coordenadas)
        nueva_poblacion = []
        for i in range(0, len(seleccionados), 2):
            padre1, padre2 = seleccionados[i], seleccionados[i + 1]
            aleatorio_cruce = random.uniform(0, 1)
            if aleatorio_cruce < probabilidad_cruce:
                hijo1 = cruzar(padre1, padre2)
                hijo2 = cruzar(padre2, padre1)
            else:
                hijo1, hijo2 = padre1, padre2
            hijo1 = mutar(hijo1, probabilidad_mutacion)
            hijo2 = mutar(hijo2, probabilidad_mutacion)
            nueva_poblacion.extend([hijo1, hijo2])
        poblacion = nueva_poblacion
        if peor < mejor_distancia:
            peor = mejor_distancia
        fitness_historial.append(fitness(mejor_distancia, peor, len(padre1)))
    mejor_solucion = poblacion[0]
    mejor_distancia = calcular_aptitud(mejor_solucion, distancias, coordenadas)
    # Visualizar el proceso del algoritmo
    visualizar_proceso_streamlit(
        mejor_distancia_historial, mejor_solucion, coordenadas, mejor_distancia
    )
    # Visualizar el fitness
    visualizar_fitness_streamlit(fitness_historial)
    # Visualizar el mejor camino encontrado
    visualizar_camino_streamlit(mejor_solucion, coordenadas, mejor_distancia)

    return mejor_solucion, mejor_distancia


def algoritmo_genetico_early_stopping(
    num_generaciones,
    num_ciudades,
    num_individuos,
    probabilidad_mutacion,
    distancias,
    coordenadas,  # Asegúrate de tener este parámetro
    probabilidad_cruce,
    max_generaciones_sin_mejora,
):
    poblacion = generar_poblacion(num_individuos, num_ciudades)
    mejor_solucion_historial = []
    mejor_distancia_historial = []
    peor = 0
    fitness_historial = []
    generaciones_sin_mejora = 0  # Inicializar contador de generaciones sin mejora

    for _ in range(num_generaciones):
        poblacion = sorted(
            poblacion, key=lambda x: calcular_aptitud(x, distancias, coordenadas)
        )
        mejor_individuo = poblacion[0]

        mejor_distancia = calcular_aptitud(mejor_individuo, distancias, coordenadas)
        # Almacenar el mejor individuo y su distancia en cada generación
        mejor_solucion_historial.append(mejor_individuo)
        mejor_distancia_historial.append(mejor_distancia)

        seleccionados = seleccion_torneo(
            poblacion, distancias, coordenadas
        )  # Pasa coordenadas aquí

        nueva_poblacion = []
        for i in range(0, len(seleccionados), 2):
            padre1, padre2 = seleccionados[i], seleccionados[i + 1]
            aleatorio_local = random.uniform(0, 1)
            if aleatorio_local <= probabilidad_cruce:
                hijo1 = cruzar(padre1, padre2)
                hijo2 = cruzar(padre2, padre1)
            else:
                hijo1, hijo2 = padre1, padre2
            hijo1 = mutar(hijo1, probabilidad_mutacion)
            hijo2 = mutar(hijo2, probabilidad_mutacion)
            nueva_poblacion.extend([hijo1, hijo2])

        poblacion = nueva_poblacion
        if peor < mejor_distancia:
            peor = mejor_distancia
            generaciones_sin_mejora = 0  # Reiniciar contador al mejorar
        else:
            generaciones_sin_mejora += 1

        # Verificar Early Stopping
        if generaciones_sin_mejora >= max_generaciones_sin_mejora:
            st.warning(
                "Early Stopping: Se detuvo el algoritmo debido a falta de mejora."
            )
            break

        fitness_historial.append(fitness(mejor_distancia, peor, len(padre1)))
    mejor_solucion = poblacion[0]
    mejor_distancia = calcular_aptitud(mejor_solucion, distancias, coordenadas)
    # Visualizar el proceso del algoritmo
    visualizar_proceso_streamlit(
        mejor_distancia_historial, mejor_solucion, coordenadas, mejor_distancia
    )
    # visualizar el fitness
    visualizar_fitness_streamlit(fitness_historial)
    # Visualizar el mejor camino encontrado
    visualizar_camino_streamlit(mejor_solucion, coordenadas, mejor_distancia)

    return mejor_solucion, mejor_distancia


def visualizar_fitness_streamlit(fitness_historial):
    generaciones = list(range(len(fitness_historial)))
    fig_fitness = go.Figure()
    fig_fitness.add_trace(
        go.Scatter(x=generaciones, y=fitness_historial, mode="lines+markers")
    )
    fig_fitness.update_layout(
        title="Evolución del fitness en Cada Generación",
        xaxis_title="Generación",
        yaxis_title="Fitness",
    )
    st.plotly_chart(fig_fitness)


def visualizar_proceso_streamlit(
    mejor_distancia_historial, mejor_solucion, coordenadas, mejor_distancia
):
    generaciones = list(range(len(mejor_distancia_historial)))

    # Crear gráfico interactivo de evolución de la distancia
    fig_distancia = go.Figure()
    fig_distancia.add_trace(
        go.Scatter(x=generaciones, y=mejor_distancia_historial, mode="lines+markers")
    )
    fig_distancia.update_layout(
        title="Evolución de la Distancia en Cada Generación",
        xaxis_title="Generación",
        yaxis_title="Distancia",
    )
    st.plotly_chart(fig_distancia)


#####################
if __name__ == "__main__":
    st.title("Algoritmo Genético para el Problema del Viajante")
    st.sidebar.header("Configuración")
    manual_input = st.sidebar.checkbox("Ingresar datos manualmente")
    # Ingresar datos manualmente o generarlos aleatoriamente (por defecto), además de generar las distancias
    if manual_input:
        st.sidebar.subheader("Ingresar coordenadas manualmente:")
        num_ciudades = st.sidebar.number_input(
            "Número de Ciudades", min_value=5, max_value=100, value=10, step=5
        )

        coordenadas = []
        for i in range(num_ciudades):
            st.sidebar.subheader(f"Coordenadas Ciudad {i + 1}")
            x = st.sidebar.number_input(
                f"X Ciudad {i + 1}:", value=0.0, key=f"x_{i}", step=1.0
            )
            y = st.sidebar.number_input(
                f"Y Ciudad {i + 1}:", value=0.0, key=f"y_{i}", step=1.0
            )
            coordenadas.append((x, y))

        data = pd.DataFrame(coordenadas, columns=["X", "Y"])
        distancias, _ = generar_distancias(num_ciudades)
    else:
        num_ciudades = st.sidebar.number_input(
            "Número de Ciudades", min_value=5, max_value=100, value=10, step=5
        )

        distancias, coordenadas = generar_distancias(num_ciudades)
        data = pd.DataFrame(coordenadas, columns=["X", "Y"])

    # Mostrar datos en la interfaz
    st.write(
        "Puntos en el espacio bidimensional (X, Y), donde cada punto es una ciudad"
    )
    st.dataframe(data=data, use_container_width=True)

    # Configuraciones adicionales
    num_generaciones = st.sidebar.number_input(
        "Número de Generaciones", min_value=10, max_value=1000, value=50
    )
    num_individuos = st.sidebar.slider(
        "Tamaño de la Población ($par$)", min_value=10, max_value=500, value=50, step=2
    )
    probabilidad_mutacion = st.sidebar.slider(
        "Probabilidad de Mutación", min_value=0.01, max_value=0.5, value=0.1, step=0.01
    )
    probabilidad_cruce = st.sidebar.slider(
        "Probabilidad de cruce", min_value=0.90, max_value=1.0, value=0.95, step=0.01
    )
    distancias_generadas, coordenadas_generadas = generar_distancias(num_ciudades)
    checkbox = st.sidebar.checkbox("Early Stopping")
    if checkbox:
        max_generaciones_sin_mejora = st.sidebar.number_input(
            "Limite de generaciones sin mejora",
            min_value=5,
            max_value=1000,
            value=20,
            step=5,
        )
        mejor_solucion, mejor_distancia = algoritmo_genetico_early_stopping(
            num_generaciones,
            num_ciudades,
            num_individuos,
            probabilidad_mutacion,
            distancias,
            coordenadas,
            probabilidad_cruce,
            max_generaciones_sin_mejora,
        )

    else:
        mejor_solucion, mejor_distancia = algoritmo_genetico(
            num_generaciones,
            num_ciudades,
            num_individuos,
            probabilidad_mutacion,
            distancias,
            coordenadas,
            probabilidad_cruce,
        )

    # Mostrar resultados
    st.success(f"Mejor solución encontrada: {mejor_solucion}")
    st.success(f"Mejor distancia encontrada: {mejor_distancia:.2f}")