Otimização de cargas com algoritmo genético

---

Deparei-me a alguns dias com um problema de uma área a qual ainda não havia estudado, quando um amigo, dono de uma frota de caminhões me pediu para realizar uma distribuição de encomendas em uma região, no entanto, ele queria utilizar o máximo de espaço de seus caminhões, usar o máximo de peso suportado e maximizar o seu lucro na entrega das encomendas, levando em consideração que para quanto maior o valor da carga geral maior será lucro nas entregas.

Então... Pesquisando como iria resolver esse problema, achei uma área em que hoje dedico boa parte do meu tempo para estudar, chamado Algoritmos Genéticos. Esse tipo de algoritmo de inteligência computacional funciona como um processo de evolução de espécies (esse mesmo que você está pensando), a famosa teoria da evolução de Darwin, mas não muito como essa imagem que vemos aqui em baixo, a qual só considera meio que um "salto evolutivo".

Mas, mais como uma explicação genética em especial o processo reprodutivo das espécies, nas quais sofrem um fenômeno chamado de crossover, que "mistura" parte do DNA de um pai e de uma mãe, além dos efeitos ambientais que podem causar a famosa mutação (mas não essa do X-men), esses dois fenômenos modificam a genética com o tempo ou gerações, adaptando as espécies ao ambiente devido a "sobrevivência das espécies", onde estas que sobreviverem tem mais facilidade de reproduzir.

É exatamente esse processo que simulamos quando estamos elaborando um algoritmo genético, e como fazemos isso? Posso dizer a você que é muito simples. Só é preciso criar uma polução de indivíduos, os quais possuíram em seu gene valores binários que indicarão se o caminhão levará ou não os produtos.

Todo o processo básico de um algoritmo genético se define basicamente a partir desse fluxograma abaixo, desde a criação da população, fitness, selection até a otimização.

Adaptado de Eyal Wirsansky, 2020

Os produtos usados no caminhão foram retirados de uma competição do Kaggle de nome brazilian-ecommerce, o qual possuem vários datasets separados, sendo necessário realizar um join entre os produtos, para que todos as variáveis necessárias para a otimização da carga fosse disponibilizada, assim como vemos na tabela abaixo.

Outra coisa necessária para simular, são a nossas constraints, sendo o volume máximo do caminhão VUC que é de 5.544,00 cm³ e carga de peso máximo de 4.000.000,00 gramas. Então, o passo agora é criar a classe produto no python e transformar o dataset em lista, com o seguinte código.

#Criar Classe do Produto
class Produto():
    def __init__(self, nome, pesos, volume, valores):
        self.nome = nome
        self.pesos = pesos
        self.volume = volume
        self.valor = valor

#Transformar em lista
espacos = list(produtos.volume)
valores = list(produtos.preco)
nome = list(produtos.product_id)
pesos = list(produtos.product_weight_g)

Com isso entramos em uma das partes mais chatinha do algoritmo, que a parte da função de avaliação, onde avaliar qual a melhor população e dar uma nota (assim como na evolução lá), dando assim, prioridade para esse se reproduzir na próxima geração. Neste caso, usei a função de avaliação da "roleta viciada", considerando a restrição de peso e espaço do caminhão.

#Criar a função de avaliação
def avaliacao(individual):
    nota=0
    soma_espacos=0
    soma_pesos=0

    for i in range(len(individual)):
        if individual[i]==1:
            nota+=valores[i]
            soma_espacos+=espacos[i]
            soma_pesos+=pesos[i]
            
           if soma_espacos > limtie_espacos and soma_pesos>limtie_peso:
            nota=1
return nota/100000,

Com tudo isso feito, agora é só chamarmos o framework de algoritmos evolucionários DEAP , criando oque o frame work chama Toolbox. Colocando e registrando tudo nessa caixa de ferramenta, a qual será chamada depois para executar a otimização.

#Criar a toolbox
toolbox=base.Toolbox()

#Criando parâmetros na toolbox
creator.create("FitnessMax",base.Fitness,weights=(1.0,))creator.create("Individual",list,fitness=creator.FitnessMax)

#Registrando na toolbox
toolbox.register("attr_bool",random.randint,0,1)
toolbox.register("individual",tools.initRepeat,creator.Individual,toolbox.attr_bool,n=len(espacos))
toolbox.register("population",tools.initRepeat,list,toolbox.individual)toolbox.register("evaluate",avaliacao)
toolbox.register("mate",tools.cxOnePoint)
toolbox.register("mutate",tools.mutFlipBit,indpb=0.05)
toolbox.register("select",tools.selRoulette)

Todo esse processo realizado agora é somente executar o algoritmo, colocando usas estatísticas que serão avaliadas, além do número de indivíduos de cada geração (população), a portabilidade rossover de gerações.

#Iniciando a toolbox
if__name__=="__main__":
    population=toolbox.population(n=24)
    probabilidade_crossover=5.0
    probabilidade_mutação=0.03
    numero_gerações=250
    
    
    estatisticas = tools.Statistics(key=lambdaindividuo:
            individuo.fitness.values)
            
    estatisticas.register("max",np.max)
    estatisticas.register("min",np.min)
    estatisticas.register("med",np.mean)
    estatisticas.register("std",np.std)
    
    populacao,info=algorithms.eaSimple(population,toolbox,
                                         probabilidade_crossover,
                                        probabilidade_mutação,
                                        numero_gerações, estatisticas)

Chegando então no melhor indivíduo após as 250 gerações, o qual ficou com um valor de R$ 7968387.8, somando 56604 equipamentos, algum desses você pode observar nos cinco primeiros produtos.

Além disso, podemos também ver como foi o aprendizado do algoritmo em cada época, plotando o valor máximo do melhor do indivíduo das gerações.

#Plotando o aprendizado
valores_pop = info.select("max")
plt.figure(figsize = (12,6))
plt.plot(valores_pop)
plt.show()

O qual podemos ver, que o melhor indivíduo já foi encontrado logo no começo do algoritmo, mais especificamente na geração 23.

Então é isso, foi um exemplo simples de uso de algoritmo genético, mas que mostrou que com um programação simples é possível gerar a maximização do lucro da empresa, podendo ser melhorado e aplicado para vários problemas de negócio, lá no meu GitHub você pode ver o notebook completo.

Espero que tenha gostado do artigo, compartilha se gostou. :)