algoritmos.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "upper-theorem",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "import random\n",
    "import time\n",
    "import matplotlib.pyplot as plt \n",
    "import datetime\n",
    "from multiprocessing import Pool\n",
    "from itertools import combinations, product\n",
    "from statistics import mean, stdev\n",
    "from itertools import combinations\n",
    "from numpy import log, append, setdiff1d, array\n",
    "from collections import deque # Cola FIFO para la lista tabú\n",
    "from numpy import argsort # Ordenar lista por indices (GRASP)\n",
    "from functools import partial \n",
    "import matplotlib\n",
    "import matplotlib.pyplot as plt\n",
    "import bisect\n",
    "from heapq import nsmallest # Seleccion torneo\n",
    "verbose = False"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "infinite-trustee",
   "metadata": {},
   "source": [
    "# Funciones comunes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "historical-bacteria",
   "metadata": {},
   "outputs": [],
   "source": [
    "def leeFichero(nombreFichero ='tsp/a280.tsp'):\n",
    "    rutaFichero = './tsp/'\n",
    "    extension = '.tsp'\n",
    "    fichero = open(rutaFichero + nombreFichero + extension, 'r')\n",
    "    array_puntos = []\n",
    "\n",
    "    # Saltamos las cabeceras del fichero #\n",
    "    for i in range(6):\n",
    "        fichero.readline()\n",
    "\n",
    "    for line in fichero:\n",
    "        try:\n",
    "            array_temp = line.replace('   ', ' ').replace('  ', ' ').replace('\\n', '').split(' ')\n",
    "            array_temp = [float(item) for item in array_temp if item]\n",
    "\n",
    "            if(len(array_temp) > 1):\n",
    "                array_puntos.append(array_temp)\n",
    "        except:\n",
    "            pass\n",
    "\n",
    "    fichero.close()\n",
    "\n",
    "    return array_puntos"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "healthy-speaker",
   "metadata": {},
   "outputs": [],
   "source": [
    "def getDistancia(p1, p2):\n",
    "    xd = p1[1] - p2[1]\n",
    "    yd = p1[2] - p2[2]\n",
    "    \n",
    "    dij = round(math.sqrt(xd*xd + yd*yd))\n",
    "    \n",
    "    return dij"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "greatest-communist",
   "metadata": {},
   "outputs": [],
   "source": [
    "def getMDistancias(nodos):\n",
    "   \n",
    "    distancias = [[0]*len(nodos) for i in range(len(nodos))]\n",
    "    \n",
    "    for i in range(len(nodos)):\n",
    "        for j in range(len(nodos)):\n",
    "            \n",
    "            if(i==j):\n",
    "                dij = 0 # Distancia a sí mismo infinita\n",
    "            else:\n",
    "                dij = getDistancia(nodos[i], nodos[j])\n",
    "                \n",
    "            distancias[i][j] = dij\n",
    "            \n",
    "    return distancias"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "filled-print",
   "metadata": {},
   "outputs": [],
   "source": [
    "def pintaCamino(camino, nodos, titulo):\n",
    "    \n",
    "    x = []\n",
    "    y = []\n",
    "    \n",
    "    for i in range(0, len(camino)-1):\n",
    "        \n",
    "        x.append(nodos[camino[i]-1][1])\n",
    "        y.append(nodos[camino[i]-1][2])\n",
    "        \n",
    "    plt.figure(figsize=(12,12))    \n",
    "    plt.title(titulo)\n",
    "    plt.scatter(x, y, color='green') \n",
    "    \n",
    "    for i in range(len(x)):\n",
    "        if(i < len(x)-1):\n",
    "            plt.arrow(x[i], y[i], x[i+1] - x[i], y[i+1] - y[i], head_width=1, length_includes_head=True)\n",
    "        else:\n",
    "             plt.arrow(x[i], y[i], x[0] - x[i], y[0] - y[i], head_width=1, length_includes_head=True)\n",
    "                \n",
    "    # Punto rojo inicial\n",
    "    plt.plot(x[0],y[0], marker='o',\n",
    "     markerfacecolor='red', markersize=12)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "liberal-arizona",
   "metadata": {},
   "outputs": [],
   "source": [
    "def getCosteCamino(camino, distancias, verbose=False):\n",
    "    coste = 0\n",
    "    \n",
    "    for i in range(0, len(camino)-1):\n",
    "        dij = distancias[camino[i]][camino[i+1]]\n",
    "        coste += dij # Sumamos la distancia de un nodo al siguiente\n",
    "        if(verbose):\n",
    "            print(f\"Acumulando Distancia {camino[i]} -> {camino[i+1]} = {dij}\")\n",
    "        \n",
    "        \n",
    "    dij = distancias[camino[-1]][camino[0]] #Sumamos la distancia del ultimo al primero\n",
    "    coste += dij\n",
    "    if(verbose):\n",
    "            print(f\"Acumulando Distancia {camino[-1]} -> {camino[0]} = {dij}\")\n",
    "    \n",
    "    return coste"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "rational-prescription",
   "metadata": {},
   "outputs": [],
   "source": [
    "def getCostePivotes(distancias, caminoAnt, costeAnt, piv1, piv2):\n",
    "      \n",
    "    caminoAnt1 = [caminoAnt[piv1-1], caminoAnt[piv1]]\n",
    "    if(piv1 != len(distancias)-1):\n",
    "        caminoAnt1.append(caminoAnt[piv1+1])\n",
    "    else:\n",
    "        # Pivote es el último elemento: último al primero\n",
    "        caminoAnt1.append(caminoAnt[0])\n",
    "        \n",
    "    caminoAnt2 = [caminoAnt[piv2-1], caminoAnt[piv2]]\n",
    "    if(piv2 != len(distancias)-1):\n",
    "        caminoAnt2.append(caminoAnt[piv2+1])\n",
    "    else:\n",
    "        # Pivote es el último elemento: último al primero\n",
    "        caminoAnt2.append(caminoAnt[0])\n",
    "        \n",
    "    caminoNuevo1 = caminoAnt1.copy()\n",
    "    if caminoAnt[piv2] in caminoNuevo1:\n",
    "        caminoNuevo1[caminoNuevo1.index(caminoAnt[piv2])] = caminoAnt[piv1]\n",
    "    caminoNuevo1[1] = caminoAnt[piv2]\n",
    "    \n",
    "    \n",
    "    caminoNuevo2 = caminoAnt2.copy()\n",
    "    if caminoAnt[piv1] in caminoNuevo2:\n",
    "        caminoNuevo2[caminoNuevo2.index(caminoAnt[piv1])] = caminoAnt[piv2]\n",
    "    caminoNuevo2[1] = caminoAnt[piv1]\n",
    "   \n",
    "    #print(\"SubCaminos anteriores: \", caminoAnt1, caminoAnt2)\n",
    "    #print(\"SubCaminos nuevos: \", caminoNuevo1, caminoNuevo2)\n",
    "    \n",
    "    return (costeAnt - distancias[caminoAnt1[0]][caminoAnt1[1]] - distancias[caminoAnt1[1]][caminoAnt1[2]] - distancias[caminoAnt2[0]][caminoAnt2[1]] - distancias[caminoAnt2[1]][caminoAnt2[2]] + distancias[caminoNuevo1[0]][caminoNuevo1[1]] +  distancias[caminoNuevo1[1]][caminoNuevo1[2]] + distancias[caminoNuevo2[0]][caminoNuevo2[1]] + distancias[caminoNuevo2[1]][caminoNuevo2[2]])\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "coupled-conservative",
   "metadata": {},
   "source": [
    "# Algoritmo Greedy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "responsible-canvas",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Algoritmo Greedy\n",
    "def algoritmoGreedy(distancias):\n",
    "    \n",
    "    caminoSolucion = [0] # Empezamos en el primer indice de nodo\n",
    "    nodosPendientes = list(range(1,len(distancias[1]))) # Lista del segundo al ultimo indice de nodo\n",
    "    \n",
    "    while len(nodosPendientes) > 0: # Mientras queden nodos por visitar\n",
    "\n",
    "        nodoActual = caminoSolucion[-1] # Partimos desde el útlimo nodo añadido\n",
    "        minDistancia = distancias[nodoActual][nodosPendientes[0]] # Inicializamos la distancia del actual al primer pendiente\n",
    "        nodoMinDistancia = nodosPendientes[0]\n",
    "        \n",
    "        for nodoVecino in nodosPendientes: # Recorremos todos los nodos pendientes y nos quedamos con el de menor distancia\n",
    "            d = distancias[nodoActual][nodoVecino]\n",
    "            \n",
    "            if d < minDistancia:\n",
    "                minDistancia = d\n",
    "                nodoMinDistancia = nodoVecino\n",
    "                \n",
    "        caminoSolucion.append(nodoMinDistancia)\n",
    "        nodosPendientes.remove(nodoMinDistancia)\n",
    "        \n",
    "    return caminoSolucion\n",
    "    #return [indice+1 for indice in caminoSolucion] # + 1 a cada elemento (tiene que empezar por 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "unauthorized-senegal",
   "metadata": {},
   "source": [
    "# Algoritmo Genético Básico"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "massive-amber",
   "metadata": {},
   "source": [
    "## Estructura de datos"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "planned-mercy",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Cromosoma:\n",
    "    \n",
    "    # Métodos de clase\n",
    "    def set_nodos_distancias(num_nodos, distancias):\n",
    "        Cromosoma.num_nodos = num_nodos\n",
    "        Cromosoma.distancias = distancias\n",
    "    \n",
    "    # Métodos de instancias\n",
    "    \n",
    "    # Operador minimo\n",
    "    # https://stackoverflow.com/questions/3621826/python-minimum-of-a-list-of-instance-variables\n",
    "    def __lt__(self, other):\n",
    "        return self.coste < other.coste\n",
    "    \n",
    "    def __eq__(self, other):\n",
    "        for index in range(len(self.camino)):\n",
    "            if not self.camino[index] == other.camino[index]:\n",
    "                return False\n",
    "        return True\n",
    "    \n",
    "    def __str__(self):\n",
    "        return str(self.coste) \n",
    "    \n",
    "    def __repr__(self):\n",
    "        return str(self.coste)\n",
    "    \n",
    "    # Se puede instanciar de 3 maneras:\n",
    "    # Cromosoma(): solucion aleatoria no elite\n",
    "    # Cromosoma(camino, coste): solucion y coste definidos, no elite\n",
    "    def __init__(self, *args):\n",
    "        \n",
    "        if not Cromosoma.num_nodos or not Cromosoma.distancias:\n",
    "            raise TypeError(\"No se ha inicializado el num nodos o las distancias para la clase Cromosoma\") \n",
    "        \n",
    "        if len(args) == 0:\n",
    "            # Combinación aleatoria sin repeteción de nodos\n",
    "            self.camino = random.sample(range(Cromosoma.num_nodos), Cromosoma.num_nodos) # Combinación aleatoria sin repeteción de nodos\n",
    "            self.coste = getCosteCamino(self.camino, Cromosoma.distancias) \n",
    "            \n",
    "        elif len(args) == 2:\n",
    "            self.camino = args[0]\n",
    "            self.coste = args[1]        \n",
    "        else:\n",
    "            raise TypeError(\"Número de argumentos no válido, solo 0 ó 2\") \n",
    "            \n",
    "    def set_camino(self, camino):\n",
    "        self.camino = camino\n",
    "        \n",
    "    def set_coste(self, coste):\n",
    "        self.camino = coste\n",
    "        \n",
    "    def get_camino(self):\n",
    "        return self.camino\n",
    "    \n",
    "    def get_coste(self):\n",
    "        return self.coste\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "czech-bridge",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Poblacion:\n",
    "    \n",
    "    def __init__(self): \n",
    "        self.coste = 0\n",
    "        self.media = 0\n",
    "        self.individuos = []\n",
    "#         self.elite = []\n",
    "#         self.tam_elite = tam_elite\n",
    "\n",
    "    def __eq__(self, other):\n",
    "        if len(self.individuos) != len(other.individuos):\n",
    "            return False\n",
    "\n",
    "#         ordenado1 = sorted(self.individuos)\n",
    "#         ordenado2 = sorted(other.individuos)\n",
    "\n",
    "#         for index in range(len(ordenado1)):\n",
    "#             if not ordenado1[index] in ordenado2[index]:\n",
    "#                 return False\n",
    "\n",
    "        for indv in self.individuos:\n",
    "            if not indv in other.individuos:\n",
    "                return False\n",
    "            \n",
    "        return True\n",
    "\n",
    "    \n",
    "    def add(self, cromosoma):\n",
    "        self.individuos.append(cromosoma)\n",
    "        self.coste += cromosoma.coste\n",
    "        self.media = self.coste / len(self.individuos)\n",
    "        \n",
    "        \n",
    "#         if len(self.elite) < self.tam_elite:\n",
    "#             self.elite.append(cromosoma)\n",
    "#         # Si es mejor que el peor de los elites  \n",
    "#         elif cromosoma < max(self.elite):\n",
    "#             self.elite.remove(max(self.elite))\n",
    "#             self.elite.append(cromosoma)\n",
    "    \n",
    "    def remove(self, cromosoma):\n",
    "        self.individuos.remove(cromosoma)\n",
    "        self.coste -= cromosoma.coste\n",
    "        self.media = self.coste / len(self.individuos)\n",
    "#         if cromosoma in self.elite:\n",
    "#             self.elite.remove(cromosoma)\n",
    "        del cromosoma\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "confident-potter",
   "metadata": {},
   "source": [
    "## Funciones auxiliares"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "annual-success",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Número de posiciones en las que varían los nodos del individuo 1 y 2\n",
    "# https://stackoverflow.com/questions/54172831/hamming-distance-between-two-strings-in-python\n",
    "def distancia_hamming(indv1, indv2):\n",
    "    return sum(nodo1 != nodo2 for nodo1, nodo2 in zip(indv1.camino, indv2.camino))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "insured-egypt",
   "metadata": {},
   "outputs": [],
   "source": [
    "def seleccion_torneo(poblacion, k):\n",
    "    \n",
    "    # Seleccionar k individuos aleatorios\n",
    "    individuos = random.sample(poblacion.individuos, k)\n",
    "    \n",
    "    # Devolver los dos mejores padres\n",
    "    return nsmallest(2,individuos)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "integrated-cisco",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Torneo restringido (RTS)\n",
    "# Seleciona el individuo más parecido a hijo\n",
    "# De entre k individuos aleatorios de la población\n",
    "# Problema: no tiene en consideración si el seleccionado es mejor (ver WAMS)\n",
    "def reemplazo_torneo(poblacion, k, hijo):\n",
    "    \n",
    "    # Si el peor individuo es una solución élite, se repite el torneo\n",
    "    seguir = True\n",
    "    intentos = 0\n",
    "    while(seguir):\n",
    "        # Seleccionar k individuos aleatorios\n",
    "        individuos = random.sample(poblacion.individuos, k)\n",
    "        \n",
    "        # Lista ordenada según la distancia de hamming al hijo\n",
    "        # https://stackoverflow.com/questions/27202942/sort-list-of-objects-by-return-of-object-method\n",
    "        # https://stackoverflow.com/questions/22483867/how-to-pass-multiple-arguments-to-the-method-key-of-sorted\n",
    "        individuos_ordenados = sorted(individuos, key=partial(distancia_hamming, indv2=hijo))\n",
    "        \n",
    "        # Elegimos al de menor distancia de hamming (más parecido al hijo)\n",
    "        individuo_reemplazar = individuos_ordenados[0]\n",
    "        \n",
    "        # Controlar que no reemplace a uno mejor\n",
    "        if hijo < individuo_reemplazar :\n",
    "            # Devolver el individuo a reemplazar\n",
    "            return individuo_reemplazar\n",
    "#         # Si no, se sigue intentando\n",
    "#         elif intentos < 3:\n",
    "#             continue\n",
    "        # Si no, no se produce reemplazo y se avanza a la creacion de otro hijo\n",
    "        else:\n",
    "            return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "taken-engineer",
   "metadata": {},
   "outputs": [],
   "source": [
    "# individuos = [Cromosoma([1,2,3,4],0), Cromosoma([1,2,4,3],1), Cromosoma([4,3,2,1],2)]\n",
    "# hijo = Cromosoma([1,2,3,4],0)\n",
    "# print(sorted(individuos, key=partial(distancia_hamming, indv2=hijo)))\n",
    "# print(individuos[0])\n",
    "# distancia_hamming(individuos[2], hijo)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "id": "musical-dryer",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Operador de Cruce: basado en Orden OX\n",
    "def cruce_OX(padre1, padre2, s, distancias):\n",
    "    \n",
    "    # Mantenemos una sublista del primer padre de tamaño s\n",
    "    # Indices de la sublista\n",
    "    pivote1 = int(random.randint(0, padre1.num_nodos-1))\n",
    "    pivote2 = (pivote1 + s) % padre1.num_nodos # Si se sale por la derecha, corrije\n",
    "        \n",
    "    # Si no se sale\n",
    "    if pivote1 < pivote2:\n",
    "        \n",
    "        hijo = [-1] * padre1.num_nodos # Inicialmente una lista de todo -1\n",
    "    \n",
    "        # Sublista del padre1 a mantener\n",
    "        sublista = padre1.camino[pivote1:pivote2]\n",
    "    \n",
    "        # Copiamos la sublista del primer padre en el hijo\n",
    "        hijo[pivote1:pivote2] = sublista\n",
    "        \n",
    "        # Subista de elementos del padre2 que no se repiten en la sublista\n",
    "        sublista2 = [i for i in padre2.camino if i not in sublista]\n",
    "        \n",
    "    else: # Si se sale por la derecha\n",
    "        \n",
    "        hijo = [-1] * padre1.num_nodos # Inicialmente una lista de todo -1\n",
    "        \n",
    "        # Sublistas del padre 1 a mantener\n",
    "        sublista1_1 = padre1.camino[pivote1:]\n",
    "        sublista1_2 = padre1.camino[:pivote2]\n",
    "        \n",
    "        # Subista de elementos del padre2 que no se repiten en las sublistas anteriores\n",
    "        sublista2 = [i for i in padre2.camino if i not in sublista1_1 and i not in sublista1_2]\n",
    "        \n",
    "        # Copiamos la sublista1 del primer padre en el hijo\n",
    "        hijo[pivote1:] = sublista1_1\n",
    "        # Copiamos la sublista2 del primer padre en el hijo\n",
    "        hijo[:pivote2] = sublista1_2\n",
    "        \n",
    "        \n",
    "    # Insertamos el resto de nodos del segundo padre\n",
    "    for i in range(len(hijo)):\n",
    "        if hijo[i] == -1:\n",
    "            hijo[i] = sublista2[0]\n",
    "            sublista2.remove(sublista2[0])\n",
    "    \n",
    "    \n",
    "    return Cromosoma(hijo, getCosteCamino(hijo, distancias))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "southeast-culture",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Sublista Aleatoria de Tamaño Fijo\n",
    "def mutacion(cromosoma, s, distancias):\n",
    "    numNodos = len(cromosoma.camino)\n",
    "    camino = cromosoma.camino.copy()\n",
    "    \n",
    "    # Indices de la sublista\n",
    "    pivote1 = random.randint(0, numNodos-2)\n",
    "    pivote2 = pivote1 + s\n",
    "    \n",
    "#     print(pivote, \", \", pivote2)\n",
    "    \n",
    "    # Como no es cíclica, si se sale por la derecha, hay que limitarla\n",
    "    if pivote2 > numNodos:\n",
    "        pivote2 = numNodos\n",
    "    \n",
    "    # Desordenar los nodos contenidos en la sublista\n",
    "    sublista = camino[pivote1:pivote2]\n",
    "\n",
    "    random.shuffle(sublista)\n",
    "    \n",
    "    camino[pivote1:pivote2] = sublista\n",
    "    \n",
    "    return Cromosoma(camino, getCosteCamino(camino, distancias))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "sunset-demographic",
   "metadata": {},
   "outputs": [],
   "source": [
    "# EJEMPLO\n",
    "# padre1 = [7,3,1,8,2,4,6,5]\n",
    "# padre2 = [4,3,2,8,6,7,1,5]\n",
    "\n",
    "# pivote1 = 2\n",
    "# pivote2 = 5\n",
    "# sublista = padre1[pivote1:pivote2]\n",
    "# print(\"sublista: \", sublista)\n",
    "\n",
    "# hijo = [-1] * len(padre1) # Inicialmente una lista de todo -1\n",
    "\n",
    "# # Copiamos la sublista del primer padre en el hijo\n",
    "# hijo[pivote1:pivote2] = sublista\n",
    "# print(hijo)\n",
    "\n",
    "# # Subista de elementos del padre2 que no se repiten en la sublista\n",
    "# sublista2 = [i for i in padre2 if i not in sublista]\n",
    "# print(\"sublista2: \", sublista2)\n",
    "\n",
    "# # Insertamos el resto de nodos del segundo padre\n",
    "# for i in range(len(hijo)):\n",
    "#     if hijo[i] == -1:\n",
    "#         hijo[i] = sublista2[0]\n",
    "#         sublista2.remove(sublista2[0])\n",
    "    \n",
    "\n",
    "# print(hijo)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "direct-temple",
   "metadata": {},
   "outputs": [],
   "source": [
    "def plt_dynamic(fig, x, y, ax, colors=['b']):\n",
    "    for color in colors:\n",
    "        ax.plot(x, y, color)\n",
    "    fig.canvas.draw()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "decent-disabled",
   "metadata": {},
   "source": [
    "## Algoritmo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "restricted-garbage",
   "metadata": {},
   "outputs": [],
   "source": [
    "def genetico_basico(semilla, num_nodos, distancias, tam_poblacion, k_torneo, tam_cruce, prob_mutacion, tam_mutacion, sembrar_greedy=False, fig=False, ax=False):\n",
    "    \n",
    "    # Representación\n",
    "    #ax.set_xlim(0,360) ; ax.set_ylim(-1,1)\n",
    "    xs, ys, ys2 = [], [], []\n",
    "    \n",
    "    # Aplicamos la semilla\n",
    "    random.seed(semilla)\n",
    "    \n",
    "    # Inicializamos los atributos de la clase Cromosoma\n",
    "    Cromosoma.num_nodos = num_nodos\n",
    "    Cromosoma.distancias = distancias\n",
    "\n",
    "    # Creamos la población inicial\n",
    "    poblacion = Poblacion()\n",
    "    \n",
    "    if sembrar_greedy:\n",
    "        for i in range(tam_poblacion-1):\n",
    "            poblacion.add(Cromosoma())\n",
    "\n",
    "        # Sembramos una solución greedy en la población\n",
    "        camino_greedy = algoritmoGreedy(distancias)\n",
    "        coste_greedy = getCosteCamino(camino_greedy, distancias)\n",
    "        poblacion.add(Cromosoma(camino_greedy, coste_greedy))\n",
    "        \n",
    "    else: # Todas las soluciones aleatorias\n",
    "        for i in range(tam_poblacion):\n",
    "            poblacion.add(Cromosoma())\n",
    "        \n",
    "    cruces_sin_mejorar = 0\n",
    "    poblacion_min_ant = min(poblacion.individuos)\n",
    "    parada = False\n",
    "    iteraciones = 0\n",
    "    while(not parada):\n",
    "        iteraciones += 1\n",
    "#         print(cruces_sin_mejorar)\n",
    "        # SELECCION\n",
    "        # Seleccionamos dos padres mediante torneo\n",
    "        padres = seleccion_torneo(poblacion, k_torneo)\n",
    "        \n",
    "        # CRUCE\n",
    "        # Obtenemos el hijo mediante el operador de cruce\n",
    "        # Tiene la mitad de probabilidad de parecerse al padre/madre\n",
    "        if random.random() < 0.5:\n",
    "            hijo = cruce_OX(padres[0], padres[1], tam_cruce, distancias)\n",
    "        else:\n",
    "            hijo = cruce_OX(padres[1], padres[0], tam_cruce, distancias)\n",
    "\n",
    "      \n",
    "        # MUTACIÓN\n",
    "        # Según una probabilidad, se mutarán el hijo\n",
    "        if random.random() < prob_mutacion:\n",
    "            hijo = mutacion(hijo, tam_mutacion, distancias)\n",
    "    \n",
    "        # REEMPLAZO\n",
    "        # Modelo estacionario: población fija y se reemplaza por torneo restringido (RTS)\n",
    "        individuo_reemplazo = reemplazo_torneo(poblacion, k_torneo, hijo)\n",
    "        \n",
    "        # Si el hijo no era lo suficientemente bueno como para mejorar el individuo seleccionado\n",
    "        # Se avanza a la siguiente iteración\n",
    "\n",
    "        if individuo_reemplazo is None:\n",
    "            cruces_sin_mejorar += 1\n",
    "            continue\n",
    "        \n",
    "        poblacion.remove(individuo_reemplazo)\n",
    "        poblacion.add(hijo)\n",
    "        \n",
    "        # REPRESENTACIÓN\n",
    "        xs.append(iteraciones)\n",
    "        ys.append(poblacion.media)\n",
    "        ys2.append(min(poblacion.individuos).coste)\n",
    "\n",
    "        # CRITERIO DE PARADA\n",
    "        # Si no mejoramos EL MEJOR INDV de la población\n",
    "        min_actual = min(poblacion.individuos)\n",
    "\n",
    "\n",
    "        if not min_actual < poblacion_min_ant:\n",
    "            cruces_sin_mejorar += 1\n",
    "\n",
    "        else:\n",
    "            cruces_sin_mejorar = 0\n",
    "\n",
    "        \n",
    "\n",
    "        #print(poblacion_media_ant, \" - \", poblacion.media)\n",
    "        poblacion_min_ant = min_actual\n",
    "        \n",
    "        # Si llegamos a 1000 cruces sin mejorar, paramos\n",
    "        if cruces_sin_mejorar >= 100000:\n",
    "            parada = True\n",
    "#             plt_dynamic(fig, xs, ys, ax)\n",
    "#             plt_dynamic(fig, xs, ys2, ax, ['r'])\n",
    "        \n",
    "\n",
    "            return [poblacion, iteraciones, xs, ys, ys2]  \n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "protective-album",
   "metadata": {},
   "source": [
    "# Algoritmo Genético CHC"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "higher-first",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Devuelve una nueva población desordenada dada una población\n",
    "def select_r(poblacion_ant):\n",
    "    \n",
    "    poblacion_new = Poblacion()\n",
    "    \n",
    "    individuos_shuflle = random.sample(poblacion_ant.individuos, len(poblacion_ant.individuos))\n",
    "    \n",
    "    for i in individuos_shuflle:\n",
    "        poblacion_new.add(i)\n",
    "        \n",
    "    return poblacion_new"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "saved-identity",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Devuelve una poblacion de los n mejores individuos dadas dos poblaciones\n",
    "def select_s(poblacion_ant, poblacion_new, n):\n",
    "    \n",
    "    poblacion = Poblacion()\n",
    "    \n",
    "    # Unimos las poblaciones\n",
    "    individuos = poblacion_ant.individuos + poblacion_new.individuos\n",
    "    \n",
    "    # Devolvemos los n mejores individuos\n",
    "    for i in nsmallest(n,individuos):\n",
    "        poblacion.add(i)\n",
    "    \n",
    "    return poblacion"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "complete-flour",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Reseteo de la población con el mejor individuo como plantilla\n",
    "def diverge(poblacion_ant, tam_poblacion, tam_mutacion, distancias):\n",
    "    \n",
    "    # Se escoge al mejor individuo para servir como plantilla\n",
    "    mejor_individuo = min(poblacion_ant.individuos)\n",
    "    \n",
    "    poblacion_new = Poblacion()\n",
    "    \n",
    "    # Añadimos al mejor\n",
    "    poblacion_new.add(mejor_individuo)\n",
    "    \n",
    "    # Creamos el resto usando el mejor como plantilla\n",
    "    # TODO: Usar 3 mejores individuos\n",
    "    for i in range(tam_poblacion - 1):\n",
    "            individuo_nuevo = mejor_individuo\n",
    "            # Mutamos tam_mutacion nodos\n",
    "            individuo_nuevo = mutacion(individuo_nuevo, tam_mutacion, distancias)\n",
    "            poblacion_new.add(individuo_nuevo)\n",
    "    \n",
    "    return poblacion_new"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "congressional-israel",
   "metadata": {},
   "outputs": [],
   "source": [
    "def seleccion_incesto(poblacion, umbral_cruce):\n",
    "    \n",
    "    # Contenedor de parejas a cruzar\n",
    "    parejas_cruce = []\n",
    "    \n",
    "    # Seleccionar de 2 en 2 los individuos\n",
    "    for i in range(0, math.floor(len(poblacion.individuos)/2)*2, 2):\n",
    "    \n",
    "        # Si se diferencian en más bits que el umbral de cruce\n",
    "        if distancia_hamming(poblacion.individuos[i], poblacion.individuos[i+1])/2 > umbral_cruce:\n",
    "            \n",
    "            # Se selecciona para ser cruzados\n",
    "            parejas_cruce.append([poblacion.individuos[i], poblacion.individuos[i+1]])\n",
    "            \n",
    "            \n",
    "    return parejas_cruce  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "strong-backing",
   "metadata": {},
   "outputs": [],
   "source": [
    "def cruce_HUX(padres, distancias):\n",
    "    padre1 = padres[0].camino.copy()\n",
    "    padre2 = padres[1].camino.copy()\n",
    "    \n",
    "    hijo1 = [-1] * len(padre1)\n",
    "    hijo2 = [-1] * len(padre2)   \n",
    "\n",
    "    # Mantener en los hijos la parte común de los padres\n",
    "    i=0\n",
    "    for nodo1, nodo2 in zip(padre1, padre2):\n",
    "        if nodo1 == nodo2:\n",
    "            hijo1[i] = nodo1\n",
    "            hijo2[i] = nodo2\n",
    "        i+=1\n",
    "    \n",
    "    # Eliminar los ya añadidos\n",
    "    for x in hijo1:\n",
    "        if x in padre1:\n",
    "            padre1.remove(x)\n",
    "        if x in padre2:\n",
    "            padre2.remove(x)\n",
    "    \n",
    "    # Copiar la mitad de la sublista del padre en el hijo1\n",
    "    for nodo in padre1[0 : round(len(padre1)/2)]:\n",
    "        # Insertamos el nodo en el primer hueco libre\n",
    "        hijo1[hijo1.index(-1)] = nodo\n",
    "    \n",
    "    # Copiar la mitad de la sublista del padre en el hijo2\n",
    "    for nodo in padre2[0 : round(len(padre2)/2)]:\n",
    "        # Insertamos el nodo en el primer hueco libre\n",
    "        hijo2[hijo2.index(-1)] = nodo\n",
    "        \n",
    "        \n",
    "    # Copiar el resto del otro padre, que no se repita\n",
    "    nodos_restantes1 = [x for x in padre2 if x not in hijo1]\n",
    "    while -1 in hijo1:\n",
    "        hijo1[hijo1.index(-1)] = nodos_restantes1[0]\n",
    "        nodos_restantes1.remove(nodos_restantes1[0])\n",
    "    \n",
    "    # Copiar el resto del otro padre, que no se repita\n",
    "    nodos_restantes2 = [x for x in padre1 if x not in hijo2]\n",
    "    while -1 in hijo2:\n",
    "        hijo2[hijo2.index(-1)] = nodos_restantes2[0]\n",
    "        nodos_restantes2.remove(nodos_restantes2[0]) \n",
    "\n",
    "    return [Cromosoma(hijo1, getCosteCamino(hijo1, distancias)), Cromosoma(hijo2, getCosteCamino(hijo2, distancias))] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "historical-greece",
   "metadata": {},
   "outputs": [],
   "source": [
    "def genetico_CHC(semilla, num_nodos, distancias, tam_poblacion, tam_mutacion, sembrar_greedy, fig=False, ax=False):\n",
    "    \n",
    "    # Representación\n",
    "    #ax.set_xlim(0,360) ; ax.set_ylim(-1,1)\n",
    "    xs, ys, ys2 = [], [], []\n",
    "    \n",
    "    # Aplicamos la semilla\n",
    "    random.seed(semilla)\n",
    "    \n",
    "    # Inicializamos los atributos de la clase Cromosoma\n",
    "    Cromosoma.num_nodos = num_nodos\n",
    "    Cromosoma.distancias = distancias\n",
    "\n",
    "    # Creamos la población inicial\n",
    "    poblacion_ant = Poblacion()\n",
    "    \n",
    "    if sembrar_greedy:\n",
    "        for i in range(tam_poblacion-1):\n",
    "            poblacion_ant.add(Cromosoma())\n",
    "\n",
    "        # Sembramos una solución greedy en la población\n",
    "        camino_greedy = algoritmoGreedy(distancias)\n",
    "        coste_greedy = getCosteCamino(camino_greedy, distancias)\n",
    "        poblacion_ant.add(Cromosoma(camino_greedy, coste_greedy))\n",
    "        \n",
    "    else: # Todas las soluciones aleatorias\n",
    "        for i in range(tam_poblacion):\n",
    "            poblacion_ant.add(Cromosoma())\n",
    "            \n",
    "    # Inicializamos la elite a los n mejores de la poblacion\n",
    "#     elite_ant = nsmallest(n_elite,individuos)\n",
    "    \n",
    "    # Inicializamos la distancia del umbral de cruce\n",
    "    umbral_cruce = num_nodos / 4\n",
    "    \n",
    "    \n",
    "    iteraciones = 0 \n",
    "    reinicializaciones = 0\n",
    "    parada = False\n",
    "    \n",
    "    while not parada:\n",
    "        \n",
    "        # Select_R: reordenar la poblacion antes de cruzarla\n",
    "        poblacion = select_r(poblacion_ant)\n",
    "        \n",
    "        # Nueva generación de individuos\n",
    "        poblacion_new = Poblacion()\n",
    "            \n",
    "        # RECOMBINE\n",
    "        # Seleccionar parejas que cumplan condición\n",
    "        parejas_cruce = seleccion_incesto(poblacion, umbral_cruce)\n",
    "        \n",
    "        # Si se van a producir curces\n",
    "        if len(parejas_cruce) > 0:\n",
    "\n",
    "            for pareja in parejas_cruce:\n",
    "                # CRUCE OX\n",
    "                hijo1 = cruce_OX(pareja[0], pareja[1], round(num_nodos*0.9), distancias)\n",
    "                hijo2 = cruce_OX(pareja[1], pareja[0], round(num_nodos*0.9), distancias)\n",
    "                \n",
    "                # Los añadimos a la nueva poblacion\n",
    "                poblacion_new.add(hijo1)\n",
    "                poblacion_new.add(hijo2)   \n",
    "\n",
    "            \n",
    "        # Select S: se queda con los mejores individuos de ambas poblaciones\n",
    "        poblacion = select_s(poblacion_ant, poblacion_new, tam_poblacion)\n",
    "\n",
    "        # Si no se producen cruces que mejoren el Select S de la población actual\n",
    "        if poblacion == poblacion_ant:\n",
    "            \n",
    "            umbral_cruce -= 1 # Bajamos el umbral\n",
    "            \n",
    "#         print(umbral_cruce)\n",
    "        # DIVERGE\n",
    "        if umbral_cruce <= 0:\n",
    "            poblacion = diverge(poblacion, tam_poblacion, tam_mutacion, distancias)\n",
    "            reinicializaciones += 1\n",
    "            umbral_cruce = round(num_nodos / 4)\n",
    "#             print(\"\\t\",reinicializaciones)\n",
    "            # TODO: r\n",
    "            \n",
    "        # REPRESENTACIÓN\n",
    "        xs.append(iteraciones)\n",
    "        ys.append(poblacion.media)\n",
    "        ys2.append(min(poblacion.individuos).coste)\n",
    "#         plt_dynamic(fig, xs, ys, ax)\n",
    "#         plt_dynamic(fig, xs, ys2, ax, ['r'])\n",
    "        \n",
    "        \n",
    "        poblacion_ant = poblacion\n",
    "        iteraciones += 1\n",
    "        \n",
    "        # CONDICION DE PARADA\n",
    "        if reinicializaciones >= 10:\n",
    "            parada = True\n",
    "            return [poblacion,iteraciones, xs, ys, ys2]\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "premier-burlington",
   "metadata": {},
   "source": [
    "# Algoritmo Genético Multimodal Secuencial"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "superior-topic",
   "metadata": {},
   "outputs": [],
   "source": [
    "# def clearing(poblacion, distancias, radio_nicho, tam_nicho):\n",
    "    \n",
    "#     individuos = sorted(poblacion.individuos)\n",
    "    \n",
    "#     for i in range(len(individuos)):\n",
    "        \n",
    "#         if individuos[i].coste != float('inf'):\n",
    "#             num_ganadores = 1\n",
    "            \n",
    "#             for j in range(i+1, len(poblacion.individuos)):\n",
    "#                 if individuos[j].coste != float('inf') and distancia_hamming(individuos[i], individuos[j]) < radio_nicho:\n",
    "                    \n",
    "#                     if num_ganadores < tam_nicho:\n",
    "#                         num_ganadores += 1\n",
    "#                     else:\n",
    "#                         individuos[j].coste = float('inf')\n",
    "    \n",
    "#     poblacion_new = Poblacion()\n",
    "    \n",
    "#     # Devolvemos la población eliminando los individuos marcados\n",
    "#     for individuo in individuos:\n",
    "#         if individuo.coste != float('inf'):\n",
    "#             poblacion_new.add(individuo)\n",
    "                        \n",
    "#     return poblacion_new\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "hawaiian-finish",
   "metadata": {},
   "outputs": [],
   "source": [
    "# def genetico_multimodal(semilla, num_nodos, distancias, tam_poblacion, k_torneo, tam_cruce, prob_mutacion, tam_mutacion, radio_nicho, tam_nicho, sembrar_greedy, fig, ax):\n",
    "    \n",
    "#     # Representación\n",
    "#     #ax.set_xlim(0,360) ; ax.set_ylim(-1,1)\n",
    "#     xs, ys, ys2 = [], [], []\n",
    "    \n",
    "#     # Aplicamos la semilla\n",
    "#     random.seed(semilla)\n",
    "    \n",
    "#     # Inicializamos los atributos de la clase Cromosoma\n",
    "#     Cromosoma.num_nodos = num_nodos\n",
    "#     Cromosoma.distancias = distancias\n",
    "\n",
    "#     # Creamos la población inicial\n",
    "#     poblacion = Poblacion()\n",
    "    \n",
    "#     if sembrar_greedy:\n",
    "#         for i in range(tam_poblacion-1):\n",
    "#             poblacion.add(Cromosoma())\n",
    "\n",
    "#         # Sembramos una solución greedy en la población\n",
    "#         camino_greedy = algoritmoGreedy(distancias)\n",
    "#         coste_greedy = getCosteCamino(camino_greedy, distancias)\n",
    "#         poblacion.add(Cromosoma(camino_greedy, coste_greedy))\n",
    "        \n",
    "#     else: # Todas las soluciones aleatorias\n",
    "#         for i in range(tam_poblacion):\n",
    "#             poblacion.add(Cromosoma())\n",
    "       \n",
    "#     cruces = 0\n",
    "#     cruces_sin_mejorar =0\n",
    "#     poblacion_min_ant = min(poblacion.individuos)\n",
    "#     parada = False\n",
    "#     iteraciones = 0\n",
    "#     while(not parada):\n",
    "        \n",
    "#         # CLEARING cada tam_poblacion/2 cruces\n",
    "#         if cruces % (round(tam_poblacion/2)) == 0:\n",
    "#             poblacion = clearing(poblacion, distancias, radio_nicho, tam_nicho)\n",
    "            \n",
    "        \n",
    "# #         print(cruces_sin_mejorar)\n",
    "#         # SELECCION\n",
    "#         # Seleccionamos dos padres mediante torneo\n",
    "#         padres = seleccion_torneo(poblacion, k_torneo)\n",
    "        \n",
    "#         # CRUCE\n",
    "#         # Obtenemos el hijo mediante el operador de cruce\n",
    "#         hijo = cruce_OX(padres[0], padres[1], tam_cruce, distancias)\n",
    "\n",
    "#         # MUTACIÓN\n",
    "#         # Según una probabilidad, se mutarán el hijo\n",
    "#         if random.random() < prob_mutacion:\n",
    "#             hijo = mutacion(hijo, tam_mutacion, distancias)\n",
    "    \n",
    "#         # REEMPLAZO\n",
    "#         # Modelo estacionario: población fija y se reemplaza por torneo restringido (RTS)\n",
    "#         individuo_reemplazo = reemplazo_torneo(poblacion, k_torneo, hijo)\n",
    "        \n",
    "#         # Si el hijo no era lo suficientemente bueno como para mejorar el individuo seleccionado\n",
    "#         # Se avanza a la siguiente iteración\n",
    "\n",
    "#         if individuo_reemplazo is None:\n",
    "#             cruces_sin_mejorar += 1\n",
    "#             continue\n",
    "        \n",
    "#         # Cruce y reemplazo efectivos\n",
    "#         cruces += 1\n",
    "        \n",
    "#         poblacion.remove(individuo_reemplazo)\n",
    "#         poblacion.add(hijo)\n",
    "        \n",
    "#         # REPRESENTACIÓN\n",
    "#         xs.append(iteraciones)\n",
    "#         ys.append(poblacion.media)\n",
    "#         ys2.append(min(poblacion.individuos).coste)\n",
    "\n",
    "#         # CRITERIO DE PARADA\n",
    "#         # Si no mejoramos EL MEJOR INDV de la población\n",
    "#         min_actual = min(poblacion.individuos)\n",
    "\n",
    "\n",
    "#         if not min_actual < poblacion_min_ant:\n",
    "#             cruces_sin_mejorar += 1\n",
    "\n",
    "#         else:\n",
    "#             cruces_sin_mejorar = 0\n",
    "\n",
    "#         iteraciones += 1\n",
    "\n",
    "#         #print(poblacion_media_ant, \" - \", poblacion.media)\n",
    "#         poblacion_min_ant = min_actual\n",
    "        \n",
    "#         # Si llegamos a 1000 iteraciones sin mejorar, paramos\n",
    "#         if cruces_sin_mejorar >= 100000:\n",
    "#             parada = True\n",
    "# #             plt_dynamic(fig, xs, ys, ax)\n",
    "# #             plt_dynamic(fig, xs, ys2, ax, ['r'])\n",
    "        \n",
    "\n",
    "#             return [poblacion, iteraciones, xs, ys, ys2]  \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "id": "valued-gregory",
   "metadata": {},
   "outputs": [],
   "source": [
    "def genetico_basico_secuencial(semilla, num_nodos, distancias, tam_poblacion, k_torneo, tam_cruce, prob_mutacion, tam_mutacion, sembrar_greedy, soluciones_anteriores, radio_nicho):\n",
    "    \n",
    "    # Aplicamos la semilla\n",
    "    random.seed(semilla)\n",
    "\n",
    "    # Inicializamos los atributos de la clase Cromosoma\n",
    "    Cromosoma.num_nodos = num_nodos\n",
    "    Cromosoma.distancias = distancias\n",
    "    \n",
    "    # Creamos la población inicial\n",
    "    poblacion = Poblacion()\n",
    "    \n",
    "    if sembrar_greedy:\n",
    "        for i in range(tam_poblacion-1):\n",
    "            poblacion.add(Cromosoma())\n",
    "\n",
    "        # Sembramos una solución greedy en la población\n",
    "        camino_greedy = algoritmoGreedy(distancias)\n",
    "        coste_greedy = getCosteCamino(camino_greedy, distancias)\n",
    "        poblacion.add(Cromosoma(camino_greedy, coste_greedy))\n",
    "        \n",
    "    else: # Todas las soluciones aleatorias\n",
    "        for i in range(tam_poblacion):\n",
    "            poblacion.add(Cromosoma())\n",
    "        \n",
    "    cruces_sin_mejorar = 0\n",
    "    poblacion_min_ant = min(poblacion.individuos)\n",
    "    parada = False\n",
    "    iteraciones = 0\n",
    "    while(not parada):\n",
    "        \n",
    "        # SELECCION\n",
    "        # Seleccionamos dos padres mediante torneo\n",
    "        padres = seleccion_torneo(poblacion, k_torneo)\n",
    "        \n",
    "        # CRUCE\n",
    "        # Obtenemos el hijo mediante el operador de cruce\n",
    "        hijo = cruce_OX(padres[0], padres[1], tam_cruce, distancias)\n",
    "        \n",
    "        # PENALIZACIÓN SEGÚN DISTANCIA HAMMING\n",
    "        for solucion_anterior in soluciones_anteriores:\n",
    "            distancia = distancia_hamming(solucion_anterior, hijo)\n",
    "            if distancia < radio_nicho:\n",
    "                \n",
    "                hijo.coste *= radio_nicho / (distancia + 0.01)\n",
    "                break # Se penaliza solo una vez\n",
    "\n",
    "        # MUTACIÓN\n",
    "        # Según una probabilidad, se mutarán el hijo\n",
    "        if random.random() < prob_mutacion:\n",
    "            hijo = mutacion(hijo, tam_mutacion, distancias)\n",
    "    \n",
    "        # REEMPLAZO\n",
    "        # Modelo estacionario: población fija y se reemplaza por torneo restringido (RTS)\n",
    "        individuo_reemplazo = reemplazo_torneo(poblacion, k_torneo, hijo)\n",
    "        \n",
    "        # Si el hijo no era lo suficientemente bueno como para mejorar el individuo seleccionado\n",
    "        # Se avanza a la siguiente iteración\n",
    "        if individuo_reemplazo is None:\n",
    "            cruces_sin_mejorar += 1\n",
    "            continue\n",
    "        \n",
    "        poblacion.remove(individuo_reemplazo)\n",
    "        poblacion.add(hijo)\n",
    "\n",
    "\n",
    "        # CRITERIO DE PARADA\n",
    "        # Si no mejoramos EL MEJOR INDV de la población\n",
    "        min_actual = min(poblacion.individuos)\n",
    "\n",
    "        if not min_actual < poblacion_min_ant:\n",
    "            cruces_sin_mejorar += 1\n",
    "\n",
    "        else:\n",
    "            cruces_sin_mejorar = 0\n",
    "\n",
    "        iteraciones += 1\n",
    "\n",
    "        #print(poblacion_media_ant, \" - \", poblacion.media)\n",
    "        poblacion_min_ant = min_actual\n",
    "        \n",
    "        # Si llegamos a 1000 iteraciones sin mejorar, paramos\n",
    "        if cruces_sin_mejorar >= 100000:\n",
    "            parada = True\n",
    "            mejor_individuo = min(poblacion.individuos)\n",
    "            print(mejor_individuo)\n",
    "            return mejor_individuo # Devolvemos el mejor individuo\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "backed-automation",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "id": "southeast-earthquake",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "welsh-findings",
   "metadata": {},
   "outputs": [],
   "source": [
    "import import_ipynb\n",
    "from hormigas import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "included-promise",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Hormiga:\n",
    "    \n",
    "    # Métodos de clase\n",
    "    def set_nodos_distancias(num_nodos, distancias):\n",
    "        Hormiga.num_nodos = num_nodos\n",
    "        Hormiga.distancias = distancias\n",
    "    \n",
    "    # Métodos de instancias\n",
    "    \n",
    "    # Operador minimo\n",
    "    # https://stackoverflow.com/questions/3621826/python-minimum-of-a-list-of-instance-variables\n",
    "    def __lt__(self, other):\n",
    "        return self.coste < other.coste\n",
    "    \n",
    "    def __eq__(self, other):\n",
    "        return self.camino == other.camino\n",
    "    \n",
    "    def __str__(self):\n",
    "        return str(self.coste) \n",
    "    \n",
    "    def __repr__(self):\n",
    "        return str(self.coste)\n",
    "    \n",
    "    def __init__(self, *args):\n",
    "        \n",
    "        if not Hormiga.num_nodos or not Hormiga.distancias:\n",
    "            raise TypeError(\"No se ha inicializado el num nodos o las distancias para la clase Hormiga\") \n",
    "        \n",
    "        if len(args) == 0 or len(args) == 1 and args[0]==None:\n",
    "            # Hormiga con nodo inicial aleatorio\n",
    "            self.camino = [random.randint(0,Hormiga.num_nodos-1)]\n",
    "            self.coste = 0\n",
    "            \n",
    "        elif len(args) == 1:\n",
    "            # Hormiga con nodo inicial\n",
    "            self.camino = [args[0]]\n",
    "            self.coste = 0\n",
    "            \n",
    "        elif len(args) == 2:\n",
    "            self.camino = args[0]\n",
    "            self.coste = args[1]        \n",
    "        else:\n",
    "            raise TypeError(\"Número de argumentos no válido, solo 0 ó 2\") \n",
    "            \n",
    "    def add(self, nodo):\n",
    "        self.coste += self.distancias[self.camino[-1]][nodo]\n",
    "        self.camino.append(nodo)\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "fitted-summary",
   "metadata": {},
   "outputs": [],
   "source": [
    "def algoritmo_SH(semilla, num_nodos, distancias, num_hormigas, num_iteraciones, feromona_ini, heuristica, alpha, beta, evaporacion, nodo_inicial=None):\n",
    "    \n",
    "    # Aplicamos la semilla\n",
    "    random.seed(semilla)\n",
    "    \n",
    "    # Representacion\n",
    "    xs, ys = [], []\n",
    "    \n",
    "    # Inicializamos los atributos de la clase Hormiga\n",
    "    Hormiga.num_nodos = num_nodos\n",
    "    Hormiga.distancias = distancias\n",
    "    \n",
    "    # Inicializamos la matriz de feromonas\n",
    "    feromona = [[feromona_ini]*len(nodos) for i in range(len(nodos))]\n",
    "    \n",
    "    mejor_global = None\n",
    "    for it in range(num_iteraciones):\n",
    "        \n",
    "        # Inicializamos las hormigas al nodo inicial\n",
    "        hormigas = []\n",
    "        for k in range(num_hormigas):\n",
    "            hormigas.append(Hormiga(nodo_inicial))\n",
    "        \n",
    "        # Construcción de soluciones por las hormigas\n",
    "        for i in range(num_hormigas):\n",
    "            for k in range(num_nodos-1):\n",
    "                # Añadimos el nodo resultante de aplicar la regla de transición\n",
    "                hormigas[i].add(regla_transicion(hormigas[i], feromona, heuristica, alpha, beta))\n",
    "            \n",
    "        # Actualización de feromona: Aporte y evaporación\n",
    "        for i in range(num_nodos):\n",
    "            for j in range(num_nodos):\n",
    "                feromona[i][j] = actualizacion_feromona(feromona[i][j], hormigas, evaporacion, i, j)\n",
    "                \n",
    "        # Actualización de la mejor solucion global\n",
    "        mejor_actual = min(hormigas)\n",
    "\n",
    "        if mejor_global is None or mejor_actual < mejor_global:\n",
    "            mejor_global = mejor_actual\n",
    "            \n",
    "        # Representación\n",
    "        xs.append(it)\n",
    "        ys.append(mejor_global.coste)\n",
    "            \n",
    "    return [mejor_global, semilla, xs, ys]"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}