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

[su_button url=”https://deus-ex-machina-ism.com/?p=6642&lang=en” target=”blank”]Mathematics[/su_button] [su_button url=”https://deus-ex-machina-ism.com/?page_id=3768&lang=en” target=”blank”]Machine Learning[/su_button] [su_button url=”https://deus-ex-machina-ism.com/?page_id=3788&lang=en” target=”blank”]Artificial Intelligence[/su_button] [su_button url=”https://deus-ex-machina-ism.com/?p=20913&lang=en” target=”blank”]Graph Data Algorithm[/su_button] [su_button url=”https://deus-ex-machina-ism.com/?page_id=3798&lang=en” target=”blank”]Programming[/su_button] [su_button url=”https://deus-ex-machina-ism.com/?page_id=3812&lang=en” target=”blank”]Digital Transformation[/su_button] [su_button url=”https://deus-ex-machina-ism.com/?p=6626&lang=en” target=”blank”]Algorithms and Data structures[/su_button] [su_button url=”https://deus-ex-machina-ism.com/?page_id=12241&lang=en” target=”blank”]Navigation of this blog[/su_button]

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)
  • 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.

Feature MOEA/D NSGA-II
optimization technique Decomposition Non-dominated Sorting
local search Use of nearby individuals Utilize whole individuals
scalability Strong in higher dimensional problems (4 objectives and above) Suitable for 2 to 3 purposes
Uniformity of Pareto front Good (strong for constrained problems) Uniformity may be reduced

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.

Exit mobile version
タイトルとURLをコピーしました