GRASP Simples para o TSP

tsp.py

"""TSP."""

import math
import random
import sys
import timeit
from collections import defaultdict
from itertools import chain
from typing import List, Optional, Tuple

Grafo = List[List[float]]
Caminho = List[int]
Vertice = int


class Timer:
    """Medição de tempo."""

    def __init__(self):
        """Inicializa o timer com tempo 0."""
        self.reset()

    def reset(self):
        """Reseta o timer."""
        self.start = timeit.default_timer()

    def elapsed(self) -> float:
        """Retorna o tempo desde que o timer foi resetado pela última vez."""
        return timeit.default_timer() - self.start


def vizinho_mais_proximo(grafo: Grafo) -> Caminho:
    """Gera um caminho através da heurística Vizinho Mais Próximo.

    O caminho satisfaz as restrições do TSP: graus de entrada e saída iguais
    a 1, subcaminhos não são permitidos.
    """
    num_vertices = len(grafo)
    caminho = []  # type: List[Vertice]
    marcados = [False] * num_vertices

    inicial = random.randint(0, num_vertices-1)
    caminho.append(inicial)
    marcados[inicial] = True

    while not all(marcados):
        atual = marcados[-1]
        adjacentes = grafo[atual]
        abertos = [(vertice, peso) for vertice, (peso, marcado)
                   in enumerate(zip(adjacentes, marcados)) if not marcado]
        menor, _ = min(abertos, key=lambda p: p[1])

        caminho.append(menor)
        marcados[menor] = True

    caminho.append(inicial)
    return caminho


def vizinho_mais_proximo_grasp(grafo: Grafo, alfa: float) -> Optional[Caminho]:
    """Gera um caminho através da heurística Vizinho Mais Próximo.

    O caminho satisfaz as restrições do TSP: graus de entrada e saída iguais
    a 1, subcaminhos não são permitidos.
    """
    num_vertices = len(grafo)
    caminho = []  # type: List[Vertice]
    marcados = [False] * num_vertices

    inicial = random.randint(0, num_vertices-1)
    caminho.append(inicial)
    marcados[inicial] = True

    while not all(marcados):
        atual = marcados[-1]
        adjacentes = grafo[atual]
        abertos = [(vertice, peso) for vertice, (peso, marcado)
                   in enumerate(zip(adjacentes, marcados)) if not marcado]
        abertos.sort(key=lambda p: p[1])

        num_candidatos = math.ceil(len(abertos) * alfa)
        if num_candidatos == 0:
            return None
        candidatos = abertos[:num_candidatos]

        proximo, _ = random.choice(candidatos)
        caminho.append(proximo)
        marcados[proximo] = True

    caminho.append(inicial)
    return caminho


def grasp_construcao(grafo: Grafo, alfa: float) -> Caminho:
    """Constrói uma solução através de uma heurística semi-gulosa."""
    caminho = vizinho_mais_proximo_grasp(grafo, alfa)
    while not caminho:
        caminho = vizinho_mais_proximo_grasp(grafo, alfa)

    return caminho


def grasp_busca_local(grafo: Grafo, caminho: Caminho):
    """Tenta melhorar `caminho` com a 2-opt."""
    atual = caminho
    nova = grasp_busca_local_vizinho(grafo, atual)
    while nova:
        atual = nova
        nova = grasp_busca_local_vizinho(grafo, atual)
    return atual


def grasp_busca_local_vizinho(grafo: Grafo, caminho: Caminho
                              ) -> Optional[Caminho]:
    """Tenta encontrar um vizinho através da aplicação da 2-opt."""
    num_vertices = len(caminho)
    fo_best = calcula_fo(grafo, caminho)

    for i in range(num_vertices):
        for k in range(num_vertices-1):
            nova = two_opt_swap(caminho[:], i, k)
            fo_nova = calcula_fo(grafo, nova)
            if fo_nova < fo_best:
                return nova


