UC6 — Multi-Modal Optimization

Objectives

Understand the multi-modal optimization problem: finding all optima, not just one
Learn how SHGA combines Deterministic Crowding GA with CMA-ES
See benchmark results on Himmelblau’s function and CEC2013 suite
Understand the parallelization strategy and NAIC multi-core benefits

Repository: wp7-UC6-multimodal-optimization Tutorial: https://naicno.github.io/wp7-UC6-multimodal-optimization/ Contributors: Klaus Johannsen, Hasan Asyari Arief (NORCE Research) Reference: Johannsen, K., Goris, N., Jensen, B., & Tjiputra, J. (2022). Nordic Machine Intelligence, 02, 16–27. DOI:10.5617/nmi.9633

The Problem

Many real-world optimization problems in engineering design, molecular modeling, and scientific parameter estimation have multiple valid solutions — not just one global optimum.

Standard optimization algorithms converge to one solution and stop. Finding all optima requires strategies that balance:

Exploration — searching the full domain
Exploitation — refining promising regions

SHGA: Scalable Hybrid Genetic Algorithm

UC6 implements SHGA, which combines two complementary strategies:

        graph TD
    A[Initialize Population] --> B[Deterministic Crowding GA<br>Global exploration]
    B --> C[Nearest-Neighbor Clustering<br>Identify promising regions]
    C --> D[CMA-ES Refinement<br>Local precision per seed]
    D --> E{Found all optima?}
    E -->|No| F[Scale up population]
    F --> B
    E -->|Yes| G[Report all optima]

Component 1: Deterministic Crowding GA

Handles global exploration while keeping population diversity. Individuals are replaced only by similar ones (nearest-neighbor replacement), preventing the population from collapsing onto a single solution.

Component 2: CMA-ES Local Search

Once promising regions are identified through clustering, individual CMA-ES (Covariance Matrix Adaptation Evolution Strategy) instances refine each seed to high precision.

Outer Loop

Scales up the population and repeats, progressively discovering additional optima.

Parallelization

The inner CMA-ES loop is parallelized across available CPU cores:

Cores	Speedup
1	1x (baseline)
4	~3x
8	~3.5x
16	~3.8x

This yields 3–4x speedup on 16-core NAIC Orchestrator VMs, showing that NAIC infrastructure benefits workloads beyond deep learning.

Results

Himmelblau’s Function

SHGA reliably discovers all 4 global optima of Himmelblau’s function within 50,000 evaluations:

Optimum	Location (x, y)	f(x, y)
1	(3.0, 2.0)	0.0
2	(-2.805, 3.131)	0.0
3	(-3.779, -3.283)	0.0
4	(3.584, -1.848)	0.0

CEC2013 Benchmark Suite

Average peak ratio of 66% across the 20-function CEC2013 benchmark suite (2–20 dimensions). Peak ratio measures the fraction of known global optima found.

Key Dependencies

Package	Role
DEAP	Evolutionary algorithm framework (GA operators)
CMA-ES	Local optimization (covariance matrix adaptation)
NumPy	Numerical operations
Matplotlib	Visualization

Quick Start

git clone https://github.com/NAICNO/wp7-UC6-multimodal-optimization.git
cd wp7-UC6-multimodal-optimization
pip install -r requirements.txt
jupyter notebook demonstrator-v1.orchestrator.ipynb

The self-contained orchestrator notebook runs SHGA on CEC2013 F1–F7 benchmarks with synthetic data, demonstrating the algorithm’s ability to find multiple optima.

Keypoints

Multi-modal optimization finds all optima, not just one global optimum
SHGA combines Deterministic Crowding GA (exploration) with CMA-ES (exploitation)
Reliably discovers all 4 optima of Himmelblau’s function within 50K evaluations
66% average peak ratio on the CEC2013 20-function benchmark suite
Parallelized CMA-ES achieves 3–4x speedup on 16-core NAIC VMs
Based on prior work published in Nordic Machine Intelligence (2022)