Evolutionary Multi-Objective Optimization
Implementation and analysis of NSGA II algorithm on the m-LOTZ benchmark function
Abstract
Many real-world problems aim to optimize completely antagonistic functions. For instance, one might try to obtain the most number of items from a shop while spending the least amount of money. The first thing to notice is that not all possible pairs of values are comparable. Economists have developed a partial order called preference, which helps users make economic decisions in such cases, after maximizing the function associated with the problem.
The Non-Dominated Sorting Genetic Algorithm (NSGA) is a randomized algorithm that provides optima for multi-objective problems. It is not purely deterministic, but according to the results in the article by Weijie Zheng and Benjamin Doerr, it yields sufficiently good results on the benchmark m-LOTZ (Leading Ones Trailing Zeros).
The aim of this project was to implement the NSGA II algorithm and analyze the results on the m-LOTZ function. We implemented fast non-dominated sorting, crowding distance assignment, and a modified version of the crowding distance with improved time complexity O(mN log N). For m=4 and n=10, we always obtained the complete Pareto front; for n=20, we achieved 95% coverage on average.