NSGA-II

I joked at the start of my term presentation that one thing I've learned in this class is that you can't use actual words in the name of your algorithm (hence D-BESt). NSGA-II follows form and stands for Non-dominated Sorting Genetic Algorithm. It is designed for solving multi-objective functions where the objectives are conflicting (that is, improving one may hurt the other).

Primary paper: Actually two, since NSGA-II is a refinement of the original by the same principal author. But, we'll just give the latter for now: 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.

Notes:

The idea of all multi-objective algorithms is not to find the optimal solution, but rather to identify the optimal pareto front, that is, the set of points that beat every other point on at least one objective. Put another way, the point is non-dominated: there is no point that beats it on all counts.

NSGA sorts the existing solutions into "fronts". The first front is non-dominated by all other points in the sample. The second front is non-dominated by all points not in the first front. This is repeated for as many front as you want.

The fitness is then determined by the front and by how "crowded" the point is. This is to force the solution away from a single point, since the idea is to capture the front, not an optima.

Points are then selected for the next generation based on fitness (tournament selection is most common).

Having selected parents, the rest of the generation is normal Genetic Algorithm (GA) stuff. Cross, mutate, etc. The NSGA-II algorithm does not mandate any particular strategy for these steps.

Convergence is somewhat problematic to assess since you can't measure progress against a single optimal value. Elitist strategies are employed so there can at least be an assessment of whether the best values from the previous generation are surviving in the first front of the next. If they consistently wind up in the first front, that's a clue that the front isn't moving very much.