# Minimum Spanning Tree using PSO, ICA and FA

URL: https://yarpiz.com/minimum-spanning-tree-ypap116
Author: Mostapha Kalami Heris
Published: 2015-09-22
Updated: 2026-10-30
Topics: Applications

> Study graph encoding in MATLAB with PSO, ICA, and Firefly search for a minimum spanning tree, and compare the result with an exact baseline.

This package solves the minimum spanning tree problem with three metaheuristics: Particle Swarm Optimization (PSO), the Imperialist Competitive Algorithm (ICA) and the Firefly Algorithm (FA). It is written in MATLAB.

The model uses 20 points in the plane, and the distance between each pair of points is the edge cost. A solution vector is converted to a connection matrix. The cost is the total length of the selected edges plus a penalty for a disconnected graph.

::: callout {type="note" title="A teaching example"}
The minimum spanning tree problem does not need a metaheuristic. Exact greedy algorithms, such as Kruskal's algorithm (1956) and Prim's algorithm (1957), find the optimal tree in polynomial time, without the repeated stochastic search used here. This package is a teaching example: it shows how to encode a graph problem with binary edge variables and a penalty, so that a general method such as PSO, ICA or FA can work on it. The encoding and penalty ideas can also be adapted to more constrained network design problems.
:::

## The problem

Given a connected graph with $n$ nodes and a length $d_{ij}$ on each edge, a spanning tree is a set of $n - 1$ edges that connects all nodes and has no cycle. The minimum spanning tree (MST) is the spanning tree with the smallest total length. Here the graph is complete: every pair of the 20 points can be joined, and $d_{ij}$ is their Euclidean distance.

## How the code models it

There is one decision variable for each possible edge, so the 20 points give $20 \cdot 19 / 2 = 190$ variables. Each variable is a real number in $[0, 1]$. `MyCost.m` rounds it: a value of at least 0.5 means that the edge is selected. `CreateMatrixFromVector.m` turns the 190 values into a symmetric 20 by 20 connection matrix $A$.

The cost is

$$
z = \sum_{i=1}^{n} \sum_{j=1}^{n} A_{ij} \, d_{ij} \; + \; \alpha \, q, \qquad \alpha = 5 \sum_{i}\sum_{j} d_{ij}
$$

- The first term is the length of the selected edges. The sum runs over the full symmetric matrix, so each edge is counted twice. This does not change which solution is best.
- $q$ is the disconnectivity, computed in `CalcDisconnectivity.m`. The code finds which pairs of nodes are joined by some path, from the powers of $I + A$, and $q$ is the share of pairs that are not. A connected graph has $q = 0$.

The penalty only asks for a connected graph. It does not limit the number of edges or forbid cycles. Among connected graphs with positive edge lengths, a cycle can be shortened by removing an edge while preserving connectivity. The cheapest connected graph is therefore a spanning tree. The finite penalty and the metaheuristic search still require an explicit feasibility check.

`Mutate.m` makes small changes in one of two ways, with equal probability. It either flips a random set of variables (each with probability `mu` = 0.1), or it swaps one selected edge with one unselected edge.

## Files in the download

- `main.m`: opens a dialog where you choose PSO, FA or ICA, then runs the chosen script.
- `pso.m`, `fa.m` and `ica.m`: the three algorithms.
- ICA helper files: `CreateInitialEmpires.m`, `AssimilateColonies.m`, `DoRevolution.m`, `IntraEmpireCompetition.m`, `InterEmpireCompetition.m` and `UpdateTotalCost.m`.
- `CreateModel.m`, `CreateMatrixFromVector.m`, `CalcDisconnectivity.m` and `MyCost.m`: define the problem and compute the cost.
- `Mutate.m`, `RouletteWheelSelection.m` and `PlotSolution.m`: other helpers.
- `license.txt`: license terms.

## How to run

Open the folder in MATLAB and run `main.m`. Choose PSO, FA or ICA in the dialog. The program prints the best cost in every iteration and draws the current best tree. The ICA version adds a `*` when the best solution is connected, and otherwise prints its disconnectivity. At the end, a figure shows the best cost against the iteration.

To use your own points, change `X` and `Y` in `CreateModel.m`. The code calls `randsample` and `unifrnd`, so it probably needs the Statistics and Machine Learning Toolbox.

## Parameters in the code

| Algorithm | Main parameters |
| --- | --- |
| PSO | `MaxIt` 250, `nPop` 250, `w` 0.2 (no damping), `c1` 0.7, `c2` 1.0, `mu` 0.1, 2 mutations per particle and 5 on the global best |
| FA | `MaxIt` 1000, `nPop` 25, `gamma` 1, `beta0` 2, `alpha` 0.2 with `alpha_damp` 0.98, 2 extra mutations, `mu` 0.1 |
| ICA | `MaxIt` 500, `nPop` 150, `nEmp` 10 empires, selection pressure `alpha` 1, assimilation coefficient `beta` 2, `pRevolution` 0.5, `mu` 0.1, `zeta` 0.1 |

## Check the result

Check connectivity, count the selected undirected edges, and verify that a returned tree has exactly $n-1$ edges with no cycle. Divide the symmetric edge-length sum by two when reporting its physical length. Compare the feasible result with Kruskal or Prim on the same distance matrix, which provides an exact baseline for this unconstrained problem. A low penalized score alone does not prove that the candidate is connected or minimum.

## Applications

Minimum spanning trees are used in network design (cables, pipes, roads and power lines), in clustering (single linkage clustering cuts the longest edges of an MST), in image segmentation, and as a step in approximation methods for the Traveling Salesman Problem.

## Related posts

- [Particle Swarm Optimization in MATLAB](https://yarpiz.com/particle-swarm-optimization-ypea102)
- [Imperialist Competitive Algorithm in MATLAB](https://yarpiz.com/imperialist-competitive-algorithm-ypea118)
- [Firefly Algorithm in MATLAB](https://yarpiz.com/firefly-algorithm-ypea112)

## How to cite

Mostapha Kalami Heris, Minimum Spanning Tree using PSO, ICA and FA (YPAP116), Yarpiz, 2015. https://yarpiz.com/minimum-spanning-tree-ypap116