Source code for surrogate.sorting.sorLogNondominated

# Copyright 2016 Quan Pan
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# See the License for the specific language governing permissions and
# limitations under the License.
# Author: Quan Pan <>
# License: Apache License, Version 2.0
# Create: 2016-12-02

from collections import defaultdict

from .sorNDHelperA import sorNDHelperA

[docs]def sorLogNondominated(individuals, k, first_front_only=False): """Sort *individuals* in pareto non-dominated fronts using the Generalized Reduced Run-Time Complexity Non-Dominated Sorting Algorithm presented by Fortin et al. (2013). :param individuals: A list of individuals to select from. :returns: A list of Pareto fronts (lists), with the first list being the true Pareto front. """ if k == 0: return [] # Separate individuals according to unique fitnesses unique_fits = defaultdict(list) for i, ind in enumerate(individuals): unique_fits[].append(ind) # Launch the sorting algorithm obj = len(individuals[0].fitness.wvalues) - 1 fitnesses = unique_fits.keys() front = dict.fromkeys(fitnesses, 0) # Sort the fitnesses lexicographically. fitnesses.sort(reverse=True) sorNDHelperA(fitnesses, obj, front) # Extract individuals from front list here nbfronts = max(front.values()) + 1 pareto_fronts = [[] for i in range(nbfronts)] for fit in fitnesses: index = front[fit] pareto_fronts[index].extend(unique_fits[fit]) # Keep only the fronts required to have k individuals. if not first_front_only: count = 0 for i, front in enumerate(pareto_fronts): count += len(front) if count >= k: return pareto_fronts[:i + 1] return pareto_fronts else: return pareto_fronts[0]