Multiobjective Evolutionary Algorithm — MOEA/D vs. NSGA-II

A from-scratch implementation of a decomposition-based multiobjective evolutionary algorithm (MOEA/D-style) benchmarked against NSGA-II on standard continuous optimization problems. The algorithm uses differential evolution crossover and Gaussian mutation, evaluated on both unconstrained (ZDT3) and constrained (CF6) benchmark functions.

---

Problem Statement

Multiobjective optimization requires finding a set of solutions that simultaneously minimize multiple conflicting objectives — the Pareto front. Two algorithmic paradigms are compared here:

• Aggregation-based EA (this work): decomposes the problem into scalar subproblems via weight vectors, updates each individual's neighborhood cooperatively.
• NSGA-II (reference): a dominance-based algorithm widely used as a community baseline.

Both algorithms are run for a fixed evaluation budget and compared on Hypervolume (quality of coverage) and Spacing (uniformity of the approximated front).

---

Benchmark Problems

Problem	Dimensions	Type	Constraints	Search Space
ZDT3	30	Unconstrained	—	[0, 1]³⁰
CF6-4D	4	Constrained	2	x₁ ∈ [0,1], xᵢ ∈ [-2,2]
CF6-16D	16	Constrained	2	x₁ ∈ [0,1], xᵢ ∈ [-2,2]

ZDT3 is a classical benchmark with a disconnected Pareto front, making diversity preservation challenging. CF6 adds two nonlinear inequality constraints, handled via a penalty method.

---

Algorithm

The aggregation EA decomposes the multiobjective problem into N scalar subproblems defined by weight vectors λ⁽¹⁾, …, λ⁽ᴺ⁾. Each generation:

1. For each individual i, select three neighbors from its neighborhood.
2. Generate a child via differential evolution crossover (DE/rand/1/bin).
3. Apply Gaussian mutation with adaptive sigma proportional to the search space width.
4. Update the neighborhood: replace any neighbor j if the new solution improves the aggregation function g(y | λ⁽ʲ⁾, z*).
5. Update the reference point z* with the best objective values seen so far.

For constrained problems (CF6), constraint violations are incorporated into the aggregation function via a penalty term.

---

Results

Each configuration was run 10 independent times. Pareto front approximations were compared visually against the ideal front and against NSGA-II populations.

Sample results for ZDT3 (P=100, G=100):

Sample results for CF6-4D (P=100, G=100):

Sample results for CF6-16D (P=100, G=100):

(Blue = ideal Pareto front, Red = this algorithm, Black = NSGA-II)

Quantitative metrics (Hypervolume and Spacing) were computed across all 10 runs using the C-based metrics tool in METRICS/.

---

Project Structure

.
├── src/
│   ├── ev_algorithm.py          # MOEA/D-style EA (main algorithm class)
│   ├── evolutionary_operators.py # DE crossover and Gaussian mutation
│   ├── problems.py              # ZDT3 and CF6 problem definitions
│   ├── metrics.py               # Hypervolume and spacing metric wrappers
│   └── metrics_data/            # Metric output files (hypervolume, spacing)
│
├── METRICS/                     # C implementation of HV and spacing metrics
│   ├── metrics.c                # Main metrics computation (C)
│   ├── hv.c / hv.h              # Hypervolume calculation
│   ├── allocate.c / dominance.c # Supporting data structures
│   ├── Makefile                 # Build the metrics binary: make
│   └── PF.dat                   # Reference Pareto front data
│
├── data/
│   ├── zdt3/                    # Pareto front plots — ZDT3
│   ├── cf6_4d/                  # Pareto front plots — CF6 (4D)
│   └── cf6_16d/                 # Pareto front plots — CF6 (16D)
│
├── notebooks/
│   └── exploration.ipynb        # Exploratory runs and visualizations
│
├── generator.py                 # Batch run script (multi-execution launcher)
├── trainer.py                   # Single-run execution helper
├── analysis.py                  # Comparative plots (Pareto fronts)
└── requirements.txt

---

Installation

git clone https://github.com/MarianodelRio/evolutionaryComputation.git
cd evolutionaryComputation
pip install -r requirements.txt

To build the C metrics binary (requires GCC):

cd METRICS && make

---

Usage

Single run:

from src.problems import ZDT3
from trainer import execute

problem = ZDT3(dimension=30)
execute(
    problem=problem,
    population_size=100,
    generations=100,
    mutation_rate=0.5,
    neighborhood_size=30,
    SIG=20,
    F=0.5,
    name_file="output_all.out",
    name_file2="output_final.out"
)

Batch runs (10 executions, multiple configurations):

python generator.py

Compute and plot metrics after runs:

from src.metrics import run_all

run_all(my_route="METRICS/resultados/zdt3/...", prof_route="METRICS/resultados_NSGAII/zdt3/...", pop_gen=(100, 100))

Interactive exploration:

jupyter notebook notebooks/exploration.ipynb

---

Key Parameters

Parameter	Description	Typical values
population_size (N)	Number of subproblems / individuals	40, 80, 100, 200
generations	Number of generations	40, 50, 100, 250
neighborhood_size	Neighbors per individual	N/10 – N/3
mutation_rate	Probability of mutating each gene	0.5
SIG	Controls Gaussian mutation width (σ = range/SIG)	20
F	DE scaling factor	0.5

---

Dependencies

• NumPy — numerical computations
• Matplotlib — result visualizations
• Pandas — data handling
• GCC — required to compile the C metrics tool

---

Author

Mariano del Río Angulo — GitHub