Solving the Quadratic Assignment Problem with DEAP
Let’s tackle a challenging combinatorial optimization problem, specifically the Quadratic Assignment Problem ($QAP$).
This is a classic problem in combinatorial optimization, known for its complexity and difficulty.
Problem: Quadratic Assignment Problem (QAP)
The $QAP$ models scenarios where a set of facilities needs to be assigned to a set of locations, and the cost depends on both the flow between facilities and the distance between locations.
The goal is to minimize the total cost of assignment.
Problem Definition
You are given:
- n facilities and n locations.
- A flow matrix $( F \in \mathbb{R}^{n \times n} )$ where $( F[i][j] )$ is the flow between facility $( i )$ and facility $( j )$.
- A distance matrix $( D \in \mathbb{R}^{n \times n} )$ where $( D[i][j] )$ is the distance between location $( i )$ and location $( j )$.
The objective is to find a permutation $( \pi )$ of $( {1, 2, …, n} )$ that assigns each facility to a location such that the total cost is minimized.
The cost function is defined as:
$$
C(\pi) = \sum_{i=1}^{n} \sum_{j=1}^{n} F[i][j] \cdot D[\pi(i)][\pi(j)]
$$
where $( \pi(i) )$ denotes the location assigned to facility $( i )$.
Example Scenario
Imagine you’re optimizing the layout of a factory.
There are multiple machines (facilities) and various spots (locations) where the machines can be placed.
The machines have specific interactions with each other (flow of goods), and the goal is to minimize transportation costs between machines by placing them in optimal spots based on their interactions.
Problem Setup
- Objective: Minimize the total cost of assigning facilities to locations.
- Constraints:
- Each facility must be assigned to exactly one location.
- Each location must host exactly one facility.
- Method: Use a Genetic Algorithm (GA) via $DEAP$ to find the optimal assignment of facilities to locations.
DEAP Implementation
We will use $DEAP$ to model this problem as a permutation-based optimization problem, where each individual in the population represents a permutation (assignment of facilities to locations).
Step-by-Step Approach:
- Representation: Each individual is a permutation of integers representing the assignment of facilities to locations.
- Evaluation: The fitness of an individual is the total cost of the assignment (using the cost function described above).
- Crossover and Mutation: Since this is a combinatorial problem, specialized crossover (e.g., partially mapped crossover) and mutation (e.g., swap mutation) operators are used.
- Selection: Individuals are selected based on their fitness values for the next generation.
Here’s how to solve the $QAP$ using $DEAP$ in $Python$:
1 | import random |
Explanation of the Code
- Fitness Function: The
fitness_functioncalculates the total cost of assigning facilities to locations based on the flow and distance matrices. - Individual Representation: Each individual is a permutation of the indices $( {0, 1, 2, …, n-1} )$, representing an assignment of facilities to locations.
- Crossover: We use partially matched crossover (PMX), which ensures valid permutations after crossover.
- Mutation: The mutShuffleIndexes operator randomly swaps the positions of two elements in the permutation, introducing small variations.
- Selection: We use tournament selection (
selTournament) to select individuals for reproduction.
Running the Algorithm
When you run the genetic algorithm, $DEAP$ will evolve the population over time. The algorithm will keep track of the best solution (the permutation that results in the lowest cost) and report the final best individual and its corresponding cost.
Why This Is Challenging
The Quadratic Assignment Problem is NP-hard, meaning it is computationally difficult to solve optimally for large instances.
The problem’s complexity grows rapidly as the number of facilities increases, due to the factorial number of possible assignments $( n! )$.
This makes it a perfect candidate for metaheuristic approaches like Genetic Algorithms, which can efficiently search large solution spaces.
Real-World Applications
- Facility Layout Planning: Optimizing the layout of machinery in factories to minimize transportation costs.
- Data Center Design: Assigning servers to racks in a way that minimizes the cost of communication between servers.
- Hospital Design: Assigning departments (facilities) to rooms (locations) to minimize the movement of patients, staff, and resources.
This example illustrates how $DEAP$ can be applied to solve complex combinatorial optimization problems using evolutionary algorithms.
Output
gen nevals avg min 0 100 1611.06 1436 1 73 1582.84 1436 2 85 1546.18 1436 3 64 1501.92 1436 4 71 1476.96 1436 5 79 1467.72 1436 6 81 1463.3 1436 7 70 1441.28 1436 8 75 1451.24 1436 9 70 1454.02 1436 10 64 1449.72 1436 11 79 1464.28 1436 12 68 1457.32 1436 13 73 1464.88 1436 14 69 1451.34 1436 15 69 1450.1 1436 16 76 1458.96 1436 17 79 1457.3 1436 18 78 1456 1436 19 78 1453.9 1436 20 74 1459.32 1436 21 70 1459.76 1436 22 85 1449.28 1436 23 75 1454.76 1436 24 84 1456.92 1436 25 87 1444.84 1436 26 78 1458.72 1436 27 82 1452.36 1436 28 83 1458.68 1436 29 76 1459.28 1436 30 77 1457.08 1436 31 76 1455.68 1436 32 70 1451.78 1436 33 72 1455.36 1436 34 79 1447.14 1436 35 65 1456.52 1436 36 79 1449.48 1436 37 78 1454.12 1436 38 63 1457.16 1436 39 75 1458.6 1436 40 80 1454.94 1436 41 68 1453.44 1436 42 78 1456.34 1436 43 84 1444.42 1436 44 69 1450.64 1436 45 76 1447.82 1436 46 70 1454.64 1436 47 78 1447.74 1436 48 81 1459.22 1436 49 72 1454.06 1436 50 73 1455.82 1436 51 81 1463.56 1436 52 81 1450.4 1436 53 72 1458.44 1436 54 79 1451.44 1436 55 81 1461 1436 56 77 1456.52 1436 57 79 1446.98 1436 58 66 1462.22 1436 59 72 1444.18 1436 60 62 1461.26 1436 61 71 1457.9 1436 62 90 1445.26 1436 63 78 1458.44 1436 64 81 1455.92 1436 65 72 1454.92 1436 66 81 1446.14 1436 67 72 1440.92 1436 68 81 1451.46 1436 69 78 1451.18 1436 70 85 1458.2 1436 71 75 1457 1436 72 74 1452.4 1436 73 77 1456.96 1436 74 71 1445.98 1436 75 83 1457 1436 76 80 1448.7 1436 77 84 1456.38 1436 78 74 1468.24 1436 79 75 1453.36 1436 80 75 1452.34 1436 81 87 1463.12 1436 82 73 1450.84 1436 83 70 1451.94 1436 84 73 1454.76 1436 85 76 1449.5 1436 86 76 1454.96 1436 87 81 1452.58 1436 88 79 1460.16 1436 89 70 1466.76 1436 90 76 1445.5 1436 91 69 1460.82 1436 92 72 1455.46 1436 93 76 1455.96 1436 94 70 1451.98 1436 95 78 1446.96 1436 96 69 1446.6 1436 97 71 1461.48 1436 98 76 1469.44 1436 99 73 1462.18 1436 100 69 1456.28 1436 101 82 1455.74 1436 102 72 1458.5 1436 103 74 1458.44 1436 104 72 1444.3 1436 105 81 1457.88 1436 106 76 1453.9 1436 107 69 1457.82 1436 108 79 1446.86 1436 109 73 1445.1 1436 110 76 1457.14 1436 111 77 1458.52 1436 112 82 1444.12 1436 113 78 1463.36 1436 114 69 1455.58 1436 115 71 1459.42 1436 116 78 1453.62 1436 117 74 1448.24 1436 118 79 1459.58 1436 119 73 1454.62 1436 120 87 1454.76 1436 121 81 1457.76 1436 122 77 1453.88 1436 123 63 1444.22 1436 124 74 1452.24 1436 125 80 1455.92 1436 126 70 1451.1 1436 127 76 1454.48 1436 128 66 1449.18 1436 129 76 1448.24 1436 130 73 1454.5 1436 131 77 1456.12 1436 132 71 1461.96 1436 133 85 1450.24 1436 134 64 1453.94 1436 135 80 1449.18 1436 136 75 1458.52 1436 137 74 1460.74 1436 138 84 1459.9 1436 139 73 1463.12 1436 140 85 1455.72 1436 141 80 1457.12 1436 142 72 1449.9 1436 143 79 1445.54 1436 144 74 1455.94 1436 145 81 1462.96 1436 146 75 1453.94 1436 147 78 1447.94 1436 148 73 1453.86 1436 149 77 1452.66 1436 150 87 1451.82 1436 151 69 1448.36 1436 152 71 1453.52 1436 153 76 1448.16 1436 154 71 1447.4 1436 155 75 1448.06 1436 156 76 1449.04 1436 157 78 1453.22 1436 158 83 1449.98 1436 159 75 1456.72 1436 160 71 1457.84 1436 161 66 1450.36 1436 162 82 1467.6 1436 163 81 1458.16 1436 164 77 1457.58 1436 165 68 1455.12 1436 166 70 1453.78 1436 167 85 1456.32 1436 168 76 1452.36 1436 169 74 1452.36 1436 170 73 1462.48 1436 171 71 1450.2 1436 172 72 1450.98 1436 173 79 1452.08 1436 174 78 1453 1436 175 74 1454.96 1436 176 75 1451.64 1436 177 82 1443.52 1436 178 66 1455.34 1436 179 75 1466.22 1436 180 79 1453.08 1436 181 74 1450.58 1436 182 88 1452.12 1436 183 81 1460.62 1436 184 70 1449.4 1436 185 85 1457.42 1436 186 74 1462.48 1436 187 74 1454.24 1436 188 77 1454.88 1436 189 70 1444.34 1436 190 71 1441 1436 191 76 1454.46 1436 192 70 1453.3 1436 193 81 1452.88 1436 194 77 1445.44 1436 195 69 1450.14 1436 196 78 1462.52 1436 197 72 1460.7 1436 198 61 1449.24 1436 199 69 1449.1 1436 200 76 1455.04 1436 Best individual: [3, 2, 0, 1] Best fitness (cost): 1436.0
This output represents the progress of the genetic algorithm over $200$ generations as it attempts to solve a combinatorial optimization problem using $DEAP$.
The key columns are:
- gen: The current generation number.
- nevals: The number of individuals evaluated in that generation.
- avg: The average fitness (cost) of the population in that generation.
- min: The minimum fitness (best solution) found in that generation.
Explanation:
- The algorithm begins with an initial population, and over time, it refines the solutions.
- The minimum fitness (cost) starts at 1436 and remains the same throughout the generations, indicating that the optimal solution was found early (possibly in the first generation).
- The best individual (solution) is
[3, 2, 0, 1], with a cost of 1436.
Despite multiple generations and evaluations, no better solution than $1436$ was found after the initial discovery.
The algorithm successfully converged, finding the optimal or near-optimal solution.