Source code for orion.algo.evolution_es

# -*- coding: utf-8 -*-
"""
The Evolved Transformer and large-scale evolution of image classifiers
======================================================================

Implement evolution to exploit configurations with fixed resource efficiently

"""
import copy
import importlib
import logging

import numpy as np

from orion.algo.hyperband import Hyperband, HyperbandBracket
from orion.core.utils import format_trials

logger = logging.getLogger(__name__)

REGISTRATION_ERROR = """
Bad fidelity level {fidelity}. Should be in {budgets}.
Params: {params}
"""

SPACE_ERROR = """
EvolutionES cannot be used if space does not contain a fidelity dimension.
"""

BUDGET_ERROR = """
Cannot build budgets below max_resources;
(max: {}) - (min: {}) > (num_rungs: {})
"""


def compute_budgets(
    min_resources, max_resources, reduction_factor, nums_population, pairs
):
    """Compute the budgets used for each execution of hyperband"""
    budgets_eves = []
    if reduction_factor == 1:
        for i in range(min_resources, max_resources + 1):
            if i == min_resources:
                budgets_eves.append([(nums_population, i)])
            else:
                budgets_eves[0].append((pairs * 2, i))
    else:
        num_brackets = int(np.log(max_resources) / np.log(reduction_factor))
        budgets = []
        budgets_tab = {}  # just for display consideration
        for bracket_id in range(0, num_brackets + 1):
            bracket_budgets = []
            num_trials = int(
                np.ceil(
                    int((num_brackets + 1) / (num_brackets - bracket_id + 1))
                    * (reduction_factor ** (num_brackets - bracket_id))
                )
            )

            min_resources = max_resources / reduction_factor ** (
                num_brackets - bracket_id
            )
            for i in range(0, num_brackets - bracket_id + 1):
                n_i = int(num_trials / reduction_factor ** i)
                min_i = int(min_resources * reduction_factor ** i)
                bracket_budgets.append((n_i, min_i))

                if budgets_tab.get(i):
                    budgets_tab[i].append((n_i, min_i))
                else:
                    budgets_tab[i] = [(n_i, min_i)]

            budgets.append(bracket_budgets)

        for i in range(len(budgets[0])):
            if i == 0:
                budgets_eves.append([(nums_population, budgets[0][i][1])])
            else:
                budgets_eves[0].append((pairs * 2, budgets[0][i][1]))

    return budgets_eves


