Overview of MOEA/D (Multi-Objective Evolutionary Algorithm based on Decomposition) and examples of algorithms and implementations

Overview of MOEA/D(Multi-Objective Evolutionary Algorithm based on Decomposition)

MOEA/D (Multi-Objective Evolutionary Algorithm Based on Decomposition) is a type of evolutionary algorithm (EA) for solving multi-objective optimization problems (MOP) and was proposed by Zhang and Li in 2007.

The features of MOEA/D include the following

• Utilizes a decomposition method
  • A multi-objective optimization problem is decomposed into a set of single-objective optimization problems, each of which is optimized in parallel.
  • Each sub-problem is represented by a different weighted scalarization function (Weighted Sum, Tchebycheff, Penalty-based Boundary Intersection, etc.)
• Utilize Neighborhood-based Search (Neighborhood-based Search)
  • When seeking the optimal solution for each subproblem, information is shared with neighboring subproblems to promote evolution.
  • Unlike conventional multi-objective GAs such as NSGA-II described in “Overview of NSGA-II (Non-dominated Sorting Genetic Algorithm II), algorithm and implementation examples“, it uses a local search-like update method instead of non-dominated sorting.
• High scalability.
  • Relatively easy to apply even to high-dimensional objective functions (4 or more objectives).
  • Easier to maintain uniformity of Pareto fronts compared to NSGA-II.

The algorithm flow of MOEA/D is as follows

1. Define sub-problems: Decompose a multi-objective optimization problem into several single-objective optimization problems using weight vectors. For example, for 3-objective optimization, different weight vectors (λ1, λ2, λ3) are set and sub-problems are defined for each vector.
2. Generate initial population: randomly generate initial individuals and assign an individual to each subproblem.
3. Generate local children: For each subproblem, apply crossover and mutation using nearby solutions to generate new children.
4. Update the optimal solution for each subproblem: If the generated child is better than the existing solution, replace it. Evolution proceeds by sharing with neighboring solutions.
5. Repeat 3-4 until the termination condition is met.

Since MOEA/D is strong in high-dimensional multi-objective optimization, it is often used in combination with NSGA-II described in “Overview of NSGA-II (Non-dominated Sorting Genetic Algorithm II), Algorithm and Implementation Examples”. A comparison of MOEA/D and NSGA-II described is shown below.

MOEA/D was designed to improve the scalability of multi-objective optimization, and it will be the algorithm of interest as a method suitable for high-dimensional (multi-objective) optimization.

Implementation Example

We describe an example of a Python implementation of MOEA/D. Libraries such as PlatEMO (MATLAB) and Pymoo (Python) are often used to implement MOEA/D. In this paper, we show a simple implementation of MOEA/D that solves a two-objective (ZDT1) problem using the multi-objective optimization library pymoo.

Here, we show a simple implementation of MOEA/D that solves a two-objective (ZDT1) problem using the multi-objective optimization library pymoo.

Python Implementation of MOEA/D

import numpy as np
from pymoo.algorithms.moo.moead import MOEAD
from pymoo.factory import get_problem, get_reference_directions
from pymoo.optimize import minimize
from pymoo.core.problem import Problem
from pymoo.visualization.scatter import Scatter

# Problem to optimize (ZDT1:2 objective function)
problem = get_problem("zdt1")

# Setting the reference direction (Weight Vectors)
ref_dirs = get_reference_directions("das-dennis", 2, n_partitions=99)

# Algorithm settings for MOEA/D
algorithm = MOEAD(
    ref_dirs=ref_dirs,  # Reference direction
    n_neighbors=15,  # Number of individuals in the vicinity
    decomposition="tchebi",  # Decomposition method (Tchebycheff method)
    prob_neighbor_mating=0.7  # Neighborhood selection probability at crossover
)

# Perform optimization
res = minimize(
    problem,
    algorithm,
    termination=('n_gen', 200),  # Run up to 200 generations
    seed=1,
    verbose=True
)

# Visualization of results
plot = Scatter()
plot.add(res.F, facecolor="none", edgecolor="r")
plot.show()

Key points of the code

1. Optimize ZDT1 problem: ZDT1 (Zitzler-Deb-Thiele Function 1) is a benchmark problem with two objectives (objective functions f1 and f2), defined using pymoo’s get_problem(“zdt1”).
2. Generation of reference directions (Weight Vectors): get_reference_directions(“das-dennis”, 2, n_partitions=99) generates 99 reference vectors. This allows for a uniform Pareto front search.
3. MOEA/D settings: decomposition=“tchebi” (Tchebycheff decomposition method). n_neighbors=15 (neighborhood size), prob_neighbor_mating=0.7 (neighborhood utilization at intersection).
4. Run optimization: use minimize() and run 200 generations of evolution.
5. Visualization of the results: Draw the distribution of the optimal solution using scatter() (check the Pareto front).

Execution result: Execution of the above code yields the following Pareto front.

• Red dots are obtained non-inferior solutions (Pareto optimal solutions)
• It can be confirmed that the distribution is uniform.

Application Examples

MOEA/D (Multi-Objective Evolutionary Algorithm based on Decomposition) is used in various fields where multiple objective functions need to be optimized simultaneously. Specific applications are described below.

1. factory production scheduling optimization

• Challenge: Multiple production lines need to efficiently manufacture different products.
• Objective function:
  • Minimize production costs
  • Minimize delivery delays
  • Minimize energy consumption
• Application of MOEA/D
  • Treat each schedule as an individual (solution), evolving with each generation
  • Use decomposition approaches (e.g. Tchebycheff method) and consider trade-offs between different objectives
  • Result:
    • Discovered the optimal schedule to meet deadlines while reducing energy consumption
    • Increased overall plant efficiency

2. automotive design optimization

