Implementação do algoritmo de beam search para o problema da mochila irrestrita, com variações determinística e não determinística

beam_search.py

import random
import copy


class Item:
    """Classe que representa um item da mochila."""

    def __init__(self, valor, tamanho):
        self.valor = valor
        self.tamanho = tamanho

    def get_valor_item(self):
        """Retorna o valor de um item."""
        return self.valor

    def get_tamanho_item(self):
        """Retorna o tamanho de um item."""
        return self.tamanho

    def __str__(self):
        """Retorna uma string que representa o item."""
        return f"Item: ({self.valor}, {self.tamanho})"

    def __repr__(self):
        """Retorna representação do item."""
        return f"({self.valor}, {self.tamanho})"

    def __lt__(self, other):
        """Retorna True se um item for menos valioso que outro."""
        return self.valor < other.valor


class MochilaIrrestrita:
    def __init__(self, s=1, i=list()):
        # s: capacidade da mochila
        self.s = s
        # i: itens da mochila
        self.i = [Item(item[0], item[1]) for item in i]

    def avalia_estado(self, estado):
        """Avalia um estado da mochila, consultando a quantidade de itens no estado e consultando a lista de itens para obter valor e tamanho total."""

        valorEstado = 0
        tamanhoEstado = 0

        print(f"Itens da mochila: {self.get_itens()}")
        print(f"Avaliando estado {estado}: ", end="")

        for item in range(len(estado)):
            valorEstado += estado[item] * self.consulta_valor_item(item)
            tamanhoEstado += estado[item] * self.consulta_tamanho_item(item)

        print(f"valor: {valorEstado}, tamanho: {tamanhoEstado}")

        return Item(valorEstado, tamanhoEstado)

    def estado_valido_mochila(self, tamanhoEstado):
        """Retorna True se o estado é válido para a mochila."""
        return tamanhoEstado <= self.s

    def get_itens(self):
        """Retorna a lista de itens da mochila."""
        return self.i

    def get_capacidade(self):
        """Retorna a capacidade da mochila."""
        return self.s

    def get_estado_inicial(self):
        """Retorna o estado inicial da mochila, (0, 0, 0)."""
        return (0, 0, 0)

    def consulta_valor_item(self, item):
        """Obtém o valor de um item dado seu índice e a lista de itens."""
        return self.i[item].get_valor_item()

    def consulta_tamanho_item(self, item):
        """Obtém o tamanho de um item dado seu índice e a lista de itens."""
        return self.i[item].get_tamanho_item()

    def __str__(self):
        """Retorna a representação textual da mochila."""
        return f"Mochila: ({self.s}, {self.i})"

    def __repr__(self):
        """Retorna representação do item."""
        return f"({self.s}, {self.i})"


def expande_estado_mochila(estado):
    """Expande um estado da mochila, isto é, gera todos os estados subsequentes possíveis, na forma de adição de um item ao estado atual em qualquer posição."""

    nItens = len(estado)
    estados = list()

    # Cria cópias dos estados para a lista
    for i in range(nItens):
        estados.append(copy.copy(list(estado)))

    # Soma 1 quantidade para cada item nos estados
    for i in range(nItens):
        estados[i][i] = estados[i][i] + 1
        estados[i] = tuple(estados[i])

    return estados


def funcao_objetivo(estadoEAvaliacao):
    """Função objetivo para o método de busca beam search. Ingenuamente utiliza o valor do estado."""
    return estadoEAvaliacao[1].get_valor_item()


def metodo_da_roleta(listaEstados, nItens=1):
    """Retorna um estado com base em probabilidades obtidas a partir de uma função objetivo."""
    # Inicializa variáveis para escolha randômica sem reposição (acho que é a única forma sem numpy)
    estadosEAvaliacoes = copy.deepcopy(listaEstados)
    estadosEscolhidos = list()

    # Calcula a probabilidade de cada estado
    probabilidades = [funcao_objetivo(estado) for estado in estadosEAvaliacoes]

    # Escolhe os estados com base na probabilidade
    for i in range(nItens):
        escolhido = random.choices(estadosEAvaliacoes, weights=probabilidades, k=1)[0]

        # Remove o escolhido das listas (para não ocorrer reposição)
        indiceEscolhido = estadosEAvaliacoes.index(escolhido)
        del estadosEAvaliacoes[indiceEscolhido]
        del probabilidades[indiceEscolhido]

        if not (estadosEAvaliacoes or probabilidades):
            break

        estadosEscolhidos.append(escolhido)

    return estadosEscolhidos


