Exploring Different Types of Optimization

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

👈 Crafting Fitness Functions | TOC | What You Learned 👉

So far, the problems you’ve implemented in this book have focused on optimizing a single objective using a simple fitness function. In the real world, some of the problems you’ll encounter will be much more complex.

In this section, you’ll briefly explore two classes of optimization that require more advanced approaches to evaluation: multi-objective optimization and interactive optimization.

Optimizing Multiple Objectives

The real world is full of competing interests that need to be optimized. For example, you might find yourself trying to balance work, relationships, health, fun, and sleep every day — a classic example of a multi-objective optimization problem. A multi-objective optimization problem is one in which you have multiple parameters or objective functions that need to be optimized. Oftentimes, but not always, the objective functions are in competition with one another — when you increase the value of one, the value of the other goes down.

Multi-objective optimization problems are some of the most common problems that appear in the real world. They also can be the most difficult to solve because they require a means of balancing your objectives. It’s important to note that there isn’t a single global solution to a multi-objective optimization problem. Instead, the best solutions exist on a line representing a set of optimal solutions. You can intuitively think of this in the context of people balancing work, relationships, health, and so on. In this context, no single balance works for everybody — instead, people determine what works best for them. There are multiple solutions.

The simplest way to solve a multi-objective optimization problem is to transform it into a single objective. This makes the problem simple enough because you can use the same means you used to solve optimization problems with a single objective.

To better understand this concept, consider a trivial portfolio optimization problem. Start by creating a new file scripts/portfolio.exs. In this file, you’ll write a genetic algorithm for solving a trivial portfolio optimization problem. In the original portfolio example, your goal was to maximize ROI. In this example, you’re still trying to maximize ROI, but this time you also have to minimize risk.

To simplify the problem, assume you have a function which provides a predicted ROI and risk score for every stock in your portfolio. A solution in this situation is a collection of stocks. Stocks are represented as tuples of the form (ROI, Risk). Note that in a practical example, you’d need some way of differentiating between stocks using a Ticker or some other identifier. That’s excluded to simplify the example.

Open scripts/portfolio.exs and implement genotype/0 and terminate?/1 like this:

​ ​defmodule​ Portfolio ​do​
​   @behaviour Problem
​   alias Types.Chromosome
​ 
​   @target_fitness 180
​ 
​   @impl true
​   ​def​ genotype ​do​
​     genes =
​       for _ <- 1..10, ​do​:
​         {​:rand​.uniform(10), ​:rand​.uniform(10)}
​     %Chromosome{​genes:​ genes, ​size:​ 10}
​   ​end​
​ 
​   @impl true
​   ​def​ fitness_function(chromosome) ​do​
​     ​# TODO​
​   ​end​
​ 
​   @impl true
​   ​def​ terminate?(population, _generation) ​do​
​     max_value = Enum.max_by(population, &Portfolio.fitness_function/1)
​     max_value > @target_fitness
​   ​end​
​ ​end​

The genotype generates portfolios of 10 stocks each with ROI and risk scores between 0 and 10. The algorithm is set to terminate when the max fitness of the population is greater than @target_fitness, which is defined as 180.

Your goal, then, is to implement a fitness function that effectively optimizes both ROI and risk. The simplest way to do this is to turn it into a single objective. You can achieve this using a weighted sum. A weighted sum is when you assign weights to each parameter and sum them to produce a single fitness. A weighted sum for this problem would look something like this:

​ ​def​ fitness_function(chromosome) ​do​
​   chromosome
​   |> Enum.map(​fn​ {roi, risk} -> 2 * roi - risk ​end​)
​   |> Enum.sum()
​ ​end​

Notice how the formula in this case weights ROI as two times more important than risk. With this fitness function, you’ve effectively turned your multi-objective optimization problem into a single-objective optimization problem. You can now run your algorithm using the same means as a simple optimization problem.

Real-Value Genotypes

INFORMATION

