Exibir código-fonte para 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

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

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

<syntaxhighlight lang=json line>
{
  "capacity": "22",
  "itens": [
    { "name": "a", "price": "5", "weight": "7" },
    { "name": "b", "price": "8", "weight": "8" },
    { "name": "c", "price": "3", "weight": "4" },
    { "name": "d", "price": "2", "weight": "10" },
    { "name": "e", "price": "7", "weight": "4" },
    { "name": "f", "price": "9", "weight": "6" },
    { "name": "g", "price": "4", "weight": "4" }
  ]
}
</syntaxhighlight>

= Programa em Python =

<syntaxhighlight lang=Python line>
import json
from random import *


# Lê o arquivo de configuração com a informação dos
# itens disponíveis, preço e pêso
def load():
    config = open('config.json')
    data = json.load(config)
    config.close()
    return data


def create_population():
    global data, population
    population = []
    for p in range(population_size):
        element = []
        for i in range(len(data["itens"])):
            # 1 se o elemento está na mochila e 0 se ele está ausente
            element = element + [randint(0, 1)]
        element = element + [compute_fitness(element)]  # aptidão
        element = element + [0, 0]  # aptidão acumulada e se foi selecionado
        population = population + [element]
    # return population


def unselect_all():
    global data, population
    for i in range(len(population)):
        population[i][len(data["itens"]) + 2] = 0

def clone_element(element):
    clone = []
    for i in range(len(element)):
        clone += [element[i]]
    return clone


def compute_fitness(element):
    global data
    price = 0
    weight = 0
    for i in range(len(data["itens"])):
        if element[i] == 1:
            price = price + int(data["itens"][i]["price"])
            weight = weight + int(data["itens"][i]["weight"])
    fitness = price
    if weight > int(data["capacity"]):
        fitness = fitness - 100
    return fitness


def evaluate():
    global population
    for i in range(len(population)):
        compute_fitness(population[i])


def selection(best):
    print("selection", best)
    unselect_all()
    global data, population, population_size, selection_size
    # procura o menor fitness negativo
    lower = 0
    fitness_pos = len(data["itens"])
    for i in range(len(population)):
        if population[i][fitness_pos] < lower:
            lower = population[i][fitness_pos]

    # 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 range(len(population)):
            population[i][fitness_pos] = population[i][fitness_pos] - lower

    # ordena a população com base no fitness
    population = sorted(population, key=lambda x: x[fitness_pos])

    # calcula a aptidão acumulada e aptidão total
    fitness_total = 0
    for i in range(len(population)):
        fitness_total = fitness_total + population[i][fitness_pos]
        population[i][fitness_pos + 1] = fitness_total

    # seleciona os n melhores. Se for pra escolher quem vai sobreviver
    # escolhe o tamanho da população
    aux = selection_size
    if not best:
        aux = population_size

    for j in range(aux):
        last = 0
        num = randint(0, fitness_total)
        # encontra a posição da roleta do selecionado
        found = False
        i = 0
        while not found:
            current = population[i][fitness_pos + 1]
            if last < num and num <= current:
                is_selected = population[i][fitness_pos + 2]
                # se já está selecionado, pega o próximo não selecionado da roleta
                while is_selected:
                    i = i + 1
                    # se chegou ao final, volta no primeiro
                    if i >= len(population):
                        i = 0
                    is_selected = population[i][fitness_pos + 2]
                # seleciona
                population[i][fitness_pos + 2] = 1
                found = True
            last = current
            i += 1
            if i >= len(population):
                i = 0


def crossover():
    print("crossover")
    global data, population, crossover_size, selection_size
    selected_pos = len(data["itens"]) + 2
    unselected = []
    selected = []
    for i in range(len(population)):
        if population[i][selected_pos] == 0:
            unselected = unselected + [population[i]]
        else:
            selected = selected + [population[i]]
    # randomiza para fazer pares aleatórios
    shuffle(selected)
    i = 0
    while i < len(selected):
        # deseleciona os pais
        selected[i][selected_pos] = 0
        selected[i+1][selected_pos] = 0
        # clona os pais criando os filhos
        child_a = clone_element(selected[i])
        child_b = clone_element(selected[i+1])
        # faz as trocas genéticas
        for j in range(crossover_size):
            cross_gen = randint(0, len(data["itens"]) - 1)
            child_a[cross_gen] = selected[i+1][cross_gen]
            child_b[cross_gen] = selected[i][cross_gen]
        compute_fitness(child_a)
        compute_fitness(child_b)
        # coloca os filhos criados na lista unselected, que depois
        # irá compor a população
        unselected = unselected + [child_a, child_b]
        i = i + 2
    population = unselected + selected


def mutation():
    print("mutation")
    global mutation_elements_size, mutation_size, population, data
    size = randint(0, mutation_elements_size)
    for i in range(size):
        element_pos = randint(1, len(population)) - 1
        for j in range(mutation_size):
            mutation_gen = randint(0, len(data["itens"]) - 1)
            if population[element_pos][mutation_gen] == 1:
                population[element_pos][mutation_gen] = 0
            else:
                population[element_pos][mutation_gen] = 1


def survival():
    print("survival")
    global population, data
    selected_pos = len(data["itens"]) + 2
    aux = population[:]
    population = []
    for i in range(len(aux)):
        if aux[i][selected_pos] == 1:
            population += [aux[i]]


# PROGRAMA PRINCIPAL ------------------------------------------
data = load()
population_size = 50
selection_size = 20
crossover_size = 2
mutation_elements_size = 10
mutation_size = 2
epochs = 100

create_population()
for epoch in range(epochs):
    print("epoch", epoch)
    selection(True)
    crossover()
    mutation()
    # evaluate()
    selection(False)
    survival()
    # show population
    for i in range(len(population)):
        print(population[i])
</syntaxhighlight>