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

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.

Arquivo de Configuração config.json

 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}

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