[docs]class EvolutionES(Hyperband): """EvolutionES formulates hyperparameter optimization as an evolution. For more information on the algorithm, see original paper at https://arxiv.org/pdf/1703.01041.pdf and https://arxiv.org/pdf/1901.11117.pdf Real et al. "Large-Scale Evolution of Image Classifiers" So et all. "The Evolved Transformer" Parameters ---------- space: `orion.algo.space.Space` Optimisation space with priors for each dimension. seed: None, int or sequence of int Seed for the random number generator used to sample new trials. Default: ``None`` repetitions: int Number of execution of Hyperband. Default is numpy.inf which means to run Hyperband until no new trials can be suggested. nums_population: int Number of population for EvolutionES. Larger number of population often gets better performance but causes more computation. So there is a trade-off according to the search space and required budget of your problems. Default: 20 mutate: str or None, optional In the mutate part, one can define the customized mutate function with its mutate factors, such as multiply factor (times/divides by a multiply factor) and add factor (add/subtract by a multiply factor). The function must be defined by an importable string. If None, default mutate function is used: ``orion.algo.mutate_functions.default_mutate``. """ requires_type = None requires_dist = None requires_shape = "flattened" def __init__( self, space, seed=None, repetitions=np.inf, nums_population=20, mutate=None, max_retries=1000, ): super(EvolutionES, self).__init__(space, seed=seed, repetitions=repetitions) pair = nums_population // 2 mutate_ratio = 0.3 self.nums_population = nums_population self.nums_comp_pairs = pair self.max_retries = max_retries self.mutate_ratio = mutate_ratio self.mutate = mutate self.nums_mutate_gene = ( int((len(self.space.values()) - 1) * mutate_ratio) if int((len(self.space.values()) - 1) * mutate_ratio) > 0 else 1 ) self._param_names += ["nums_population", "mutate", "max_retries"] self.hurdles = [] self.population = {} for i, dim in enumerate(self.space.values()): if dim.type != "fidelity": self.population[i] = [-1] * nums_population self.performance = np.inf * np.ones(nums_population) self.budgets = compute_budgets( self.min_resources, self.max_resources, self.reduction_factor, nums_population, pair, ) self.brackets = [ BracketEVES(self, bracket_budgets, 1) for bracket_budgets in self.budgets ] self.seed_rng(seed) @property def state_dict(self): """Return a state dict that can be used to reset the state of the algorithm.""" state_dict = super(EvolutionES, self).state_dict state_dict["population"] = copy.deepcopy(self.population) state_dict["performance"] = copy.deepcopy(self.performance) state_dict["hurdles"] = copy.deepcopy(self.hurdles) return state_dict def set_state(self, state_dict): """Reset the state of the algorithm based on the given state_dict""" super(EvolutionES, self).set_state(state_dict) self.population = state_dict["population"] self.performance = state_dict["performance"] self.hurdles = state_dict["hurdles"] def _get_bracket(self, trial): """Get the bracket of a trial during observe""" return self.brackets[-1]
class BracketEVES(HyperbandBracket): """Bracket of rungs for the algorithm Hyperband. Parameters ---------- evolutiones: `evolutiones` algorithm The evolutiones algorithm object which this bracket will be part of. budgets: list of tuple Each tuple gives the (n_trials, resource_budget) for the respective rung. repetition_id: int The id of hyperband execution this bracket belongs to """ def __init__(self, evolution_es, budgets, repetition_id): super(BracketEVES, self).__init__(evolution_es, budgets, repetition_id) self.eves = self.hyperband self.search_space_without_fidelity = [] self._candidates = {} if evolution_es.mutate: self.mutate_attr = copy.deepcopy(evolution_es.mutate) else: self.mutate_attr = {} function_string = self.mutate_attr.pop( "function", "orion.algo.mutate_functions.default_mutate" ) mod_name, func_name = function_string.rsplit(".", 1) mod = importlib.import_module(mod_name) self.mutate_func = getattr(mod, func_name) for i, dim in enumerate(self.space.values()): if dim.type != "fidelity": self.search_space_without_fidelity.append(i) @property def space(self): return self.eves.space @property def state_dict(self): state_dict = super(BracketEVES, self).state_dict state_dict["candidates"] = copy.deepcopy(self._candidates) return state_dict def set_state(self, state_dict): super(BracketEVES, self).set_state(state_dict) self._candidates = state_dict["candidates"] def _get_teams(self, rung_id): """Get the red team and blue team""" if self.has_rung_filled(rung_id + 1): return [] rung = self.rungs[rung_id]["results"] population_range = ( self.eves.nums_population if len(list(rung.values())) > self.eves.nums_population else len(list(rung.values())) ) rung_trials = list(rung.values()) for trial_index in range(population_range): objective, trial = rung_trials[trial_index] self.eves.performance[trial_index] = objective for ith_dim in self.search_space_without_fidelity: self.eves.population[ith_dim][trial_index] = trial.params[ self.space[ith_dim].name ] population_index = list(range(self.eves.nums_population)) red_team = self.eves.rng.choice( population_index, self.eves.nums_comp_pairs, replace=False ) diff_list = list(set(population_index).difference(set(red_team))) blue_team = self.eves.rng.choice( diff_list, self.eves.nums_comp_pairs, replace=False ) return rung, population_range, red_team, blue_team def _mutate_population(self, red_team, blue_team, rung, population_range, fidelity): """Get the mutated population and hurdles""" winner_list = [] loser_list = [] if set(red_team) != set(blue_team): hurdles = 0 for i, _ in enumerate(red_team): winner, loser = ( (red_team, blue_team) if self.eves.performance[red_team[i]] < self.eves.performance[blue_team[i]] else (blue_team, red_team) ) winner_list.append(winner[i]) loser_list.append(loser[i]) hurdles += self.eves.performance[winner[i]] self._mutate(winner[i], loser[i]) hurdles /= len(red_team) self.eves.hurdles.append(hurdles) logger.debug("Evolution hurdles are: %s", str(self.eves.hurdles)) trials = [] trial_ids = set() nums_all_equal = [0] * population_range for i in range(population_range): point = [0] * len(self.space) while True: point = list(point) point[ list(self.space.keys()).index(self.eves.fidelity_index) ] = fidelity for j in self.search_space_without_fidelity: point[j] = self.eves.population[j][i] trial = format_trials.tuple_to_trial(point, self.space) trial = self.eves.format_trial(trial) trial_id = self.eves.get_id(trial) if trial_id in trial_ids: nums_all_equal[i] += 1 logger.debug("find equal one, continue to mutate.") self._mutate(i, i) elif self.eves.has_suggested(trial): nums_all_equal[i] += 1 logger.debug("find one already suggested, continue to mutate.") self._mutate(i, i) else: break if nums_all_equal[i] > self.eves.max_retries: logger.warning( "Can not Evolve any more. You can make an early stop." ) break if nums_all_equal[i] < self.eves.max_retries: trials.append(trial) trial_ids.add(trial_id) else: logger.debug("Dropping trial %s", trial) return trials, np.array(nums_all_equal) def get_candidates(self, rung_id): """Get a candidate for promotion""" if rung_id not in self._candidates: rung, population_range, red_team, blue_team = self._get_teams(rung_id) fidelity = self.rungs[rung_id + 1]["resources"] self._candidates[rung_id] = self._mutate_population( red_team, blue_team, rung, population_range, fidelity )[0] candidates = [] for candidate in self._candidates[rung_id]: if not self.eves.has_suggested(candidate): candidates.append(candidate) return candidates def _mutate(self, winner_id, loser_id): select_genes_key_list = self.eves.rng.choice( self.search_space_without_fidelity, self.eves.nums_mutate_gene, replace=False, ) self.copy_winner(winner_id, loser_id) kwargs = copy.deepcopy(self.mutate_attr) for i, _ in enumerate(select_genes_key_list): space = self.space.values()[select_genes_key_list[i]] old = self.eves.population[select_genes_key_list[i]][loser_id] new = self.mutate_func(space, self.eves.rng, old, **kwargs) self.eves.population[select_genes_key_list[i]][loser_id] = new self.eves.performance[loser_id] = -1 def copy_winner(self, winner_id, loser_id): """Copy winner to loser""" for key in self.search_space_without_fidelity: self.eves.population[key][loser_id] = self.eves.population[key][winner_id]