Use um AG para encontrar o ponto máximo da função: f(x) = x^2 sendo 0 <= x <= 31 e x é inteiro

ga.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "GA.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyMd+oFuEn9Iz5J45qJ2/2t4",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/gist/EduVencovsky/c778e6adaf84f98b5ae056dcf89f2190/ga.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "NqyPZBuOUw2P",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import numpy as np\n",
        "from numpy.random import randint\n",
        "from numpy import binary_repr as to_bin"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BvlE15XrRQyK",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# add 1 because it can return 0\n",
        "def max_func(x):\n",
        "  return 1 + pow(x, 2)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "fssd_Ee7RqF2",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# must be even\n",
        "population_size = 10"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "jANJzU2VUKA8",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# input range\n",
        "min_num = 0\n",
        "max_num = 31\n",
        "# 31 => 5 bytes\n",
        "bytes_num = 5"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ih_dUoYLsqJy",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "mutation_percentage = 1"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "LzjUglccUR8j",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def get_random_population(low, high, size):\n",
        "  return randint(low, high + 1, size)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gMTIEFlsVmtV",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# get population function value\n",
        "def get_population_value(pop): \n",
        "  return [max_func(p) for p in pop]"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ObXal2D-W_UC",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def weighted_random_selection(pop, size):\n",
        "  pop_value = get_population_value(pop)\n",
        "\n",
        "  # sum of values (weights)\n",
        "  cdf_value = np.cumsum(pop_value)\n",
        "\n",
        "  # random selection by weight\n",
        "  selected_weights = [randint(0, cdf_value[-1] + 1) for x in range(0, size)]\n",
        "\n",
        "  # find selected population individual\n",
        "  # should be binary search for better performance\n",
        "  selected_index = []\n",
        "  pop.sort()\n",
        "  for sw in selected_weights:\n",
        "    for i, c in enumerate(cdf_value):\n",
        "      if sw <= c: \n",
        "        selected_index.append(i)\n",
        "        break\n",
        "\n",
        "  # return selected individuals\n",
        "  return [pop[x] for x in selected_index]"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "YeuEyCFNmCu5",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def crossover(ind1, ind2, width):\n",
        "  cut_point = randint(1, width)\n",
        "  bin_ind1 = to_bin(ind1, width)\n",
        "  bin_ind2 = to_bin(ind2, width)\n",
        "  return [bin_ind1[:cut_point] + bin_ind2[cut_point:], bin_ind2[:cut_point] + bin_ind1[cut_point:]]\n",
        "\n",
        "def crossover_population(selected_pop, b_size):\n",
        "  count = 0\n",
        "  new_pop = []\n",
        "  while count < len(selected_pop):\n",
        "    new_pop += [int(x, 2) for x in crossover(selected_pop[count], selected_pop[count + 1], b_size)]\n",
        "    count += 2\n",
        "  return new_pop"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "EZYCjhdasuD_",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def should_do(percent):\n",
        "    return randint(100) < percent\n",
        "\n",
        "# change last bit\n",
        "def mutate(x):\n",
        "  bx = to_bin(x, width=bytes_num)\n",
        "  return int(bx[:-1] + ('0' if bx[-1] == '1' else '1'), 2)\n",
        "\n",
        "def mutate_population(pop, percentage):\n",
        "  return [mutate(p) if (should_do(percentage)) else p for p in pop]"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "JAdkCLrD1uro",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def generate_population(pop):\n",
        "  selected_pop = weighted_random_selection(pop, population_size)\n",
        "  cross_pop = crossover_population(selected_pop, bytes_num)\n",
        "  mutate_pop = mutate_population(cross_pop, mutation_percentage)\n",
        "  return mutate_pop"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "4RcwDgOUvvcg",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 289
        },
        "outputId": "6b2baf63-5451-4246-9186-3728d706eba4"
      },
      "source": [
        "generation_limit = 15\n",
        "pop = get_random_population(min_num, max_num, population_size)\n",
        "print('population 0', pop)\n",
        "for i in range(0, generation_limit):\n",
        "  pop = generate_population(pop)\n",
        "  print('population ' + str(i + 1), pop)"
      ],
      "execution_count": 1462,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "population 0 [ 4  1  0  3 29 20 26 31  3 27]\n",
            "population 1 [20, 11, 4, 4, 28, 19, 27, 31, 31, 20]\n",
            "population 2 [24, 31, 20, 20, 27, 31, 20, 20, 23, 28]\n",
            "population 3 [20, 20, 23, 31, 20, 20, 27, 27, 28, 23]\n",
            "population 4 [20, 23, 20, 20, 28, 20, 28, 27, 27, 20]\n",
            "population 5 [20, 20, 28, 20, 27, 28, 20, 20, 20, 20]\n",
            "population 6 [20, 20, 20, 29, 20, 20, 28, 20, 29, 26]\n",
            "population 7 [20, 20, 28, 21, 29, 29, 28, 28, 22, 24]\n",
            "population 8 [29, 29, 29, 21, 20, 31, 29, 20, 20, 29]\n",
            "population 9 [29, 29, 29, 20, 28, 21, 21, 28, 29, 20]\n",
            "population 10 [29, 29, 21, 28, 28, 29, 21, 20, 21, 29]\n",
            "population 11 [20, 29, 21, 21, 20, 29, 29, 28, 29, 29]\n",
            "population 12 [21, 29, 21, 21, 29, 29, 29, 29, 28, 29]\n",
            "population 13 [20, 29, 29, 29, 29, 29, 28, 29, 29, 29]\n",
            "population 14 [29, 29, 20, 29, 29, 29, 29, 29, 29, 29]\n",
            "population 15 [21, 28, 29, 29, 28, 29, 29, 29, 29, 29]\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}