Constraint Satisfaction

In this chapter, you will learn how genetic algorithms can be utilized for solving constraint satisfaction problems. We will start by describing the concept of constraint satisfaction and how it applies to search problems and combinatorial optimization. Then, we will look at several hands-on examples of constraint satisfaction problems and their Python-based solutions using the DEAP framework. The problems we will cover include the well-known N-Queen problem, followed by the nurse scheduling problem, and finally the graph coloring problem. Along the way, we will learn the difference between hard and soft constraints, as well as how they can be incorporated into the solution process.

In this chapter, we will cover the following topics:

• Understanding the nature of constraint satisfaction problems
• Solving the N-Queens problem using a genetic algorithm coded...

Technical requirements

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

• deap
• numpy
• matplotlib
• seaborn
• networkx – introduced in this chapter

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

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

Constraint satisfaction in search problems

In the previous chapter, we looked at solving search problems, which focused on the methodic evaluation of states and transitions between states. Every state transition typically involves a cost or gain, and the objective of the search was to minimize the cost or maximize the gain. Constraint satisfaction problems are a variant of search problems, where the states must satisfy a number of constraints or limitations. If we are able to translate the various violations of constraints into cost and then strive to minimize the cost, solving a constraint satisfaction problem can resemble solving a general search problem.

Like combinatorial optimization problems, constraint satisfaction problems have important applications in fields such as artificial intelligence, operations research, and pattern matching. A better understanding of these problems...

Solving the N-Queens problem

Originally known as the eight-queen puzzle, the classic N-Queens problem originated from the game of chess, and the 8x8 chessboard was its early playground. The task was to place eight chess queens on the board without any two of them threatening each other. In other words, no two queens can share the same row, same column, or same diagonal. The N-Queens problem is similar, using an N×N chessboard and N chess queens.

The problem is known to have a solution for any natural number, n, except for the cases of n=2 and n=3. For the original eight-queen case, there are 92 solutions, or 12 unique solutions if we consider symmetrical solutions to be identical. One of the solutions is as follows:

One of the 92 possible solutions for the eight-queen puzzle

By applying combinatorics, the count of all possible ways to place eight pieces on the 8×8 board...

Solving the nurse scheduling problem

Imagine you are responsible for scheduling the shifts for the nurses in your hospital department for this week. There are three shifts in a day – morning, afternoon, and night – and for each shift, you need to assign one or more of the eight nurses that work in your department. If this sounds like a simple task, take a look at the list of relevant hospital rules:

• A nurse is not allowed to work two consecutive shifts.
• A nurse is not allowed to work more than five shifts per week.
• The number of nurses per shift in your department should fall within the following limits:
  • Morning shift: 2–3 nurses
  • Afternoon shift: 2–4 nurses
  • Night shift: 1–2 nurses

In addition, each nurse can have shift preferences. For example, one nurse prefers to only work morning shifts, another nurse prefers to not work afternoon shifts...

Solving the graph coloring problem

In the mathematical branch of graph theory, a graph is a structured collection of objects that represents the relationships between pairs of these objects. The objects appear as vertices (or nodes) in the graph, while the relation between a pair of objects is represented using an edge. A common way of illustrating a graph is by drawing the vertices as circles and the edges as connecting lines, as depicted in the following diagram of the Petersen graph, named after the Danish mathematician Julius Petersen:

Petersen graph
Source: https://commons.wikimedia.org/wiki/File:Petersen1_tiny.svg
Image by Leshabirukov. Licensed under Creative Commons CC BY-SA 3.0: https://creativecommons.org/licenses/by-sa/3.0/deed.en

Graphs are remarkably useful objects as they can represent and help us research an overwhelming variety of real-life structures, patterns...

Summary

In this chapter, you were introduced to constraint satisfaction problems, a close relative of the previously studied combinatorial optimization problems. Then, we explored three classic constraint satisfaction cases – the N-Queen problem, the nurse scheduling problem, and the graph coloring problem. For each of these problems, we followed the now-familiar process of finding an appropriate representation for a solution, creating a class that encapsulates the problem and evaluates a given solution, and creating a genetic algorithm solution that utilizes that class. We ended up with valid solutions for the problems while getting acquainted with the concept of hard constraints versus soft constraints.

So far, we have been looking into discrete search problems consisting of states and state transitions. In the next chapter, we will study search problems in a continuous...

Further reading

For more information on the topics that were covered in this chapter, please refer to the following resources:

• Constraint Satisfaction Problems, from the book Artificial Intelligence with Python by Prateek Joshi, January 2017

• Introduction to graph theory, from the book Python Data Science Essentials – Second Edition by Alberto Boschetti, Luca Massaron, October 2016

• NetworkX Tutorial: https://networkx.github.io/documentation/stable/tutorial.html