MOEA/D in MATLAB

Decomposition is a classic approach to multi-objective optimization. A multi-objective problem is decomposed into a family of single-objective subproblems. The decomposed objective functions can be defined in several ways, such as a weighted sum of the objectives, or the distance (norm) between the objective vector and a predefined ideal point in the objective space. However, solving each single-objective problem separately takes one full run per Pareto solution, and some of these methods, such as the weighted sum, cannot find the parts of the Pareto front that are not convex.

MOEA/D

The Multi-Objective Evolutionary Algorithm based on Decomposition (MOEA/D) is an evolutionary algorithm that decomposes a multi-objective problem into several single-objective sub-problems and solves them all together in one population. Each sub-problem keeps its own best solution found so far, which is replaced only when a new solution created in its neighborhood scores better on that sub-problem. MOEA/D was proposed by Qingfu Zhang and Hui Li in 2007 (paper (opens in a new tab)).

The problem and the Tchebycheff approach

The goal is to minimize $M$ conflicting objectives $F(x) = (f_1(x), \dots, f_M(x))$. MOEA/D creates $N$ weight vectors $\lambda^1, \dots, \lambda^N$, one for each sub-problem. With the Tchebycheff approach, sub-problem $j$ minimizes

where $z^*$ is the ideal point, the best value of each objective found so far. Different weight vectors encourage different trade-offs, although the resulting coverage depends on the front and the search.

Neighborhoods

Subproblems with nearby weight vectors are grouped so that they can share candidate solutions. So each sub-problem $j$ has a neighborhood $B(j)$: the indices of the $T$ weight vectors closest to $\lambda^j$. In each iteration, for each sub-problem $j$, the algorithm:

1. Picks two parents at random from the current solutions of the neighbors in $B(j)$.
2. Creates a child $y$ from them and evaluates $F(y)$.
3. Updates the ideal point: $z_i^* \leftarrow \min(z_i^*, f_i(y))$.
4. Replaces the solution of each neighbor $k \in B(j)$ with $y$ when $g^{te}(y \mid \lambda^k, z^*)$ is not worse than the cost of its current solution.

An external population (archive) collects the non-dominated solutions found during the run.

Implementation in MATLAB

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

The MOEA-D folder holds the main script moead.m, a one line entry point main.m, and the helper functions CreateSubProblems.m (weight vectors and neighborhoods), DecomposedCost.m (the Tchebycheff cost), Crossover.m, DetermineDomination.m, Dominates.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 MOEA-D folder in MATLAB and run main.m. In each iteration the program prints the number of Pareto solutions in the archive and plots them. At the end it prints the minimum, maximum, range, standard deviation and mean of each objective over the archive.

A few details of this code differ from the basic description above:

• The weight vectors are random. Each one is drawn uniformly in $[0, 1]^M$ and scaled to unit length. A commented line in CreateSubProblems.m shows an evenly spread alternative for two objectives.
• New solutions come from an arithmetic crossover of the two parents. There is no separate mutation step.
• The ideal point starts at zero and is then updated with every new solution.
• When the archive grows beyond its size limit, randomly chosen members are deleted.

The code uses unifrnd, randsample and pdist2, functions 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 moead.m:

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 moead.m.

Check the result

Check the archive for dominance and feasibility, then inspect whether the weight vectors cover the trade-offs you need. This implementation starts its ideal-point estimate at zero. For an objective that remains strictly positive, that entry stays at zero rather than becoming the best observed value, which changes the scalarized search. Review that initialization and objective scaling before adapting the method. Random archive deletion and crossover without mutation are also implementation choices to account for in comparisons.

Related posts

NSGA-II, NSGA-III, SPEA2 and PESA-II are other multi-objective algorithms on Yarpiz, implemented in the same style.

Mostapha Kalami Heris, MOEA/D in MATLAB (YPEA124), Yarpiz, 2015. https://yarpiz.com/moead-ypea124

@misc{yarpiz-ypea124,
  author = {{Mostapha Kalami Heris}},
  title = {{MOEA/D in MATLAB}},
  howpublished = {Yarpiz},
  year = {2015},
  note = {Code YPEA124},
  url = {https://yarpiz.com/moead-ypea124}
}