Applying a Penalty to the Shipping Problem

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

👈 Introducing Penalty Functions | TOC | Defining Termination Criteria 👉

Now that you understand penalty functions, you need to apply them in the context of your cargo problem. You’ll implement a very basic penalty: if a solution exceeds the weight limit, its fitness is 0. Otherwise, its fitness is equal to the profit it yields.

To implement this penalty, change your fitness function to look like this:

​ ​def​ fitness_function(chromosome) ​do​
​   profits = [6, 5, 8, 9, 6, 7, 3, 1, 2, 6]
​   weights = [10, 6, 8, 7, 10, 9, 7, 11, 6, 8]
​   weight_limit = 40
​ 
​   potential_profits =
​     chromosome.genes
​     |> Enum.zip(profits)
​     |> Enum.map(​fn​ {c, p} -> c * p ​end​)
​     |> Enum.sum()
​ 
​   over_limit? =
​     chromosome.genes
​     |> Enum.zip(weights)
​     |> Enum.map(​fn​ {c, w} -> c * w ​end​)
​     |> Enum.sum()
​     |> Kernel.>(weight_limit)
​ 
​   profits = ​if​ over_limit?, ​do​: 0, ​else​: potential_profits
​   profits
​ ​end​

In this snippet, you define problem-specific constants: profits, weights, and weight_limit. Then you calculate the potential profit in the same way you did in your previous fitness function. Next, you calculate the total weight and determine whether or not it exceeds weight_limit. Finally, you return a profit based on your penalty.

Now, you can try running your algorithm again:

​ ​$ ​​mix​​ ​​run​​ ​​scripts/cargo.exs​
​ Current Best: 39

After awhile, you might notice your algorithm stops improving but doesn’t stop running. You may have anticipated this. With your new penalty, but old termination criteria, your algorithm will never stop running because it can never reach the maximum possible profits.

Theoretically, you could calculate your new potential max, but that defeats the purpose of using a genetic algorithm. Instead, you need to know when to stop your algorithm, even when you don’t know what the best solution looks like.

👈 Introducing Penalty Functions | TOC | Defining Termination Criteria 👉

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.