Mudanças entre as edições de "Genéticos: Problema da Mochila em Python"

De Aulas
Linha 4: Linha 4:
  
 
Para mostrar uma implementação de um Algoritmo Genético, iremos trabalhar com o '''Problema da Mochila'''.
 
Para mostrar uma implementação de um Algoritmo Genético, iremos trabalhar com o '''Problema da Mochila'''.
 +
 +
Sobre o problema da mochila:
  
 
* Problema de otimização combinatória (NP-Completo)
 
* Problema de otimização combinatória (NP-Completo)
Linha 11: Linha 13:
 
<center>[[Image:Ag_mochila.png|400px]]</center>
 
<center>[[Image:Ag_mochila.png|400px]]</center>
  
−
Podemos representar a '''aptidão''' de uma solução como a soma dos valores dos objetos e com uma penalidade para soluções que passam do limite de volume.
+
Podemos representar a aptidão de uma solução como a soma dos valores dos objetos e com uma penalidade para soluções que passam do limite de volume.
  
 
* Queremos o maior valor possível sem ultrapassar o limite da mochila.
 
* Queremos o maior valor possível sem ultrapassar o limite da mochila.
 
* Vários itens que gostaria de levar em uma mochila
 
* Vários itens que gostaria de levar em uma mochila
 
* Cada item tem um peso e um benefício, ou valor
 
* Cada item tem um peso e um benefício, ou valor
−
* Há uma capacidade limite de peso
+
* Existe uma capacidade limite de peso
 
* Deve-se carregar itens com o máximo valor total sem superar o limite de peso
 
* Deve-se carregar itens com o máximo valor total sem superar o limite de peso
  
 
= Programa em Python =
 
= Programa em Python =
 +
 +
Coloquei o programa no github, fica mais fácil, fazer atualizações, de baixar e bom para visualizar. Vejam que o programa deu quase 300 linhas, mas é porque está todo comentado. Se tirar os comentários ele fica bem menor. É um algoritmo muito fácil e simples, talvez um dos mais fáceis de se implementar da Inteligência Artificial.
  
 
'''Link do github''': https://github.com/saulopz/ia_genetico_mochila
 
'''Link do github''': https://github.com/saulopz/ia_genetico_mochila
  
−
Pra baixar, basta executar o comando
+
Para baixar em seu computador, basta executar o comando:
  
 
  git clone https://github.com/saulopz/ia_genetico_mochila
 
  git clone https://github.com/saulopz/ia_genetico_mochila
  
 
{{tip|Eu estava fazendo procedural e estava tendo que fazer uns remendos, como encher de variáveis globais e outras coisas mais, e acho que isso estava permitindo um bug difícil de encontrar. Então decidi ir pra orientação a objetos que pra mim é mais fácil de entender e organizar. A ideia do algoritmo é a mesma que expliquei, mesmas funções, mesmaa funcionalidade, só está organizado como objetos. E, no final, era um bug bobo mesmo por causa de variáveis globais.}}
 
{{tip|Eu estava fazendo procedural e estava tendo que fazer uns remendos, como encher de variáveis globais e outras coisas mais, e acho que isso estava permitindo um bug difícil de encontrar. Então decidi ir pra orientação a objetos que pra mim é mais fácil de entender e organizar. A ideia do algoritmo é a mesma que expliquei, mesmas funções, mesmaa funcionalidade, só está organizado como objetos. E, no final, era um bug bobo mesmo por causa de variáveis globais.}}
−
 
−
== Arquivo de Configuração config.json ==
 
−
 
−
<syntaxhighlight lang=json line>
 
−
{
 
−
  "capacity": "22",
 
−
  "items": [
 
−
    { "name": "notebook", "value": "5", "weight": "7" },
 
−
    { "name": "tv", "value": "8", "weight": "8" },
 
−
    { "name": "tablet", "value": "3", "weight": "4" },
 
−
    { "name": "anel", "value": "2", "weight": "10" },
 
−
    { "name": "colar", "value": "7", "weight": "4" },
 
−
    { "name": "videogame", "value": "9", "weight": "6" },
 
−
    { "name": "smarthone", "value": "4", "weight": "4" }
 
−
  ]
 
−
}
 
