Optimizing Cargo Loads

Genetic Algorithms in Elixir — by Sean Moriarity (35 / 101)

👈 Chapter 4 Evaluating Solutions and Populations | TOC | Introducing Penalty Functions 👉

Suppose you work for a shipping company that has asked you to determine how to properly load cargo with different products so that you maximize profits and don’t exceed a specified weight limit. You have ten products, labeled A–J, with corresponding weights: [10, 6, 8, 7, 10, 9, 7, 11, 6, 8]. Each project has an associated profit margin: [6, 5, 8, 9, 6, 7, 3, 1, 2, 6] and the weight limit of the cargo is 40. The image shows the loads and their corresponding weights and profit margin.

You need to determine exactly which products to load to maximize profits and not go over the weight limit.

The problem presented here is a modification of the knapsack problem. The knapsack problem belongs to a class of optimization problems known as constraint satisfaction problems. Constraint satisfaction problems or CSPs are a type of optimization problem in which you’re asked to optimize a value under a set of constraints. Constraints are some limitation placed on your solutions. For example, in the problem above, your profits are limited by the amount of cargo you can fit in your truck.

To get started solving this problem, create a new file cargo.exs and add a new Problem implementation to it:

​ ​defmodule​ Cargo ​do​
​   @behaviour Problem
​   alias Types.Chromosome
​ 
​   @impl true
​   ​def​ genotype, ​do​: ​# ...​
​ 
​   @impl true
​   ​def​ fitness_function(chromosome), ​do​: ​# ...​
​ 
​   @impl true
​   ​def​ terminate?(population), ​do​: ​# ...​
​ 
​ ​end​

The first thing you need to do is determine how to represent your solutions. You have ten classes of cargo you can bring on board. You have two options with each class of cargo: bring it or not bring it. You can represent configurations with a binary genotype of size 10. In this case, the solution 1011000010 means you are bringing Product A, Product C, Product D, and Product I.

Implement the genotype like this:

​ ​def​ genotype ​do​
​   genes = for _ <- 1..10, ​do​: Enum.random(0..1)
​   %Chromosome{​genes:​ genes, ​size:​ 10}
​ ​end​

Next, you need to implement a fitness function. Your objective is to maximize profit, so your fitness function needs to somehow relate back to profitability. You need to somehow account for weights, but you can worry about that later.

Your fitness function should sum the total profits gained by the proposed cargo configuration. Implement it like this:

​ ​def​ fitness_function(chromosome) ​do​
​   profits = [6, 5, 8, 9, 6, 7, 3, 1, 2, 6]
​   profits
​   |> Enum.zip(chromosome.genes)
​   |> Enum.map(​fn​ {p, g} -> p * g ​end​)
​   |> Enum.sum()
​ ​end​

Here you multiply the potential profit of a product by 1 or 0 depending whether or not it’s present in the cargo configuration. Then you sum the list to receive the total profits.

The final thing you need to implement is the termination criteria. The maximum total profit you can achieve if you fit all the cargo on your truck is 53. For now, your termination criteria will look like this:

​ ​def​ terminate?(population), ​do​:
​   Enum.max_by(population, &Cargo.fitness_function/1).fitness == 53

Now, below your module definition, add the following:

​ soln = Genetic.run(Cargo, ​population_size:​ 50)
​ 
​ IO.write(​"​​\n"​)
​ IO.inspect(soln)
​ 
​ weight =
​   soln.genes
​   |> Enum.zip([10, 6, 8, 7, 10, 9, 7, 11, 6, 8])
​   |> Enum.map(​fn​ {g, w} -> w*g ​end​)
​   |> Enum.sum()
​ 
​ IO.write(​"​​\nWeight is: ​​#{​weight​}​​\n"​)

In this snippet, you run your algorithm with a population of 50 to obtain a solution. Then, you inspect the solution to see what the best configuration is. Finally, you calculate the total weight of this configuration and output the result to the console.

Next, run your problem like this:

​ ​$ ​​mix​​ ​​run​​ ​​examples/cargo.exs​
​ Current Best: 53
​ [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
​ Weight is: 82

While your profits are very high, your weight is through the roof. Your solution doesn’t correctly account for the stated constraint. Essentially, you’ve just implemented One-Max all over again. You need a different technique to account for constraints: penalty functions.

👈 Chapter 4 Evaluating Solutions and Populations | TOC | Introducing Penalty Functions 👉

Genetic Algorithms in Elixir by Sean Moriarity can be purchased in other book formats directly from the Pragmatic Programmers. If you notice a code error or formatting mistake, please let us know here so that we can fix it.