0/1 Knapsack Problem

O problema da mochila é um velho conhecido dos que se preocupam com questões de optimização. Na sua formulação binária consiste em encontrar a melhor selecção de entre um conjunto de objectos, cada um com um peso e um valor, que uma mochila de capacidade limitada consegue suportar, procurando maximizar o valor total dos objectos seleccionados. Para os que têm uma inclinação matemática a definição rigorosa é a seguinte: $$ maximizar \quad\quad z = \sum_{j=1}^n v_j x_j$$ $$sujeito \quad a \quad\quad \sum_{j=1}^n p_j x_j \le c$$ $com \quad\quad x_j = 0 \quad ou \quad x_j = 1$ (vale 1 quando o item de ordem $j$ vai para a mochila). $v_j$ é o valor, $p_j$ é o peso, e $c$ a capacidade.

A dificuldade deste problema aumenta com o aumento da dimensão do conjunto dos objectos, como é natural, mas também é função da relação entre os pesos, os valores e a capacidade.

Vamos procurar resolver esta questão recorrendo a um dos métodos estocásticos de estado único dados nas aulas. Vamos ter que resolver várias questões, nomeadamente, a representação do problema, o modo como calculamos a qualidade das soluções candidatas, o algoritmo a usar e a forma como determinamos soluções alternativas candidatas a melhor solução.

Dada a natureza do problema uma representação binária é adequada: numa cadeia binária um 1 numa posição $j$ significa que o item $j$ está na mochila. Quanto à qualidade o mais simples é fazer a qualidade igual à soma dos valores de todos os objectos colocados na mochila. Vamos escolher como algoritmo o trepa-colinas básico. Já o candidato alternativo obtém-se trocando um bit uma posição escolhida aleatoriamente na cadeia candidata corrente. A qualidade de um indivíduo será dada simplesmente pelo valor total dos objectos seleccionados como decorre da definição do problema. Mas temos um ponto prévio a resolver: a escolha dos dados para testar a nossa solução. Os pesos e os valores podem ser não correlacionados, fracamente relacionados ou fortemente relacionados. A capacidade pode ser escolhida em função do peso total dos objectos, por exemplo, considerando metade desse valor. Podemos implementar as três situações de modo muito simples:

def generate_uncor(size_items,max_value):
    weights = [random.uniform(1,max_value) for i in range(size_items)]
    values = [random.uniform(1,max_value) for i in range(size_items)]
    capacity = int(0.5 * sum(weights))
    return weights, values, capacity

def generate_weak_cor(size_items,max_value, amplitude):
    """No negative weight allowed!"""
    weights = [random.uniform(1,max_value) for i in range(size_items)]
    values = []
    for i in range(size_items):
        value = weights[i] + random.uniform(-amplitude,amplitude)
        while value <= 0:
            value = weights[i] + random.uniform(-amplitude,amplitude)
        values.append(value)
    capacity = int(0.5 * sum(weights))
    return weights, values, capacity

def generate_strong_cor(size_items,max_value,amplitude):
    weights = [random.uniform(1,max_value) for i in range(size_items)]
    values = [weights[i] + amplitude for i in range(size_items)]
    capacity = int(0.5 * sum(weights))
    return weights, values, capacity

Como se pode ver, a geração dos dados depende de dois parâmetros: o valor máximo para os pesos, e o que designamos por amplitude (que determina o afastamento entre os pesos e os valores). Na listagem abaixo estes parâmetros estão definidos. Pode sempre testar com outros valores e observar a existência ou não de diferenças na qualidade dos resultados.

. Posto isto apresentamos a solução simples para o 0/1 KP.

import random
import matplotlib.pyplot as plt

# Data Sets
def generate_uncor(size_items,max_value):
    weights = [random.uniform(1,max_value) for i in range(size_items)]
    values = [random.uniform(1,max_value) for i in range(size_items)]
    capacity = int(0.5 * sum(weights))
    return weights, values, capacity

def generate_weak_cor(size_items,max_value, amplitude):
    """No negative weight allowed!"""
    weights = [random.uniform(1,max_value) for i in range(size_items)]
    values = []
    for i in range(size_items):
        value = weights[i] + random.uniform(-amplitude,amplitude)
        while value <= 0:
            value = weights[i] + random.uniform(-amplitude,amplitude)
        values.append(value)
    capacity = int(0.5 * sum(weights))
    return weights, values, capacity

def generate_strong_cor(size_items,max_value,amplitude):
    weights = [random.uniform(1,max_value) for i in range(size_items)]
    values = [weights[i] + amplitude for i in range(size_items)]
    capacity = int(0.5 * sum(weights))
    return weights, values, capacity


