Genéticos: Problema da Mochila em Python

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

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.

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
--------------------------------------