Combinatorial Optimization

In this chapter, you will learn how genetic algorithms can be utilized in combinatorial optimization applications. We will start by describing search problems and combinatorial optimization, and outline several hands-on examples of combinatorial optimization problems. We will then analyze each of these problems and match them with a Python-based solution using the DEAP framework. The optimization problems we will cover are the well-known knapsack problem, the traveling salesman problem (TSP), and the vehicle routing problem (VRP). As a bonus, we will cover the topics of genotype-to-phenotype mapping and exploration versus exploitation.

In this chapter, you will do the following:

• Understand the nature of search problems and combinatorial optimization
• Solve the knapsack problem using a genetic algorithm coded with the DEAP framework
• Solve the TSP using...

Technical requirements

In this chapter, we will be using Python 3 with the following supporting libraries:

• deap
• numpy
• matplotlib
• seaborn

In addition, we will be using the benchmark data from the Rosetta Code Knapsack problem/0-1 (http://rosettacode.org/wiki/Knapsack_problem/0-1), and the TSP LIB (http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/).

The programs used in this chapter can be found in the book's GitHub repository at https://github.com/PacktPublishing/Hands-On-Genetic-Algorithms-with-Python/tree/master/Chapter04.

Check out the following video to see the Code in Action:
http://bit.ly/2tfyfMI

Search problems and combinatorial optimization

One main area of applying genetic algorithms is search problems, which have important applications in fields such as logistics, operations, artificial intelligence, and machine learning. Examples include determining the optimal routes for package delivery, designing hub-based airline networks, managing investment portfolios, and assigning passengers to available drivers in a fleet of taxis.

A search algorithm is focused on solving a problem through methodic evaluation of states and state transitions, aiming to find a path from the initial state to a desirable final (or goal) state. Typically, there is a cost or gain involved in every state transition, and the objective of the corresponding search algorithm is to find a path that minimizes the cost or maximizes the gain. Since the optimal path is one of many possible ones, this kind...

Solving the knapsack problem

Think of the familiar situation of packing for a long trip. There are many items that you would like to take with you, but you are limited by the capacity of your suitcase. In your mind, each item has a certain value it will add to your trip; at the same time, each has a size (and weight) associated with it, and each will compete with other items over the available space in your suitcase. This situation is just one of many real-life examples of the knapsack problem, which is considered one of the oldest and most investigated combinatorial search problems.

More formally, the knapsack problem consists of the following components:

• A set of items, each of them associated with a certain value and a certain weight
• A bag/sack/container (the knapsack) of a certain weight capacity

Our goal is to come up with a group of selected items that will provide the...

Solving the TSP

Imagine that you manage a small fulfillment center and need to deliver packages to a list of customers using a single vehicle. What is the best route for the vehicle to take so that you visit all your customers and then return to the starting point? This is an example of the classic TSP.

The TSP dates back to 1930, and since then has been and is one of the most thoroughly studied problems in optimization. It is often used to benchmark optimization algorithms. The problem has many variants, but it was originally based on a traveling salesman that needs to take a trip covering several cities:

"Given a list of cities and the distances between each pair of the cities, find the shortest possible path that goes through all the cities, and returns to the starting city."

Using combinatorics, you could find that when given n cities, the number of possible paths...

Solving the VRP

Imagine that you now manage a larger fulfillment center. You still need to deliver packages to a list of customers, but now you have a fleet of several vehicles at your disposal. What is the best way to deliver the packages to the customers using these vehicles?

This is an example of VRP, a generalization of the TSP described in the previous section. The basic VRP consists of the following three components:

• The list of locations that need to be visited
• The number of vehicles
• The location of the depot, which is used as the starting and ending point for each one of the vehicles

The problem has numerous variations, such as several depot locations, time-critical deliveries, different types of vehicles (with varying capacity and varying fuel consumption, for instance), and many more.

The goal of the problem is to minimize the cost, which can also be defined in many...

Summary

In this chapter, you were first introduced to search problems and combinatorial optimization. We then examined closely three classic combinatorial problems—each with numerous real-life applications—the knapsack problem, the TSP, and the VRP. For each of these problems, we followed a similar process of finding an appropriate representation for a solution, creating a class that encapsulates the problem and evaluates a given solution, then creating a genetic algorithm solution that utilizes that class. We ended up with valid solutions for all three problems while experimenting with genotype-to-phenotype mapping and elitism-backed exploration.

In the next chapter, we will look into a family of closely related tasks, namely constraint satisfaction problems, starting with the classic N-Queen problem.

Further reading

For more information, please refer to the following resources:

• Solving the knapsack problem using Dynamic Programming, from the book Keras Reinforcement Learning Projects by Giuseppe Ciaburro, September 2018
• The Vehicle Routing Problem, from the book Keras Reinforcement Learning Projects by Giuseppe Ciaburro, September 2018