A novel high speed multi-objective evolutionary optimisation algorithm

Abstract Multi-objective optimisation problems (MOOPs) consider multiple objectives simultaneously. Solving these problems does not render one unique solution but instead a set of equally optimal solutions, i.e., the Pareto front. The goal of solving a MOOP is to accurately and efficiently approximate the Pareto front. The use of evolutionary optimisation algorithms is widespread in this discipline. During each iteration, parent solutions are combined and mutated to create new offspring solutions. Both populations are subsequently combined and sorted. Only the N fittest solutions of the combined set are selected as the parent solutions for the subsequent iteration. The fitness of a solution is defined by its convergence to the Pareto front and its contribution to the overall solution diversity. Widely used evolutionary algorithms, like NSGA-II (Deb et al., 2002), use non-dominated sorting to assess the convergence of solutions and the concept of crowding distance to ensure a high solution diversity. Both concepts, however, require that all N solutions of the population are compared with all other (N — 1) solutions for both aspects, and this for all M objectives. This results in a computational complexity of O(MN2). In this contribution, a novel evolutionary algorithm is presented, boasting a significantly lower computational complexity of O(N log(N)). This is achieved by subdividing the feasible space into angular sections. Solutions are scored based on their distance from the current Utopia point and the overall crowdedness of their respective section. Sorting the population based on the attributed scores allows the selection of the N fittest solutions, without having to mutually compare them.