Overview of NSGA-II (Non-dominated Sorting Genetic Algorithm II), algorithm and implementation examples

Mathematics Machine Learning Artificial Intelligence Graph Data Algorithm Programming Digital Transformation Algorithms and Data structures Navigation of this blog
Overview of NSGA-II(Non-dominated Sorting Genetic Algorithm II)

NSGA-II (Non-dominated Sorting Genetic Algorithm II) is a type of Evolutionary Algorithm (EA) for solving multi-objective optimization problems. It is designed to optimize multiple objective functions simultaneously based on the Genetic Algorithm (GA) described in “Overview of Genetic Algorithm and Examples of Application and Implementation”.

The main features of NSGA-II include the following

  • Non-dominated Sorting (Non-dominated Sorting)
    • Individuals are ranked based on Pareto optimality.
    • Individuals within the same rank have no dominance relationship with each other, and between different ranks, individuals of lower ranks are given priority.
  • Crowding Distance
    • Calculates the distance between individuals on the Pareto front in order to maintain diversity.
    • Preference is given to individuals with larger crowding distances to maintain an even distribution of solutions.
  • Elitism
    • Retains good solutions by selecting the next generation from the combined set of parents and children.
    • This improves convergence and search stability.
  • Selection, crossover and mutation
    • Selection of superior individuals based on tournament selection.
    • Apply Simulated Binary Crossover (SBX) and Polynomial Mutation to ensure diversity in the search.

Algorithm Step is as follows.

  1. Initial population generation: Randomly generate an initial population.
  2. Adaptation evaluation: Evaluate the objective function value of each individual.
  3. Non-dominant sorting and crowding distance calculation: Individuals are ranked based on a Pareto front. Within the same rank, priority is given to individuals with a higher crowding distance.
  4. Selection, crossover, and mutation: select parents by tournament selection; apply SBX crossover and mutation to generate offspring generations.
  5. Elitist generation: merge parent and offspring populations, again performing non-dominant sorting and crowding distance calculations. The top individuals are passed to the next generation.
  6. Determination of termination conditions: Repeat until the specified number of generations is reached or convergence conditions are met.