def beam_search_com_mochila_irrestrita(s, i, m, deterministico):
    """Chama o método de busca beam search dado parâmetros de uma mochila irrestrita."""
    mochila = MochilaIrrestrita(s, i)

    return beam_search(tamViga=m, deterministico=deterministico, mochila=mochila)


# Ainda é determinístico
def beam_search(tamViga, deterministico=True, mochila=MochilaIrrestrita()):
    """"""

    def obtem_m_estados(f, m, deterministico=True):
        print("Avaliando e obtendo melhores estados...")

        estados = f

        avaliacaoEstados = [mochila.avalia_estado(estado) for estado in estados]

        estadosDict = {estado: avaliacaoEstados[i] for i, estado in enumerate(estados)}

        print(f"Avaliações de estados: {estadosDict}")

        # Filtra os estados com peso maior que o limite mochila.s
        print("\nFiltrando estados válidos... ", end="")
        estadosValidos = {
            estado: avaliacao
            for estado, avaliacao in estadosDict.items()
            if mochila.estado_valido_mochila(avaliacao.get_tamanho_item())
        }

        print(estadosValidos)

        print(f"\nOrdenando estados por valor e obtendo {tamViga} estados... ", end="")
        estadosOrdenados = sorted(
            estadosValidos.items(), key=lambda x: x[1], reverse=True
        )
        print(estadosOrdenados)

        if estadosOrdenados:
            if deterministico:
                return estadosOrdenados[:tamViga]
            else:
                estadosRoleta = metodo_da_roleta(
                    listaEstados=estadosOrdenados,
                    nItens=min(tamViga, len(estadosOrdenados)),
                )
                return sorted(estadosRoleta, key=lambda x: x[1], reverse=True)
        else:
            return []

    melhorEstado = tuple()
    f = list()

    # Insere o estado inicial na fila/lista
    f.append(mochila.get_estado_inicial())

    print(f"f (fila):\t{f}\ns, i (mochila):\t{mochila}\nm (tamViga):\t{tamViga}\n")

    it = 0
    while True:
        it += 1
        # Expande todos os estados na fila/lista f e os avalia
        print(f"=== {it}ª iteração - estados na fila: {f}")

        # Esvazia variável da lista sem apagar estados da memória
        listaAux = f
        f = list()

        # Reescreve lista como expansão dos estados em uma única lista
        for estado in listaAux:
            f += expande_estado_mochila(estado)

        print(f"\nExpansões dos estados da fila:\n{f}\n")

        # Mantém apenas os m estados com melhor avaliação
        melhoresEstados = obtem_m_estados(f, tamViga, deterministico)

        if deterministico:
            print("\n'm' melhores estados: ", melhoresEstados)
        else:
            print("\n'm' estados escolhidos: ", melhoresEstados)

        if melhoresEstados:
            # Atualiza melhor estado
            melhorEstado = melhoresEstados[0]
        # Retorna [] se não for possível encontrar mais estados válidos
        else:
            print("Não há mais estados válidos para testar/expandir; fim da execução.")
            break

        # Atualiza f com os melhores estados
        print("Atualizando fila com melhores estados... ", end="")
        # Pega apenas estados (sem avaliação)
        f = [estado[0] for estado in melhoresEstados]
        print(f)

        print(f"Melhor estado até então: {melhorEstado}\n")

    return melhorEstado


if __name__ == "__main__":
    deterministico = False
    if deterministico:
        tipoBeamSearch = "Beam search determinístico: "
    else:
        tipoBeamSearch = "Beam search não determinístico: "

    print(
        f"\n{tipoBeamSearch}\nMelhor estado: {beam_search_com_mochila_irrestrita(s=19, i=[(1, 3), (4, 6), (5, 7)], m=2, deterministico=deterministico)}"
    )