demo/OptFrame_BRKGA_Official.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "# Installation"
      ],
      "metadata": {
        "id": "WIXTgxPD6k0z"
      }
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8edYk1L84BBx",
        "outputId": "25766d24-254b-45d0-8c2c-c3d69c7fecae"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Reading package lists... Done\n",
            "Building dependency tree       \n",
            "Reading state information... Done\n",
            "g++-10 is already the newest version (10.3.0-1ubuntu1~20.04).\n",
            "0 upgraded, 0 newly installed, 0 to remove and 34 not upgraded.\n",
            "g++-10 (Ubuntu 10.3.0-1ubuntu1~20.04) 10.3.0\n",
            "Copyright (C) 2020 Free Software Foundation, Inc.\n",
            "This is free software; see the source for copying conditions.  There is NO\n",
            "warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.\n",
            "\n",
            "update-alternatives: renaming gcc link from /usr/bin/x86_64-linux-gnu-gcc to /usr/bin/gcc\n",
            "update-alternatives: renaming gcc link from /usr/bin/gcc to /usr/bin/x86_64-linux-gnu-gcc\n"
          ]
        }
      ],
      "source": [
        "!apt install -y g++-10\n",
        "!g++-10 --version\n",
        "!update-alternatives --install /usr/bin/g++ g++ /usr/bin/g++-10 10\n",
        "!update-alternatives --install /usr/bin/gcc gcc /usr/bin/gcc-10 10\n",
        "!update-alternatives --install /usr/bin/x86_64-linux-gnu-gcc gcc /usr/bin/gcc-10 10"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "!pip install optframe -v\n",
        "\n",
        "def test_optframe():\n",
        "  import optframe\n",
        "  engine = optframe.Engine()\n",
        "  engine.welcome()\n",
        "  print(\"pyoptframe:\", optframe.__version__)\n",
        "#see: Execution Environment (Ambiente de Execução) -> See log registry (Ver registros de logs)\n",
        "test_optframe()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "vBHzbKKV5wJx",
        "outputId": "0fdc3eaa-9638-4c0f-dc46-e9e827cf0e5e"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Using pip 23.1.2 from /usr/local/lib/python3.10/dist-packages/pip (python 3.10)\n",
            "Looking in indexes: https://pypi.org/simple, https://us-python.pkg.dev/colab-wheels/public/simple/\n",
            "Requirement already satisfied: optframe in /usr/local/lib/python3.10/dist-packages (5.0.21rc0)\n",
            "pyoptframe: 5.0.21rc0\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Definition of Traveling Salesman Problem (TSP)"
      ],
      "metadata": {
        "id": "jr-dSxbb7lgA"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Solution and ProblemContext**"
      ],
      "metadata": {
        "id": "hI5ymWSu7zdf"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# OptFrame Python Demo TSP - Traveling Salesman Problem\n",
        "\n",
        "import optframe\n",
        "\n",
        "class SolutionTSP(object):\n",
        "    def __init__(self):\n",
        "        # number of cities in solution\n",
        "        self.n = 0\n",
        "        # visited cities as a list\n",
        "        self.cities = []\n",
        "\n",
        "    # MUST provide some printing mechanism\n",
        "    def __str__(self):\n",
        "        return f\"SolutionTSP(n={self.n};cities={self.cities})\"\n",
        "\n",
        "    # MUST provide some deepcopy mechanism\n",
        "    def __deepcopy__(self, memo):\n",
        "        sol2 = SolutionTSP()\n",
        "        sol2.n = self.n\n",
        "        sol2.cities = [i for i in self.cities]\n",
        "        return sol2\n",
        "\n",
        "    def __del__(self):\n",
        "        # print(\"~SolutionTSP\")\n",
        "        pass\n",
        "import math\n",
        "\n",
        "class ProblemContextTSP(object):\n",
        "    def __init__(self):\n",
        "        print('Init TSP')\n",
        "        # may store current optframe engine for local usage\n",
        "        self.engine = None\n",
        "        # number of cities\n",
        "        self.n = 0\n",
        "        # x coordinates\n",
        "        self.vx = []\n",
        "        # y coordinates\n",
        "        self.vy = []\n",
        "        # distance matrix\n",
        "        self.dist = []\n",
        "        \n",
        "   # Example: \"3\\n1 10 10\\n2 20 20\\n3 30 30\\n\"\n",
        "\n",
        "    def load(self, filename):\n",
        "        with open(filename, 'r') as f:\n",
        "            lines = f.readlines()\n",
        "            self.n = int(lines[0])\n",
        "            for i in range(self.n):\n",
        "               id_x_y = lines[i+1].split()\n",
        "               # ignore id_x_y[0]\n",
        "               self.vx.append(int(id_x_y[1]))\n",
        "               self.vy.append(int(id_x_y[2]))\n",
        "            #\n",
        "            self.dist = [[0 for col in range(self.n)] for row in range(self.n)]\n",
        "            for i in range(self.n):\n",
        "               for j in range(self.n):\n",
        "                  self.dist[i][j] = round(self.euclidean(self.vx[i], self.vy[i], self.vx[j], self.vy[j]))\n",
        "\n",
        "    def euclidean(self, x1, y1, x2, y2):\n",
        "        return math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))\n",
        "\n",
        "    def __str__(self):\n",
        "        return f\"ProblemContextTSP(n={self.n};vx={self.vx};vy={self.vy};dist={self.dist})\"\n",
        "\n"
      ],
      "metadata": {
        "id": "KXLXmuVX6CRD"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Evaluator and Constructive**"
      ],
      "metadata": {
        "id": "nTD6qr6Q8A8l"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "\n",
        "def mycallback_fevaluate(pTSP: ProblemContextTSP, s: SolutionTSP):\n",
        "    assert (s.n == pTSP.n)\n",
        "    assert (len(s.cities) == s.n)\n",
        "    # remember this is an API1d method\n",
        "    f = 0.0\n",
        "    for i in range(pTSP.n-1):\n",
        "      f += pTSP.dist[s.cities[i]][s.cities[i + 1]];\n",
        "    f += pTSP.dist[s.cities[int(pTSP.n) - 1]][s.cities[0]];\n",
        "    return f\n",
        "import random\n",
        "\n",
        "def mycallback_constructive(problemCtx: ProblemContextTSP) -> SolutionTSP:\n",
        "    sol = SolutionTSP()\n",
        "    for i in range(problemCtx.n):\n",
        "        sol.cities.append(i)\n",
        "    random.shuffle(sol.cities)\n",
        "    sol.n = problemCtx.n\n",
        "    return sol\n",
        "\n",
        "\n",
        "\n"
      ],
      "metadata": {
        "id": "CCiG4xH38HRB"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Definition of Move**"
      ],
      "metadata": {
        "id": "Hq1MZ4IY9Ojt"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "\n",
        "# move\n",
        "class MoveSwap(object):\n",
        "    def __init__(self):\n",
        "        #print('__init__ MoveSwap')\n",
        "        self.i = 0\n",
        "        self.j = 0\n",
        "\n",
        "    def __del__(self):\n",
        "        # print(\"~MoveSwap\")\n",
        "        pass\n",
        "\n",
        "# Move Apply MUST return an Undo Move or Reverse Move (a Move that can undo current application)\n",
        "def apply_swap(problemCtx: ProblemContextTSP, m: MoveSwap, sol: SolutionTSP) -> MoveSwap:\n",
        "    i = m.i\n",
        "    j = m.j\n",
        "    #\n",
        "    aux = sol.cities[j]\n",
        "    sol.cities[j] = sol.cities[i]\n",
        "    sol.cities[i] = aux\n",
        "    # must create reverse move (j,i)\n",
        "    mv = MoveSwap()\n",
        "    mv.i = j\n",
        "    mv.j = i\n",
        "    return mv\n",
        "\n",
        "# Moves can be applied or not (best performance is to have a True here)\n",
        "def cba_swap(problemCtx: ProblemContextTSP, m: MoveSwap, sol: SolutionTSP) -> bool:\n",
        "    return True\n",
        "\n",
        "# Move equality must be provided\n",
        "def eq_swap(problemCtx: ProblemContextTSP, m1: MoveSwap, m2: MoveSwap) -> bool:\n",
        "    return (m1.i == m2.i) and (m1.j == m2.j)"
      ],
      "metadata": {
        "id": "rpsAGOQ-9Yst"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Definition of NS (random) and NSSeq (iterator)**"
      ],
      "metadata": {
        "id": "GFwDI5ek9dyN"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "\n",
        "def mycallback_ns_rand_swap(pTSP: ProblemContextTSP, sol: SolutionTSP) -> MoveSwap:\n",
        "    i = random.randint(0, pTSP.n - 1)\n",
        "    j = i\n",
        "    while  j<= i:\n",
        "        i = random.randint(0, pTSP.n - 1)\n",
        "        j = random.randint(0, pTSP.n - 1)\n",
        "    mv = MoveSwap()\n",
        "    mv.i = i\n",
        "    mv.j = j\n",
        "    return mv\n",
        "\n",
        "\n",
        "# For NSSeq, one must provide a Move Iterator\n",
        "# A Move Iterator has five actions: Init, First, Next, IsDone and Current\n",
        "\n",
        "\n",
        "class IteratorSwap(object):\n",
        "    def __init__(self):\n",
        "        # print('__init__ IteratorSwap')\n",
        "        self.k = 0\n",
        "\n",
        "    def __del__(self):\n",
        "        # print(\"__del__ IteratorSwap\")\n",
        "        pass\n",
        "\n",
        "\n",
        "def mycallback_nsseq_it_init_swap(pTSP: ProblemContextTSP, sol: SolutionTSP) -> IteratorSwap:\n",
        "    it = IteratorSwap()\n",
        "    it.i = -1\n",
        "    it.j = -1\n",
        "    return it\n",
        "\n",
        "\n",
        "def mycallback_nsseq_it_first_swap(pTSP: ProblemContextTSP, it: IteratorSwap):\n",
        "    it.i = 0\n",
        "    it.j = 1\n",
        "\n",
        "\n",
        "def mycallback_nsseq_it_next_swap(pTSP: ProblemContextTSP, it: IteratorSwap):\n",
        "    if it.j < pTSP.n - 1:\n",
        "        it.j = it.j+1\n",
        "    else:\n",
        "        it.i = it.i + 1\n",
        "        it.j = it.i + 1\n",
        "\n",
        "def mycallback_nsseq_it_isdone_swap(pTSP: ProblemContextTSP, it: IteratorSwap):\n",
        "    return it.i >= pTSP.n - 1\n",
        "\n",
        "\n",
        "def mycallback_nsseq_it_current_swap(pTSP: ProblemContextTSP, it: IteratorSwap):\n",
        "    mv = MoveSwap()\n",
        "    mv.i = it.i\n",
        "    mv.j = it.j\n",
        "    return mv"
      ],
      "metadata": {
        "id": "UAcWeJna9i8p"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Decoder for BRKGA**"
      ],
      "metadata": {
        "id": "JHAaRX_w8--I"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#\n",
        "# random constructive: updates parameter ptr_array_double of type (LibArrayDouble*)\n",
        "#\n",
        "def mycallback_constructive_rk(problemCtx: ProblemContextTSP, ptr_array_double) -> int:\n",
        "    rkeys = []\n",
        "    for i in range(problemCtx.n):\n",
        "        key = random.random() # [0,1] uniform\n",
        "        rkeys.append(key)\n",
        "    #\n",
        "    ptr_array_double.contents.size = len(rkeys)\n",
        "    ptr_array_double.contents.v = optframe.engine.callback_adapter_list_to_vecdouble(rkeys)\n",
        "    return len(rkeys)\n",
        "\n",
        "#\n",
        "# decoder function: receives a problem instance and an array of random keys (as LibArrayDouble)\n",
        "#\n",
        "def mycallback_decoder_rk(problemCtx: ProblemContextTSP, array_double : optframe.engine.LibArrayDouble) -> SolutionTSP:\n",
        "    #\n",
        "    sol = SolutionTSP()\n",
        "    #\n",
        "    lpairs = []\n",
        "    for i in range(array_double.size):\n",
        "        p = [array_double.v[i], i]\n",
        "        lpairs.append(p)\n",
        "    #\n",
        "    #print(\"lpairs: \", lpairs)\n",
        "    sorted_list = sorted(lpairs)\n",
        "    #print(\"sorted_list: \", sorted_list)\n",
        "    #\n",
        "    sol.n = problemCtx.n\n",
        "    sol.cities = []\n",
        "    for i in range(array_double.size):\n",
        "        sol.cities.append(sorted_list[i][1]) # append index of city in order\n",
        "    return sol"
      ],
      "metadata": {
        "id": "ElRBExI68cai"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [],
      "metadata": {
        "id": "NAfYKlc08dLx"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "# BRKGA Example"
      ],
      "metadata": {
        "id": "a8aC1QgL6r_i"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "################\n",
        "# BEGIN: MAIN\n",
        "################\n",
        "\n",
        "# CREATE EXAMPLE FOR FILE\n",
        "f = open(\"tsp-example.txt\", \"w\")\n",
        "f.write(\"5\\n\")\n",
        "f.write(\"1 10 10\\n\")\n",
        "f.write(\"2 20 20\\n\")\n",
        "f.write(\"3 30 30\\n\")\n",
        "f.write(\"4 40 40\\n\")\n",
        "f.write(\"5 50 50\\n\")\n",
        "f.close()"
      ],
      "metadata": {
        "id": "LJmggale_tCe"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "\n",
        "# set random seed for system\n",
        "random.seed(0) # bad generator, just an example..\n",
        "\n",
        "# loads problem from filesystem\n",
        "pTSP = ProblemContextTSP()\n",
        "pTSP.load('tsp-example.txt')\n",
        "\n",
        "# initializes optframe engine\n",
        "pTSP.engine = optframe.Engine(optframe.APILevel.API1d)\n",
        "# print(pTSP)\n",
        "\n",
        "# Register Basic Components\n",
        "\n",
        "ev_idx = pTSP.engine.minimize(pTSP, mycallback_fevaluate)\n",
        "print(\"evaluator id:\", ev_idx)\n",
        "\n",
        "c_rk_idx = pTSP.engine.add_constructive_rk(pTSP, mycallback_constructive_rk)\n",
        "print(\"c_rk_idx=\", c_rk_idx)\n",
        "\n",
        "pTSP.engine.list_components(\"OptFrame:\")\n",
        "\n",
        "initepop_rk_id = pTSP.engine.build_component(\n",
        "    \"OptFrame:ComponentBuilder:EA:RK:BasicInitialEPopulationRKBuilder\", \n",
        "    \"OptFrame:Constructive:EA:RK:ConstructiveRK 0\",\n",
        "    \"OptFrame:InitialEPopulation:EA:RK:InitialEPopulationRK\")\n",
        "print(\"initepop_rk_id=\", initepop_rk_id)\n",
        "\n",
        "print(\"\")\n",
        "print(\"WILL CREATE DECODER!!\")\n",
        "dec_rk_idx = pTSP.engine.add_decoder_rk(pTSP, mycallback_decoder_rk)\n",
        "print(\"dec_rk_idx=\", dec_rk_idx)\n",
        "\n",
        "pTSP.engine.list_components(\"OptFrame:\")\n",
        "\n",
        "print(\"\")\n",
        "print(\"WILL BUILD COMPLETE DECODER WITH EVALUATOR!!\")\n",
        "drk_rk_id = pTSP.engine.build_component(\n",
        "    \"OptFrame:ComponentBuilder:EA:RK:BasicDecoderRandomKeysBuilder\", \n",
        "    \"OptFrame:GeneralEvaluator:Evaluator 0  OptFrame:EA:RK:DecoderRandomKeysNoEvaluation 0\",\n",
        "    \"OptFrame:EA:RK:DecoderRandomKeys\")\n",
        "print(\"drk_rk_id=\", drk_rk_id)\n",
        "\n",
        "\n",
        "# =======================\n",
        "\n",
        "print(\"\")\n",
        "print(\"testing builder (build_global_search) for BRKGA...\")\n",
        "print(\"\")\n",
        "\n",
        "g_idx = pTSP.engine.build_global_search(\n",
        "    \"OptFrame:ComponentBuilder:GlobalSearch:EA:RK:BRKGA\",\n",
        "    \"OptFrame:EA:RK:DecoderRandomKeys 0  OptFrame:InitialEPopulation:EA:RK:InitialEPopulationRK 0 \"\n",
        "    \"30 1000 0.4 0.3 0.6\")\n",
        "print(\"g_idx=\", g_idx)\n",
        "\n",
        "\n",
        "\n",
        "pTSP.engine.list_components(\"OptFrame:\")\n",
        "\n",
        "print(\"\")\n",
        "print(\"testing execution of GlobalSearch (run_global_search) for BRKGA...\")\n",
        "print(\"\")\n",
        "\n",
        "lout = pTSP.engine.run_global_search(g_idx, 3.0)\n",
        "print('solution:', lout)\n",
        "\n",
        "print(\"FINISHED\")"
      ],
      "metadata": {
        "id": "Pp7k9f8B8Z3V",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "eb60049e-b749-4f20-e16c-f377bf75da6b"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Init TSP\n",
            "evaluator id: 0\n",
            "c_rk_idx= 0\n",
            "initepop_rk_id= 0\n",
            "\n",
            "WILL CREATE DECODER!!\n",
            "dec_rk_idx= 0\n",
            "\n",
            "WILL BUILD COMPLETE DECODER WITH EVALUATOR!!\n",
            "drk_rk_id= 0\n",
            "\n",
            "testing builder (build_global_search) for BRKGA...\n",
            "\n",
            "g_idx= 0\n",
            "\n",
            "testing execution of GlobalSearch (run_global_search) for BRKGA...\n",
            "\n",
            "solution: SearchOutput(status=0;has_best=True;best_s=SolutionTSP(n=5;cities=[0, 1, 2, 4, 3]);best_e=112.0;)\n",
            "FINISHED\n"
          ]
        }
      ]
    }
  ]
}