−
</syntaxhighlight>
 
−
 
−
== Programa mochila.py ==
 
−
<syntaxhighlight lang=Python line>
 
−
import json
 
−
from random import *
 
−
 
−
 
−
# ITEM CLASS ---------------------------------------------
 
−
# representa os itens do arquivo config.json
 
−
class Item:
 
−
    def __init__(self, name, value, weight):
 
−
        self.name = name        # nome do produto
 
−
        self.value = value      # valor
 
−
        self.weight = weight    # peso
 
−
 
−
 
−
# DATA STATIC CLASS ------------------------------------
 
−
# Lê as configurações do arquivo config.json e carrega
 
−
# nessa classe estática para ser usada em todo o programa
 
−
class Data:
 
−
    size = 0        # quantidade de itens
 
−
    capacity = 0    # capacidade da mochila
 
−
    items = []      # vetor contendo os itens
 
−
 
−
    @staticmethod
 
−
    def load():
 
−
        # abre o arquivo e converte para um objeto json
 
−
        file = open("config.json")
 
−
        data = json.load(file)
 
−
        file.close()
 
−
        # coloca as informações do objeto json na classe
 
−
        # Data pra facilitar o acesso aos dados
 
−
        Data.capacity = int(data["capacity"])
 
−
        for i in range(len(data["items"])):
 
−
            name = data["items"][i]["name"]
 
−
            value = int(data["items"][i]["value"])
 
−
            weight = int(data["items"][i]["weight"])
 
−
            Data.items.append(Item(name, value, weight))
 
−
            Data.size += 1
 
−
 
−
 
−
# INDVIDUAL CLASS -------------------------------------------
 
−
# Cada instância dessa classe representa cada indivíduo da
 
−
# população do ecossistema do algoritmo
 
−
class Individual:
 
−
    def __init__(self):
 
−
        self.fitness = 0                # aptidão do indivíduo
 
−
        self.accumulated_fitness = 0    # aptidão acumulada (usada na seleção)
 
−
        self.selected = False          # se indivíduo foi selecionado
 
−
        self.gene = []                  # gens, representando os ítens na mochiila
 
−
        for i in range(Data.size):
 
−
            # coloca ítens aleatórios na mochila
 
−
            self.gene.append(randint(0, 1))
 
−
 
−
    # Calcula a aptidão do indivíduo
 
−
    def evaluate(self):
 
−
        self.accumulated_fitness = 0
 
−
        self.fitness = 0
 
−
        weight = 0
 
−
        # primeiro soma todos os valores dos ítens que estão inclusos
 
−
        # nessa solução de mochila
 
−
        for i in range(Data.size):
 
−
            if self.gene[i] == 1:
 
−
                self.fitness += Data.items[i].value
 
−
                weight += Data.items[i].weight
 
−
        # caso o peso total de ítens incluso seja maior que a capacidade
 
−
        # da mochila, dá uma penalidade, diminuindo em 100 a aptidão
 
−
        if weight > Data.capacity:
 
−
            self.fitness -= 100
 
−
 
−
    # apresenta informações do indivíduo de forma simplificada para debug
 
−
    def show(self):
 
−
        print(self.gene, self.fitness, self.selected, self.accumulated_fitness)
 
−
 
−
    # apresenta informações completas da solução, representada por um indivíduo
 
−
    def show_info(self):
 
−
        print("SOLUÇÃO ------------------------------")
 
−
        print("Capacidade da mochila:", Data.capacity)
 
−
        weight = 0
 
−
        value = 0
 
−
        for i in range(Data.size):
 
−
            if self.gene[i] == 1:
 
−
                weight += Data.items[i].weight
 
−
                value += Data.items[i].value
 
−
                print("-", Data.items[i].name, "valor:",
 
−
                      Data.items[i].value, "gold - peso:", Data.items[i].weight)
 
