agmochila.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "agmochila.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyOKA5VJdA2g2NNFjtYkyszj",
      "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/github/eduardadelavle/projeto-InteligenciaArtificial/blob/master/agmochila.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8xVQvIqf51s-",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import numpy as np\n",
        "import pandas as pd\n",
        "import random as rd\n",
        "from random import randint\n",
        "import matplotlib.pyplot as plt\n",
        "import random\n",
        " #utilização do random para questões aleatórias"
      ],
      "execution_count": 118,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aEqIPKja6dsG",
        "colab_type": "text"
      },
      "source": [
        "**Criação da mochila e dos itens**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "hkYLfOvF6b3V",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 374
        },
        "outputId": "3eae08ef-430e-4f60-d106-1dfd42c9018e"
      },
      "source": [
        "itens = np.arange(1,11)\n",
        "\n",
        "#randint nesse caso abaixo gera um vetor aleatório de 10 posições com valores de 1 até 15\n",
        "peso = np.random.randint(1, 15, size = 10)    #10 pesos aleatorios entre 1 e 15\n",
        "valor = np.random.randint(10, 150, size = 10) #10 valores entre 10 e 150\n",
        "peso_maximo_mochila = 20    \n",
        "print('Item No.   Peso   Valor')\n",
        "#shape pega o tamanho do vetor \n",
        "for i in range(itens.shape[0]):  #shape retorna quantidade de elemento de um vetor\n",
        "    print('{0}          {1}         {2}\\n'.format(itens[i], peso[i], valor[i]))"
      ],
      "execution_count": 127,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Item No.   Peso   Valor\n",
            "1          3         99\n",
            "\n",
            "2          1         26\n",
            "\n",
            "3          11         54\n",
            "\n",
            "4          2         72\n",
            "\n",
            "5          8         115\n",
            "\n",
            "6          7         142\n",
            "\n",
            "7          1         16\n",
            "\n",
            "8          6         140\n",
            "\n",
            "9          9         25\n",
            "\n",
            "10          11         39\n",
            "\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LQksrRtA6x-N",
        "colab_type": "text"
      },
      "source": [
        "**Cria população inicial aleatóriamente e definição o número de gerações (iterações) que o processo de busca irá ocorrer**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "IAMSYQfs6b-H",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 221
        },
        "outputId": "ef2326e4-0387-45ec-967c-a1ca88aa9d43"
      },
      "source": [
        "tamanho_populacao = 10\n",
        "\n",
        "#Esse comando abaixo serve para estabelecer um vetor onde temos 10 linhas com 10 colunas\n",
        "pop_size = (tamanho_populacao, itens.shape[0])\n",
        "\n",
        "print('Tamanho da População = {}'.format(pop_size))\n",
        "\n",
        "populacao_inicial = np.random.randint(2, size = pop_size)\n",
        "populacao_inicial = populacao_inicial.astype(int)\n",
        "num_geracoes = 100\n",
        "print('Populacao Inicial: \\n{}'.format(populacao_inicial))\n",
        "\n",
        "# 1 significa tem tem o item na mochila e 0 não"
      ],
      "execution_count": 120,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Tamanho da População = (10, 10)\n",
            "Populacao Inicial: \n",
            "[[0 1 1 0 1 1 0 1 0 0]\n",
            " [0 0 1 1 1 0 1 0 1 1]\n",
            " [0 1 0 1 1 1 1 1 0 1]\n",
            " [1 1 1 0 1 0 0 0 1 1]\n",
            " [1 1 0 1 0 0 1 1 1 1]\n",
            " [0 1 1 0 0 1 1 1 0 0]\n",
            " [1 1 0 0 0 0 1 1 0 0]\n",
            " [0 0 1 0 1 0 1 1 1 0]\n",
            " [1 1 0 1 0 0 0 0 1 0]\n",
            " [0 1 0 1 1 1 0 1 1 0]]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GeiLRan17UbB",
        "colab_type": "text"
      },
      "source": [
        "**Calcula o fitness da população existente**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BZy6hU-l6cIR",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#Calcula Fitness\n",
        "def calc_fitness(peso, valor, populacao, peso_maximo_mochila): #valor cabe na mochila\n",
        "    fitness = np.empty(populacao.shape[0])\n",
        "    for i in range(populacao.shape[0]):\n",
        "        a1 = np.sum(populacao[i] * valor)\n",
        "        a2 = np.sum(populacao[i] * peso) # verifica o peso e multiplica pela posição, depois soma \n",
        "        if a2 <= peso_maximo_mochila:  #verifica se o peso n ultrapassou o de 20\n",
        "            fitness[i] = 1  # se for menor que 20 ele guarda\n",
        "        else :\n",
        "            fitness[i] = 0   # se for maior ele elimina\n",
        "    return fitness.astype(int)   "
      ],
      "execution_count": 128,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LUxPIu-X7Z1i",
        "colab_type": "text"
      },
      "source": [
        "**Executa o processo** - aplicação do genético\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "_8miRzVu6cFp",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def optimize(pesos, valor, population, pop_size, num_geracoes, peso_maximo_mochila):\n",
        "    parameters, fitness_history = [], []\n",
        "    \n",
        "    num_pais_selecao = int(pop_size[0]*0.6) #numero de pais que participam da seleção cruzamento, mutação\n",
        "    #faz a evolução do processo durante o número de gerações\n",
        "    for i in range(num_geracoes):\n",
        "        #calcula o fitness da população atual\n",
        "        fitness = calc_fitness(pesos, valor, population, peso_maximo_mochila)\n",
        "        \n",
        "        #elitismo - entra a partir da 2° geração, mantém os melhores individuios\n",
        "        population=population[fitness.argsort()[-pop_size[0]:][::-1]]\n",
        "        fitness=fitness[fitness.argsort()[-pop_size[0]:][::-1]]\n",
        "        #fitness.argsort: ordena do menor para maior.\n",
        "        \n",
        "        fitness_history.append(fitness) #imprime gráfico\n",
        "\n",
        "        #seleciona os pais\n",
        "        pais = selection(fitness, num_pais_selecao, population)\n",
        "\n",
        "        #realiza o cruzamento\n",
        "        filhos = crossover(pais)\n",
        "\n",
        "        #realiza a mutação\n",
        "        mutants = mutation(filhos)\n",
        "\n",
        "        #insere novos filhos na populacao\n",
        "        if(mutants.size != 0.):\n",
        "          population=np.append(population, mutants, axis = 0)\n",
        "        \n",
        "        #Mantém apenas vetores únicos, ignorando repetições\n",
        "        population, index = np.unique(population, axis=0, return_index=True)\n",
        "\n",
        "        \n",
        "    print('Última Geração: \\n{}\\n'.format(population)) \n",
        "    fitness_last_gen = calc_fitness(pesos, valor, population, peso_maximo_mochila)  \n",
        "\n",
        "    print('Fitness da última geração: \\n{}\\n'.format(fitness_last_gen))\n",
        "    max_fitness = np.where(fitness_last_gen == np.max(fitness_last_gen))\n",
        "    \n",
        "    parameters.append(population[max_fitness[0][0],:])\n",
        "    return parameters, fitness_history"
      ],
      "execution_count": 130,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "JEnRicug8QUy",
        "colab_type": "text"
      },
      "source": [
        "**Operação de seleção (usando torneio)**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "JxxvHbE16cEB",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def selection(fitness2, num_pais, population):\n",
        "    fitness = list(fitness2)\n",
        "    parents = np.empty((num_pais, population.shape[1]))\n",
        "    \n",
        "    #taxa de comparação\n",
        "    k=0.6\n",
        "    for i in range(num_pais):\n",
        "\n",
        "        #seleciona aleatoriamente 2 individuos da população\n",
        "        x1=random.randint(0, population.shape[0]-1)\n",
        "        x2=random.randint(0, population.shape[0]-1)\n",
        "\n",
        "        #Verifica se já não foram utilizados, se foram utilizados tenho\n",
        "        #que selecionar outro\n",
        "        while (fitness[x1]==-999999):\n",
        "          x1=random.randint(0, population.shape[0]-1)\n",
        "        while (fitness[x2]==-999999):\n",
        "          x2=random.randint(0, population.shape[0]-1)\n",
        "\n",
        "        #Ajuste para o individuo de maior fitness sempre ser o x1\n",
        "        if (fitness[x1]<fitness[x2]):\n",
        "          aux=x1\n",
        "          x1=x2\n",
        "          x2=aux\n",
        "      \n",
        "        r=random.random() #valor aleatorio\n",
        "        # seleciono fitness de maior valor no primeiro caso(x1) e pior valor no segundo(x2)\n",
        "        if (r<k): \n",
        "          parents[i,:] = population[x1, :]\n",
        "          fitness[x1] = -999999\n",
        "        else:\n",
        "          parents[i,:] = population[x2, :]\n",
        "          fitness[x2] = -999999\n",
        "    # retorno todos pais selecionados\n",
        "    return parents\n",
        "  #para esse caso a chance é de encontrar melhor fitness por porcentagem é maior(60%)."
      ],
      "execution_count": 131,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1jHYa8dB8Yn_",
        "colab_type": "text"
      },
      "source": [
        "**Cruzamento**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "1lSQkbnR6cBr",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def crossover(parents):\n",
        "    #gerando um vetor para armazenar os filhos\n",
        "    vetFilhos = []\n",
        "    #determinando que no cruzamento vou pegar o meio de cada individuo\n",
        "    crossover_point = int(parents.shape[1]/2)\n",
        "\n",
        "    #estabelecendo uma taxa do cruzamento ocorrer\n",
        "    crossover_rate = 0.8\n",
        "    i=0\n",
        "    while (i < parents.shape[0]):\n",
        "        x = rd.random()\n",
        "        if x < crossover_rate:\n",
        "          parent1_index = i%parents.shape[0]\n",
        "          parent2_index = (i+1)%parents.shape[0]\n",
        "          \n",
        "          #pega a metade de cada pai para fazer os filhos\n",
        "          #f1 metade do Pai 1 e outra do Pai 2\n",
        "          #f2 metade do Pai 1 e outra do Pai 2\n",
        "\n",
        "          f1 = np.empty(parents.shape[1])\n",
        "          f2 = np.empty(parents.shape[1])\n",
        "\n",
        "          f1[0:crossover_point] = parents[parent1_index,0:crossover_point]\n",
        "          f1[crossover_point:]  = parents[parent2_index,crossover_point:]\n",
        "          \n",
        "          f2[0:crossover_point] = parents[parent2_index,0:crossover_point]\n",
        "          f2[crossover_point:]  = parents[parent1_index,crossover_point:]\n",
        "          \n",
        "          \n",
        "         vetFilhos.append(f1)\n",
        "          vetFilhos.append(f2)\n",
        "        i=i+2\n",
        "    return np.asarray(vetFilhos, dtype=np.int32)"
      ],
      "execution_count": 132,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hMw7MIKe8eew",
        "colab_type": "text"
      },
      "source": [
        "**Mutação**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9s0e_Ttz8hW7",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def mutation(vetFilhos):\n",
        "    mutants = np.empty((vetFilhos.shape))\n",
        "    mutation_rate = 0.3\n",
        "    for i in range(mutants.shape[0]):\n",
        "        random_value = rd.random()\n",
        "        mutants[i,:] = vetFilhos[i,:]\n",
        "        if random_value > mutation_rate:\n",
        "            continue\n",
        "        int_random_value = randint(0,vetFilhos.shape[1]-1)    \n",
        "        if mutants[i,int_random_value] == 0 :\n",
        "            mutants[i,int_random_value] = 1\n",
        "        else :\n",
        "            mutants[i,int_random_value] = 0\n",
        "    return mutants"
      ],
      "execution_count": 133,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "MUHQ71d99C45",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 629
        },
        "outputId": "1780489f-e24c-4fbc-d467-1a1a7db452b2"
      },
      "source": [
        "parameters, fitness_history = optimize(peso, valor, populacao_inicial, pop_size, num_geracoes, peso_maximo_mochila)\n",
        "print('A solução que de saída é: \\n{}'.format(parameters))\n",
        "itens_selecionados = itens * parameters\n",
        "print('\\nOs item que irão maximizar a mochila são:')\n",
        "total_peso=0\n",
        "total_valor=0\n",
        "for i in range(itens_selecionados.shape[1]):\n",
        "  if itens_selecionados[0][i] != 0:\n",
        "     print('{0}          {1}         {2}\\n'.format(itens[i], peso[i], valor[i]))\n",
        "     total_peso=total_peso+peso[i]\n",
        "     total_valor=total_valor+valor[i]\n",
        "print('      Peso: {0}        Valor {1}\\n'.format(total_peso,total_valor))"
      ],
      "execution_count": 126,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Última Geração: \n",
            "[[0. 0. 0. 0. 1. 1. 1. 0. 1. 1.]\n",
            " [0. 0. 0. 0. 1. 1. 1. 1. 1. 1.]\n",
            " [0. 0. 1. 0. 1. 0. 1. 0. 1. 1.]\n",
            " [0. 0. 1. 0. 1. 1. 0. 0. 1. 1.]\n",
            " [0. 0. 1. 0. 1. 1. 1. 0. 0. 1.]\n",
            " [0. 0. 1. 0. 1. 1. 1. 0. 1. 1.]\n",
            " [0. 0. 1. 0. 1. 1. 1. 1. 0. 1.]\n",
            " [1. 0. 0. 0. 1. 0. 0. 0. 1. 1.]\n",
            " [1. 0. 0. 0. 1. 0. 1. 0. 1. 1.]\n",
            " [1. 0. 0. 0. 1. 1. 0. 0. 1. 1.]\n",
            " [1. 0. 0. 0. 1. 1. 1. 0. 0. 1.]\n",
            " [1. 0. 0. 0. 1. 1. 1. 1. 0. 1.]\n",
            " [1. 0. 1. 0. 1. 0. 1. 0. 1. 1.]]\n",
            "\n",
            "Fitness da última geração: \n",
            "[459 476 442 453 405 506 422 427 480 491 443 460   0]\n",
            "\n",
            "A solução que de saída é: \n",
            "[array([0., 0., 1., 0., 1., 1., 1., 0., 1., 1.])]\n",
            "\n",
            "Os item que irão maximizar a mochila são:\n",
            "3          7         47\n",
            "\n",
            "5          5         140\n",
            "\n",
            "6          1         64\n",
            "\n",
            "7          1         53\n",
            "\n",
            "9          5         101\n",
            "\n",
            "10          1         101\n",
            "\n",
            "      Peso: 20        Valor 506\n",
            "\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}