PESA-II in MATLAB

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 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

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:

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, NSGA-II, SPEA2 and MOEA/D are other multi-objective algorithms on Yarpiz, implemented in the same style.

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

@misc{yarpiz-ypea123,
  author = {{Mostapha Kalami Heris}},
  title = {{PESA-II in MATLAB}},
  howpublished = {Yarpiz},
  year = {2015},
  note = {Code YPEA123},
  url = {https://yarpiz.com/pesa2-ypea123}
}