−
        print("Valor total:", value, "gold")
 
−
        print("Peso total :", weight)
 
−
        print("--------------------------------------")
 
−
 
−
    # clona o indivíduo e retorna uma instância dessa cópia
 
−
    def clone(self):
 
−
        other = Individual()
 
−
        for i in range(Data.size):
 
−
            other.gene[i] = self.gene[i]
 
−
        other.fitness = self.fitness
 
−
        return other
 
−
 
−
 
−
# GENETIC CLASS --------------------------------------------------
 
−
class Genetic:
 
−
    # Configuro um padrão aqui, mas faço ajustes no main
 
−
    population_size = 50            # tamanho da população
 
−
    selection_size = 20            # quantos vou selecionar
 
−
    crossover_gene_size = 2        # quantos gens vou usar no cruzamento
 
−
    mutation_individual_size = 10  # quantos indivíduos vou mutar cada geração
 
−
    mutation_gene_size = 2          # quantos gens de cada indivíduo vou mutar
 
−
    generations = 100              # por quantas gerações o algoritmo vai executar
 
−
 
−
    # constructor
 
−
    def __init__(self):
 
−
        Data.load()            # carrega as configurações
 
−
        self.population = []    # inicia com população vazia
 
−
 
−
    # mostra todos os indivíduos da população
 
−
    def show(self):
 
−
        for i in self.population:
 
−
            i.show()
 
−
 
−
    # cria a população inicial com indivíduos contendo ítens aleatórios
 
−
    def create_population(self):
 
−
        print("CREIANDO POPULAÇÃO INICIAL...")
 
−
        for i in range(Genetic.population_size):
 
−
            self.population.append(Individual())
 
−
 
−
    # calcula a aptidão de todos os indivíduos da população
 
−
    def evaluate(self):
 
−
        for i in self.population:
 
−
            i.evaluate()
 
−
        # ordena a população com base na aptidão
 
−
        self.population.sort(key=lambda x: x.fitness)
 
−
 
−
    # seleciona uma quantidade de indivíduos. Se best for verdadeiro,
 
−
    # então seleciona os melhores, se for falso, seleciona os piores.
 
−
    def selection(self, best):
 
−
        who = "MELHORES"
 
−
        if not best:
 
−
            who = "PIORES"
 
−
        print("SELECIONANDO OS", who, "INDIVÍDUOS ...")
 
−
        # como para fins de cálculo não pode haver aptidão negativa,
 
−
        # procura a menor aptidão negativa para subtrair de todos,
 
−
        # deixando todos positivos.
 
−
        lower = 0
 
−
        for i in self.population:
 
−
            if i.fitness < lower:
 
−
                lower = i.fitness
 
−
 
−
        # Se houve aptidão negativa, subtrai o menor valor de
 
−
        # todos os elementos para não termos aptidão negativa
 
−
        if lower < 0:
 
−
            for i in self.population:
 
−
                i.fitness = i.fitness - lower
 
−
 
−
        # ordena a população com base na aptidão
 
−
        self.population.sort(key=lambda x: x.fitness)
 
−
 
−
        # calcula a aptidão acumulada e aptidão total
 
−
        fitness_total = 0
 
−
        for i in self.population:
 
−
            fitness_total += i.fitness
 
−
            i.accumulated_fitness = fitness_total
 
−
 
−
        # se é pra selecionar os piores, inverte o aptidão
 
−
        # acumulada e ordena novamente pela aptidão acumulada
 
−
        # assim, os piores tem mais chances de serem escolhidos
 
−
        if not best:
 
−
            # Inverte as probabilidades. Os piores vão ganhar uma
 
−
            # porção maior na roleta e os melhores menor
 
−
            size = len(self.population)
 
−
            for i in range(int(size / 2)):
 
−
                a = self.population[i]
 
−
                b = self.population[size - 1 - i]
 
−
                aux = a.accumulated_fitness
 
−
                a.accumulated_fitness = b.accumulated_fitness
 
−
                b.accumulated_fitness = aux
 
