cc_SOS_ACO___apenas_kroA100.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "v0kEn7CvKBfs"
      },
      "source": [
        "# Tá rodando"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LSN7flsjOPqs"
      },
      "source": [
        "## Instalando bibliotecas necessárias"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "mITOIUQTfku_"
      },
      "source": [
        "https://github.com/mastqe/tsplib/blob/master/kroA100.tsp\n",
        "\n",
        "Essa aqui instala a biblioteca que puxa os dados das cidades do caixeiro viajante desse repositório no Github."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "zj8dkaxDkyvN",
        "outputId": "06611e91-80ae-49c8-d45e-7412bc6c83a5"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Collecting tsplib95\n",
            "  Downloading tsplib95-0.7.1-py2.py3-none-any.whl (25 kB)\n",
            "Requirement already satisfied: Click>=6.0 in /usr/local/lib/python3.10/dist-packages (from tsplib95) (8.1.7)\n",
            "Collecting Deprecated~=1.2.9 (from tsplib95)\n",
            "  Downloading Deprecated-1.2.14-py2.py3-none-any.whl (9.6 kB)\n",
            "Collecting networkx~=2.1 (from tsplib95)\n",
            "  Downloading networkx-2.8.8-py3-none-any.whl (2.0 MB)\n",
            "\u001b[2K     \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m2.0/2.0 MB\u001b[0m \u001b[31m10.9 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25hCollecting tabulate~=0.8.7 (from tsplib95)\n",
            "  Downloading tabulate-0.8.10-py3-none-any.whl (29 kB)\n",
            "Requirement already satisfied: wrapt<2,>=1.10 in /usr/local/lib/python3.10/dist-packages (from Deprecated~=1.2.9->tsplib95) (1.14.1)\n",
            "Installing collected packages: tabulate, networkx, Deprecated, tsplib95\n",
            "  Attempting uninstall: tabulate\n",
            "    Found existing installation: tabulate 0.9.0\n",
            "    Uninstalling tabulate-0.9.0:\n",
            "      Successfully uninstalled tabulate-0.9.0\n",
            "  Attempting uninstall: networkx\n",
            "    Found existing installation: networkx 3.3\n",
            "    Uninstalling networkx-3.3:\n",
            "      Successfully uninstalled networkx-3.3\n",
            "\u001b[31mERROR: pip's dependency resolver does not currently take into account all the packages that are installed. This behaviour is the source of the following dependency conflicts.\n",
            "torch 2.3.0+cu121 requires nvidia-cublas-cu12==12.1.3.1; platform_system == \"Linux\" and platform_machine == \"x86_64\", which is not installed.\n",
            "torch 2.3.0+cu121 requires nvidia-cuda-cupti-cu12==12.1.105; platform_system == \"Linux\" and platform_machine == \"x86_64\", which is not installed.\n",
            "torch 2.3.0+cu121 requires nvidia-cuda-nvrtc-cu12==12.1.105; platform_system == \"Linux\" and platform_machine == \"x86_64\", which is not installed.\n",
            "torch 2.3.0+cu121 requires nvidia-cuda-runtime-cu12==12.1.105; platform_system == \"Linux\" and platform_machine == \"x86_64\", which is not installed.\n",
            "torch 2.3.0+cu121 requires nvidia-cudnn-cu12==8.9.2.26; platform_system == \"Linux\" and platform_machine == \"x86_64\", which is not installed.\n",
            "torch 2.3.0+cu121 requires nvidia-cufft-cu12==11.0.2.54; platform_system == \"Linux\" and platform_machine == \"x86_64\", which is not installed.\n",
            "torch 2.3.0+cu121 requires nvidia-curand-cu12==10.3.2.106; platform_system == \"Linux\" and platform_machine == \"x86_64\", which is not installed.\n",
            "torch 2.3.0+cu121 requires nvidia-cusolver-cu12==11.4.5.107; platform_system == \"Linux\" and platform_machine == \"x86_64\", which is not installed.\n",
            "torch 2.3.0+cu121 requires nvidia-cusparse-cu12==12.1.0.106; platform_system == \"Linux\" and platform_machine == \"x86_64\", which is not installed.\n",
            "torch 2.3.0+cu121 requires nvidia-nccl-cu12==2.20.5; platform_system == \"Linux\" and platform_machine == \"x86_64\", which is not installed.\n",
            "torch 2.3.0+cu121 requires nvidia-nvtx-cu12==12.1.105; platform_system == \"Linux\" and platform_machine == \"x86_64\", which is not installed.\n",
            "bigframes 1.8.0 requires tabulate>=0.9, but you have tabulate 0.8.10 which is incompatible.\u001b[0m\u001b[31m\n",
            "\u001b[0mSuccessfully installed Deprecated-1.2.14 networkx-2.8.8 tabulate-0.8.10 tsplib95-0.7.1\n"
          ]
        }
      ],
      "source": [
        "!pip install tsplib95"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "D4usipmMWCEp"
      },
      "source": [
        "Esse código verifica se a biblioteca foi instalada com sucesso."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "background_save": true
        },
        "id": "V40QjYSP5G2A",
        "outputId": "7d6caf9f-6050-4f06-8500-4ef630c3dc4b"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Name: tsplib95\n",
            "Version: 0.7.1\n",
            "Summary: TSPLIB95 works with TSPLIB95 files.\n",
            "Home-page: https://github.com/rhgrant10/tsplib95\n",
            "Author: Robert Grant\n",
            "Author-email: rhgrant10@gmail.com\n",
            "License: Apache Software License 2.0\n",
            "Location: /usr/local/lib/python3.10/dist-packages\n",
            "Requires: Click, Deprecated, networkx, tabulate\n",
            "Required-by: \n"
          ]
        }
      ],
      "source": [
        "!pip show tsplib95"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "DScTOm0nWIvQ"
      },
      "source": [
        "Esse outro instala biblioteca de requisição. Para baixar o arquivo de dados do problema TSP"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "MzHN0JUA4mQt",
        "outputId": "0f0e04c4-f1bb-4264-f8bb-81a7ed4611d3"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Requirement already satisfied: requests in /usr/local/lib/python3.10/dist-packages (2.31.0)\n",
            "Requirement already satisfied: charset-normalizer<4,>=2 in /usr/local/lib/python3.10/dist-packages (from requests) (3.3.2)\n",
            "Requirement already satisfied: idna<4,>=2.5 in /usr/local/lib/python3.10/dist-packages (from requests) (3.7)\n",
            "Requirement already satisfied: urllib3<3,>=1.21.1 in /usr/local/lib/python3.10/dist-packages (from requests) (2.0.7)\n",
            "Requirement already satisfied: certifi>=2017.4.17 in /usr/local/lib/python3.10/dist-packages (from requests) (2024.6.2)\n"
          ]
        }
      ],
      "source": [
        "!pip install requests"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "TT2onMdmWvhc"
      },
      "source": [
        "Esse código verifica se a biblioteca `requests` foi instalada com sucesso."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "GQP3fMr6-gXc",
        "outputId": "427408a7-da36-47aa-ec9b-50ab7fb720d1"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Name: requests\n",
            "Version: 2.31.0\n",
            "Summary: Python HTTP for Humans.\n",
            "Home-page: https://requests.readthedocs.io\n",
            "Author: Kenneth Reitz\n",
            "Author-email: me@kennethreitz.org\n",
            "License: Apache 2.0\n",
            "Location: /usr/local/lib/python3.10/dist-packages\n",
            "Requires: certifi, charset-normalizer, idna, urllib3\n",
            "Required-by: bigframes, CacheControl, community, earthengine-api, fastai, folium, gcsfs, gdown, geocoder, google-api-core, google-cloud-bigquery, google-cloud-storage, google-colab, huggingface-hub, kaggle, kagglehub, moviepy, music21, pandas-datareader, panel, pooch, pymystem3, requests-oauthlib, spacy, Sphinx, tensorboard, tensorflow-datasets, torchtext, transformers, tweepy, weasel, yfinance\n"
          ]
        }
      ],
      "source": [
        "!pip show requests"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Czg95XNmW5Ph"
      },
      "source": [
        "Esse outro instala biblioteca para representar o problema TSP como um grafo. Foi sugestão do Gemini"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "-SvZnJqmB7Bu",
        "outputId": "e8202285-cc82-48e0-99e1-c1528b8e55c0"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Requirement already satisfied: networkx in /usr/local/lib/python3.10/dist-packages (2.8.8)\n"
          ]
        }
      ],
      "source": [
        "!pip install networkx"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_qk2h7_8OU9F"
      },
      "source": [
        "## Código funcional kroA100\n",
        "- 50 gerações + 10 SOS iterações\n",
        "- se vcs precisarem mudar, fica na linha **256**.\n",
        "- parâmetros do SOS_ACO\n",
        "  * `num_ants`=10,\n",
        "  * `num_iterations`=50,\n",
        "  * `decay`=0.95,\n",
        "  * `alpha`=1.0,\n",
        "  * `beta`=2.0,\n",
        "  * `population_size`=20,\n",
        "  * `sos_iterations`=10"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "BPT9cnxYIj4L",
        "outputId": "6193fc84-3db4-4d3b-9f63-2c301791c6ef"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Iteration 1/50, Best Distance: 52290.0\n",
            "Iteration 2/50, Best Distance: 51473.0\n",
            "Iteration 3/50, Best Distance: 51473.0\n",
            "Iteration 4/50, Best Distance: 51473.0\n",
            "Iteration 5/50, Best Distance: 51473.0\n",
            "Iteration 6/50, Best Distance: 51473.0\n",
            "Iteration 7/50, Best Distance: 51473.0\n",
            "Iteration 8/50, Best Distance: 51473.0\n",
            "Iteration 9/50, Best Distance: 51473.0\n",
            "Iteration 10/50, Best Distance: 51473.0\n",
            "Iteration 11/50, Best Distance: 47747.0\n",
            "Iteration 12/50, Best Distance: 47747.0\n",
            "Iteration 13/50, Best Distance: 47747.0\n",
            "Iteration 14/50, Best Distance: 47747.0\n",
            "Iteration 15/50, Best Distance: 47747.0\n",
            "Iteration 16/50, Best Distance: 47747.0\n",
            "Iteration 17/50, Best Distance: 47747.0\n",
            "Iteration 18/50, Best Distance: 47747.0\n",
            "Iteration 19/50, Best Distance: 47747.0\n",
            "Iteration 20/50, Best Distance: 47747.0\n",
            "Iteration 21/50, Best Distance: 47747.0\n",
            "Iteration 22/50, Best Distance: 47747.0\n",
            "Iteration 23/50, Best Distance: 47747.0\n",
            "Iteration 24/50, Best Distance: 47747.0\n",
            "Iteration 25/50, Best Distance: 47747.0\n",
            "Iteration 26/50, Best Distance: 47747.0\n",
            "Iteration 27/50, Best Distance: 47747.0\n",
            "Iteration 28/50, Best Distance: 47747.0\n",
            "Iteration 29/50, Best Distance: 47747.0\n",
            "Iteration 30/50, Best Distance: 47747.0\n",
            "Iteration 31/50, Best Distance: 47747.0\n",
            "Iteration 32/50, Best Distance: 47747.0\n",
            "Iteration 33/50, Best Distance: 47747.0\n",
            "Iteration 34/50, Best Distance: 47747.0\n",
            "Iteration 35/50, Best Distance: 46940.0\n",
            "Iteration 36/50, Best Distance: 46940.0\n",
            "Iteration 37/50, Best Distance: 46940.0\n",
            "Iteration 38/50, Best Distance: 46940.0\n",
            "Iteration 39/50, Best Distance: 46940.0\n",
            "Iteration 40/50, Best Distance: 46940.0\n",
            "Iteration 41/50, Best Distance: 43029.0\n",
            "Iteration 42/50, Best Distance: 43029.0\n",
            "Iteration 43/50, Best Distance: 43029.0\n",
            "Iteration 44/50, Best Distance: 43029.0\n",
            "Iteration 45/50, Best Distance: 43029.0\n",
            "Iteration 46/50, Best Distance: 43028.0\n",
            "Iteration 47/50, Best Distance: 43028.0\n",
            "Iteration 48/50, Best Distance: 40957.0\n",
            "Iteration 49/50, Best Distance: 40957.0\n",
            "Iteration 50/50, Best Distance: 40957.0\n",
            "Iteration 1/50, Best Distance: 105016.0\n",
            "Iteration 2/50, Best Distance: 97337.0\n",
            "Iteration 3/50, Best Distance: 97337.0\n",
            "Iteration 4/50, Best Distance: 97337.0\n",
            "Iteration 5/50, Best Distance: 96154.0\n",
            "Iteration 6/50, Best Distance: 95352.0\n",
            "Iteration 7/50, Best Distance: 95352.0\n",
            "Iteration 8/50, Best Distance: 95352.0\n",
            "Iteration 9/50, Best Distance: 95352.0\n",
            "Iteration 10/50, Best Distance: 95352.0\n",
            "Iteration 11/50, Best Distance: 92796.0\n",
            "Iteration 12/50, Best Distance: 92796.0\n",
            "Iteration 13/50, Best Distance: 92796.0\n",
            "Iteration 14/50, Best Distance: 90871.0\n",
            "Iteration 15/50, Best Distance: 90871.0\n",
            "Iteration 16/50, Best Distance: 90871.0\n",
            "Iteration 17/50, Best Distance: 81673.0\n",
            "Iteration 18/50, Best Distance: 81673.0\n",
            "Iteration 19/50, Best Distance: 81673.0\n",
            "Iteration 20/50, Best Distance: 81673.0\n",
            "Iteration 21/50, Best Distance: 81673.0\n",
            "Iteration 22/50, Best Distance: 81673.0\n",
            "Iteration 23/50, Best Distance: 81673.0\n",
            "Iteration 24/50, Best Distance: 81673.0\n",
            "Iteration 25/50, Best Distance: 81673.0\n",
            "Iteration 26/50, Best Distance: 81673.0\n",
            "Iteration 27/50, Best Distance: 81673.0\n",
            "Iteration 28/50, Best Distance: 81673.0\n",
            "Iteration 29/50, Best Distance: 81673.0\n",
            "Iteration 30/50, Best Distance: 81673.0\n",
            "Iteration 31/50, Best Distance: 81673.0\n",
            "Iteration 32/50, Best Distance: 81673.0\n",
            "Iteration 33/50, Best Distance: 81673.0\n",
            "Iteration 34/50, Best Distance: 81673.0\n",
            "Iteration 35/50, Best Distance: 81673.0\n",
            "Iteration 36/50, Best Distance: 81673.0\n",
            "Iteration 37/50, Best Distance: 81673.0\n",
            "Iteration 38/50, Best Distance: 81673.0\n",
            "Iteration 39/50, Best Distance: 81673.0\n",
            "Iteration 40/50, Best Distance: 81673.0\n",
            "Iteration 41/50, Best Distance: 81673.0\n",
            "Iteration 42/50, Best Distance: 81673.0\n",
            "Iteration 43/50, Best Distance: 81673.0\n",
            "Iteration 44/50, Best Distance: 81673.0\n",
            "Iteration 45/50, Best Distance: 81673.0\n",
            "Iteration 46/50, Best Distance: 81673.0\n",
            "Iteration 47/50, Best Distance: 81673.0\n",
            "Iteration 48/50, Best Distance: 81673.0\n",
            "Iteration 49/50, Best Distance: 81673.0\n",
            "Iteration 50/50, Best Distance: 81673.0\n",
            "Iteration 1/50, Best Distance: 123810.0\n",
            "Iteration 2/50, Best Distance: 120726.0\n",
            "Iteration 3/50, Best Distance: 107523.0\n",
            "Iteration 4/50, Best Distance: 107523.0\n",
            "Iteration 5/50, Best Distance: 107523.0\n",
            "Iteration 6/50, Best Distance: 107523.0\n",
            "Iteration 7/50, Best Distance: 107523.0\n",
            "Iteration 8/50, Best Distance: 107523.0\n",
            "Iteration 9/50, Best Distance: 107523.0\n",
            "Iteration 10/50, Best Distance: 107523.0\n",
            "Iteration 11/50, Best Distance: 107523.0\n",
            "Iteration 12/50, Best Distance: 107523.0\n",
            "Iteration 13/50, Best Distance: 107523.0\n",
            "Iteration 14/50, Best Distance: 107523.0\n",
            "Iteration 15/50, Best Distance: 107523.0\n",
            "Iteration 16/50, Best Distance: 107523.0\n",
            "Iteration 17/50, Best Distance: 107523.0\n",
            "Iteration 18/50, Best Distance: 107523.0\n",
            "Iteration 19/50, Best Distance: 107523.0\n",
            "Iteration 20/50, Best Distance: 107523.0\n",
            "Iteration 21/50, Best Distance: 107523.0\n",
            "Iteration 22/50, Best Distance: 107523.0\n",
            "Iteration 23/50, Best Distance: 107523.0\n",
            "Iteration 24/50, Best Distance: 107523.0\n",
            "Iteration 25/50, Best Distance: 107523.0\n",
            "Iteration 26/50, Best Distance: 107523.0\n",
            "Iteration 27/50, Best Distance: 107523.0\n",
            "Iteration 28/50, Best Distance: 107523.0\n",
            "Iteration 29/50, Best Distance: 107523.0\n",
            "Iteration 30/50, Best Distance: 107523.0\n",
            "Iteration 31/50, Best Distance: 107523.0\n",
            "Iteration 32/50, Best Distance: 107523.0\n",
            "Iteration 33/50, Best Distance: 107523.0\n",
            "Iteration 34/50, Best Distance: 107523.0\n",
            "Iteration 35/50, Best Distance: 107523.0\n",
            "Iteration 36/50, Best Distance: 107523.0\n",
            "Iteration 37/50, Best Distance: 107523.0\n",
            "Iteration 38/50, Best Distance: 107523.0\n",
            "Iteration 39/50, Best Distance: 107523.0\n",
            "Iteration 40/50, Best Distance: 107523.0\n",
            "Iteration 41/50, Best Distance: 107523.0\n",
            "Iteration 42/50, Best Distance: 107523.0\n",
            "Iteration 43/50, Best Distance: 107523.0\n",
            "Iteration 44/50, Best Distance: 107523.0\n",
            "Iteration 45/50, Best Distance: 107523.0\n",
            "Iteration 46/50, Best Distance: 107523.0\n",
            "Iteration 47/50, Best Distance: 107523.0\n",
            "Iteration 48/50, Best Distance: 107523.0\n",
            "Iteration 49/50, Best Distance: 107523.0\n",
            "Iteration 50/50, Best Distance: 107523.0\n",
            "Iteration 1/50, Best Distance: 69464.0\n",
            "Iteration 2/50, Best Distance: 57778.0\n",
            "Iteration 3/50, Best Distance: 57778.0\n",
            "Iteration 4/50, Best Distance: 57778.0\n",
            "Iteration 5/50, Best Distance: 57778.0\n",
            "Iteration 6/50, Best Distance: 57778.0\n",
            "Iteration 7/50, Best Distance: 57778.0\n",
            "Iteration 8/50, Best Distance: 57778.0\n",
            "Iteration 9/50, Best Distance: 57778.0\n",
            "Iteration 10/50, Best Distance: 57778.0\n",
            "Iteration 11/50, Best Distance: 57778.0\n",
            "Iteration 12/50, Best Distance: 57778.0\n",
            "Iteration 13/50, Best Distance: 57778.0\n",
            "Iteration 14/50, Best Distance: 55121.0\n",
            "Iteration 15/50, Best Distance: 55121.0\n",
            "Iteration 16/50, Best Distance: 55121.0\n",
            "Iteration 17/50, Best Distance: 54806.0\n",
            "Iteration 18/50, Best Distance: 54806.0\n",
            "Iteration 19/50, Best Distance: 54806.0\n",
            "Iteration 20/50, Best Distance: 54806.0\n",
            "Iteration 21/50, Best Distance: 54806.0\n",
            "Iteration 22/50, Best Distance: 54806.0\n",
            "Iteration 23/50, Best Distance: 54806.0\n",
            "Iteration 24/50, Best Distance: 54806.0\n",
            "Iteration 25/50, Best Distance: 54806.0\n",
            "Iteration 26/50, Best Distance: 54806.0\n",
            "Iteration 27/50, Best Distance: 54806.0\n",
            "Iteration 28/50, Best Distance: 54806.0\n",
            "Iteration 29/50, Best Distance: 54806.0\n",
            "Iteration 30/50, Best Distance: 54806.0\n",
            "Iteration 31/50, Best Distance: 54806.0\n",
            "Iteration 32/50, Best Distance: 54806.0\n",
            "Iteration 33/50, Best Distance: 54806.0\n",
            "Iteration 34/50, Best Distance: 54806.0\n",
            "Iteration 35/50, Best Distance: 54806.0\n",
            "Iteration 36/50, Best Distance: 50302.0\n",
            "Iteration 37/50, Best Distance: 50302.0\n",
            "Iteration 38/50, Best Distance: 50302.0\n",
            "Iteration 39/50, Best Distance: 50302.0\n",
            "Iteration 40/50, Best Distance: 50302.0\n",
            "Iteration 41/50, Best Distance: 50302.0\n",
            "Iteration 42/50, Best Distance: 50302.0\n",
            "Iteration 43/50, Best Distance: 50302.0\n",
            "Iteration 44/50, Best Distance: 50302.0\n",
            "Iteration 45/50, Best Distance: 50302.0\n",
            "Iteration 46/50, Best Distance: 50302.0\n",
            "Iteration 47/50, Best Distance: 50302.0\n",
            "Iteration 48/50, Best Distance: 50302.0\n",
            "Iteration 49/50, Best Distance: 50302.0\n",
            "Iteration 50/50, Best Distance: 50302.0\n",
            "Iteration 1/50, Best Distance: 113150.0\n",
            "Iteration 2/50, Best Distance: 113150.0\n",
            "Iteration 3/50, Best Distance: 113150.0\n",
            "Iteration 4/50, Best Distance: 113150.0\n",
            "Iteration 5/50, Best Distance: 113150.0\n",
            "Iteration 6/50, Best Distance: 113150.0\n",
            "Iteration 7/50, Best Distance: 113150.0\n",
            "Iteration 8/50, Best Distance: 113150.0\n",
            "Iteration 9/50, Best Distance: 113150.0\n",
            "Iteration 10/50, Best Distance: 113150.0\n",
            "Iteration 11/50, Best Distance: 113150.0\n",
            "Iteration 12/50, Best Distance: 113150.0\n",
            "Iteration 13/50, Best Distance: 113150.0\n",
            "Iteration 14/50, Best Distance: 113150.0\n",
            "Iteration 15/50, Best Distance: 113150.0\n",
            "Iteration 16/50, Best Distance: 113150.0\n",
            "Iteration 17/50, Best Distance: 113150.0\n",
            "Iteration 18/50, Best Distance: 113150.0\n",
            "Iteration 19/50, Best Distance: 113150.0\n",
            "Iteration 20/50, Best Distance: 113150.0\n",
            "Iteration 21/50, Best Distance: 113150.0\n",
            "Iteration 22/50, Best Distance: 113150.0\n",
            "Iteration 23/50, Best Distance: 113150.0\n",
            "Iteration 24/50, Best Distance: 113150.0\n",
            "Iteration 25/50, Best Distance: 113088.0\n",
            "Iteration 26/50, Best Distance: 113088.0\n",
            "Iteration 27/50, Best Distance: 113088.0\n",
            "Iteration 28/50, Best Distance: 113088.0\n",
            "Iteration 29/50, Best Distance: 113088.0\n",
            "Iteration 30/50, Best Distance: 113088.0\n",
            "Iteration 31/50, Best Distance: 113088.0\n",
            "Iteration 32/50, Best Distance: 113088.0\n",
            "Iteration 33/50, Best Distance: 113088.0\n",
            "Iteration 34/50, Best Distance: 113088.0\n",
            "Iteration 35/50, Best Distance: 113088.0\n",
            "Iteration 36/50, Best Distance: 113088.0\n",
            "Iteration 37/50, Best Distance: 113088.0\n",
            "Iteration 38/50, Best Distance: 113088.0\n",
            "Iteration 39/50, Best Distance: 113088.0\n",
            "Iteration 40/50, Best Distance: 113088.0\n",
            "Iteration 41/50, Best Distance: 113088.0\n",
            "Iteration 42/50, Best Distance: 113088.0\n",
            "Iteration 43/50, Best Distance: 113088.0\n",
            "Iteration 44/50, Best Distance: 113088.0\n",
            "Iteration 45/50, Best Distance: 113088.0\n",
            "Iteration 46/50, Best Distance: 113088.0\n",
            "Iteration 47/50, Best Distance: 113088.0\n",
            "Iteration 48/50, Best Distance: 113088.0\n",
            "Iteration 49/50, Best Distance: 113088.0\n",
            "Iteration 50/50, Best Distance: 113088.0\n",
            "Iteration 1/50, Best Distance: 59729.0\n",
            "Iteration 2/50, Best Distance: 59109.0\n",
            "Iteration 3/50, Best Distance: 59109.0\n",
            "Iteration 4/50, Best Distance: 49841.0\n",
            "Iteration 5/50, Best Distance: 49841.0\n",
            "Iteration 6/50, Best Distance: 49841.0\n",
            "Iteration 7/50, Best Distance: 49841.0\n",
            "Iteration 8/50, Best Distance: 49841.0\n",
            "Iteration 9/50, Best Distance: 49841.0\n",
            "Iteration 10/50, Best Distance: 49841.0\n",
            "Iteration 11/50, Best Distance: 49841.0\n",
            "Iteration 12/50, Best Distance: 49841.0\n",
            "Iteration 13/50, Best Distance: 49841.0\n",
            "Iteration 14/50, Best Distance: 49841.0\n",
            "Iteration 15/50, Best Distance: 49841.0\n",
            "Iteration 16/50, Best Distance: 49841.0\n",
            "Iteration 17/50, Best Distance: 49841.0\n",
            "Iteration 18/50, Best Distance: 49841.0\n",
            "Iteration 19/50, Best Distance: 49841.0\n",
            "Iteration 20/50, Best Distance: 49841.0\n",
            "Iteration 21/50, Best Distance: 49841.0\n",
            "Iteration 22/50, Best Distance: 49841.0\n",
            "Iteration 23/50, Best Distance: 49841.0\n",
            "Iteration 24/50, Best Distance: 49841.0\n",
            "Iteration 25/50, Best Distance: 49841.0\n",
            "Iteration 26/50, Best Distance: 49841.0\n",
            "Iteration 27/50, Best Distance: 49841.0\n",
            "Iteration 28/50, Best Distance: 49841.0\n",
            "Iteration 29/50, Best Distance: 49841.0\n",
            "Iteration 30/50, Best Distance: 49841.0\n",
            "Iteration 31/50, Best Distance: 49841.0\n",
            "Iteration 32/50, Best Distance: 49841.0\n",
            "Iteration 33/50, Best Distance: 49841.0\n",
            "Iteration 34/50, Best Distance: 49841.0\n",
            "Iteration 35/50, Best Distance: 49841.0\n",
            "Iteration 36/50, Best Distance: 49841.0\n",
            "Iteration 37/50, Best Distance: 49841.0\n",
            "Iteration 38/50, Best Distance: 49841.0\n",
            "Iteration 39/50, Best Distance: 49841.0\n",
            "Iteration 40/50, Best Distance: 46496.0\n",
            "Iteration 41/50, Best Distance: 45309.0\n",
            "Iteration 42/50, Best Distance: 45309.0\n",
            "Iteration 43/50, Best Distance: 45309.0\n",
            "Iteration 44/50, Best Distance: 45309.0\n",
            "Iteration 45/50, Best Distance: 45309.0\n",
            "Iteration 46/50, Best Distance: 45309.0\n",
            "Iteration 47/50, Best Distance: 45309.0\n",
            "Iteration 48/50, Best Distance: 45309.0\n",
            "Iteration 49/50, Best Distance: 45309.0\n",
            "Iteration 50/50, Best Distance: 45309.0\n",
            "Iteration 1/50, Best Distance: 81438.0\n",
            "Iteration 2/50, Best Distance: 77534.0\n",
            "Iteration 3/50, Best Distance: 77534.0\n",
            "Iteration 4/50, Best Distance: 77513.0\n",
            "Iteration 5/50, Best Distance: 77513.0\n",
            "Iteration 6/50, Best Distance: 77513.0\n",
            "Iteration 7/50, Best Distance: 77513.0\n",
            "Iteration 8/50, Best Distance: 77513.0\n",
            "Iteration 9/50, Best Distance: 77513.0\n",
            "Iteration 10/50, Best Distance: 77513.0\n",
            "Iteration 11/50, Best Distance: 77513.0\n",
            "Iteration 12/50, Best Distance: 76459.0\n",
            "Iteration 13/50, Best Distance: 76459.0\n",
            "Iteration 14/50, Best Distance: 75104.0\n",
            "Iteration 15/50, Best Distance: 75104.0\n",
            "Iteration 16/50, Best Distance: 75104.0\n",
            "Iteration 17/50, Best Distance: 75104.0\n",
            "Iteration 18/50, Best Distance: 75104.0\n",
            "Iteration 19/50, Best Distance: 75104.0\n",
            "Iteration 20/50, Best Distance: 75104.0\n",
            "Iteration 21/50, Best Distance: 75104.0\n",
            "Iteration 22/50, Best Distance: 70633.0\n",
            "Iteration 23/50, Best Distance: 70633.0\n",
            "Iteration 24/50, Best Distance: 70633.0\n",
            "Iteration 25/50, Best Distance: 70633.0\n",
            "Iteration 26/50, Best Distance: 70633.0\n",
            "Iteration 27/50, Best Distance: 70633.0\n",
            "Iteration 28/50, Best Distance: 70633.0\n",
            "Iteration 29/50, Best Distance: 70633.0\n",
            "Iteration 30/50, Best Distance: 70633.0\n",
            "Iteration 31/50, Best Distance: 70633.0\n",
            "Iteration 32/50, Best Distance: 70633.0\n",
            "Iteration 33/50, Best Distance: 70633.0\n",
            "Iteration 34/50, Best Distance: 70633.0\n",
            "Iteration 35/50, Best Distance: 70633.0\n",
            "Iteration 36/50, Best Distance: 70633.0\n",
            "Iteration 37/50, Best Distance: 70633.0\n",
            "Iteration 38/50, Best Distance: 70633.0\n",
            "Iteration 39/50, Best Distance: 70633.0\n",
            "Iteration 40/50, Best Distance: 70633.0\n",
            "Iteration 41/50, Best Distance: 70633.0\n",
            "Iteration 42/50, Best Distance: 70633.0\n",
            "Iteration 43/50, Best Distance: 70633.0\n",
            "Iteration 44/50, Best Distance: 70448.0\n",
            "Iteration 45/50, Best Distance: 70448.0\n",
            "Iteration 46/50, Best Distance: 70448.0\n",
            "Iteration 47/50, Best Distance: 70448.0\n",
            "Iteration 48/50, Best Distance: 70448.0\n",
            "Iteration 49/50, Best Distance: 70448.0\n",
            "Iteration 50/50, Best Distance: 70448.0\n",
            "Iteration 1/50, Best Distance: 98665.0\n",
            "Iteration 2/50, Best Distance: 98665.0\n",
            "Iteration 3/50, Best Distance: 98665.0\n",
            "Iteration 4/50, Best Distance: 96042.0\n",
            "Iteration 5/50, Best Distance: 96042.0\n",
            "Iteration 6/50, Best Distance: 89929.0\n",
            "Iteration 7/50, Best Distance: 89929.0\n",
            "Iteration 8/50, Best Distance: 89929.0\n",
            "Iteration 9/50, Best Distance: 89929.0\n",
            "Iteration 10/50, Best Distance: 89929.0\n",
            "Iteration 11/50, Best Distance: 89929.0\n",
            "Iteration 12/50, Best Distance: 89929.0\n",
            "Iteration 13/50, Best Distance: 89929.0\n",
            "Iteration 14/50, Best Distance: 89929.0\n",
            "Iteration 15/50, Best Distance: 89929.0\n",
            "Iteration 16/50, Best Distance: 89929.0\n",
            "Iteration 17/50, Best Distance: 89929.0\n",
            "Iteration 18/50, Best Distance: 89929.0\n",
            "Iteration 19/50, Best Distance: 89929.0\n",
            "Iteration 20/50, Best Distance: 89929.0\n",
            "Iteration 21/50, Best Distance: 89929.0\n",
            "Iteration 22/50, Best Distance: 89929.0\n",
            "Iteration 23/50, Best Distance: 89929.0\n",
            "Iteration 24/50, Best Distance: 89929.0\n",
            "Iteration 25/50, Best Distance: 89929.0\n",
            "Iteration 26/50, Best Distance: 89929.0\n",
            "Iteration 27/50, Best Distance: 89929.0\n",
            "Iteration 28/50, Best Distance: 89929.0\n",
            "Iteration 29/50, Best Distance: 89929.0\n",
            "Iteration 30/50, Best Distance: 89929.0\n",
            "Iteration 31/50, Best Distance: 89929.0\n",
            "Iteration 32/50, Best Distance: 89929.0\n",
            "Iteration 33/50, Best Distance: 89929.0\n",
            "Iteration 34/50, Best Distance: 89929.0\n",
            "Iteration 35/50, Best Distance: 89929.0\n",
            "Iteration 36/50, Best Distance: 89929.0\n",
            "Iteration 37/50, Best Distance: 89929.0\n",
            "Iteration 38/50, Best Distance: 89929.0\n",
            "Iteration 39/50, Best Distance: 89929.0\n",
            "Iteration 40/50, Best Distance: 89929.0\n",
            "Iteration 41/50, Best Distance: 89929.0\n",
            "Iteration 42/50, Best Distance: 89929.0\n",
            "Iteration 43/50, Best Distance: 89929.0\n",
            "Iteration 44/50, Best Distance: 89929.0\n",
            "Iteration 45/50, Best Distance: 89929.0\n",
            "Iteration 46/50, Best Distance: 89929.0\n",
            "Iteration 47/50, Best Distance: 89192.0\n",
            "Iteration 48/50, Best Distance: 89192.0\n",
            "Iteration 49/50, Best Distance: 89192.0\n",
            "Iteration 50/50, Best Distance: 89192.0\n",
            "Iteration 1/50, Best Distance: 61096.0\n",
            "Iteration 2/50, Best Distance: 55356.0\n",
            "Iteration 3/50, Best Distance: 55356.0\n",
            "Iteration 4/50, Best Distance: 55356.0\n",
            "Iteration 5/50, Best Distance: 55356.0\n",
            "Iteration 6/50, Best Distance: 55356.0\n",
            "Iteration 7/50, Best Distance: 55356.0\n",
            "Iteration 8/50, Best Distance: 55356.0\n",
            "Iteration 9/50, Best Distance: 55356.0\n",
            "Iteration 10/50, Best Distance: 55356.0\n",
            "Iteration 11/50, Best Distance: 55356.0\n",
            "Iteration 12/50, Best Distance: 55356.0\n",
            "Iteration 13/50, Best Distance: 55356.0\n",
            "Iteration 14/50, Best Distance: 54664.0\n",
            "Iteration 15/50, Best Distance: 54664.0\n",
            "Iteration 16/50, Best Distance: 54664.0\n",
            "Iteration 17/50, Best Distance: 54664.0\n",
            "Iteration 18/50, Best Distance: 54664.0\n",
            "Iteration 19/50, Best Distance: 54664.0\n",
            "Iteration 20/50, Best Distance: 54664.0\n",
            "Iteration 21/50, Best Distance: 54664.0\n",
            "Iteration 22/50, Best Distance: 54664.0\n",
            "Iteration 23/50, Best Distance: 54664.0\n",
            "Iteration 24/50, Best Distance: 53169.0\n",
            "Iteration 25/50, Best Distance: 53169.0\n",
            "Iteration 26/50, Best Distance: 53169.0\n",
            "Iteration 27/50, Best Distance: 52152.0\n",
            "Iteration 28/50, Best Distance: 52152.0\n",
            "Iteration 29/50, Best Distance: 52152.0\n",
            "Iteration 30/50, Best Distance: 52152.0\n",
            "Iteration 31/50, Best Distance: 46446.0\n",
            "Iteration 32/50, Best Distance: 46446.0\n",
            "Iteration 33/50, Best Distance: 46446.0\n",
            "Iteration 34/50, Best Distance: 46446.0\n",
            "Iteration 35/50, Best Distance: 46446.0\n",
            "Iteration 36/50, Best Distance: 46446.0\n",
            "Iteration 37/50, Best Distance: 46446.0\n",
            "Iteration 38/50, Best Distance: 46446.0\n",
            "Iteration 39/50, Best Distance: 46446.0\n",
            "Iteration 40/50, Best Distance: 46446.0\n",
            "Iteration 41/50, Best Distance: 46446.0\n",
            "Iteration 42/50, Best Distance: 46446.0\n",
            "Iteration 43/50, Best Distance: 46446.0\n",
            "Iteration 44/50, Best Distance: 46446.0\n",
            "Iteration 45/50, Best Distance: 45893.0\n",
            "Iteration 46/50, Best Distance: 45893.0\n",
            "Iteration 47/50, Best Distance: 45893.0\n",
            "Iteration 48/50, Best Distance: 45064.0\n",
            "Iteration 49/50, Best Distance: 45064.0\n",
            "Iteration 50/50, Best Distance: 45005.0\n",
            "Iteration 1/50, Best Distance: 58356.0\n",
            "Iteration 2/50, Best Distance: 58356.0\n",
            "Iteration 3/50, Best Distance: 58356.0\n",
            "Iteration 4/50, Best Distance: 58356.0\n",
            "Iteration 5/50, Best Distance: 58356.0\n",
            "Iteration 6/50, Best Distance: 58356.0\n",
            "Iteration 7/50, Best Distance: 58356.0\n",
            "Iteration 8/50, Best Distance: 58356.0\n",
            "Iteration 9/50, Best Distance: 58356.0\n",
            "Iteration 10/50, Best Distance: 58356.0\n",
            "Iteration 11/50, Best Distance: 58356.0\n",
            "Iteration 12/50, Best Distance: 58149.0\n",
            "Iteration 13/50, Best Distance: 58149.0\n",
            "Iteration 14/50, Best Distance: 58149.0\n",
            "Iteration 15/50, Best Distance: 58149.0\n",
            "Iteration 16/50, Best Distance: 55191.0\n",
            "Iteration 17/50, Best Distance: 55191.0\n",
            "Iteration 18/50, Best Distance: 55191.0\n",
            "Iteration 19/50, Best Distance: 55191.0\n",
            "Iteration 20/50, Best Distance: 55191.0\n",
            "Iteration 21/50, Best Distance: 55191.0\n",
            "Iteration 22/50, Best Distance: 55191.0\n",
            "Iteration 23/50, Best Distance: 55191.0\n",
            "Iteration 24/50, Best Distance: 55191.0\n",
            "Iteration 25/50, Best Distance: 55191.0\n",
            "Iteration 26/50, Best Distance: 55191.0\n",
            "Iteration 27/50, Best Distance: 55191.0\n",
            "Iteration 28/50, Best Distance: 55191.0\n",
            "Iteration 29/50, Best Distance: 55191.0\n",
            "Iteration 30/50, Best Distance: 55191.0\n",
            "Iteration 31/50, Best Distance: 55191.0\n",
            "Iteration 32/50, Best Distance: 55191.0\n",
            "Iteration 33/50, Best Distance: 55191.0\n",
            "Iteration 34/50, Best Distance: 55191.0\n",
            "Iteration 35/50, Best Distance: 55191.0\n",
            "Iteration 36/50, Best Distance: 55191.0\n",
            "Iteration 37/50, Best Distance: 55191.0\n",
            "Iteration 38/50, Best Distance: 55191.0\n",
            "Iteration 39/50, Best Distance: 55191.0\n",
            "Iteration 40/50, Best Distance: 55191.0\n",
            "Iteration 41/50, Best Distance: 55191.0\n",
            "Iteration 42/50, Best Distance: 55191.0\n",
            "Iteration 43/50, Best Distance: 55191.0\n",
            "Iteration 44/50, Best Distance: 55191.0\n",
            "Iteration 45/50, Best Distance: 53061.0\n",
            "Iteration 46/50, Best Distance: 53061.0\n",
            "Iteration 47/50, Best Distance: 53061.0\n",
            "Iteration 48/50, Best Distance: 53061.0\n",
            "Iteration 49/50, Best Distance: 53061.0\n",
            "Iteration 50/50, Best Distance: 53061.0\n",
            "Iteration 1/50, Best Distance: 129810.0\n",
            "Iteration 2/50, Best Distance: 129810.0\n",
            "Iteration 3/50, Best Distance: 129810.0\n",
            "Iteration 4/50, Best Distance: 129810.0\n",
            "Iteration 5/50, Best Distance: 129493.0\n",
            "Iteration 6/50, Best Distance: 129493.0\n",
            "Iteration 7/50, Best Distance: 122611.0\n",
            "Iteration 8/50, Best Distance: 122611.0\n",
            "Iteration 9/50, Best Distance: 122611.0\n",
            "Iteration 10/50, Best Distance: 122611.0\n",
            "Iteration 11/50, Best Distance: 122611.0\n",
            "Iteration 12/50, Best Distance: 122611.0\n",
            "Iteration 13/50, Best Distance: 122611.0\n",
            "Iteration 14/50, Best Distance: 122611.0\n",
            "Iteration 15/50, Best Distance: 122611.0\n",
            "Iteration 16/50, Best Distance: 116804.0\n",
            "Iteration 17/50, Best Distance: 116804.0\n",
            "Iteration 18/50, Best Distance: 116804.0\n",
            "Iteration 19/50, Best Distance: 116804.0\n",
            "Iteration 20/50, Best Distance: 116804.0\n",
            "Iteration 21/50, Best Distance: 116804.0\n",
            "Iteration 22/50, Best Distance: 116804.0\n",
            "Iteration 23/50, Best Distance: 116804.0\n",
            "Iteration 24/50, Best Distance: 116804.0\n",
            "Iteration 25/50, Best Distance: 116804.0\n",
            "Iteration 26/50, Best Distance: 116804.0\n",
            "Iteration 27/50, Best Distance: 116804.0\n",
            "Iteration 28/50, Best Distance: 116804.0\n",
            "Iteration 29/50, Best Distance: 116804.0\n",
            "Iteration 30/50, Best Distance: 116804.0\n",
            "Iteration 31/50, Best Distance: 116804.0\n",
            "Iteration 32/50, Best Distance: 116804.0\n",
            "Iteration 33/50, Best Distance: 116804.0\n",
            "Iteration 34/50, Best Distance: 116804.0\n",
            "Iteration 35/50, Best Distance: 116804.0\n",
            "Iteration 36/50, Best Distance: 116804.0\n",
            "Iteration 37/50, Best Distance: 116804.0\n",
            "Iteration 38/50, Best Distance: 116804.0\n",
            "Iteration 39/50, Best Distance: 116804.0\n",
            "Iteration 40/50, Best Distance: 116804.0\n",
            "Iteration 41/50, Best Distance: 116804.0\n",
            "Iteration 42/50, Best Distance: 116804.0\n",
            "Iteration 43/50, Best Distance: 116804.0\n",
            "Iteration 44/50, Best Distance: 116804.0\n",
            "Iteration 45/50, Best Distance: 116804.0\n",
            "Iteration 46/50, Best Distance: 116804.0\n",
            "Iteration 47/50, Best Distance: 116804.0\n",
            "Iteration 48/50, Best Distance: 116804.0\n",
            "Iteration 49/50, Best Distance: 116804.0\n",
            "Iteration 50/50, Best Distance: 116804.0\n",
            "Iteration 1/50, Best Distance: 79322.0\n",
            "Iteration 2/50, Best Distance: 79322.0\n",
            "Iteration 3/50, Best Distance: 76490.0\n",
            "Iteration 4/50, Best Distance: 76490.0\n",
            "Iteration 5/50, Best Distance: 76490.0\n",
            "Iteration 6/50, Best Distance: 76490.0\n",
            "Iteration 7/50, Best Distance: 76490.0\n",
            "Iteration 8/50, Best Distance: 76490.0\n",
            "Iteration 9/50, Best Distance: 69326.0\n",
            "Iteration 10/50, Best Distance: 69326.0\n",
            "Iteration 11/50, Best Distance: 69326.0\n",
            "Iteration 12/50, Best Distance: 69326.0\n",
            "Iteration 13/50, Best Distance: 69326.0\n",
            "Iteration 14/50, Best Distance: 69326.0\n",
            "Iteration 15/50, Best Distance: 69326.0\n",
            "Iteration 16/50, Best Distance: 69326.0\n",
            "Iteration 17/50, Best Distance: 69326.0\n",
            "Iteration 18/50, Best Distance: 69326.0\n",
            "Iteration 19/50, Best Distance: 69326.0\n",
            "Iteration 20/50, Best Distance: 69326.0\n",
            "Iteration 21/50, Best Distance: 69326.0\n",
            "Iteration 22/50, Best Distance: 69326.0\n",
            "Iteration 23/50, Best Distance: 69326.0\n",
            "Iteration 24/50, Best Distance: 69326.0\n",
            "Iteration 25/50, Best Distance: 69326.0\n",
            "Iteration 26/50, Best Distance: 69326.0\n",
            "Iteration 27/50, Best Distance: 69326.0\n",
            "Iteration 28/50, Best Distance: 69326.0\n",
            "Iteration 29/50, Best Distance: 69326.0\n",
            "Iteration 30/50, Best Distance: 69326.0\n",
            "Iteration 31/50, Best Distance: 69326.0\n",
            "Iteration 32/50, Best Distance: 69326.0\n",
            "Iteration 33/50, Best Distance: 69326.0\n",
            "Iteration 34/50, Best Distance: 69326.0\n",
            "Iteration 35/50, Best Distance: 69326.0\n",
            "Iteration 36/50, Best Distance: 69326.0\n",
            "Iteration 37/50, Best Distance: 69326.0\n",
            "Iteration 38/50, Best Distance: 69326.0\n",
            "Iteration 39/50, Best Distance: 69326.0\n",
            "Iteration 40/50, Best Distance: 69326.0\n",
            "Iteration 41/50, Best Distance: 69326.0\n",
            "Iteration 42/50, Best Distance: 69326.0\n",
            "Iteration 43/50, Best Distance: 62136.0\n",
            "Iteration 44/50, Best Distance: 62136.0\n",
            "Iteration 45/50, Best Distance: 62136.0\n",
            "Iteration 46/50, Best Distance: 62136.0\n",
            "Iteration 47/50, Best Distance: 62136.0\n",
            "Iteration 48/50, Best Distance: 62136.0\n",
            "Iteration 49/50, Best Distance: 62136.0\n",
            "Iteration 50/50, Best Distance: 62136.0\n",
            "Iteration 1/50, Best Distance: 120242.0\n",
            "Iteration 2/50, Best Distance: 120242.0\n",
            "Iteration 3/50, Best Distance: 118319.0\n",
            "Iteration 4/50, Best Distance: 118319.0\n",
            "Iteration 5/50, Best Distance: 118319.0\n",
            "Iteration 6/50, Best Distance: 117518.0\n",
            "Iteration 7/50, Best Distance: 117518.0\n",
            "Iteration 8/50, Best Distance: 117518.0\n",
            "Iteration 9/50, Best Distance: 117518.0\n",
            "Iteration 10/50, Best Distance: 117518.0\n",
            "Iteration 11/50, Best Distance: 117518.0\n",
            "Iteration 12/50, Best Distance: 112440.0\n",
            "Iteration 13/50, Best Distance: 112440.0\n",
            "Iteration 14/50, Best Distance: 112440.0\n",
            "Iteration 15/50, Best Distance: 112440.0\n",
            "Iteration 16/50, Best Distance: 112440.0\n",
            "Iteration 17/50, Best Distance: 112440.0\n",
            "Iteration 18/50, Best Distance: 112440.0\n",
            "Iteration 19/50, Best Distance: 112440.0\n",
            "Iteration 20/50, Best Distance: 112440.0\n",
            "Iteration 21/50, Best Distance: 112440.0\n",
            "Iteration 22/50, Best Distance: 112440.0\n",
            "Iteration 23/50, Best Distance: 112440.0\n",
            "Iteration 24/50, Best Distance: 112440.0\n",
            "Iteration 25/50, Best Distance: 112440.0\n",
            "Iteration 26/50, Best Distance: 112440.0\n",
            "Iteration 27/50, Best Distance: 112440.0\n",
            "Iteration 28/50, Best Distance: 112440.0\n",
            "Iteration 29/50, Best Distance: 112440.0\n",
            "Iteration 30/50, Best Distance: 112440.0\n",
            "Iteration 31/50, Best Distance: 112440.0\n",
            "Iteration 32/50, Best Distance: 112440.0\n",
            "Iteration 33/50, Best Distance: 112440.0\n",
            "Iteration 34/50, Best Distance: 112440.0\n",
            "Iteration 35/50, Best Distance: 112440.0\n",
            "Iteration 36/50, Best Distance: 112440.0\n",
            "Iteration 37/50, Best Distance: 112440.0\n",
            "Iteration 38/50, Best Distance: 112440.0\n",
            "Iteration 39/50, Best Distance: 112440.0\n",
            "Iteration 40/50, Best Distance: 112440.0\n",
            "Iteration 41/50, Best Distance: 112440.0\n",
            "Iteration 42/50, Best Distance: 112440.0\n",
            "Iteration 43/50, Best Distance: 112440.0\n",
            "Iteration 44/50, Best Distance: 112440.0\n",
            "Iteration 45/50, Best Distance: 112440.0\n",
            "Iteration 46/50, Best Distance: 112440.0\n",
            "Iteration 47/50, Best Distance: 104423.0\n",
            "Iteration 48/50, Best Distance: 104423.0\n",
            "Iteration 49/50, Best Distance: 104423.0\n",
            "Iteration 50/50, Best Distance: 104423.0\n",
            "Iteration 1/50, Best Distance: 57053.0\n",
            "Iteration 2/50, Best Distance: 53561.0\n",
            "Iteration 3/50, Best Distance: 53561.0\n",
            "Iteration 4/50, Best Distance: 53561.0\n",
            "Iteration 5/50, Best Distance: 53561.0\n",
            "Iteration 6/50, Best Distance: 49871.0\n",
            "Iteration 7/50, Best Distance: 49871.0\n",
            "Iteration 8/50, Best Distance: 49871.0\n",
            "Iteration 9/50, Best Distance: 49871.0\n",
            "Iteration 10/50, Best Distance: 49871.0\n",
            "Iteration 11/50, Best Distance: 49871.0\n",
            "Iteration 12/50, Best Distance: 49871.0\n",
            "Iteration 13/50, Best Distance: 49871.0\n",
            "Iteration 14/50, Best Distance: 49871.0\n",
            "Iteration 15/50, Best Distance: 47119.0\n",
            "Iteration 16/50, Best Distance: 47119.0\n",
            "Iteration 17/50, Best Distance: 47119.0\n",
            "Iteration 18/50, Best Distance: 47119.0\n",
            "Iteration 19/50, Best Distance: 47119.0\n",
            "Iteration 20/50, Best Distance: 47119.0\n",
            "Iteration 21/50, Best Distance: 47119.0\n",
            "Iteration 22/50, Best Distance: 47119.0\n",
            "Iteration 23/50, Best Distance: 47119.0\n",
            "Iteration 24/50, Best Distance: 47119.0\n",
            "Iteration 25/50, Best Distance: 47119.0\n",
            "Iteration 26/50, Best Distance: 47119.0\n",
            "Iteration 27/50, Best Distance: 47119.0\n",
            "Iteration 28/50, Best Distance: 47119.0\n",
            "Iteration 29/50, Best Distance: 47119.0\n",
            "Iteration 30/50, Best Distance: 47119.0\n",
            "Iteration 31/50, Best Distance: 47119.0\n",
            "Iteration 32/50, Best Distance: 47119.0\n",
            "Iteration 33/50, Best Distance: 47119.0\n",
            "Iteration 34/50, Best Distance: 47119.0\n",
            "Iteration 35/50, Best Distance: 47119.0\n",
            "Iteration 36/50, Best Distance: 47119.0\n",
            "Iteration 37/50, Best Distance: 47119.0\n",
            "Iteration 38/50, Best Distance: 47119.0\n",
            "Iteration 39/50, Best Distance: 47119.0\n",
            "Iteration 40/50, Best Distance: 47119.0\n",
            "Iteration 41/50, Best Distance: 47119.0\n",
            "Iteration 42/50, Best Distance: 45421.0\n",
            "Iteration 43/50, Best Distance: 45421.0\n",
            "Iteration 44/50, Best Distance: 45421.0\n",
            "Iteration 45/50, Best Distance: 43486.0\n",
            "Iteration 46/50, Best Distance: 43486.0\n",
            "Iteration 47/50, Best Distance: 43486.0\n",
            "Iteration 48/50, Best Distance: 43486.0\n",
            "Iteration 49/50, Best Distance: 43486.0\n",
            "Iteration 50/50, Best Distance: 43486.0\n",
            "Iteration 1/50, Best Distance: 121276.0\n",
            "Iteration 2/50, Best Distance: 118631.0\n",
            "Iteration 3/50, Best Distance: 107025.0\n",
            "Iteration 4/50, Best Distance: 107025.0\n",
            "Iteration 5/50, Best Distance: 107025.0\n",
            "Iteration 6/50, Best Distance: 107025.0\n",
            "Iteration 7/50, Best Distance: 107025.0\n",
            "Iteration 8/50, Best Distance: 107025.0\n",
            "Iteration 9/50, Best Distance: 107025.0\n",
            "Iteration 10/50, Best Distance: 107025.0\n",
            "Iteration 11/50, Best Distance: 107025.0\n",
            "Iteration 12/50, Best Distance: 107025.0\n",
            "Iteration 13/50, Best Distance: 107025.0\n",
            "Iteration 14/50, Best Distance: 107025.0\n",
            "Iteration 15/50, Best Distance: 107025.0\n",
            "Iteration 16/50, Best Distance: 107025.0\n",
            "Iteration 17/50, Best Distance: 107025.0\n",
            "Iteration 18/50, Best Distance: 107025.0\n",
            "Iteration 19/50, Best Distance: 107025.0\n",
            "Iteration 20/50, Best Distance: 107025.0\n",
            "Iteration 21/50, Best Distance: 107025.0\n",
            "Iteration 22/50, Best Distance: 107025.0\n",
            "Iteration 23/50, Best Distance: 107025.0\n",
            "Iteration 24/50, Best Distance: 107025.0\n",
            "Iteration 25/50, Best Distance: 107025.0\n",
            "Iteration 26/50, Best Distance: 107025.0\n",
            "Iteration 27/50, Best Distance: 107025.0\n",
            "Iteration 28/50, Best Distance: 107025.0\n",
            "Iteration 29/50, Best Distance: 107025.0\n",
            "Iteration 30/50, Best Distance: 107025.0\n",
            "Iteration 31/50, Best Distance: 107025.0\n",
            "Iteration 32/50, Best Distance: 107025.0\n",
            "Iteration 33/50, Best Distance: 107025.0\n",
            "Iteration 34/50, Best Distance: 107025.0\n",
            "Iteration 35/50, Best Distance: 106090.0\n",
            "Iteration 36/50, Best Distance: 106090.0\n",
            "Iteration 37/50, Best Distance: 106090.0\n",
            "Iteration 38/50, Best Distance: 106090.0\n",
            "Iteration 39/50, Best Distance: 106090.0\n",
            "Iteration 40/50, Best Distance: 106090.0\n",
            "Iteration 41/50, Best Distance: 106090.0\n",
            "Iteration 42/50, Best Distance: 106090.0\n",
            "Iteration 43/50, Best Distance: 106090.0\n",
            "Iteration 44/50, Best Distance: 106090.0\n",
            "Iteration 45/50, Best Distance: 106090.0\n",
            "Iteration 46/50, Best Distance: 106090.0\n",
            "Iteration 47/50, Best Distance: 106090.0\n",
            "Iteration 48/50, Best Distance: 106090.0\n",
            "Iteration 49/50, Best Distance: 106090.0\n",
            "Iteration 50/50, Best Distance: 106090.0\n",
            "Iteration 1/50, Best Distance: 108061.0\n",
            "Iteration 2/50, Best Distance: 108061.0\n",
            "Iteration 3/50, Best Distance: 99286.0\n",
            "Iteration 4/50, Best Distance: 99286.0\n",
            "Iteration 5/50, Best Distance: 99286.0\n",
            "Iteration 6/50, Best Distance: 99286.0\n",
            "Iteration 7/50, Best Distance: 99286.0\n",
            "Iteration 8/50, Best Distance: 99286.0\n",
            "Iteration 9/50, Best Distance: 99286.0\n",
            "Iteration 10/50, Best Distance: 99286.0\n",
            "Iteration 11/50, Best Distance: 99286.0\n",
            "Iteration 12/50, Best Distance: 99286.0\n",
            "Iteration 13/50, Best Distance: 99286.0\n",
            "Iteration 14/50, Best Distance: 99286.0\n",
            "Iteration 15/50, Best Distance: 99286.0\n",
            "Iteration 16/50, Best Distance: 99286.0\n",
            "Iteration 17/50, Best Distance: 99286.0\n",
            "Iteration 18/50, Best Distance: 99286.0\n",
            "Iteration 19/50, Best Distance: 99286.0\n",
            "Iteration 20/50, Best Distance: 99286.0\n",
            "Iteration 21/50, Best Distance: 99286.0\n",
            "Iteration 22/50, Best Distance: 99286.0\n",
            "Iteration 23/50, Best Distance: 99286.0\n",
            "Iteration 24/50, Best Distance: 99286.0\n",
            "Iteration 25/50, Best Distance: 99286.0\n",
            "Iteration 26/50, Best Distance: 99286.0\n",
            "Iteration 27/50, Best Distance: 99286.0\n",
            "Iteration 28/50, Best Distance: 99286.0\n",
            "Iteration 29/50, Best Distance: 99286.0\n",
            "Iteration 30/50, Best Distance: 99286.0\n",
            "Iteration 31/50, Best Distance: 99286.0\n",
            "Iteration 32/50, Best Distance: 99286.0\n",
            "Iteration 33/50, Best Distance: 99286.0\n",
            "Iteration 34/50, Best Distance: 98661.0\n",
            "Iteration 35/50, Best Distance: 98661.0\n",
            "Iteration 36/50, Best Distance: 98661.0\n",
            "Iteration 37/50, Best Distance: 98661.0\n",
            "Iteration 38/50, Best Distance: 98661.0\n",
            "Iteration 39/50, Best Distance: 98661.0\n",
            "Iteration 40/50, Best Distance: 98661.0\n",
            "Iteration 41/50, Best Distance: 98661.0\n",
            "Iteration 42/50, Best Distance: 98661.0\n",
            "Iteration 43/50, Best Distance: 98661.0\n",
            "Iteration 44/50, Best Distance: 98661.0\n",
            "Iteration 45/50, Best Distance: 98661.0\n",
            "Iteration 46/50, Best Distance: 98661.0\n",
            "Iteration 47/50, Best Distance: 98661.0\n",
            "Iteration 48/50, Best Distance: 98661.0\n",
            "Iteration 49/50, Best Distance: 98661.0\n",
            "Iteration 50/50, Best Distance: 98661.0\n",
            "Iteration 1/50, Best Distance: 73717.0\n",
            "Iteration 2/50, Best Distance: 69456.0\n",
            "Iteration 3/50, Best Distance: 64547.0\n",
            "Iteration 4/50, Best Distance: 63561.0\n",
            "Iteration 5/50, Best Distance: 63561.0\n",
            "Iteration 6/50, Best Distance: 62866.0\n",
            "Iteration 7/50, Best Distance: 62866.0\n",
            "Iteration 8/50, Best Distance: 62866.0\n",
            "Iteration 9/50, Best Distance: 62866.0\n",
            "Iteration 10/50, Best Distance: 62866.0\n",
            "Iteration 11/50, Best Distance: 62866.0\n",
            "Iteration 12/50, Best Distance: 62866.0\n",
            "Iteration 13/50, Best Distance: 62866.0\n",
            "Iteration 14/50, Best Distance: 62866.0\n",
            "Iteration 15/50, Best Distance: 62866.0\n",
            "Iteration 16/50, Best Distance: 61880.0\n",
            "Iteration 17/50, Best Distance: 61880.0\n",
            "Iteration 18/50, Best Distance: 61880.0\n",
            "Iteration 19/50, Best Distance: 61880.0\n",
            "Iteration 20/50, Best Distance: 61326.0\n",
            "Iteration 21/50, Best Distance: 61326.0\n",
            "Iteration 22/50, Best Distance: 61326.0\n"
          ]
        },
        {
          "output_type": "error",
          "ename": "KeyboardInterrupt",
          "evalue": "",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
            "\u001b[0;32m<ipython-input-8-c0fb7550ad1a>\u001b[0m in \u001b[0;36m<cell line: 281>\u001b[0;34m()\u001b[0m\n\u001b[1;32m    279\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    280\u001b[0m \u001b[0;31m# Execute o experimento e armazene os resultados\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 281\u001b[0;31m \u001b[0mmean_kroa100\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mstd_kroa100\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mtime_kroa100\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mrun_experiment\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mproblem\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    282\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    283\u001b[0m experimental_results = {\n",
            "\u001b[0;32m<ipython-input-8-c0fb7550ad1a>\u001b[0m in \u001b[0;36mrun_experiment\u001b[0;34m(problem, num_runs)\u001b[0m\n\u001b[1;32m    256\u001b[0m         \u001b[0;31m# é aqui que altera os parâmetros gerais de execução\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    257\u001b[0m         \u001b[0msos_aco\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mSOS_ACO\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnum_ants\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;36m10\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mnum_iterations\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;36m50\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdecay\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;36m0.95\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0malpha\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;36m1.0\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mbeta\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;36m2.0\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mpopulation_size\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;36m20\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0msos_iterations\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;36m10\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 258\u001b[0;31m         \u001b[0mbest_path\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mbest_distance\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0msos_aco\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mrun\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mdistances\u001b[0m\u001b[0;34m)\u001b[0m  \u001b[0;31m# Use a matriz NumPy para distâncias\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    259\u001b[0m         \u001b[0mbest_distances\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mbest_distance\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    260\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m<ipython-input-8-c0fb7550ad1a>\u001b[0m in \u001b[0;36mrun\u001b[0;34m(self, distances)\u001b[0m\n\u001b[1;32m    228\u001b[0m             \u001b[0;32mreturn\u001b[0m \u001b[0mdistance\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    229\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 230\u001b[0;31m         \u001b[0mbest_params\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msos\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0moptimize\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mobjective_function\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    231\u001b[0m         \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0maco\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0malpha\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0maco\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbeta\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mbest_params\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    232\u001b[0m         \u001b[0mbest_path\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mbest_distance\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0maco\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mrun\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mdistances\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m<ipython-input-8-c0fb7550ad1a>\u001b[0m in \u001b[0;36moptimize\u001b[0;34m(self, objective_function)\u001b[0m\n\u001b[1;32m    142\u001b[0m             \u001b[0;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpopulation_size\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    143\u001b[0m                 \u001b[0morganism\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mpopulation\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 144\u001b[0;31m                 \u001b[0mfitness\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mobjective_function\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0morganism\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# calcula o fitness\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    145\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    146\u001b[0m                 \u001b[0;32mif\u001b[0m \u001b[0mfitness\u001b[0m \u001b[0;34m<\u001b[0m \u001b[0mbest_fitness\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m<ipython-input-8-c0fb7550ad1a>\u001b[0m in \u001b[0;36mobjective_function\u001b[0;34m(params)\u001b[0m\n\u001b[1;32m    225\u001b[0m             \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0maco\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0malpha\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0malpha\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    226\u001b[0m             \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0maco\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbeta\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mbeta\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 227\u001b[0;31m             \u001b[0m_\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdistance\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0maco\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mrun\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mdistances\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    228\u001b[0m             \u001b[0;32mreturn\u001b[0m \u001b[0mdistance\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    229\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m<ipython-input-8-c0fb7550ad1a>\u001b[0m in \u001b[0;36mrun\u001b[0;34m(self, distances)\u001b[0m\n\u001b[1;32m     43\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     44\u001b[0m         \u001b[0;32mfor\u001b[0m \u001b[0miteration\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mnum_iterations\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 45\u001b[0;31m             \u001b[0mall_paths\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_construct_solutions\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mpheromones\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdistances\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     46\u001b[0m             \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_update_pheromones\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mpheromones\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mall_paths\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdistances\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     47\u001b[0m             \u001b[0mbest_path\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mbest_distance\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_find_best_path\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mall_paths\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdistances\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mbest_path\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mbest_distance\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m<ipython-input-8-c0fb7550ad1a>\u001b[0m in \u001b[0;36m_construct_solutions\u001b[0;34m(self, pheromones, distances)\u001b[0m\n\u001b[1;32m     51\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     52\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0m_construct_solutions\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mpheromones\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdistances\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 53\u001b[0;31m         \u001b[0mall_paths\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_generate_path\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mpheromones\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdistances\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0m_\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mnum_ants\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     54\u001b[0m         \u001b[0;32mreturn\u001b[0m \u001b[0mall_paths\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     55\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m<ipython-input-8-c0fb7550ad1a>\u001b[0m in \u001b[0;36m<listcomp>\u001b[0;34m(.0)\u001b[0m\n\u001b[1;32m     51\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     52\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0m_construct_solutions\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mpheromones\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdistances\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 53\u001b[0;31m         \u001b[0mall_paths\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_generate_path\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mpheromones\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdistances\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0m_\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mnum_ants\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     54\u001b[0m         \u001b[0;32mreturn\u001b[0m \u001b[0mall_paths\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     55\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m<ipython-input-8-c0fb7550ad1a>\u001b[0m in \u001b[0;36m_generate_path\u001b[0;34m(self, pheromones, distances)\u001b[0m\n\u001b[1;32m     63\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     64\u001b[0m         \u001b[0;32mwhile\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mvisited\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m<\u001b[0m \u001b[0mnum_cities\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 65\u001b[0;31m             \u001b[0mnext_city\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_select_next_city\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcurrent_city\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mpheromones\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdistances\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mvisited\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     66\u001b[0m             \u001b[0mpath\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnext_city\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     67\u001b[0m             \u001b[0mvisited\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0madd\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnext_city\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m<ipython-input-8-c0fb7550ad1a>\u001b[0m in \u001b[0;36m_select_next_city\u001b[0;34m(self, current_city, pheromones, distances, visited)\u001b[0m\n\u001b[1;32m     81\u001b[0m                 \u001b[0mprobabilities\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mcity\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mpheromones\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mcurrent_city\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mcity\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m**\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0malpha\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m*\u001b[0m\u001b[0;31m \u001b[0m\u001b[0;31m\\\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     82\u001b[0m                                       \u001b[0;34m(\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1.0\u001b[0m \u001b[0;34m/\u001b[0m \u001b[0mdistance\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m**\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbeta\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 83\u001b[0;31m                 \u001b[0mvalid_cities\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcity\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     84\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     85\u001b[0m         \u001b[0;32mif\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0mvalid_cities\u001b[0m\u001b[0;34m:\u001b[0m  \u001b[0;31m# Tratar o caso em que nenhuma cidade válida foi encontrada\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
          ]
        }
      ],
      "source": [
        "import numpy as np # Para trabalhar com matrizes e operações numéricas\n",
        "import random # Geração de números aleatórios (usado na inicialização e seleção)\n",
        "import time # Para medir o tempo de execução do algoritmo.\n",
        "import matplotlib.pyplot as plt # Para visualização (gráfico de barras)\n",
        "\n",
        "#depende do !pip antes\n",
        "import tsplib95 #  Leitura e manipulação de problemas do TSP em formato TSPLIB.\n",
        "import requests # Para baixar o arquivo de dados do problema TSP.\n",
        "import networkx as nx # Para representar o problema TSP como um grafo.\n",
        "\n",
        "\"\"\"\n",
        "Classe do Algoritmo Ant Colony Optimization (ACO)\n",
        "\n",
        "Parâmetros:\n",
        "--> num_ants - número de formigas\n",
        "--> num_iterations - número de iterações (ou gerações)\n",
        "--> decay - Taxa de evaporação do feromônio (ρ).\n",
        "--> alpha -  Importância do feromônio na escolha do caminho (α)\n",
        "--> beta - Importância da distância na escolha do caminho.\n",
        "\n",
        "\"\"\"\n",
        "class ACO:\n",
        "    def __init__(self, num_ants, num_iterations, decay, alpha, beta): #decay = ro\n",
        "        self.num_ants = num_ants\n",
        "        self.num_iterations = num_iterations\n",
        "        self.decay = decay\n",
        "        self.alpha = alpha\n",
        "        self.beta = beta\n",
        "\n",
        "    # Método principal que executa o algoritmo ACO. Recebe a matriz de distâncias entre as cidades.\n",
        "    # Inicializa os feromônios em todas as arestas.\n",
        "    # Em cada iteração:\n",
        "      # 1) Constrói soluções (caminhos) para cada formiga.\n",
        "      # 2) Atualiza os feromônios com base nas soluções encontradas.\n",
        "      # 3) Encontra o melhor caminho encontrado até o momento.\n",
        "      # 4) Retorna o melhor caminho e sua distância total.\n",
        "\n",
        "    def run(self, distances):\n",
        "        num_cities = len(distances)\n",
        "        pheromones = np.ones((num_cities, num_cities)) / num_cities\n",
        "        best_path = None\n",
        "        best_distance = float('inf')\n",
        "\n",
        "        for iteration in range(self.num_iterations):\n",
        "            all_paths = self._construct_solutions(pheromones, distances)\n",
        "            self._update_pheromones(pheromones, all_paths, distances)\n",
        "            best_path, best_distance = self._find_best_path(all_paths, distances, best_path, best_distance)\n",
        "            print(f\"Iteration {iteration+1}/{self.num_iterations}, Best Distance: {best_distance}\")\n",
        "\n",
        "        return best_path, best_distance\n",
        "\n",
        "    def _construct_solutions(self, pheromones, distances):\n",
        "        all_paths = [self._generate_path(pheromones, distances) for _ in range(self.num_ants)]\n",
        "        return all_paths\n",
        "\n",
        "    def _generate_path(self, pheromones, distances): # função que gera o caminho com feromônio\n",
        "        num_cities = len(distances)\n",
        "        path = []\n",
        "        visited = set()\n",
        "        current_city = random.randint(0, num_cities - 1)\n",
        "        path.append(current_city)\n",
        "        visited.add(current_city)\n",
        "\n",
        "        while len(visited) < num_cities:\n",
        "            next_city = self._select_next_city(current_city, pheromones, distances, visited)\n",
        "            path.append(next_city)\n",
        "            visited.add(next_city)\n",
        "            current_city = next_city\n",
        "\n",
        "        return path\n",
        "\n",
        "    def _select_next_city(self, current_city, pheromones, distances, visited):\n",
        "        num_cities = len(pheromones)\n",
        "        probabilities = np.zeros(num_cities)\n",
        "\n",
        "        valid_cities = []  # Armazenar cidades válidas (aquelas não visitadas e com distância finita)\n",
        "\n",
        "        for city in range(num_cities):\n",
        "            if city not in visited and distances[current_city][city] != float('inf'):\n",
        "                distance = distances[current_city][city]\n",
        "                probabilities[city] = (pheromones[current_city][city] ** self.alpha) * \\\n",
        "                                      ((1.0 / distance) ** self.beta)\n",
        "                valid_cities.append(city)\n",
        "\n",
        "        if not valid_cities:  # Tratar o caso em que nenhuma cidade válida foi encontrada\n",
        "            return random.choice(list(set(range(num_cities)) - visited))  # Escolha aleatoriamente entre as cidades restantes\n",
        "\n",
        "        probabilities = probabilities / probabilities.sum()  # Normaliza probabilidades apenas para cidades válidas\n",
        "        return np.random.choice(valid_cities, p=probabilities[valid_cities])  # Escolhe das cidades válidas\n",
        "\n",
        "    def _update_pheromones(self, pheromones, all_paths, distances): # atualiza os feromonios\n",
        "        num_cities = len(distances)\n",
        "        pheromones *= self.decay  # no artigo é o ro\n",
        "\n",
        "        for path in all_paths:\n",
        "            path_length = self._calculate_path_length(path, distances)\n",
        "            for i in range(len(path) - 1):\n",
        "                pheromones[path[i]][path[i + 1]] += 1.0 / path_length\n",
        "                pheromones[path[i + 1]][path[i]] += 1.0 / path_length\n",
        "\n",
        "    def _calculate_path_length(self, path, distances): # calcula o comprimento do caminho\n",
        "        length = sum(distances[path[i]][path[i + 1]] for i in range(len(path) - 1))\n",
        "        length += distances[path[-1]][path[0]]\n",
        "        return length\n",
        "\n",
        "    def _find_best_path(self, all_paths, distances, best_path, best_distance):\n",
        "        for path in all_paths:\n",
        "            length = self._calculate_path_length(path, distances)\n",
        "            if length < best_distance:\n",
        "                best_distance = length\n",
        "                best_path = path\n",
        "        return best_path, best_distance\n",
        "\n",
        "\"\"\"\n",
        "Classe do Algortimo SOS (Simbiose de Organismos):\n",
        "\n",
        "Parâmetros:\n",
        "--> population_size - tamanho da população\n",
        "--> iterations - número de iterações (ou gerações)\n",
        "\n",
        "\"\"\"\n",
        "class SOS:\n",
        "    def __init__(self, population_size, iterations): #iniciializa\n",
        "        self.population_size = population_size\n",
        "        self.iterations = iterations\n",
        "\n",
        "    # Método principal que executa o algoritmo SOS.\n",
        "      # objective_function: Função que avalia a qualidade de uma solução (no caso, a distância total do caminho).\n",
        "      # Inicializa a população com soluções aleatórias.\n",
        "      # Em cada iteração, para cada organismo:\n",
        "          # 1) Aplica os relacionamentos de mutualismo, comensalismo e parasitismo.\n",
        "          # 2) Atualiza o organismo com base nos relacionamentos.\n",
        "          # 3) Atualiza a melhor solução encontrada.\n",
        "          # 4) Retorna a melhor solução.\n",
        "\n",
        "    def optimize(self, objective_function): # define a função objetivo\n",
        "        population = [self._initialize_solution() for _ in range(self.population_size)]\n",
        "        best_solution = None\n",
        "        best_fitness = float('inf')\n",
        "\n",
        "        for iteration in range(self.iterations):\n",
        "            for i in range(self.population_size):\n",
        "                organism = population[i]\n",
        "                fitness = objective_function(organism) # calcula o fitness\n",
        "\n",
        "                if fitness < best_fitness:\n",
        "                    best_fitness = fitness\n",
        "                    best_solution = organism\n",
        "\n",
        "                j = random.randint(0, self.population_size - 1)\n",
        "                if i != j:\n",
        "                    organism, population[j] = self._mutualism(organism, population[j], objective_function)\n",
        "\n",
        "                j = random.randint(0, self.population_size - 1)\n",
        "                if i != j:\n",
        "                    organism = self._commensalism(organism, population[j], objective_function)\n",
        "\n",
        "                j = random.randint(0, self.population_size - 1)\n",
        "                if i != j:\n",
        "                    organism = self._parasitism(organism, population[j], objective_function)\n",
        "\n",
        "                population[i] = organism\n",
        "            print(f\"Iteration {iteration+1}/{self.iterations}, Best Fitness: {best_fitness}\")\n",
        "\n",
        "        return best_solution\n",
        "\n",
        "    def _initialize_solution(self):\n",
        "        alpha = random.uniform(0.5, 2.0)\n",
        "        beta = random.uniform(0.5, 2.0)\n",
        "        return (alpha, beta)\n",
        "\n",
        "    # Realiza o mutualismo\n",
        "    def _mutualism(self, organism1, organism2, objective_function):\n",
        "        new_organism1 = self._adjust_solution(organism1)\n",
        "        new_organism2 = self._adjust_solution(organism2)\n",
        "        return new_organism1, new_organism2\n",
        "\n",
        "    # Realiza o Comensalismo\n",
        "    def _commensalism(self, organism, other_organism, objective_function):\n",
        "        new_organism = self._adjust_solution(organism)\n",
        "        return new_organism\n",
        "\n",
        "    # Realiza o Parasitismo\n",
        "    def _parasitism(self, organism, other_organism, objective_function):\n",
        "        new_organism = self._adjust_solution(organism)\n",
        "        return new_organism\n",
        "\n",
        "    # Faz um ajuste na solução para os mínimos e máximos de aplha e beta\n",
        "    def _adjust_solution(self, solution):\n",
        "        alpha, beta = solution\n",
        "        alpha += random.uniform(-0.1, 0.1)\n",
        "        beta += random.uniform(-0.1, 0.1)\n",
        "        alpha = max(0.1, min(2.0, alpha))\n",
        "        beta = max(0.1, min(2.0, beta))\n",
        "        return (alpha, beta)\n",
        "\n",
        "\"\"\"\n",
        "Classe do Algortimo híbrido SOS-ACO (Simbiose de Organismos com Ant Colony Optimization):\n",
        "\n",
        "Parâmetros:\n",
        "--> num_ants - número de formigas\n",
        "--> num_iterations - número de iterações (ou gerações)\n",
        "--> decay - fator de decaimento ou o Rô\n",
        "--> alpha, beta - parâmetros de pheromone\n",
        "--> population_size - tamanho da população\n",
        "--> sos_iterations - número de iterações (ou gerações) do algoritmo SOS\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "class SOS_ACO:\n",
        "    def __init__(self, num_ants, num_iterations, decay, alpha, beta, population_size, sos_iterations):\n",
        "        self.aco = ACO(num_ants, num_iterations, decay, alpha, beta)\n",
        "        self.sos = SOS(population_size, sos_iterations)\n",
        "\n",
        "    # Combina ACO e SOS para otimizar os parâmetros do ACO (alpha e beta).\n",
        "    # Utiliza o SOS para encontrar os melhores valores de alpha e beta que minimizam a distância total do caminho encontrado pelo ACO.\n",
        "    # Execução do Experimento:\n",
        "      # 1) Baixa o arquivo de dados do problema TSP \"kroA100.tsp\".\n",
        "      # 2) Carrega o problema usando a biblioteca tsplib95.\n",
        "      # 3) Executa o algoritmo híbrido SOS-ACO.\n",
        "      # 4) Imprime e (opcionalmente) visualiza os resultados.\n",
        "    def run(self, distances):\n",
        "        def objective_function(params):\n",
        "            alpha, beta = params\n",
        "            self.aco.alpha = alpha\n",
        "            self.aco.beta = beta\n",
        "            _, distance = self.aco.run(distances)\n",
        "            return distance\n",
        "\n",
        "        best_params = self.sos.optimize(objective_function)\n",
        "        self.aco.alpha, self.aco.beta = best_params\n",
        "        best_path, best_distance = self.aco.run(distances)\n",
        "        return best_path, best_distance\n",
        "\n",
        "# Começa aqui a impressão dos resultados da execução\n",
        "def print_results(experimental, article):\n",
        "    print(\"\\nExperimental Results:\")\n",
        "    for name, data in experimental.items():\n",
        "        print(f\"- {name}: Distance = {data['distance']:.2f} ± {data['std_dev']:.2f}, Time = {data['time']:.2f} seconds\")\n",
        "\n",
        "    print(\"\\nArticle Results:\")\n",
        "    for name, data in article.items():\n",
        "        print(f\"- {name}: Distance = {data['distance']}, Time = {data.get('time', 'N/A')}\")\n",
        "\n",
        "# Começa aqui a execução do experimento\n",
        "def run_experiment(problem, num_runs=10):\n",
        "    best_distances = []\n",
        "    total_time = 0  # Acompanhe o tempo total de todas as execuções\n",
        "\n",
        "    # Obtenha distâncias como um array NumPy para indexação eficiente\n",
        "    graph = problem.get_graph()\n",
        "    distances = nx.to_numpy_array(graph)  # Converter gráfico NetworkX em matriz NumPy\n",
        "\n",
        "    for _ in range(num_runs):\n",
        "        start_time = time.time()\n",
        "        # é aqui que altera os parâmetros gerais de execução\n",
        "        sos_aco = SOS_ACO(num_ants=10, num_iterations=50, decay=0.95, alpha=1.0, beta=2.0, population_size=20, sos_iterations=10)\n",
        "        best_path, best_distance = sos_aco.run(distances)  # Use a matriz NumPy para distâncias\n",
        "        best_distances.append(best_distance)\n",
        "\n",
        "        end_time = time.time()\n",
        "        total_time += (end_time - start_time)\n",
        "\n",
        "    # calculo da média da distancia\n",
        "    avg_distance = np.mean(best_distances)\n",
        "    std_dev = np.std(best_distances)\n",
        "    avg_time = total_time / num_runs\n",
        "    return avg_distance, std_dev, avg_time\n",
        "\n",
        "\n",
        "# Baixe e processe o conjunto de dados\n",
        "url = 'https://raw.githubusercontent.com/mastqe/tsplib/master/kroA100.tsp'\n",
        "response = requests.get(url)\n",
        "\n",
        "with open('kroA100.tsp', 'w') as f: # cria 1 arquivo temporário do kroA100\n",
        "    f.write(response.text)\n",
        "\n",
        "problem = tsplib95.load('kroA100.tsp')\n",
        "\n",
        "# Execute o experimento e armazene os resultados\n",
        "mean_kroa100, std_kroa100, time_kroa100 = run_experiment(problem)\n",
        "\n",
        "experimental_results = {\n",
        "    \"kroA100\": {\"distance\": mean_kroa100, \"std_dev\": std_kroa100, \"time\": time_kroa100}  # Adicionado desvio padrão\n",
        "}\n",
        "\n",
        "# Dados de referência do artigo (substituir por valores reais)\n",
        "article_results = {\n",
        "    \"kroA100\": {\"distance\": 21282}  # Substitua pela distância real do artigo\n",
        "}\n",
        "\n",
        "# Saída e visualização\n",
        "print_results(experimental_results, article_results)\n",
        "\n",
        "# Visualizar resultados (opcional) #ignorem esse gráfico q tá ruim. Não deu tempo de melhorar\n",
        "plt.bar(experimental_results.keys(), [v['distance'] for v in experimental_results.values()])\n",
        "plt.ylabel('Tour Distance')\n",
        "plt.title('Experimental Results (SOS-ACO)')\n",
        "plt.show()\n"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "collapsed_sections": [
        "naP7EPRF4Xvf",
        "yAFfntDw4d4y",
        "1FkOAH5J7OV0",
        "VEhygC6yAkit",
        "LSN7flsjOPqs",
        "yKdtb4JCRgDS",
        "i1J-PW1FwEJr"
      ],
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}