Pareto front

smac.utils.pareto_front

calculate_pareto_front

calculate_pareto_front(
    runhistory: RunHistory,
    configs: list[Configuration],
    config_instance_seed_budget_keys: list[
        list[InstanceSeedBudgetKey]
    ],
) -> list[Configuration]

Compares the passed configurations and returns only the ones on the pareto front.

PARAMETER	DESCRIPTION
runhistory	The runhistory containing the given configurations. TYPE: RunHistory
configs	The configurations from which the Pareto front should be computed. TYPE: list[Configuration]
config_instance_seed_budget_keys	The instance-seed budget keys for the configurations on the basis of which the Pareto front should be computed. TYPE: list[list[InstanceSeedBudgetKey]]

RETURNS	DESCRIPTION
pareto_front	The pareto front computed from the given configurations. TYPE: list[Configuration]

Source code in smac/utils/pareto_front.py

def calculate_pareto_front(
    runhistory: RunHistory,
    configs: list[Configuration],
    config_instance_seed_budget_keys: list[list[InstanceSeedBudgetKey]],
) -> list[Configuration]:
    """Compares the passed configurations and returns only the ones on the pareto front.

    Parameters
    ----------
    runhistory : RunHistory
        The runhistory containing the given configurations.
    configs : list[Configuration]
        The configurations from which the Pareto front should be computed.
    config_instance_seed_budget_keys: list[list[InstanceSeedBudgetKey]]
        The instance-seed budget keys for the configurations on the basis of which the Pareto front should be computed.

    Returns
    -------
    pareto_front : list[Configuration]
        The pareto front computed from the given configurations.
    """
    costs = _get_costs(runhistory, configs, config_instance_seed_budget_keys)

    # The following code is an efficient pareto front implementation
    is_efficient = np.arange(costs.shape[0])
    next_point_index = 0  # Next index in the is_efficient array to search for
    while next_point_index < len(costs):
        nondominated_point_mask = np.any(costs < costs[next_point_index], axis=1)
        nondominated_point_mask[next_point_index] = True
        is_efficient = is_efficient[nondominated_point_mask]  # Remove dominated points
        costs = costs[nondominated_point_mask]
        next_point_index = np.sum(nondominated_point_mask[:next_point_index]) + 1

    new_incumbents = [configs[i] for i in is_efficient]
    return new_incumbents

sort_by_crowding_distance

sort_by_crowding_distance(
    runhistory: RunHistory,
    configs: list[Configuration],
    config_instance_seed_budget_keys: list[
        list[InstanceSeedBudgetKey]
    ],
) -> list[Configuration]

Sorts the passed configurations by their crowding distance. Taken from github.com/anyoptimization/pymoo/blob/20abef1ade71915352217400c11ece4c2f35163e/pymoo/algorithms/nsga2.py

PARAMETER	DESCRIPTION
runhistory	The runhistory containing the given configurations. TYPE: RunHistory
configs	The configurations which should be sorted. TYPE: list[Configuration]
config_instance_seed_budget_keys	The instance-seed budget keys for the configurations which should be sorted. TYPE: list[list[InstanceSeedBudgetKey]]

RETURNS	DESCRIPTION
sorted_list	Configurations sorted by crowding distance. TYPE: list[Configuration]

Source code in smac/utils/pareto_front.py

def sort_by_crowding_distance(
    runhistory: RunHistory,
    configs: list[Configuration],
    config_instance_seed_budget_keys: list[list[InstanceSeedBudgetKey]],
) -> list[Configuration]:
    """Sorts the passed configurations by their crowding distance. Taken from
    https://github.com/anyoptimization/pymoo/blob/20abef1ade71915352217400c11ece4c2f35163e/pymoo/algorithms/nsga2.py


    Parameters
    ----------
    runhistory : RunHistory
        The runhistory containing the given configurations.
    configs : list[Configuration]
        The configurations which should be sorted.
    config_instance_seed_budget_keys: list[list[InstanceSeedBudgetKey]]
        The instance-seed budget keys for the configurations which should be sorted.

    Returns
    -------
    sorted_list : list[Configuration]
        Configurations sorted by crowding distance.
    """
    F = _get_costs(runhistory, configs, config_instance_seed_budget_keys)
    infinity = 1e14

    n_points = F.shape[0]
    n_obj = F.shape[1]

    if n_points <= 2:
        # distances = np.full(n_points, infinity)
        return configs
    else:
        # Sort each column and get index
        I = np.argsort(F, axis=0, kind="mergesort")  # noqa

        # Now really sort the whole array
        F = F[I, np.arange(n_obj)]

        # get the distance to the last element in sorted list and replace zeros with actual values
        dist = np.concatenate([F, np.full((1, n_obj), np.inf)]) - np.concatenate([np.full((1, n_obj), -np.inf), F])

        index_dist_is_zero = np.where(dist == 0)

        dist_to_last = np.copy(dist)
        for i, j in zip(*index_dist_is_zero):
            dist_to_last[i, j] = dist_to_last[i - 1, j]

        dist_to_next = np.copy(dist)
        for i, j in reversed(list(zip(*index_dist_is_zero))):
            dist_to_next[i, j] = dist_to_next[i + 1, j]

        # Normalize all the distances
        norm = np.max(F, axis=0) - np.min(F, axis=0)
        norm[norm == 0] = np.nan
        dist_to_last, dist_to_next = dist_to_last[:-1] / norm, dist_to_next[1:] / norm

        # If we divided by zero because all values in one columns are equal replace by none
        dist_to_last[np.isnan(dist_to_last)] = 0.0
        dist_to_next[np.isnan(dist_to_next)] = 0.0

        # Sum up the distance to next and last and norm by objectives - also reorder from sorted list
        J = np.argsort(I, axis=0)
        crowding = np.sum(dist_to_last[J, np.arange(n_obj)] + dist_to_next[J, np.arange(n_obj)], axis=1) / n_obj

    # Replace infinity with a large number
    crowding[np.isinf(crowding)] = infinity
    config_with_crowding = [(config, v) for config, v in zip(configs, crowding)]
    config_with_crowding = sorted(config_with_crowding, key=lambda x: x[1], reverse=True)

    return [c for c, _ in config_with_crowding]