−
            self.population.sort(key=lambda x: x.accumulated_fitness)
 
−
 
−
        # e roda a roleta para selecionar a quantidade de indivúdios
 
−
        # definida em Genetic.selection_size
 
−
        for j in range(Genetic.selection_size):
 
−
            # pega um número aleatório com base na aptidão total
 
−
            num = randint(0, fitness_total)
 
−
            last = 0
 
−
            i = 0
 
−
            found = False
 
−
            # enquanto não encontrou um indivíduo que tem a ficha
 
−
            # desse número, procura
 
−
            while not found:
 
−
                current = self.population[i].accumulated_fitness
 
−
                # se encontrou o felizardo (ou não)
 
−
                if last <= num <= current:
 
−
                    # se já está selecionado, pega o próximo não
 
−
                    # selecionado da roleta
 
−
                    while self.population[i].selected:
 
−
                        # se chegou ao final, volta para o início
 
−
                        # veja que está girando a roleta e é circular
 
−
                        i += 1
 
−
                        if i >= len(self.population):
 
−
                            i = 0
 
−
                    # achou um indivíduo seleciona ele
 
−
                    self.population[i].selected = True
 
−
                    found = True
 
−
                last = current
 
−
                i += 1
 
−
 
−
    # faz o cruzamento dos indivíduos selecioados
 
−
    def crossover(self):
 
−
        print("CRUZAMENTO...")
 
−
        # cria uma lista para os selecionados. Fica mais fácil.
 
−
        selected = []
 
−
        for i in self.population:
 
−
            if i.selected:
 
−
                selected.append(i)
 
−
                # já deseleciona os pais
 
−
                i.selected = False
 
−
        # randomiza para fazer pares aleatórios
 
−
        shuffle(selected)
 
−
        i = 0
 
−
        # vai seguindo a lista dos selecionados pegando os dois
 
−
        # primeiros, depois os dois seguintes e assim por diante
 
−
        while i < len(selected):
 
−
            child_a = selected[i].clone()
 
−
            child_b = selected[i+1].clone()
 
−
            for j in range(Genetic.crossover_gene_size):
 
−
                # escolhe um gen aleatório e troca nos filhos
 
−
                k = randint(0, Data.size - 1)
 
−
                child_a.gene[k] = selected[i+1].gene[k]
 
−
                child_b.gene[k] = selected[i].gene[k]
 
−
            # coloca os filhos na lista da população
 
−
            self.population.append(child_a)
 
−
            self.population.append(child_b)
 
−
            i += 2
 
−
 
−
    # Faz a mutação de alguns indivíduos escolhidos aleatoriamente.
 
−
    def mutation(self):
 
−
        print("MUTAÇÃO...")
 
−
        # pega uma quantidade aleatória de indivíduos para mutar
 
−
        # a cada geração, entre 0 e Genetic.mutation_individual_size
 
−
        size = randint(0, Genetic.mutation_individual_size)
 
−
        for i in range(size):
 
−
            # pega um indivíduo aleatório da população
 
−
            k = randint(0, len(self.population) - 1)
 
−
            # pega alguns gens aleatórios e inverte o valor
 
−
            for j in range(Genetic.mutation_gene_size):
 
−
                l = randint(0, Data.size - 1)
 
−
                if self.population[k].gene[l] == 1:
 
−
                    self.population[k].gene[l] = 0
 
−
                else:
 
−
                    self.population[k].gene[l] = 1
 
−
 
−
    # Depois de selecionar os piores indivíduos, mas com
 
−
    # possibilidades de alguns bons serem selecionados na
 
−
    # roleta, mata esses selecionados, deixando apenas os
 
−
    # "melhores" para a próxima geração
 
−
    def survival(self):
 
−
        print("SOBREVIVENTES...")
 
−
        aux = []
 
−
        for i in self.population:
 
−
            if not i.selected:
 
−
                aux.append(i)
 
−
        self.population = aux
 
−
 
−
    # Algoritmo genético propriamente dito.
 
