Crafting Fitness Functions
Genetic Algorithms in Elixir — by Sean Moriarity (40 / 101)
👈 Applying Termination Criteria to Shipping | TOC | Exploring Different Types of Optimization 👉
In the previous few sections, you explored the importance of evaluation through the context of a modified knapsack problem. While the problem shows the importance of crafting a good fitness function, you learned only one way to evaluate a specific type of problem. Countless problems exist, each requiring unique evaluation tools. Unfortunately, you can’t generalize one fitness function to all problems. You need to fully understand what fitness functions aim to accomplish.
Understanding Fitness
Recall from Chapter 1, Writing Your First Genetic Algorithm, the problem of being lost in the woods. Some of the trees are marked indicating how close you are to escaping the woods. The markings on the trees show the value of your current position — they tell you how to navigate the woods and where to go next. Without this information, it’s likely you’d never escape.
Fitness is, in essence, the same as the markings on the trees. Specifically, fitness is the value assigned to a particular chromosome based on the criteria defined in the fitness function. Consider this: you’re lost in the woods again, only this time, the trees aren’t marked. Instead, you have a guide who tells you how close to civilization you are after every step. In this example, the guide acts as your fitness function, providing you with information based on your current position. This information is the fitness of your current position and tells you how close you are to making it back to civilization.
Understanding Schemas
Theoretically, fitness is supposed to be tied to a chromosome’s viability for reproduction. Viability for reproduction means that the chromosome is likely to produce strong offspring — something about the chromosome makes it fundamentally better than others for creating children.
That “something” that makes some chromosomes better than others are the schemas that comprise the chromosome. In Chapter 1, Writing Your First Genetic Algorithm, we briefly introduced the idea of schemas. Schemas are templates of genes that make up the genes of a chromosome. A schema is represented by a set of valid genes and wildcards represented by *. For example, the following are example schemas for a binary genotype.
- 11*01*
- 0*10*1
- 011*00
Schemas propagate from generation to generation as parents pass their schemas down to their children. Over time, as chromosomes exchange fit schemas, the presence of fit schemas in the population grows exponentially. Of course, with more fit schemas in the population, the fitness of the population inevitably grows as well. The theory behind schemas and how they improve populations is called the schema theorem or fundamental theorem of genetic algorithms.
The schema theorem is important because it tells you why genetic algorithms work. So, how does this relate to fitness functions? Ideally, you want to craft fitness functions that map meaningful schemas in your encoding of a problem to meaningful solutions in the real world. For example, if you tasked a genetic algorithm with designing a chair, you’d want a fitness function that was able to extract valuable schemas from certain designs, such as the presence of a flat surface to sit on or a support mechanism to hold weight.
In practice, you can’t tell a fitness function exactly what to look for because you don’t always know exactly what it should look for. Instead, you give it an estimate.
Fitness Functions Are Heuristics
A fitness function is a heuristic. In other words, it’s an approximation or estimate based on limited information. For example, you can’t tell your fitness function to look for seats or support in chair designs, but you can measure how much weight it will support or how comfortable the chair would be.
As another example, imagine you’re writing a program that optimizes a portfolio of stocks. Your goal is to maximize your return on investment (ROI). Unfortunately, you can’t perfectly predict what stocks will have the highest ROI. Instead, you have to make estimates based on the information available to you, such as the price-to-earnings ratio (P/E ratio). Picking stocks based on some metric like the P/E ratio won’t guarantee you perfectly maximize ROI, but it will give you a much better approximation than random stock-picking.
In the portfolio example, the P/E ratio is a heuristic used to measure the potential of a stock to provide the greatest ROI. If you were writing a genetic algorithm to accomplish portfolio optimization, evaluating a chromosome — or in this case, a portfolio — based on the P/E ratio is an example of a good fitness function because it provides a somewhat accurate estimate of how good a portfolio is.
Heuristics, like all things, are imperfect. A good heuristic will be right most of the time, but occasionally, it can be wrong. For example, Amazon is a stock with a very high ROI over the last five years that would be completely ignored when using the P/E ratio as a heuristic. A fitness function will never perfectly assess every solution; it just needs to capture the essential characteristics of your problem.
Fitness Landscapes
INFORMATION
One thing you’ll see mentioned often with genetic algorithms is the concept of a fitness landscape. At a high level, the fitness landscape is a representation of all of the fitnesses of every possible solution in your search space. For example, in portfolio optimization, the fitness landscape would graphically depict every possible portfolio and its corresponding fitness. Fitness landscapes are an abstract concept, and you don’t need to understand them to apply genetic algorithms effectively.
👈 Applying Termination Criteria to Shipping | TOC | Exploring Different Types of Optimization 👉
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.