def two_opt_swap(caminho: Caminho, i: Vertice, k: Vertice) -> Caminho:
    """Aplica o cruzamento de duas rotas.

    Remove o último vértice do caminho (que é igual ao primeiro) para diminuir
    o número de soluções infactíveis resultantes. O novo final será adicionado
    depois da geração do novo caminho.
    """
    caminho.pop()
    novo = list(chain(caminho[:i], reversed(caminho[i:k]), caminho[k:]))
    novo.append(novo[0])
    return novo


def grasp(grafo: Grafo, alfa: float, timeout: float, num_vizinhos: int,
          max_iter: int) -> Tuple[Optional[Caminho], int]:
    """Executa o GRASP."""
    best = None  # type: Optional[Caminho]
    fo_best = 0  # type: float
    t = Timer()
    it = 0
    it_melhor = 0

    while it - it_melhor <= max_iter and t.elapsed() < timeout:
        if it % (max_iter+1) == 0:
            print("i:", it)

        atual = grasp_construcao(grafo, alfa)
        for _ in range(num_vizinhos):
            vizinho = grasp_busca_local(grafo, atual)
            fo_vizinho = calcula_fo(grafo, vizinho)
            if best is None or fo_vizinho < fo_best:
                best, fo_best = vizinho, fo_vizinho
                it_melhor = it

        it += 1

    return best, it_melhor


def frequencias(caminho: Caminho) -> defaultdict:
    """Calcula as frequências dos vértices no caminho."""
    counter = defaultdict(int)  # type: defaultdict[int, int]
    for i in caminho:
        counter[i] += 1
    return counter


def is_factivel(caminho: Caminho) -> bool:
    """Verifica se o `caminho` é factível.

    A restrição analisada é se um vértice aparece mais de uma vez no caminho,
    com exceção do inicial, que pode aparecer duas vezes.
    """
    freq = frequencias(caminho)
    for k, v in freq.items():
        if (v == 2 and caminho[0] != k) or v > 2:
            return False

    return True


def calcula_fo(grafo: Grafo, caminho: Caminho) -> float:
    """Calcula o custo de um caminho no grafo.

    Retorna inf se o caminho for infactível. Caminhos que contenham arestas
    inexistentes terão valor maior ou igual a inf, uma vez que o peso de arestas
    inexistentes é inf.
    """
    if not is_factivel(caminho):
        return math.inf

    return sum(grafo[src][dst] for src, dst in zip(caminho, caminho[1:]))


def find_shortest(grafo: Grafo, n: int) -> Caminho:
    """Gera `n` soluções aleatoriamente e retorna a melhor."""
    return min((vizinho_mais_proximo(grafo) for _ in range(n)),
               key=lambda s: calcula_fo(grafo, s))


def grafo_from_arquivo(file: str) -> Grafo:
    """Carrega um grafo a partir de um arquivo contendo uma matriz de pesos."""
    with open(file) as f:
        linhas = f.readlines()
    return [[float(x) for x in linha.split()] for linha in linhas]


def main():
    """Main."""
    if len(sys.argv) == 1:
        grafo = [
            [0, 1, 4, 2],
            [1, 0, 2, 5],
            [4, 2, 0, 3],
            [2, 5, 3, 0]
        ]  # type: Grafo
    elif len(sys.argv) == 2:
        grafo = grafo_from_arquivo(sys.argv[1])
    else:
        print("Opção inválida")
        sys.exit()

    # caminho = vizinho_mais_proximo(grafo_ex1)
    # fo = calcula_fo(grafo_ex1, caminho)

    caminho, it = grasp(grafo=grafo, alfa=0.5, timeout=math.inf,
                        num_vizinhos=5, max_iter=20)

    print("Caminho:", caminho)
    print("Iteração alvo:", it)
    print("fo =", calcula_fo(grafo, caminho))

if __name__ == '__main__':
    main()