−
    def run(self):
 
−
        self.create_population()
 
−
        for g in range(Genetic.generations):
 
−
            print("GERAÇÃO", g)
 
−
            self.evaluate()
 
−
            self.selection(True)
 
−
            self.show()
 
−
            self.crossover()
 
−
            self.mutation()
 
−
            self.evaluate()
 
−
            self.selection(False)
 
−
            self.show()
 
−
            self.survival()
 
−
        self.evaluate()
 
−
        self.show()
 
−
        self.population[-1].show_info()
 
−
 
−
 
−
# MAIN PROGRAM -----------------------------------------
 
−
def main():
 
−
    # inicio o algoritmo
 
−
    genetic = Genetic()
 
−
    genetic.run()
 
−
 
−
 
−
# -------------------------------------------------------
 
−
if __name__ == "__main__":
 
−
    main()
 
−
</syntaxhighlight>
 
−
 
−
{{tip|O programa deu quase 300 linhas, mas é porque está todo comentado. Se tirar os comentários ele fica bem menor. É um algoritmo muito fácil e simples, talvez um dos mais fáceis de se implementar da Inteligência Artificial}}
 
  
 
== Solução ==
 
== Solução ==
Linha 358: Linha 51:
 
== Alterações para novo teste ==
 
== Alterações para novo teste ==
  
−
Adicionei um item (impressora) no arquivo de configuração e aumentei a capacidade para 25
+
No arquivo config.json adicionei um item (impressora) no arquivo de configuração e aumentei a capacidade para 25. Também alterei as variáveis do algoritmo aumentando a população, gerações, etc.
  
 
<syntaxhighlight lang=json line>
 
<syntaxhighlight lang=json line>
 
{
 
{
 +
  "population_size": "100",
 +
  "selection_size": "40",
 +
  "crossover_gene_size": "2",
 +
  "mutation_individual_size": "20",
 +
  "mutation_gene_size": "2",
 +
  "generations": "500",
 +
  "penality": "100",
 +
 
   "capacity": "25",
 
   "capacity": "25",
 
   "items": [
 
   "items": [
Linha 370: Linha 71:
 
     { "name": "colar", "value": "7", "weight": "4" },
 
     { "name": "colar", "value": "7", "weight": "4" },
 
     { "name": "videogame", "value": "9", "weight": "6" },
 
     { "name": "videogame", "value": "9", "weight": "6" },
−
     { "name": "smarthone", "value": "4", "weight": "4" },
+
     { "name": "smarthone", "value": "4", "weight": "1" },
 
     { "name": "impressora", "value": "2", "weight": "5" }
 
     { "name": "impressora", "value": "2", "weight": "5" }
 
   ]
 
   ]
 
}
 
}
−
</syntaxhighlight>
 
−
 
−
Alterei a função '''main''' para ficar mais fácil de alterar as configurações do algoritmo. Mais fácil que digo é que só altero ali no main mesmo que fica no final do programa. O que não aterar fica no padrão lá da classe mesmo.
 
−
 
−
<syntaxhighlight lang=python>
 
−
def main():
 
−
    # Faço ajustes para ser mais fácil (atributos globais)
 
−
    Genetic.population_size = 100
 
−
    Genetic.selection_size = 40
 
−
    Genetic.crossover_gene_size = 2
 
−
    Genetic.mutation_individual_size = 20
 
−
    Genetic.mutation_gene_size = 2
 
−
    Genetic.generations = 500
 
−
   
 
−
    # inicio o algoritmo
 
−
    genetic = Genetic()
 
−
    genetic.run()
 
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Linha 407: Linha 91:
 
</pre>
 
</pre>
  
−
A partir daí, dá pra gente ir brincando com as configurações do algoritmo, informações do problema e outras variáveis para ver como os resultados vão se alterando.
+
A partir daí, dá para gente ir brincando com as configurações do algoritmo, informações do problema e outras variáveis para ver como os resultados vão se alterando.

Edição das 08h25min de 25 de março de 2022

