|
|
| (15 revisões intermediárias pelo mesmo usuário não estão sendo mostradas) |
| Linha 1: |
Linha 1: |
| | + | |
| | Afluentes: [[Inteligência Artificial]], [[Modelos Evolutivos e Tratamento de Incertezas]] | | Afluentes: [[Inteligência Artificial]], [[Modelos Evolutivos e Tratamento de Incertezas]] |
| | | | |
| Linha 4: |
Linha 5: |
| | | | |
| | 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 14: |
| | <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 |
| | | | |
| − | = Arquivo de Configuração = | + | = 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 |
| | + | |
| | + | {{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.}} |
| | + | |
| | + | == Solução == |
| | + | |
| | + | A solução encontrada para o algoritmo com os parâmetros e configuração acima fica: |
| | + | |
| | + | <pre> |
| | + | 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 |
| | + | -------------------------------------- |
| | + | </pre> |
| | + | |
| | + | == 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. |
| | | | |
| − | <syntaxhighlight lang=json line> | + | <syntaxhighlight lang="json"> |
| | { | | { |
| | + | "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 31: |
Linha 72: |
| | { "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" } |
| | ] | | ] |
| | } | | } |
| | </syntaxhighlight> | | </syntaxhighlight> |
| | | | |
| − | = Programa em Python =
| + | E obtive a seguinte solução: |
| − | | |
| − | {{tip|O algoritmo está com um bug e as vezes trava. Se travar, pressione CTRL+C e tente novamente. Depois vou tentar descobrir o que é.}}
| |
| − | | |
| − | <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():
| |
| − | # 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
| + | <pre> |
| − | genetic = Genetic()
| + | SOLUÇÃO ------------------------------ |
| − | genetic.run()
| + | 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 |
| | + | -------------------------------------- |
| | + | </pre> |
| | | | |
| − | | + | 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. |
| − | # -------------------------------------------------------
| |
| − | if __name__ == "__main__":
| |
| − | main()
| |
| − | </syntaxhighlight>
| |
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
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
|
|
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.
{
"population_size": "100",
"selection_size": "40",
"crossover_gene_size": "2",
"mutation_individual_size": "20",
"mutation_gene_size": "2",
"generations": "500",
"penality": "100",
"capacity": "25",
"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": "1" },
{ "name": "impressora", "value": "2", "weight": "5" }
]
}
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.
