DNA Recomendado

Sistema de Recomendação que utiliza computação evolutiva para otimizar a distribuição de estoque entre depósitos e cervejarias.

  • 35000 Raised
  • 2 Juries

Categories

  • Sistema de recomendação e otimização

Featured Video

Description

Vídeo: https://www.youtube.com/watch?v=392hoKbQc1I

 

Título: DNA Recomendado

 

Autor(es): Aurora Pozo; Andrea de Fatima Cavalheiro; Celso Ishida; Eduardo Spinosa; Ernesto Malta Rodrigues

 

Resumo: 


A abordagem da Computação Evolutiva foi escolhida para o problema de otimizar a distribuição de estoque entre depósitos e cervejarias pois os algoritmos genéticos são flexíveis para se adequar as métricas que a Ambev gostaria de maximizar. Além disso são ótimos para lidar com problemas complexos em que se desconhece algum algoritmo ótimo que retorne a resposta em tempo polinomial, pois podem retornam uma resposta próxima da ótima em um tempo plausível.

 

Palavras-chave:  Computação Evolutiva; Algoritmo GenéticoProgramação Genética 

 

Introdução: 


A escolha da Computação Evolutiva para este problema foi dada pela flexibilidade dos algoritmos genéticos em se adaptar a diferentes métricas, por mais complexas que elas sejam e pelo fato de chegarem a uma solução próxima da ótima em um tempo plausível. 


Um dos empregos do algoritmo genético é para encontrar uma boa solução para o Problema da Mochila em um tempo hábil, já que a solução ótima muitas vezes não poderia ser encontrada em tempo curto por se tratar de um problema np-completo. 


O Problema da Mochila se trata de encontrar a combinação de objetos com pesos e valores que maximiza o valor total dos objetos dentro da mochila sem que algum peso limite seja ultrapassado. Este problema, apesar de ser mais simples, é de certa forma semelhante ao problema do estoque que queremos resolver. Portanto com modificações nesse algoritmo, seria possível resolver o problema da otimização dos estoques.


Metodologia:


Em um primeiro momento, antes de precisamente adentrar à explicação do algoritmo, gostaria de ressaltar seus componentes. Para tanto, utilizarei a definição data em Computação Evolutiva¹.


Indivíduos: as quantidades de insumos a serem adquiridas e de quais origens, a quantidade de insumo que deve ser enviado a cada cervejaria, as quantidade de cada produto produzido em cada cervejaria, a quantidade desses produtos que deverão ser enviados a cada ponto de venda ou centro de distribuição. Estas informações podem ser armazenadas em forma de uma fita:



Função de Aptidão: dado as métricas que a Ambev possui e gostaria de maximizar, calcular o quão bom é aquele individuo, ou seja, o quão boa é aquela distribuição de estoque e produção.


Algoritmo:

  1. Inicializa uma lista de indivíduos aleatoriamente;
  2. Calcula-se através da função de aptidão os scores de cada individuo;  
  3. Selecionamos a partir de alguma métrica quais indivíduos terão descendentes; 
  4. Combinamos os indivíduos selecionados para termos variabilidade genética;
  5. Adiciona a uma parcela desses novos indivíduos mutações para verificar se uma inovação iria beneficiar a solução;
  6. Repete-se o algoritmo a partir do item 2 até alguma função de parada ser satisfeita


Referências: 


¹P. Aurora; F. C. Andrea; I. Celso; S. Eduardo; M.R. Ernesto, Computação Evolutiva

https://www.inf.ufpr.br/aurora/tutoriais/Ceapostila.pdf


Copyright © 2022 All rights reserved. TAIKAI — Hackathon Platform.