Speeding Up the NSGA-II via Dynamic Population Sizes

This paper introduces a dynamic NSGA-II variant that adaptively increases its population size, achieving significantly faster theoretical runtimes on benchmark problems compared to the static version and demonstrating that a concurrent-run strategy can further create a parameter-less algorithm that outperforms the static NSGA-II by a factor of $\tilde\Omega(n)$.

The Gist

Imagine you are trying to find the perfect balance between two conflicting goals, like trying to build a car that is both the fastest and the most fuel-efficient. In the real world, you can't usually have both at the absolute maximum; improving one often hurts the other. Instead of finding one "best" car, you want to find a whole menu of perfect trade-offs (e.g., "Super Fast but Gas Guzzler," "Balanced," "Slow but Super Efficient"). This menu is called the Pareto Front.

To find this menu, computer scientists use a tool called an Evolutionary Algorithm. Think of this algorithm as a digital breeding program. It starts with a population of random car designs, breeds them, mutates them, and keeps the best ones to create the next generation.

The Problem: The "Too Many, Too Soon" Dilemma

The classic version of this tool, called NSGA-II, faces a tricky problem:

1. The Population Size: To find all the different trade-offs on the menu, you need a large group (population) of candidates. If your group is too small, you might miss some options.
2. The Speed: However, checking every single car in a huge group takes a long time. If you start with a massive group, the algorithm is slow right from the beginning.

It's like trying to find the best 100 recipes for a dinner party. If you start by cooking 10,000 dishes at once, you'll burn out before you even finish the first course. But if you only cook 5 dishes, you might miss the perfect dessert.

The Solution: The "Dynamic" Approach

The authors of this paper propose a smarter way to run this algorithm, which they call Dynamic NSGA-II.

Instead of picking a fixed group size at the start and sticking with it, they suggest starting small and growing.

• The Analogy: Imagine you are a detective trying to solve a mystery.
  • Old Way (Static NSGA-II): You hire a massive team of 1,000 detectives immediately. You pay all of them to work on the case from day one. It's expensive and slow because you have to manage everyone, even if the clues are simple at first.
  • New Way (Dynamic NSGA-II): You start with just 4 detectives. They work for a while. If they haven't solved the mystery yet, you double the team (to 8). They work for a while. If still not solved, you double again (to 16). You keep doubling the team size until you have enough people to cover all the clues, but you never pay for a huge team until you absolutely need them.

How They Tested It

The researchers tested this "growing team" strategy on two specific puzzle types (benchmarks):

1. The "OneMinOneMax" Puzzle: This is like trying to find every possible combination of red and blue marbles.

   • Result: The dynamic version was much faster (mathematically speaking, it was $O(n \log^2 n)$) compared to the old static version ($O(n^2 \log n)$). It found the full menu of trade-offs significantly quicker.

2. The "Jump" Puzzle: This is a harder puzzle where the solution is hidden behind a "valley" of bad options. You have to make a big leap to get to the good solutions.

   • Result: Again, the dynamic version was faster ($O(nk \log^2 n)$) than the static version ($O(nk+1)$).

The "Longer Start" Upgrade

The authors noticed that the very first phase (when the team is tiny) is crucial for finding the "extreme" solutions (the fastest car and the most efficient car). So, they tweaked the algorithm to stay small for a longer time before doubling up.

• The Analogy: Instead of doubling the detectives every hour, they let the small team work for a long time to get the basics right, then start doubling. This turned out to be even slightly faster, almost reaching the theoretical speed limit for this type of problem.

The "No-Settings" Version

One downside of the new method is that you have to tell the computer when to double the team (e.g., "Double the team after 100 hours of work"). If you pick the wrong time, it might not work as well.

To fix this, they created a "Concurrent Run" strategy:

• The Analogy: Instead of hiring one detective team and guessing when to grow them, you hire many teams at once.
  • Team A doubles every 10 minutes.
  • Team B doubles every 20 minutes.
  • Team C doubles every 40 minutes.
  • You run them all simultaneously but share the work. The first team to finish the job wins.
