Mastering Multi-Objective Optimization with NSGA-II: Theory and Python Example

Overview of Multi-Objective Optimization

Multi‑objective optimization (MOO) seeks to simultaneously optimize several conflicting objective functions, common in engineering, economics, and management. The goal is to find a set of Pareto‑optimal solutions rather than a single optimum.

Pareto Optimal Solutions

A solution is Pareto optimal if no other solution is better in all objectives; improvement in one objective inevitably degrades another.

NSGA‑II Algorithm Details

NSGA‑II, proposed by Deb et al. (2002), combines fast non‑dominated sorting, crowding‑distance calculation, and elitist preservation to efficiently solve MOO problems.

Algorithm Steps

Initialize population.

Evaluate fitness of individuals.

Perform non‑dominated sorting.

Calculate crowding distance.

Selection (tournament).

Crossover and mutation.

Elitist preservation.

Check termination criteria.

Population Initialization

Randomly generate an initial population of a given size; each individual represents a potential solution.

Non‑Dominated Sorting

Assign each individual a domination count and a set of solutions it dominates, then iteratively build fronts of non‑dominated solutions.

Crowding Distance Calculation

Crowding distance measures the density of solutions surrounding an individual within the same front; larger distances indicate sparser regions and are preferred.

Selection

Tournament selection prefers individuals with lower front rank; if ranks are equal, the one with larger crowding distance is chosen.

Crossover and Mutation

Standard SBX crossover and polynomial mutation generate offspring.

Elitist Preservation

Combine parent and offspring populations, re‑sort, and keep the best individuals according to rank and crowding distance.

Termination

The algorithm stops after a maximum number of generations or other stopping condition, outputting the Pareto front.

Case Study: Production Line Optimization

We minimize production cost and time while maximizing product quality using three decision variables within given bounds. The objective functions are defined as:

<code>f1 = 2*x1 + 3*x2 + 4*x3          # cost
f2 = x1**2 + x2**2 + x3**2       # time
f3 = 100 - (x1-5)**2 - (x2-5)**2 - (x3-5)**2  # quality (to be minimized)</code>

The following Python code implements NSGA‑II for this problem and visualizes the Pareto front.

<code>import numpy as np
import matplotlib.pyplot as plt

# Parameters
POP_SIZE = 100
MAX_GEN = 50
BOUNDS = [0, 10]
DIM = 3

def initialize_population(pop_size, dim, bounds):
    return np.random.uniform(bounds[0], bounds[1], (pop_size, dim))

def evaluate(individual):
    x1, x2, x3 = individual
    f1 = 2*x1 + 3*x2 + 4*x3
    f2 = x1**2 + x2**2 + x3**2
    f3 = 100 - (x1-5)**2 - (x2-5)**2 - (x3-5)**2
    return f1, f2, f3

# ... (functions for non‑dominated sorting, crowding distance, selection, crossover, mutation)

population = initialize_population(POP_SIZE, DIM, BOUNDS)
for gen in range(MAX_GEN):
    pop_values = np.array([evaluate(ind) for ind in population])
    fronts = non_dominated_sorting(pop_values)
    crowding_distances = [calculate_crowding_distance(front, pop_values) for front in fronts]
    # generate offspring
    # ...

# Plot Pareto front
final_values = np.array([evaluate(ind) for ind in population])
plt.figure(figsize=(10,7))
plt.scatter(final_values[:,0], final_values[:,1], c=final_values[:,2], cmap='viridis', marker='o')
plt.colorbar(label='Quality (f3)')
plt.xlabel('Cost (f1)')
plt.ylabel('Time (f2)')
plt.title('Pareto Front')
plt.show()</code>

The resulting plot shows each point as a Pareto‑optimal solution, illustrating trade‑offs among cost, time, and quality.