The advantages of NSGA-II include the following

  • Pareto-optimal solutions can be obtained at once (suitable for multi-objective optimization)
  • A variety of solutions can be obtained (variance due to crowding distance)
  • High computational efficiency (improved nondominated sorting yields a computational complexity of \(O(MN^2)\rightarrow O(MNlogN)\)

NSGA-II is widely used as a standard algorithm in multi-objective optimization because of its good balance and high computational efficiency.

Implementation Example

An example of a Python implementation of NSGA-II is shown. Here, we use a typical library, DEAP (Distributed Evolutionary Algorithms in Python), to create code to solve a multi-objective optimization problem.

Problem setup: NSGA-II is applied to a Schaffer function (a bi-objective optimization problem like the ZDT system).

Installation of required libraries

pip install deap numpy matplotlib

NSGA-II implementation

import random
import numpy as np
import matplotlib.pyplot as plt
from deap import base, creator, tools, algorithms

# Minimize the degree of adaptation (multi-objective optimization)
creator.create("FitnessMulti", base.Fitness, weights=(-1.0, -1.0))  # minimization
creator.create("Individual", list, fitness=creator.FitnessMulti)

# Generation of individuals
def create_individual():
    return [random.uniform(-5, 5)]  # One-dimensional variable (Schaffer function)

toolbox = base.Toolbox()
toolbox.register("individual", tools.initIterate, creator.Individual, create_individual)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

# Objective function (Schaffer function)
def schaffer(individual):
    x = individual[0]
    f1 = x**2  # first objective function
    f2 = (x - 2) ** 2  # second objective function
    return f1, f2

toolbox.register("evaluate", schaffer)
toolbox.register("mate", tools.cxSimulatedBinaryBounded, low=-5, up=5, eta=20.0)
toolbox.register("mutate", tools.mutPolynomialBounded, low=-5, up=5, eta=20.0, indpb=0.1)
toolbox.register("select", tools.selNSGA2)

# Parameter Setting
POP_SIZE = 100
NGEN = 50
CXPB, MUTPB = 0.7, 0.2

# initial population formation
pop = toolbox.population(n=POP_SIZE)
hof = tools.ParetoFront()

# Collection of statistical information
stats = tools.Statistics(lambda ind: ind.fitness.values)
stats.register("min", np.min, axis=0)
stats.register("max", np.max, axis=0)

# Performing Evolution
algorithms.eaMuPlusLambda(pop, toolbox, mu=POP_SIZE, lambda_=POP_SIZE, 
                          cxpb=CXPB, mutpb=MUTPB, ngen=NGEN, 
                          stats=stats, halloffame=hof, verbose=True)

# Plotting the results
f1_vals = [ind.fitness.values[0] for ind in hof]
f2_vals = [ind.fitness.values[1] for ind in hof]

plt.scatter(f1_vals, f2_vals, c="red")
plt.xlabel("f1 (x^2)")
plt.ylabel("f2 ((x-2)^2)")
plt.title("Pareto Front (NSGA-II)")
plt.show()

Description

  1. Configuration of DEAP
    • creator.create(“FitnessMulti”, base.Fitness, weights=(-1.0, -1.0))
    • Define two objective functions, both of which should be minimized.
      creator.create(“Individual”, list, fitness=creator.FitnessMulti)
    • Defines the structure of an individual (list with one-dimensional genes).
  2. Objective function
    • f1(x) = x^2
    • f2(x) = (x-2)^2
    • These two functions form a Pareto front on the solution space.
  3. Evolution Strategy
    • Apply cxSimulatedBinaryBounded (SBX crossover) and mutPolynomialBounded (polynomial mutation).
    • Next generation selection by elitism using selNSGA2.
  4. Algorithm Execution
    • Evolutionary execution using eaMuPlusLambda.
    • Save Pareto optimal solution to hof (Hall of Fame).
  5. Plotting the results
    • Plot the final Pareto front to see the distribution of optimal solutions.

Execution Results

When this code is executed, the final Pareto front is plotted as a red dot, and it can be confirmed that the Pareto front is formed between x ≈ 0 and x ≈ 2 due to the properties of the Schaffer function.

Implementation Features

  • NSGA-II is a powerful method for multi-objective optimization problems and can search for Pareto fronts.
  • Using DEAP, it can be implemented in a concise manner.
  • The behavior of NSGA-II can be verified through optimization of the Schaffer function.
Application Examples

NSGA-II (Non-dominated Sorting Genetic Algorithm II) has been applied in various fields requiring multi-objective optimization. The following are some specific examples.

1. optimization of automobile design

  • Example: Performance optimization of engine design
  • Objective:
    • Improve fuel economy
    • Reduce emissions
    • Maximize engine power
  • Application
    • Engine design parameters (compression ratio, intake valve timing, fuel injection amount, etc.) are adjusted using a genetic algorithm.
    • NSGA-II is used to search for the Pareto-optimal solution to find the optimal design that balances fuel consumption and emissions.
  • Effectiveness:
    • Improved fuel economy while reducing CO₂ emissions.
    • Reduced design time compared to conventional trial-and-error.

2. hyper-parameter optimization in machine learning

  • Example: Neural network optimization
  • Objective:
    • Maximize accuracy
    • Minimize computational cost (reduce learning time)
  • Application:
    • Simultaneously optimize hyperparameters such as learning rate, batch size, and number of layers using NSGA-II.
    • Consider the trade-off between improving accuracy and reducing computation time.
  • Effectiveness:
    • Highly accurate models can be built efficiently.
    • Search for optimal network structure while saving resources.

3. robotics

  • Example: Robot path planning
  • Objective:
    • Reduce travel time
    • Improve safety in avoiding obstacles
    • Minimize energy consumption
  • Application:
    • NSGA-II is used by a robot to search for the optimal route to its destination,
    • taking into account travel distance, safety, and battery consumption.
  • Effectiveness:
    • Determination of energy-saving and optimal travel routes.
    • Applicable to route optimization for autonomous vehicles and drones.

4. financial engineering

  • Example: Portfolio Optimization
  • Objective:
    • Maximize returns while minimizing risk
  • Application:
    • Optimize asset allocation of stocks, bonds, virtual currencies, etc., while considering risk/return tradeoffs.
    • NSGA-II was used to obtain Pareto fronts for different risk tolerances.
  • Effectiveness:
    • Capable of proposing optimal portfolios according to investors’ risk preferences.
    • Supports more flexible decision-making than conventional single-index-based optimization.

5. bioinformatics

  • Example: Gene expression data analysis
  • Objective:
    • Identification of disease-related genes
    • Elucidate interactions between genes
  • Application:
    • Search for a set of genes associated with a disease using microarray data and RNA-Seq data.
    • A model is constructed with NSGA-II, considering the balance between “classification accuracy” and “small number of features”.
  • Effectiveness:
    • Contributed to biomarker discovery and applied to cancer research and drug discovery.

6. smart grid optimization

  • Example: Electricity distribution of renewable energy
  • Objective:
    • Reduction of electricity costs
    • Reduction of greenhouse gas emissions
    • Stabilize power supply
  • Application:
    • NSGA-II optimizes power distribution while taking into account output fluctuations of solar and wind power generation.
    • The recharge/discharge schedule of storage batteries is also optimized at the same time.
  • Effectiveness:
    • Realization of sustainable energy management.
    • Reduced costs while maintaining supply stability.

7. transportation and logistics optimization

  • Example: Delivery route optimization
  • Objective:
    • Reduce delivery costs
    • Shorten delivery time
    • Reduction of CO₂ emissions
  • Application:
    • Optimization of multiple truck routes in a logistics network, taking into account the trade-off between fuel consumption, distance, and time.
  • Effectiveness:
    • Both CO₂ reduction and cost reduction.
    • Also applicable to drone delivery.

NSGA-II has been used in various fields where multi-objective optimization is required, with particularly significant results in automotive design, machine learning, robotics, financial engineering, bioinformatics, smart grid, and logistics. NSGA-II is a very effective approach to the problem of “seeking optimal solutions while balancing different indices.

reference book (work)

This section describes reference books on NSGA-II (Non-dominated Sorting Genetic Algorithm II).

1. basic theory and understanding of genetic algorithms

Deb, K. (2001). “Multi-Objective Optimization using Evolutionary Algorithms,” Wiley.
Basic book by Kalyanmoy Deb, the developer of NSGA-II. It details the theory of multi-objective optimization and evolutionary algorithms.

Goldberg, D. E. (1989). “Genetic Algorithms in Search, Optimization and Machine Learning. “Addison-Wesley.
A classic book suitable for learning the basics of genetic algorithms (GAs).

2. NSGA-II and Applications in Multi-objective Optimization.

Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE Transactions on Evolutionary Computation, 6(2), 182-197.
The original NSGA-II paper. It contains a detailed description of the algorithm and the computational flow.

Coello Coello, C. A., Lamont, G. B., & Veldhuizen, D. A. (2007). “Evolutionary Algorithms for Solving Multi-Objective Problems,” Springer.
Extensive coverage of evolutionary algorithms for multi-objective optimization, including NSGA-II.

Konak, A., Coit, D. W., & Smith, A. E. (2006). “Multi-objective optimization using genetic algorithms: A tutorial,” Reliability Engineering & System Safety, 91(9), 992-1007.
Explains real-world applications and the theory of multi-objective GA in an easy-to-understand manner.

3. use of NSGA-II by application field

Zitzler, E., Deb, K., & Thiele, L. (2000). “Comparison of multiobjective evolutionary algorithms: empirical results,” Evolutionary Computation, 8(2), 173-195.
Paper comparing NSGA-II with other multi-objective optimization algorithms.

Deb, K., & Jain, H. (2014). “An evolutionary many-objective optimization algorithm using reference-point-based non-dominated sorting approach, part I: Solving problems with box constraints.” IEEE Transactions on Evolutionary Computation, 18(4), 577-601.
Describes an extended method for high-dimensional (4 or more objectives) multi-objective optimization.

Miettinen, K. (1999). “Nonlinear Multiobjective Optimization.” Springer.
Explains multiobjective optimization from a mathematical perspective. Also includes many examples of applications in engineering and economics. 4.

4. implementation and programming

Luke, S. (2013). “Essentials of Metaheuristics.” Lulu.
Learn to implement metaheuristics, including NSGA-II, with example Python code.

Python: DEAP (Distributed Evolutionary Algorithms in Python)
https://deap.readthedocs.io/en/master/
A library for implementing NSGA-II in Python. It has extensive official documentation and sample code.

MATLAB: Global Optimization Toolbox
Multiobjective optimization with NSGA-II in MATLAB. Easy experimental simulation.

コメント

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