On this page
Every day, we face decisions where goals conflict. You want to buy a laptop that is incredibly fast but also very cheap. An engineer wants to design an aircraft wing that is lightweight but also strong. Because these objectives push against each other, there is no single perfect answer. Instead, there is a set of optimal trade-offs.
In 2002, researchers Kalyanmoy Deb, A. Pratap, S. Agarwal, and T. Meyarivan from the Indian Institute of Technology (IIT) Kanpur published a paper detailing the Non-dominated Sorting Genetic Algorithm II, widely known as NSGA-II. According to the Crossref database, this paper has gathered over 44,700 citations, cementing it as a foundational text in evolutionary computation.
What is a multi-objective problem?
A multi-objective problem asks you to optimise two or more conflicting variables at the same time. If you improve one, the other gets worse.
Imagine plotting all possible laptops on a graph of Cost versus Speed. Many laptops are both expensive and slow—these are "dominated" solutions because you can easily find a laptop that is cheaper and faster. However, at the very edge of the graph, you find laptops where you cannot improve the speed without increasing the cost. This edge is called the Pareto front.
The goal of a multi-objective algorithm is not to pick one winner, but to find this entire Pareto front so a human can choose the trade-off that fits their specific needs. Much like how Donald Knuth and the analysis of algorithms gave us a mathematical way to measure computational cost, Deb’s work gave us a structured way to balance competing costs.
Where did Kalyanmoy Deb develop this?
Kalyanmoy Deb earned his B.Tech. in Mechanical Engineering from IIT Kharagpur in 1985 before completing his postgraduate studies at the University of Alabama. He then returned to India, establishing the Kanpur Genetic Algorithms Laboratory (KanGAL) at IIT Kanpur in 1997. It was here that he and his team conceptualised and coded NSGA-II.
Later, Deb moved to Michigan State University, where he served as a University Distinguished Professor and established the Computational Optimization and Innovation Laboratory. His contributions to the field have been widely recognised, earning him the Infosys Prize in Engineering and Computer Science in 2011.
How does NSGA-II use evolution?
NSGA-II borrows its logic from natural selection. It is a genetic algorithm, meaning it "breeds" solutions over multiple generations to find the fittest candidates.
Creating a population: The algorithm starts with a random set of possible solutions (like a random batch of airplane wing designs).
Non-dominated sorting: It grades every solution. If a design is completely beaten by another design on both weight and strength, it gets a low rank. The designs that are not beaten by anything else are placed in the "first front" (Rank 1).
Crowding distance: If all Rank 1 solutions bunch up in one spot (for example, they are all incredibly strong but very heavy), the algorithm calculates a "crowding distance." It deliberately favours solutions that are spread out, ensuring the final menu of trade-offs covers the whole spectrum.
Breeding the next generation: The best-ranked and most widely spaced solutions are selected to "mate" (combining their features) and "mutate" (randomly tweaking a feature).
Over generations, the population marches steadily toward the true Pareto front. This evolutionary approach is a powerful subset of machine learning, tracing a different lineage than the logic-based methods pioneered at the birth of AI by John McCarthy.
If you are trying to understand the mathematical foundations of computer science, the Fermi Concept Library contains a lesson on every concept in computing and mathematics, each with its place in the map.
Why is the Pareto front so important?
Before NSGA-II, sorting these populations was computationally heavy. The original NSGA algorithm checked every solution against every other solution in a way that took massive amounts of time as the population grew. Deb and his team reduced the computational complexity significantly, making it fast enough to use on real-world industrial problems.
Today, NSGA-II is used in everything from scheduling factory floors and routing delivery vehicles to designing water distribution networks and tuning the shapes of aerodynamic bodies. It acknowledges that real life rarely has a single right answer.
When you are studying these algorithms and hit a wall on a practice question, the Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer.
If you want to map out how different events transition into one another, you might also explore Andrey Markov and the chains that link random events.
