Multi-Objective Optimization with NSGA-II

Specification for multi-objective optimization in EMEP using NSGA-II, covering non-dominated sorting, crowding distance, and Pareto front management.

EMEP supports multi-objective optimization through NSGA-II (Deb et al. 2002). When multiple competing objectives matter (for example accuracy vs. efficiency), the EvolutionEngine searches for the Pareto front rather than a single best candidate. This page specifies the multi-objective sub-loop, ranking mechanics, and front management.

Multi-Objective Flow

Non-Dominated Sorting

A candidate A dominates candidate B if A is better than or equal to B on all objectives, and strictly better on at least one. The non-dominated sorting algorithm partitions the population into fronts:

• Front 1: candidates dominated by no one
• Front 2: candidates dominated only by Front 1
• Front 3: candidates dominated by Front 1 or 2
• And so on

Sorting runs in O(MN^2) time where M is the number of objectives and N is the population size. For typical EMEP configurations (M less than or equal to 5, N less than or equal to 64), this is computationally negligible compared to model evaluation.

Crowding Distance

Within each front, candidates are ranked by crowding distance. This measures the density of solutions around a candidate in objective space. Candidates with larger crowding distance are preferred.

crowding_distance[i] = sum_j((objective[j][i+1] - objective[j][i-1]) / (objective[j][max] - objective[j][min]))

Boundary candidates (best and worst per objective within the front) receive infinite crowding distance to ensure they are preserved.

Selection in Multi-Objective Mode

Parents are selected by iterating through fronts in order. Within a front, selection uses crowding distance as a tiebreaker. The binary tournament compares:

1. Front rank (lower is better)
2. Crowding distance (higher is better)

This ensures convergence toward the Pareto front while maintaining diversity along it.

Population Truncation

After offspring generation, parent and offspring populations are merged. The combined set is re-sorted by non-dominated rank. The new population is filled front by front. If the last front that fits exceeds the remaining slots, candidates from that front are selected by highest crowding distance.

Pareto Front Output

Upon termination, the EvolutionEngine returns:

• All Front 1 candidates from the final generation
• Their full fitness vectors
• Their genomes
• Their evaluation metrics from all splits (Optimization, Validation, Hidden Test)

The front is stored in the ExperimentTracker as a single artifact with references to individual candidate records.

Supported Objectives

Common objective combinations in EMEP:

Objective 1	Objective 2	Objective 3	Use Case
Accuracy	Latency	Memory	Edge deployment
Accuracy	Safety	Robustness	Production models
Perplexity	Exact Match	Safety	Research exploration
English	Persian	Code	Multilingual balance

NSGA-III Extension

NSGA-III (Deb & Jain 2014) is planned as a future alternative for problems with more than three objectives. NSGA-III replaces crowding distance with reference point-based selection. The EvolutionEngine architecture supports pluggable selectors, so NSGA-III can be added without structural changes.

Multi-objective mode is selected at experiment initialization. Switching between single and multi-objective mid-experiment is not supported. The choice affects fitness computation, selection, and output format.