Genéticos: Problema da Mochila em Python
De Aulas
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.
- 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
- Há uma capacidade limite de peso
- Deve-se carregar itens com o máximo valor total sem superar o limite de peso
Arquivo de Configuração
1{
2 "capacity": "25",
3 "items": [
4 { "name": "notebook", "value": "5", "weight": "7" },
5 { "name": "tv", "value": "8", "weight": "8" },
6 { "name": "tablet", "value": "3", "weight": "4" },
7 { "name": "anel", "value": "2", "weight": "10" },
8 { "name": "colar", "value": "7", "weight": "4" },
9 { "name": "videogame", "value": "9", "weight": "6" },
10 { "name": "smarthone", "value": "4", "weight": "4" }
11 ]
12}
Programa em Python
|
mochila.py
1import json
2from random import *
3
4
5# ITEM CLASS ---------------------------------------------
6# representa os itens do arquivo config.json
7class Item:
8 def __init__(self, name, value, weight):
9 self.name = name # nome do produto
10 self.value = value # valor
11 self.weight = weight # peso
12
13
14# DATA STATIC CLASS ------------------------------------
15# Lê as configurações do arquivo config.json e carrega
16# nessa classe estática para ser usada em todo o programa
17class Data:
18 size = 0 # quantidade de itens
19 capacity = 0 # capacidade da mochila
20 items = [] # vetor contendo os itens
21
22 @staticmethod
23 def load():
24 # abre o arquivo e converte para um objeto json
25 file = open("config.json")
26 data = json.load(file)
27 file.close()
28 # coloca as informações do objeto json na classe
29 # Data pra facilitar o acesso aos dados
30 Data.capacity = int(data["capacity"])
31 for i in range(len(data["items"])):
32 name = data["items"][i]["name"]
33 value = int(data["items"][i]["value"])
34 weight = int(data["items"][i]["weight"])
35 Data.items.append(Item(name, value, weight))
36 Data.size += 1
37
38
39# INDVIDUAL CLASS -------------------------------------------
40# Cada instância dessa classe representa cada indivíduo da
41# população do ecossistema do algoritmo
42class Individual:
43 def __init__(self):
44 self.fitness = 0 # aptidão do indivíduo
45 self.accumulated_fitness = 0 # aptidão acumulada (usada na seleção)
46 self.selected = False # se indivíduo foi selecionado
47 self.gene = [] # gens, representando os ítens na mochiila
48 for i in range(Data.size):
49 # coloca ítens aleatórios na mochila
50 self.gene.append(randint(0, 1))
51
52 # Calcula a aptidão do indivíduo
53 def evaluate(self):
54 self.accumulated_fitness = 0
55 self.fitness = 0
56 weight = 0
57 # primeiro soma todos os valores dos ítens que estão inclusos
58 # nessa solução de mochila
59 for i in range(Data.size):
60 if self.gene[i] == 1:
61 self.fitness += Data.items[i].value
62 weight += Data.items[i].weight
63 # caso o peso total de ítens incluso seja maior que a capacidade
64 # da mochila, dá uma penalidade, diminuindo em 100 a aptidão
65 if weight > Data.capacity:
66 self.fitness -= 100
67
68 # apresenta informações do indivíduo de forma simplificada para debug
69 def show(self):
70 print(self.gene, self.fitness, self.selected, self.accumulated_fitness)
71
72 # apresenta informações completas da solução, representada por um indivíduo
73 def show_info(self):
74 print("SOLUÇÃO ------------------------------")
75 print("Capacidade da mochila:", Data.capacity)
76 weight = 0
77 value = 0
78 for i in range(Data.size):
79 if self.gene[i] == 1:
80 weight += Data.items[i].weight
81 value += Data.items[i].value
82 print("-", Data.items[i].name, "valor:",
83 Data.items[i].value, "gold - peso:", Data.items[i].weight)
84 print("Valor total:", value, "gold")
85 print("Peso total :", weight)
86 print("--------------------------------------")
87
88 # clona o indivíduo e retorna uma instância dessa cópia
89 def clone(self):
90 other = Individual()
91 for i in range(Data.size):
92 other.gene[i] = self.gene[i]
93 other.fitness = self.fitness
94 return other
95
96
97# GENETIC CLASS --------------------------------------------------
98class Genetic:
99 # Configuro um padrão aqui, mas faço ajustes no main
100 population_size = 50 # tamanho da população
101 selection_size = 20 # quantos vou selecionar
102 crossover_gene_size = 2 # quantos gens vou usar no cruzamento
103 mutation_individual_size = 10 # quantos indivíduos vou mutar cada geração
104 mutation_gene_size = 2 # quantos gens de cada indivíduo vou mutar
105 generations = 100 # por quantas gerações o algoritmo vai executar
106
107 # constructor
108 def __init__(self):
109 Data.load() # carrega as configurações
110 self.population = [] # inicia com população vazia
111
112 # mostra todos os indivíduos da população
113 def show(self):
114 for i in self.population:
115 i.show()
116
117 # cria a população inicial com indivíduos contendo ítens aleatórios
118 def create_population(self):
119 print("CREIANDO POPULAÇÃO INICIAL...")
120 for i in range(Genetic.population_size):
121 self.population.append(Individual())
122
123 # calcula a aptidão de todos os indivíduos da população
124 def evaluate(self):
125 for i in self.population:
126 i.evaluate()
127 # ordena a população com base na aptidão
128 self.population.sort(key=lambda x: x.fitness)
129
130 # seleciona uma quantidade de indivíduos. Se best for verdadeiro,
131 # então seleciona os melhores, se for falso, seleciona os piores.
132 def selection(self, best):
133 who = "MELHORES"
134 if not best:
135 who = "PIORES"
136 print("SELECIONANDO OS", who, "INDIVÍDUOS ...")
137 # como para fins de cálculo não pode haver aptidão negativa,
138 # procura a menor aptidão negativa para subtrair de todos,
139 # deixando todos positivos.
140 lower = 0
141 for i in self.population:
142 if i.fitness < lower:
143 lower = i.fitness
144
145 # Se houve aptidão negativa, subtrai o menor valor de
146 # todos os elementos para não termos aptidão negativa
147 if lower < 0:
148 for i in self.population:
149 i.fitness = i.fitness - lower
150
151 # ordena a população com base na aptidão
152 self.population.sort(key=lambda x: x.fitness)
153
154 # calcula a aptidão acumulada e aptidão total
155 fitness_total = 0
156 for i in self.population:
157 fitness_total += i.fitness
158 i.accumulated_fitness = fitness_total
159
160 # se é pra selecionar os piores, inverte o aptidão
161 # acumulada e ordena novamente pela aptidão acumulada
162 # assim, os piores tem mais chances de serem escolhidos
163 if not best:
164 # Inverte as probabilidades. Os piores vão ganhar uma
165 # porção maior na roleta e os melhores menor
166 size = len(self.population)
167 for i in range(int(size / 2)):
168 a = self.population[i]
169 b = self.population[size - 1 - i]
170 aux = a.accumulated_fitness
171 a.accumulated_fitness = b.accumulated_fitness
172 b.accumulated_fitness = aux
173 self.population.sort(key=lambda x: x.accumulated_fitness)
174
175 # e roda a roleta para selecionar a quantidade de indivúdios
176 # definida em Genetic.selection_size
177 for j in range(Genetic.selection_size):
178 # pega um número aleatório com base na aptidão total
179 num = randint(0, fitness_total)
180 last = 0
181 i = 0
182 found = False
183 # enquanto não encontrou um indivíduo que tem a ficha
184 # desse número, procura
185 while not found:
186 current = self.population[i].accumulated_fitness
187 # se encontrou o felizardo (ou não)
188 if last <= num <= current:
189 # se já está selecionado, pega o próximo não
190 # selecionado da roleta
191 while self.population[i].selected:
192 # se chegou ao final, volta para o início
193 # veja que está girando a roleta e é circular
194 i += 1
195 if i >= len(self.population):
196 i = 0
197 # achou um indivíduo seleciona ele
198 self.population[i].selected = True
199 found = True
200 last = current
201 i += 1
202
203 # faz o cruzamento dos indivíduos selecioados
204 def crossover(self):
205 print("CRUZAMENTO...")
206 # cria uma lista para os selecionados. Fica mais fácil.
207 selected = []
208 for i in self.population:
209 if i.selected:
210 selected.append(i)
211 # já deseleciona os pais
212 i.selected = False
213 # randomiza para fazer pares aleatórios
214 shuffle(selected)
215 i = 0
216 # vai seguindo a lista dos selecionados pegando os dois
217 # primeiros, depois os dois seguintes e assim por diante
218 while i < len(selected):
219 child_a = selected[i].clone()
220 child_b = selected[i+1].clone()
221 for j in range(Genetic.crossover_gene_size):
222 # escolhe um gen aleatório e troca nos filhos
223 k = randint(0, Data.size - 1)
224 child_a.gene[k] = selected[i+1].gene[k]
225 child_b.gene[k] = selected[i].gene[k]
226 # coloca os filhos na lista da população
227 self.population.append(child_a)
228 self.population.append(child_b)
229 i += 2
230
231 # Faz a mutação de alguns indivíduos escolhidos aleatoriamente.
232 def mutation(self):
233 print("MUTAÇÃO...")
234 # pega uma quantidade aleatória de indivíduos para mutar
235 # a cada geração, entre 0 e Genetic.mutation_individual_size
236 size = randint(0, Genetic.mutation_individual_size)
237 for i in range(size):
238 # pega um indivíduo aleatório da população
239 k = randint(0, len(self.population) - 1)
240 # pega alguns gens aleatórios e inverte o valor
241 for j in range(Genetic.mutation_gene_size):
242 l = randint(0, Data.size - 1)
243 if self.population[k].gene[l] == 1:
244 self.population[k].gene[l] = 0
245 else:
246 self.population[k].gene[l] = 1
247
248 # Depois de selecionar os piores indivíduos, mas com
249 # possibilidades de alguns bons serem selecionados na
250 # roleta, mata esses selecionados, deixando apenas os
251 # "melhores" para a próxima geração
252 def survival(self):
253 print("SOBREVIVENTES...")
254 aux = []
255 for i in self.population:
256 if not i.selected:
257 aux.append(i)
258 self.population = aux
259
260 # Algoritmo genético propriamente dito.
261 def run(self):
262 self.create_population()
263 for g in range(Genetic.generations):
264 print("GERAÇÃO", g)
265 self.evaluate()
266 self.selection(True)
267 self.show()
268 self.crossover()
269 self.mutation()
270 self.evaluate()
271 self.selection(False)
272 self.show()
273 self.survival()
274 self.evaluate()
275 self.show()
276 self.population[-1].show_info()
277
278
279# MAIN PROGRAM -----------------------------------------
280def main():
281 # Faço ajustes para ser mais fácil (atributos globais)
282 Genetic.population_size = 100
283 Genetic.selection_size = 40
284 Genetic.crossover_gene_size = 2
285 Genetic.mutation_individual_size = 20
286 Genetic.mutation_gene_size = 2
287 Genetic.generations = 500
288
289 # inicio o algoritmo
290 genetic = Genetic()
291 genetic.run()
292
293
294# -------------------------------------------------------
295if __name__ == "__main__":
296 main()
Solução
A solução encontrada para o algoritmo com os parâmetros e configuração acima fica:
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 --------------------------------------