If you tried running this novel genetic algorithm, you’d struggle to find any improvements in fitness. That’s because you haven’t yet been equipped with tools for driving real-value genotypes forward. You need special crossover and mutation operators to work with them. You’ll learn some in Chapter 6, ​Generating New Solutions​ and Chapter 7, ​Preventing Premature Convergence​.

Weighted sums are easy to implement and they greatly simplify your problem, but it’s difficult to determine how to weight some objectives versus others. This is once again where domain expertise comes into play. You can play around with multiple weights and determine which weights give you the best solutions.

Interactive Optimization

All of the techniques introduced in this chapter rely on numerical data that can be assessed explicitly using mathematical formulas. In every example, you were able to transform a chromosome according to a formula or set of rules; however, this isn’t always the case.

Some optimization problems are impossible to encode numerically but could still benefit from the application of a genetic algorithm. One example of this is web design optimization. A website is written as a series of rules and styles. While it’s possible to encode and interpret a website using a numerical representation, it is complex and would be difficult to change using a genetic algorithm. Additionally, it’s impossible to mathematically assess one web design as being better than the other.

To handle and assess perceptual data, you can write interactive fitness functions. Perceptual data is information based off of sensory inputs. An interactive fitness function is useful when the solutions you’re working with are impossible to assess mathematically. Instead, you present the user with a solution and ask them to assess its fitness. For example, in the case of web design, you’d show a user several different designs with slight alterations and ask them to rate the designs on a numerical scale. The values a user assigns to different solutions represents the fitness of the solution.

Another unique example of interactive optimization is generating suspect sketches from eyewitness responses. A sketch artist creates an initial sketch from an eyewitness description, and then the eyewitness is presented with variations of the sketch — rating each one based on how closely it resembles a suspect. Over time, the sketches evolve to closely match the eyewitness description, all thanks to a genetic algorithm.

Implementing interactive fitness functions is as simple as displaying a solution and asking for feedback from the user using Elixir’s IO module. To demonstrate this concept, create and open a new file in the scripts directory named one_max_interactive.exs.

Next, copy the code from scripts/one_max.exs into the body of scripts/one_max_interactive.exs. Now, change the fitness function to look like this:

​ ​def​ fitness_function(chromosome) ​do​
​   IO.inspect(chromosome)
​   fit = IO.get(​"​​Rate from 1 to 10 "​)
​   String.to_integer(fit)
​ ​end​

When you run this algorithm, you’ll be prompted to assess the fitness of every chromosome in the population during every generation. If you want the algorithm to run to completion, you can limit the population size and the size of a chromosome.

It’s useful to note that how you display solutions to the user is problem-dependent. In the case of web design optimization, you’ll want to display the actual design and ask the user to rate it. Additionally, understand that interactive fitness functions take time and are subject to a user’s bias. You’ll likely have to work with much smaller population sizes and determine a solution over the course of fewer generations than in a traditional algorithm. You’ll also likely have to take input from multiple users to mitigate the bias from a single user assessing fitness.

One final consideration is handling user input. In this example, there’s no sanity checking on the input. The program will break pretty quickly if the user doesn’t input exactly what’s expected. You’ll want to consider how to mitigate the possibility of users breaking your algorithms if you choose to work with interactive fitness functions. Interactive fitness functions have some interesting applications; however, they require much more time and effort to utilize effectively.

Other Types of Optimization

Optimization is an incredibly broad field with a wide array of applications in science, engineering, and math. As in this chapter, in the rest of the book you’ll focus on constraint satisfaction problems, combinatorial optimization problems, single- and multi-objective optimization problems, and interactive optimizaton problems. You might also find numerous other subfields of optimization interesting:

• No-objective optimization: also called feasability problems, seeks to find feasible solutions without worrying about any particular objective.
• Convex optimization: optimization on special types of functions called convex functions that is very useful in computational finance.
• Shape optimization: seeks to find the optimal shape of an object that minimizes some cost function — for example, finding the optimal shape of a cam.

Genetic algorithms are applicable to all of these fields with varying degree. If you’re ever faced with any optimization problem, genetic algorithms are always a good place to start.

👈 Crafting Fitness Functions | TOC | What You Learned 👉

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.