#  Hill Climbing  
#  Binary representation
#  Random neighbor

def kp_hc(max_iter,problem_size, weights,values,capacity):
    candidate = random_indiv(problem_size)
    cost_candi = fitness(candidate,weights,values,capacity)
    for i in range(max_iter):
        next_neighbor = random_neighbor(candidate)
        cost_next_neighbor = fitness(next_neighbor,weights,values,capacity)
        if cost_next_neighbor >= cost_candi: 
            candidate = next_neighbor
            cost_candi = cost_next_neighbor        
    return candidate,cost_candi/sum(values)

# ------------------------------------------------------------------------------
def random_indiv(size):
    return [random.randint(0,1) for i in range(size)]

 
def random_neighbor(individual):
    new_individual = individual[:]
    pos = random.randint(0,len(individual) - 1)
    gene = individual[pos]
    new_gene = (gene + 1) % 2
    new_individual[pos] = new_gene
    return new_individual


# Fitness for a binary representation. Unfeasible individuals have fitness 0

def fitness(individual, weights,values, capacity):
    items = [ i for i in range(len(individual)) if individual[i] == 1]
    total_weight = sum([ weights[i] for i in items])
    if total_weight > capacity:
        return 0
    else:
        total_value = sum([ values[i] for i in items])
        return total_value
 
    
if __name__ == '__main__':
    size_1 = 100
    size_2 = 250
    size_3 = 500
    max_value = 10
    amplitude = 5
    weights_nc, values_nc, capacity_nc = generate_uncor(size_1, max_value)
    weights_wc, values_wc, capacity_wc = generate_weak_cor(size_2, max_value,amplitude)
    weights_cor, values_cor, capacity_cor = generate_strong_cor(size_3, max_value, amplitude)
    
 
    print(kp_hc(1000,size_1,weights_nc,values_nc,capacity_nc))
    print(kp_hc(1000,size_2,weights_wc,values_wc,capacity_wc))
    print(kp_hc(1000,size_3,weights_cor,values_cor,capacity_cor))

Podemos explorar variantes? Claro. Por exemplo, visualizar os resultados.

def kp_hc_visual(max_iter,problem_size, weights,values,capacity):
    candidate = random_indiv(problem_size)
    cost_candi = fitness(candidate,weights,values,capacity)
    quality = [cost_candi]
    for i in range(max_iter):
        next_neighbor = random_neighbor(candidate)
        cost_next_neighbor = fitness(next_neighbor,weights,values,capacity)
        if cost_next_neighbor >= cost_candi: 
            candidate = next_neighbor
            cost_candi = cost_next_neighbor
        quality.append(cost_candi)
    display_kp(quality)
    return candidate,cost_candi/sum(values)

def display_kp(data):
    """Plot the data"""
    x = list(range(len(data)))
    plt.title('0/1 Knapsack')
    plt.xlabel('Generations')
    plt.ylabel('Value')
    plt.grid(True)
    plt.plot(x,data, 'r')
    plt.show()      

Podemos também explorar outras funções de qualidade:

def fitness_2(individual, weights,values, capacity):
    items = [ i for i in range(len(individual)) if individual[i] == 1]
    total_weight = sum([ weights[i] for i in items])
    total_value = sum([ values[i] for i in items])
    if total_weight > capacity:
        return total_value - (total_weight - capacity)
    else:
        return total_value  
    
def fitness_3(individual, weights,values, capacity):
    items = [ i for i in range(len(individual)) if individual[i] == 1]
    total_weight = sum([ weights[i] for i in items])
    total_value = sum([ values[i] for i in items])
    if total_weight == 0:
        return 0
    return total_value/sum(values)

A primeira alternativa, no caso de haver excesso de peso, penaliza em função da amplitude desse excesso. A segunda alternativa, usa como medida de qualidade o valor dos objectos que conseguimos colocar no saco em função do valor total dos objectos. É claro que agora precisamos de alterar ligeiramente o programa principal para que a função de qualidade passe a ser um parâmetro.

def kp_hc_visual_fit(max_iter,problem_size, weights,values,capacity,fitness):
    candidate = random_indiv(problem_size)
    cost_candi = fitness(candidate,weights,values,capacity)
    quality = [cost_candi]
    for i in range(max_iter):
        next_neighbor = random_neighbor(candidate)
        cost_next_neighbor = fitness(next_neighbor,weights,values,capacity)
        if cost_next_neighbor >= cost_candi: 
            candidate = next_neighbor
            cost_candi = cost_next_neighbor
        quality.append(cost_candi)
    display_kp(quality)
    return candidate,cost_candi/sum(values)

Agora só falta explorar o que foi apresentado. Pode também recorrer a outro algoritmo que não o trepa colinas.