Skip to content

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.

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.

Source code in smac/utils/pareto_front.py 
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
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

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.

Source code in smac/utils/pareto_front.py 
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
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]