Otimização de cargas com algoritmo genético
Me deparei a alguns dias com uma 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 na qual hoje dedico boa parte do meu tempo para estuda-la, chamado de 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ó leva em consideração 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 fazendo 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 um 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”, levando em consideração 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
fori in range(len(individual)):
ifindividual[i]==1:
nota+=valores[i]
soma_espacos+=espacos[i]
soma_pesos+=pesos[i]
ifsoma_espacos > limtie_espacos and soma_pesos>limtie_peso:
nota=1
returnnota/100000,
Com tudo isso feito, agora é só a gente chamar o framework de algoritmos evolucionário DEAP , criando oque o frame work chama de 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 feito 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 de crossover e mutação e o número 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 ver 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 negocio, lá no meu GitHub você pode ver o notebook completo.
Espero que tenha gostado do artigo, compartilha se gostou 🙂
LinkedIn do autor:
https://www.linkedin.com/in/joaoataidee/
Post original:
#Otimização #algoritmo #genético