# PESA-II in MATLAB

URL: https://yarpiz.com/pesa2-ypea123
Author: Mostapha Kalami Heris
Published: 2015-09-01
Updated: 2026-10-30
Topics: Multiobjective Optimization

> Implement PESA-II in MATLAB with grid-based archive selection, crossover, mutation, and a two-objective optimization example.

Pareto Envelope-based Selection Algorithm II (PESA-II) is a multi-objective evolutionary algorithm proposed by Corne, Jerram, Knowles and Oates in 2001. It improves PESA, which Corne, Knowles and Oates proposed in 2000. It uses the mechanism of a genetic algorithm together with selection based on the Pareto envelope.

## The problem

PESA-II minimizes several conflicting objectives $f_1, \dots, f_M$ at the same time. A solution $x$ dominates a solution $y$ ($x \prec y$) when $f_i(x) \le f_i(y)$ for every objective $i$ and $f_j(x) < f_j(y)$ for at least one objective $j$. The non-dominated solutions approximate the Pareto front, and the algorithm tries to find many of them, spread well along the front.

## How PESA-II works

PESA-II keeps an external archive of approximate Pareto solutions. Parents and mutants are selected from this archive, using a grid built over the distribution of the archive members in objective space. [MOPSO](https://yarpiz.com/mopso-ypea121) uses a very similar grid to choose its leaders. In effect, PESA-II is a multi-objective genetic algorithm that uses grids to make selections and create the next generation.

The grid divides the objective space around the archive into hyperboxes (cells). The main idea of PESA-II is **region-based selection**: the algorithm first chooses an occupied cell, with a preference for cells that hold few members, and then a random member of that cell. In this code, a cell with $N$ members is chosen by roulette wheel selection, with a probability proportional to

$$
P_{\text{select}} \propto \frac{1}{N^{\beta_s}}
$$

so members in sparse regions of the front are chosen more often, no matter how many members a crowded cell holds.

Each generation has these steps:

1. Add the non-dominated members of the current population to the archive, and remove the archive members that are now dominated.
2. Build the grid over the archive and find the cell of each member.
3. If the archive is larger than its size limit, delete members one at a time. In this code, the cell to delete from is chosen with a probability proportional to $N^{\beta_d}$, so crowded cells lose members first.
4. Create a new population from the archive with region-based selection, crossover and mutation.

## Implementation in MATLAB

This post shares an open-source implementation of PESA-II in MATLAB. The algorithm is implemented in a structured way. If you know MATLAB, you should find the code easy to use in your research projects.

The `PESA-II` folder holds the main script `pesa2.m`, a one line entry point `main.m`, and the helper functions `CreateGrid.m`, `FindPositionInGrid.m`, `SelectFromPopulation.m`, `TruncatePopulation.m`, `DetermineDomination.m`, `Dominates.m`, `Crossover.m`, `Mutate.m`, `RouletteWheelSelection.m` and `PlotCosts.m`. The default problem is `ZDT.m`, the ZDT1 test function with two objectives, and `MOP2.m` is a second test problem.

To run the code, open the `PESA-II` folder in MATLAB and run `main.m`. In each iteration the program prints the number of archive members and plots them in objective space. At the end it prints the minimum, maximum, range, standard deviation and mean of each objective over the archive.

The code uses `unifrnd`, a function of the Statistics and Machine Learning Toolbox, so it probably needs that toolbox.

### Parameters in the code

The parameters are set at the top of `pesa2.m`:

| Parameter | Meaning | Value |
| --- | --- | ---: |
| `nVar` | Number of decision variables | 3 |
| `VarMin`, `VarMax` | Lower and upper bounds of the variables | 0, 1 |
| `MaxIt` | Maximum number of iterations | 100 |
| `nPop` | Population size | 50 |
| `nArchive` | Archive size | 50 |
| `nGrid` | Number of grid cells per objective | 7 |
| `InflationFactor` | Grid inflation | 0.1 |
| `beta_selection` | Selection pressure $\beta_s$ | 2 |
| `beta_deletion` | Deletion pressure $\beta_d$ | 1 |
| `pCrossover` | Share of the new population created by crossover | 0.5 |
| `crossover_params.gamma` | Range extension of the arithmetic crossover | 0.15 |
| `mutation_params.h` | Gaussian mutation step, as a share of the variable range | 0.3 |

The grid adds one open cell below and one above the inflated range of each objective, so each objective has `nGrid + 2` cells. To solve your own problem, write a cost function that takes a column vector and returns a column vector of objective values, and set `CostFunction`, `nVar`, `VarMin` and `VarMax` in `pesa2.m`.

## Check the result

Inspect the archive in objective space and recompute dominance from its stored objective vectors. A dense-looking plot or a full archive is not proof of convergence to the true front. Grid resolution changes how crowding is measured, so compare both spread and proximity across repeated runs. When adapting the problem, check the column-vector input and objective-output shapes as well as the variable bounds.

## Related posts

[Multi-Objective PSO](https://yarpiz.com/mopso-ypea121), [NSGA-II](https://yarpiz.com/nsga2-ypea120), [SPEA2](https://yarpiz.com/spea2-ypea122) and [MOEA/D](https://yarpiz.com/moead-ypea124) are other multi-objective algorithms on Yarpiz, implemented in the same style.

## How to cite

Mostapha Kalami Heris, PESA-II in MATLAB (YPEA123), Yarpiz, 2015. https://yarpiz.com/pesa2-ypea123