• Challenge: In automotive body design, it is important to achieve both weight reduction and crash safety
• Objective Function:
  • Minimize weight
  • Maximize crash safety performance (energy absorption)
  • Minimize production cost
• Application of MOEA/D
  • Evolve design parameters (material, shape, structure) with genetic algorithm
  • Explore Pareto front to find lightweight and safe design
  • Result:
    • Optimized balance between weight reduction (fuel economy) and safety
    • 10% lighter than existing design and improved crash safety

3. optimization of power distribution in smart grid

• Challenge: Need to optimally combine renewable energy (solar, wind) and conventional thermal power supply
• Objective function:
  • Minimize power supply costs
  • Minimize CO₂ emissions
  • Stable electricity supply (minimization of fluctuations)
• Application of MOEA/D
  • Optimize the output of each generating unit as a variable
  • Generate optimal supply patterns according to electricity demand in different regions
  • Result:
    • Achieved stable power supply while reducing CO₂ emissions
    • Cost reduction of 15% compared to conventional methods

4. hyperparameter optimization of image recognition models by AI

• Challenge: Optimize the hyperparameters of a convolutional neural network (CNN) in deep learning
• Objective Function:
  • Maximize recognition accuracy
  • Minimize computation time (inference speed)
  • Minimize model size (memory usage)
• Application of MOEA/D
  • Evolutionarily optimize the number of CNN filters, learning rate, and batch size
  • Search for optimal architecture while considering different trade-offs
  • Result:
    • Highly accurate recognition despite the small size of the model
    • 30% faster inference than existing methods

5. Financial Portfolio Optimization

• Challenge: Investors need to maximize returns while minimizing risk
• Objective Function:
  • Minimize risk (variance)
  • Maximize expected return
  • Portfolio diversification (balance of stocks)
• Application of MOEA/D
  • Evolutionary optimization of combinations of different asset classes (stocks, bonds, commodities)
  • Explore risk/return trade-offs using decomposition techniques
  • Result:
    • Created an optimal portfolio with stable returns while reducing risk
    • Reduced risk by 10% over existing model

reference book

This section describes reference books on MOEA/D (Multi-Objective Evolutionary Algorithm based on Decomposition).

Books for learning from the basics

1. “Multi-Objective Optimization Using Evolutionary Algorithms”

Author: Kalyanmoy Deb
Publication year: 2001
Abstract: MOEA (Multi-Objective Evolutionary Algorithms)

Learn the basics of MOEA (Multi-Objective Evolutionary Algorithms).
Presents theory and implementation examples of algorithms such as NSGA-II and MOEA/D
Required reading as a foundation for multiobjective optimization

2. “Evolutionary Algorithms for Solving Multi-Objective Problems”

Authors: Carlos A. Coello Coello, Gary B. Lamont, David A. Van Veldhuizen
Publication Year: 2007
Abstract:.

Provides a detailed description of the theory, applications, and implementation of multi-objective evolutionary computation.
Includes comparison of optimization algorithms such as MOEA/D
Also includes examples of engineering and AI applications

Papers and books on MOEA/D

3. “MOEA/D: A Multi-Objective Evolutionary Algorithm Based on Decomposition”

Author: Qingfu Zhang, Hui Li
Publication Year: 2007 (paper)
Abstract: The original paper on MOEA/D was published by Qingfu Zhang and Hui Li in 2007.

Original paper on MOEA/D
Basic concepts of MOEA/D, explanation of Tchebycheff decomposition method, and comparison experiments
A must-read paper if you want to implement MOEA/D

4. “Advances in Multi-Objective Nature Inspired Computing”

Author: Carlos A. Coello Coello, Hisao Ishibuchi and others
Publication year: 2010
Abstract: The paper

Contains the latest research in multi-objective optimization, including developments of MOEA/D.
Includes industrial applications and experimental results

A book for implementation and application

5. “Metaheuristics for Multiobjective Optimisation”

Author: Xavier Gandibleux and others
Publication year: 2004
Description: Metaheuristics (GA, PS)

Theory and implementation of metaheuristics (GA, PSO, MOEA/D, etc.)
Examples of implementations in Python and MATLAB are also presented.

6. “Multi-Objective Optimization: Techniques and Applications in Chemical Engineering”

Author: Gade Pandu Rangaiah
Publication year: 2008
Abstract: The book provides an overview of

Many examples of applications of Multi-Objective Optimization in engineering are presented.
Includes examples of MOEA/D applications in chemical engineering and energy

Useful book for implementation in Python and MATLAB

7. “Practical Genetic Algorithms”

Authors: Randy L. Haupt, Sue Ellen Haupt
Publication year: 2004
Abstract: This book covers the implementation of genetic algorithms (GAs).

Learn to implement Genetic Algorithms (GAs) in Python/MATLAB.
Can be applied to customize MOEA/D

8. “Hands-On Machine Learning for Algorithmic Trading”

Author: Stefan Jansen
Publication Year: 2018
Abstract:.

With applications of MOEA/D in financial engineering and portfolio optimization
Learn how to implement optimization algorithms in Python

Paper

Zhang, Q., & Li, H. (2007). “MOEA/D: A Multi-Objective Evolutionary Algorithm Based on Decomposition.” IEEE Transactions on Evolutionary Computation, 11(6), 712-731.
Original MOEA/D paper. It describes the details of the algorithm.

Deb, K. (2001). “Multi-Objective Optimization using Evolutionary Algorithms.” Wiley.
Comparison with NSGA-II is also possible.

Ishibuchi, H., et al. (2009). “Evolutionary many-objective optimization by NSGA-II and MOEA/D with large populations.” IEEE Congress on Evolutionary Computation (CEC).
The paper is rich in comparative experiments between MOEA/D and NSGA-II.