Coloración óptima de un mapa político con el algoritmo Tabu Search

En este trabajo explico el algoritmo Tabu Search que utilicé con Paula Sanín Castro para resolver el problema de coloración de un mapa político. Éste se define como un problema de optimización donde se trata de usar el mínimo número de colores posible para pintar un mapa de países sin que hayan países adyacentes con el mismo color. Con el método utilizado se consigue llegar al mínimo de 4 colores que establece el teorema de los cuatro colores.


El método que utilizamos para resolver el problema es el propuesto por Hertz y Werra (1987). La idea general del método es empezar generando una solución inicial factible donde cada país tenga un color. A partir de ahí se reduce el número de colores y se distribuyen aleatoriamente entre los países. Después se generan distribuciones 'vecinas' cambiando de color un país aleatorio que tenga frontera con otro del mismo color y se selecciona la distribución vecina que minimiza el número de pares de países adyacentes con el mismo color. Si esa distribución de colores es factible, es decir, no hace que hayan dos países adyacentes con el mismo color, se reduce el número de colores de nuevo, se añade el movimiento del país de un color a otro en la lista tabú y se vuelven a realizar los pasos anteriores. Se repiten estos pasos hasta que no se pueda reducir más el número de colores sin incumplir la condición de países adyacentes. Ahí se consigue llegar al número mínimo de colores.

El algoritmo se utilizó para realizar la coloración de un mapa de 31 países de Europa. El mapa se trató como un grafo \(G(E,V)\) donde los nodos \(V\) representan los paises y las aristas \(E\) las fronteras entre los países. Cada conjunto de países con un mismo color se denota como \(V_i\) donde \(i=1,2,..,k\). \(E(V_i)\) son las arista del conjunto de países con el color \(i\) que empieza y terminan en el mismo \(V_i\), es decir, el número de fronteras de países con el mismo color.

En cada iteración del algoritmo se obtiene una solución inicial que consiste en un agrupamiento \(s\) de países por colores dado el número de colores \(k\) que se esté usando, por lo que en la primera iteración habrán 31 grupos de países en el agrupamiento inicial.

Se genera la lista \(E(V)\) formada por las \(E(V_i)\). Éstos están formados por pares de países que tienen el color \(i\) y son adyacentes, dada la agrupación generada. También se genera una lista tabú aleatoria con 7 elementos (pares país-color).

Después se generan en cada iteración un número \(b\) de agrupamientos vecinos \(s'\) a partir del agrupamiento \(s\) obtenido al principio de la iteración. En la generación de los agrupamientos hay que tener en cuenta que éstos no se hayan creado haciendo un movimiento que esté en la lista tabú. Se elije el agrupamiento vecino que minimiza el tamaño de la lista \(E(V)\), es decir, que minimiza la cantidad de aristas dentro de un mismo conjunto \(i\). Para que el agrupamiento vecino elegido sea factible es necesario que no hayan países adyacentes con el mismo color. En el código siguiente aparece la función utilizada para determinar el número de aristas que pertenecen a un mismo conjunto/color.

Por tanto, en cada iteración del algoritmo se intenta resolver un problema de minimización del número de aristas dentro de un conjunto \(i\) dado un número de colores \(k\). Cuando en una iteración se consigue agrupar los países de modo que no hayan países adyacentes con el mismo color se reduce el número de colores a la mitad y se intenta volver a resolver el problema. Cuando no se consigue una solución factibe se incrementa el número de colores en 1 hasta llegar a la solución óptima.

En el gráfico siguiente se puede ver resultado obtenido en cada iteración.

Figura 1. Mapas generados con el algoritmo Tabu Search

El algoritmo empieza asignando 31 colores, después los reduce a la mitad, 16, y vuelve a asignar los colores. Repite este proceso hasta que llega a 2 colores, donde no puede encontrar una solución factible. A partir de ahí aumenta los colores en 1 y los distribuye hasta llegar al mínimo posible que devuelve una solución factible, que es 4.

Esta web utiliza cookies para obtener datos estadísticos de la navegación de sus usuarios. Si continúas navegando se considera que aceptas su uso. Más información Cerrar