• The Result: This removes the need for the user to guess the timing. The algorithm becomes "parameter-less" (you don't need to tune settings), and it is still incredibly fast—only slightly slower than the perfectly tuned version, but still much faster than the old static method.

Summary of Claims

• Faster: The dynamic method finds the best trade-offs much faster than the traditional method for the problems they tested.
• Robust: It works well even if you don't pick the perfect "doubling time."
• Automatic: You can run multiple versions at once to make it so the user doesn't have to tune any settings at all.
• Scope: These results are mathematical proofs for specific computer science puzzles (OneMinOneMax and OneJumpZeroJump). The paper does not claim these results apply to real-world medical diagnoses, financial trading, or other specific industries yet; it focuses strictly on the theoretical speed of the algorithm.

Technical Summary

Technical Summary: Speeding Up the NSGA-II via Dynamic Population Sizes

Problem Statement
Multi-objective evolutionary algorithms (MOEAs), particularly the Non-dominated Sorting Genetic Algorithm II (NSGA-II), are widely used for solving multi-objective optimization problems. A central challenge in their application is the management of the population size ($N$). To effectively represent the Pareto front (the set of optimal trade-offs), the population must be sufficiently large. However, a large population slows down the algorithm because the NSGA-II evaluates $N$ solutions per iteration. This creates a design dilemma: a population that is too small fails to cover the Pareto front efficiently, while a population that is too large incurs unnecessary computational costs. Recent mathematical analyses have shown that the static NSGA-II with an optimal fixed population size has a runtime of $\Theta(n^2 \log n)$ on the OneMinMax (OMM) benchmark, which is considered suboptimal compared to theoretical lower bounds for certain classes of algorithms.

Methodology
The authors propose the Dynamic NSGA-II, a variant of the classic algorithm that addresses the population size dilemma by starting with a small initial population and increasing it over time.

• Algorithm Structure: The algorithm begins with a population size of $N=4$. It performs a fixed number of function evaluations, denoted by a user-specified parameter $\tau$, before attempting to double the population size. This doubling continues until a user-defined maximum population size, $N_{max}$, is reached. Crucially, the doubling is triggered by the number of function evaluations rather than iterations, ensuring that each "phase" of the algorithm receives a roughly equal computational budget regardless of the current population size.
• Selection Mechanism: The authors utilize a specific variant of NSGA-II that employs current crowding distance for tie-breaking. This mechanism, previously shown to improve solution distribution, iteratively removes individuals with the smallest crowding distance and recomputes distances, leading to a more equidistant spread of solutions.
• Variants:
  1. Standard Dynamic NSGA-II: Doubles the population every $\tau$ evaluations.
  2. Dynamic NSGA-II with Longer Initial Phase: Extends the duration of the initial phase (where $N=4$) to match the total computational budget of all subsequent phases combined. This allows the algorithm to spend more time in the highly efficient early stage without increasing the asymptotic runtime order.
  3. Parameter-less Strategy (Algorithm 3): To remove the need for manual tuning of $\tau$, the authors propose a concurrent-run strategy. This framework launches multiple instances of the dynamic NSGA-II with different $\tau$ values (powers of two) and dynamically allocates resources to the instance that has spent the least total computational effort so far.

Key Contributions and Results
The paper provides rigorous mathematical runtime analyses for the proposed algorithms on two standard benchmarks: OneMinMax (OMM) and OneJumpZeroJump (OJZJ$_k$).

1. OMM Benchmark:

   • The standard Dynamic NSGA-II with optimal $\tau$ achieves a runtime of $O(n \log^2 n)$ function evaluations with high probability. This is a significant improvement over the $\Theta(n^2 \log n)$ runtime of the static NSGA-II.
   • The variant with the Longer Initial Phase achieves a runtime of $O(n \log n)$. This is asymptotically optimal for a large class of unbiased black-box algorithms, matching the theoretical lower bound for finding the all-ones string.
   • The parameter-less concurrent strategy (Algorithm 3) achieves runtimes of $O(n \log^3 n)$ (standard) and $O(n \log(N_{max}) \log(n \log N_{max}))$ (longer initial phase), incurring only a logarithmic factor penalty compared to the optimally tuned versions.

2. OJZJ$_k$ Benchmark (with gap size $k$):

   • The standard Dynamic NSGA-II achieves a runtime of $O(nk \log^2 n)$, improving upon the known $\Theta(nk+1)$ runtime of the static NSGA-II.
   • The variant with the Longer Initial Phase achieves $O(nk \log n)$.
   • The parameter-less strategy yields runtimes of $O(kn^k \log^3 n)$ and $O(kn^k \log(N_{max}) \log(nk \log N_{max}))$, respectively.

3. Robustness and Parameter Independence:

   • The runtime guarantees for the dynamic variants are largely independent of the maximum population size $N_{max}$, provided $N_{max}$ is slightly larger than the size of the Pareto front (e.g., $N_{max} \ge n+4$).
   • If $\tau$ is chosen suboptimally (too small), the algorithm reverts to the performance of the static NSGA-II with population size $N_{max}$, ensuring that a poor parameter choice is not catastrophic.
   • The concurrent-run strategy effectively eliminates the need for the user to select $\tau$, creating a "parameter-less" algorithm regarding population size dynamics.

Significance and Claims
The authors claim that this work is the first to mathematically analyze a MOEA with dynamic parameters, demonstrating that the multi-objective nature of the problems allows for significant speed-ups through population growth strategies.

• Theoretical Advancement: The paper establishes that dynamic population sizing can break the $\Theta(n^2 \log n)$ barrier for NSGA-II on OMM, achieving runtimes that are nearly optimal ($O(n \log n)$) when the initial phase is extended.
• Practical Implications: By showing that a simple concurrent-run strategy can achieve near-optimal performance without manual parameter tuning, the authors suggest a path toward more robust, "parameter-less" MOEAs.
• Comparison to Archives: The authors note that while other works have proposed using archives to store solutions and allow smaller populations, their dynamic approach is theoretically preferable in certain contexts (specifically regarding bit-wise mutation without crossover) because it avoids the risk of the population becoming insufficient to generate new solutions on the Pareto front.

The paper concludes that the dynamic NSGA-II offers a provable speed-up of $\tilde{\Omega}(n)$ over the static NSGA-II and that extending the initial phase further improves performance to the theoretical limits of unbiased black-box optimization. Future work is suggested to investigate whether these advantages hold for other popular scenarios, such as the LOTZ benchmark.