Multi-Objective PSO in MATLAB

Multi-Objective Particle Swarm Optimization (MOPSO) was proposed by Coello Coello, Toscano Pulido and Salazar Lechuga in 2004 (paper (opens in a new tab)). It is a multi-objective version of PSO. It uses a Pareto envelope and a grid technique, similar to the Pareto Envelope-based Selection Algorithm, to handle multi-objective optimization problems.

As in PSO, the particles share information and move toward global best particles and their own personal (local) best memory. Unlike PSO, there is more than one criterion for defining the best particle. All non-dominated particles in the swarm are collected in a sub-swarm called the Repository, and every particle chooses its global best target from the Repository. For the personal best, MOPSO uses a domination-based probabilistic rule.

How MOPSO works

Each particle has a position $x_i$, a velocity $v_i$ and a personal best $p_i$. In each iteration, it picks a leader $h$ from the Repository and moves with the usual PSO rule:

The other steps are specific to the multi-objective case:

• Grid. The objective space around the Repository is divided into hypercubes (cells). Each Repository member belongs to one cell.
• Leader selection. A cell is chosen by roulette wheel selection, with a higher chance for cells that hold fewer members. A random member of that cell becomes the leader. This pulls the swarm toward less crowded parts of the front.
• Personal best. If the new position dominates $p_i$, it replaces $p_i$. If $p_i$ dominates the new position, $p_i$ stays. If neither dominates the other, one of them is kept at random.
• Repository update. New non-dominated particles join the Repository, and members that are now dominated leave it. If the Repository is too large, members are deleted from crowded cells first.
• Mutation. A particle may be mutated, with a probability that is high at the start and falls to zero at the last iteration. This helps the swarm explore early in the run.

Implementation in MATLAB

This post shares an open-source MATLAB implementation of MOPSO. The algorithm is implemented in a structured way, so if you know MATLAB, you can easily use the code in your research projects.

To run the code, open the MOPSO folder in MATLAB and run main.m, which calls the main script mopso.m. In each iteration the program prints the number of Repository members and plots the particles and the Repository in objective space. The default problem is ZDT.m, the ZDT1 test function with two objectives. MOP2.m and MOP4.m are two more test problems. The code uses unifrnd, a function of the Statistics and Machine Learning Toolbox, so it probably needs that toolbox.

The parameters are set at the top of mopso.m:

In the code, a cell that holds $N$ Repository members is chosen as the leader cell with a probability proportional to $e^{-\beta N}$, and as the cell to delete from with a probability proportional to $e^{\gamma N}$. The mutation probability in iteration $t$ is $(1 - (t-1)/(\text{MaxIt}-1))^{1/\mu}$.

Other multi-objective algorithms on Yarpiz include NSGA-II and PESA-II, which uses a similar grid.

Check the result

Treat the repository as an approximation to the Pareto front. Recompute dominance from the returned objective values and inspect both coverage and variable bounds across repeated runs. A source review flagged that domination flags in the swarm may not be refreshed on every iteration before candidates enter the repository. Check that update path before using the implementation for comparative research. This review did not execute or change the optimizer.

Mostapha Kalami Heris, Multi-Objective PSO in MATLAB (YPEA121), Yarpiz, 2015. https://yarpiz.com/mopso-ypea121

@misc{yarpiz-ypea121,
  author = {{Mostapha Kalami Heris}},
  title = {{Multi-Objective PSO in MATLAB}},
  howpublished = {Yarpiz},
  year = {2015},
  note = {Code YPEA121},
  url = {https://yarpiz.com/mopso-ypea121}
}