# Quadratic Assignment Problem (QAP) Using GA, PSO and FA in MATLAB

URL: https://yarpiz.com/quadratic-assignment-problem-ypap104
Author: Mostapha Kalami Heris
Published: 2015-09-20
Updated: 2026-10-30
Topics: Applications

> Solve a quadratic assignment example in MATLAB with GA, PSO, or Firefly search, including permutation encoding and weighted facility-location costs.

This package solves the Quadratic Assignment Problem (QAP) in MATLAB. A solution is a permutation that assigns facilities to locations. The cost is the sum of the flow between each pair of facilities multiplied by the distance between their assigned locations.

The QAP was introduced by Koopmans and Beckmann in 1957 as a model for locating economic activities. It is one of the hardest problems in combinatorial optimization. Sahni and Gonzalez showed in 1976 that it is NP-hard, although the difficulty of an exact solve depends on the instance. This is why metaheuristics such as the Genetic Algorithm (GA), Particle Swarm Optimization (PSO) and the Firefly Algorithm (FA) are often used for it.

## The problem

In the standard square QAP, there are $n$ facilities and $n$ locations. The flow (or weight) between facilities $i$ and $j$ is $w_{ij}$, and the distance between locations $k$ and $l$ is $d_{kl}$. Each facility must go to exactly one location, and each location can hold at most one facility. If facility $i$ is placed at location $\pi(i)$, the cost is

$$
\min_{\pi} \; \sum_{i=1}^{n} \sum_{j=1}^{n} w_{ij} \, d_{\pi(i)\pi(j)}
$$

where $\pi$ runs over all permutations. The cost is quadratic because it depends on the positions of two facilities at the same time. Moving one facility changes its cost with every other facility, which makes the problem much harder than the linear assignment problem.

The sample code uses a rectangular extension with $m \ge n$ candidate locations: it assigns each facility to a distinct location while allowing some locations to remain empty.

### The model in the code

The sample model in `CreateModel.m` places $n = 20$ units on $m = 40$ candidate locations. So there are more sites than units, and 20 of the 40 sites stay empty. The locations are points in the plane, and $d_{kl}$ is the Euclidean distance between them. The weight matrix `w` is a 20 by 20 matrix of small integers.

The model also adds three special pairs by changing the weights:

- Units 19 and 20 are strongly encouraged to be close (weight 10000).
- Units 11 and 16 are strongly encouraged to be close (weight 20000).
- Units 1 and 13 are encouraged to be far apart (weight $-10000$, so a larger distance lowers the cost).

`MyCost.m` sums the cost over the pairs with $i < j$, which is half of the double sum above for a symmetric weight matrix.

## How each algorithm handles permutations

The decision variable has 40 entries, one per location. The first 20 entries give the locations of the 20 units.

- **GA.** Each individual is a permutation of 1 to 40 (`randperm`). Parents are chosen by roulette wheel selection. `PermutationCrossover.m` cuts both parents at a random point and repairs the result so that it is still a permutation. `PermutationMutate.m` uses one of three moves at random: swap two entries, reverse a part of the permutation, or move one entry to another position.
- **PSO and FA.** These algorithms work with real numbers, so each solution is a vector of 40 values in $[0, 1]$. `MyCost.m` sorts the vector, and the order of the sorted values gives the permutation. This is often called a random key encoding. After each move, `Mutate.m` swaps two values of the vector, and the change is kept only if it does not make the cost worse.

## What is in the package

The download has two folders:

- **QAP using GA**: a Genetic Algorithm (`ga.m`) with roulette wheel selection, permutation crossover and permutation mutation.
- **QAP using PSO and Firefly Algorithm**: Particle Swarm Optimization (`pso.m`) and the Firefly Algorithm (`fa.m`). Its `main.m` opens a dialog where you choose which of the two to run.

Both folders also contain `CreateModel.m` (the flow and distance data), `MyCost.m` (the cost function) and `PlotSolution.m` (a plot of the current solution).

## How to run

In the GA folder, run `main.m`. In the other folder, run `main.m` and pick PSO or FA in the dialog.

The program prints the best cost in every iteration, plots the current best assignment, and plots the best cost against the iteration at the end. To solve your own problem, change the weights and the coordinates in `CreateModel.m`. The code calls `randsample` and `unifrnd`, so it probably needs the Statistics and Machine Learning Toolbox.

## Parameters in the code

| Parameter | Meaning | GA | PSO | FA |
| --- | --- | ---: | ---: | ---: |
| `MaxIt` | Number of iterations | 1000 | 1000 | 1000 |
| `nPop` | Population size | 40 | 80 | 20 |
| `pc` | Crossover percentage | 0.4 | | |
| `pm` | Mutation percentage | 0.8 | | |
| `beta` | Selection pressure | 5 | | |
| `w`, `wdamp` | Inertia weight and its damping ratio | | 1, 0.99 | |
| `c1`, `c2` | Personal and global learning coefficients | | 1.5, 2.0 | |
| `gamma` | Light absorption coefficient | | | 1 |
| `beta0` | Base attraction | | | 2 |
| `alpha`, `alpha_damp` | Mutation coefficient and its damping ratio | | | 0.2, 0.98 |
| Extra swap mutations | Per particle or firefly in each iteration | | 1 (3 on the global best) | 2 |

## Check the result

Check that the decoded assignment uses 20 distinct sites from the 40 available locations. Recompute the weighted distance cost from that assignment rather than interpreting a convergence curve alone. The large positive and negative pair weights express objective preferences, not hard separation constraints. When comparing GA, PSO, and FA, use the same model and evaluation budget, and repeat runs because their searches are random.

## Applications

The QAP is a model for many layout and assignment tasks:

- Facility layout: placing departments in a factory or a hospital so that busy pairs are close.
- Keyboard design: placing letters on keys so that frequent letter pairs are easy to type.
- Electronics: placing components on a board to keep the wiring short.
- Campus and building planning, where the flow is the number of people who move between units.

## Related posts

- [Genetic Algorithms in MATLAB](https://yarpiz.com/genetic-algorithms-ypea101)
- [Particle Swarm Optimization in MATLAB](https://yarpiz.com/particle-swarm-optimization-ypea102)
- [Firefly Algorithm in MATLAB](https://yarpiz.com/firefly-algorithm-ypea112)
- [Facility Layout Design using PSO](https://yarpiz.com/layout-design-ypap109), a related layout problem with blocks of different sizes.

## How to cite

Mostapha Kalami Heris, Quadratic Assignment Problem (QAP) Using GA, PSO and FA in MATLAB (YPAP104), Yarpiz, 2015. https://yarpiz.com/quadratic-assignment-problem-ypap104