Afluentes: Inteligência Artificial, Modelos Evolutivos e Tratamento de Incertezas

Definição do Problema

Para mostrar uma implementação de um Algoritmo Genético, iremos trabalhar com o Problema da Mochila.

Sobre o problema da mochila:

  • Problema de otimização combinatória (NP-Completo)
  • Estudado por mais de um século (desde ~1897)
  • Resolvido por vários algoritmos
Ag mochila.png

Podemos representar a aptidão de uma solução como a soma dos valores dos objetos e com uma penalidade para soluções que passam do limite de volume.

  • Queremos o maior valor possível sem ultrapassar o limite da mochila.
  • Vários itens que gostaria de levar em uma mochila
  • Cada item tem um peso e um benefício, ou valor
  • Existe uma capacidade limite de peso
  • Deve-se carregar itens com o máximo valor total sem superar o limite de peso

Programa em Python

Coloquei o programa no github, fica mais fácil, fazer atualizações, de baixar e bom para visualizar. Vejam que o programa deu quase 300 linhas, mas é porque está todo comentado. Se tirar os comentários ele fica bem menor. É um algoritmo muito fácil e simples, talvez um dos mais fáceis de se implementar da Inteligência Artificial.

Link do github: https://github.com/saulopz/ia_genetico_mochila

Para baixar em seu computador, basta executar o comando: 

git clone https://github.com/saulopz/ia_genetico_mochila


Tplnote Bulbgraph.png

Eu estava fazendo procedural e estava tendo que fazer uns remendos, como encher de variáveis globais e outras coisas mais, e acho que isso estava permitindo um bug difícil de encontrar. Então decidi ir pra orientação a objetos que pra mim é mais fácil de entender e organizar. A ideia do algoritmo é a mesma que expliquei, mesmas funções, mesmaa funcionalidade, só está organizado como objetos. E, no final, era um bug bobo mesmo por causa de variáveis globais.

Solução

A solução encontrada para o algoritmo com os parâmetros e configuração acima fica: 

SOLUÇÃO ------------------------------
Capacidade da mochila: 22
- tv valor: 8 gold - peso: 8
- colar valor: 7 gold - peso: 4
- videogame valor: 9 gold - peso: 6
- smarthone valor: 4 gold - peso: 4
Valor total: 28 gold
Peso total : 22
--------------------------------------

Alterações para novo teste

No arquivo config.json adicionei um item (impressora) no arquivo de configuração e aumentei a capacidade para 25. Também alterei as variáveis do algoritmo aumentando a população, gerações, etc. 

 1{
 2  "population_size": "100",
 3  "selection_size": "40",
 4  "crossover_gene_size": "2",
 5  "mutation_individual_size": "20",
 6  "mutation_gene_size": "2",
 7  "generations": "500",
 8  "penality": "100",
 9
10  "capacity": "25",
11  "items": [
12    { "name": "notebook", "value": "5", "weight": "7" },
13    { "name": "tv", "value": "8", "weight": "8" },
14    { "name": "tablet", "value": "3", "weight": "4" },
15    { "name": "anel", "value": "2", "weight": "10" },
16    { "name": "colar", "value": "7", "weight": "4" },
17    { "name": "videogame", "value": "9", "weight": "6" },
18    { "name": "smarthone", "value": "4", "weight": "1" },
19    { "name": "impressora", "value": "2", "weight": "5" }
20  ]
21}

E obtive a seguinte solução: 

SOLUÇÃO ------------------------------
Capacidade da mochila: 25
- notebook valor: 5 gold - peso: 7
- tv valor: 8 gold - peso: 8
- colar valor: 7 gold - peso: 4
- videogame valor: 9 gold - peso: 6
Valor total: 29 gold
Peso total : 25
--------------------------------------

A partir daí, dá para gente ir brincando com as configurações do algoritmo, informações do problema e outras variáveis para ver como os resultados vão se alterando.

Disponível em “https://saulo.arisa.com.br/wiki/index.php?title=Genéticos:_Problema_da_Mochila_em_Python&oldid=8007”