Hands-On Genetic Algorithms with Python

Using hard and soft constraints for the graph coloring problem

When solving the nurse scheduling problem earlier in this chapter, we noted the difference between hard constraints – those we have to adhere to for the solution to be considered valid – and soft constraints – those we strive to minimize to get the best solution. In the graph coloring problem, the color assignment requirement – where no two adjacent nodes can have the same color – is a hard constraint. We have to minimize the number of violations of this constraint to zero to achieve a valid solution.

Minimizing the number of colors used, however, can be introduced as a soft constraint. We would like to minimize this number, but not at the expense of violating the hard constraint. ...