A few days ago I came across a problem in an area that I hadn't studied yet, when a friend, owner of a fleet of trucks, asked me to carry out a distribution of orders in a region, however, he wanted to use as much of space of your trucks, use the maximum weight supported and maximize your profit in the delivery of orders, taking into account that the greater the value of the general cargo, the greater the profit on deliveries.
So... Researching how I would solve this problem, I found an area in which I dedicate a good part of my time to study, called Genetic Algorithms. This kind of computational intelligence algorithm works like a species evolution process (the same one you're thinking about), Darwin's famous theory of evolution, but not quite like this image we see below, which just kind of considers an "evolutionary leap".
But, more as a genetic explanation in particular the reproductive process of species, in which they suffer a phenomenon called crossover, which "mixes" part of the DNA of a father and a mother, in addition to the environmental effects that can cause the famous mutation ( but not the one from the X-men), these two phenomena modify the genetics with time or generations, adapting the species to the environment due to "species survival", where those that survive are easier to reproduce.
Is this exactly the process that we simulate when we are designing a genetic algorithm, and how do we do it? I can tell you it's very simple. It is only necessary to create a pollution of individuals, which have in their gene binary values that will indicate whether or not the truck will carry the products.
The entire basic process of a genetic algorithm is basically defined from this flowchart below, from population creation, fitness, selection to optimization.
Adaptado de Eyal Wirsansky, 2020
The products used in the truck were taken from a Kaggle competition called brazilian-ecommerce, which has several datasets, being necessary to perform a join between the products, so that all the variables necessary for the optimization of the load were available, as well as see in the table below.
Another thing needed to simulate are our constraints, being the maximum volume of the VUC truck which is 5,544.00 cm³ and a maximum load weight of 4,000,000.00 grams. So, the step now is to create the product class in python and transform the dataset into a list, with the following code.
#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)With that we enter one of the most annoying parts of the algorithm, that part of the evaluation function, where to evaluate the best population and give it a grade (as well as in the evolution there), thus giving priority to it to reproduce in the next generation. In this case, I used the "addicted roulette" evaluation function, considering the truck's weight and space restriction.
#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,With all that done, now we just call the evolutionary algorithms framework DEAP , creating what the frame work calls Toolbox. Putting and recording everything in this toolbox, which will be called later to run the optimization.
#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)All this process carried out now is just to run the algorithm, putting your statistics that will be evaluated, in addition to the number of individuals of each generation (population), the rossover portability of generations.
#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)Arriving then at the best individual after 250 generations, which had a value of R$ 7968387.8, adding up to 56604 pieces of equipment, some of these you can observe in the first five products.
In addition, we can also see how the algorithm learned at each epoch, plotting the maximum value of the best of the individual generations.
#Plotando o aprendizado
valores_pop = info.select("max")
plt.figure(figsize = (12,6))
plt.plot(valores_pop)
plt.show()Which we can see, that the best individual has already been found at the beginning of the algorithm, more specifically in generation 23.
So that's it, it was a simple example of using a genetic algorithm, but it showed that with simple programming it is possible to maximize the company's profit, and it can be improved and applied to various business problems, on my GitHub you can see the complete notebook.
I hope you enjoyed the article, share if you liked it. :)