Yarpiz

Applications

Minimum Spanning Tree using PSO, ICA and FA

Get the code
Comments

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

4 min read

Illustration for Minimum Spanning Tree using PSO, ICA and FA
On this page

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.

The problem

Given a connected graph with nn nodes and a length dijd_{ij} on each edge, a spanning tree is a set of n−1n - 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 dijd_{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⋅19/2=19020 \cdot 19 / 2 = 190 variables. Each variable is a real number in [0,1][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 AA.

The cost is

z=∑i=1n∑j=1nAij dij  +  α q,α=5∑i∑jdijz = \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.
  • qq is the disconnectivity, computed in CalcDisconnectivity.m. The code finds which pairs of nodes are joined by some path, from the powers of I+AI + A, and qq is the share of pairs that are not. A connected graph has q=0q = 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−1n-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.

Downloads

How to cite

If you use this code or tutorial in your work, articles or publications, please cite it.

Plain text
Mostapha Kalami Heris, Minimum Spanning Tree using PSO, ICA and FA (YPAP116), Yarpiz, 2015. https://yarpiz.com/minimum-spanning-tree-ypap116
BibTeX
@misc{yarpiz-ypap116,
  author = {{Mostapha Kalami Heris}},
  title = {{Minimum Spanning Tree using PSO, ICA and FA}},
  howpublished = {Yarpiz},
  year = {2015},
  note = {Code YPAP116},
  url = {https://yarpiz.com/minimum-spanning-tree-ypap116}
}

Published Updated

Comments

Sign in or create a free account to join the discussion. No password needed.