1# Copyright (c) Facebook, Inc. and its affiliates. All Rights Reserved.
2#
3# This source code is licensed under the MIT license found in the
4# LICENSE file in the root directory of this source tree.
5
6import numpy as np
7import nevergrad.common.typing as tp
8from nevergrad.parametrization import discretization
9
10from . import utils
11
12
13class Mutator:
14    """Class defining mutations, and holding a random state used for random generation."""
15
16    def __init__(self, random_state: np.random.RandomState) -> None:
17        self.random_state = random_state
18
19    def significantly_mutate(self, v: float, arity: int):
20        """Randomly drawn a normal value, and redraw until it's different after discretization by the quantiles
21        1/arity, 2/arity, ..., (arity-1)/arity.
22        """
23        w = v
24        while discretization.threshold_discretization([w], arity) == discretization.threshold_discretization(
25            [v], arity
26        ):
27            w = self.random_state.normal(0.0, 1.0)
28        return w
29
30    def doerr_discrete_mutation(self, parent: tp.ArrayLike, arity: int = 2) -> tp.ArrayLike:
31        """Mutation as in the fast 1+1-ES, Doerr et al. The exponent is 1.5."""
32        dimension = len(parent)
33        if dimension < 5:
34            return self.discrete_mutation(parent)
35        return self.doubledoerr_discrete_mutation(parent, max_ratio=0.5, arity=arity)
36
37    def doubledoerr_discrete_mutation(
38        self, parent: tp.ArrayLike, max_ratio: float = 1.0, arity: int = 2
39    ) -> tp.ArrayLike:
40        """Doerr's recommendation above can mutate up to half variables
41        in average.
42        In our high-arity context, we might need more than that.
43
44        Parameters
45        ----------
46        parent: array-like
47            the point to mutate
48        max_ratio: float (between 0 and 1)
49            the maximum mutation ratio (careful: this is not an exact ratio)
50        """
51        assert 0 <= max_ratio <= 1
52        dimension = len(parent)
53        max_mutations = max(2, int(max_ratio * dimension))
54        p = 1.0 / np.arange(1, max_mutations) ** 1.5
55        p /= np.sum(p)
56        u = self.random_state.choice(np.arange(1, max_mutations), p=p)
57        return self.portfolio_discrete_mutation(parent, intensity=u, arity=arity)
58
59    def portfolio_discrete_mutation(
60        self, parent: tp.ArrayLike, intensity: tp.Optional[int] = None, arity: int = 2
61    ) -> tp.ArrayLike:
62        """Mutation discussed in
63        https://arxiv.org/pdf/1606.05551v1.pdf
64        We mutate a randomly drawn number of variables on average.
65        The mutation is the same for all variables - coordinatewise mutation will be different from this point of view and will make it possible
66        to do anisotropic mutations.
67        """
68        dimension = len(parent)
69        if intensity is None:
70            intensity = 1 if dimension == 1 else int(self.random_state.randint(1, dimension))
71        if dimension == 1:  # corner case.
72            return self.random_state.normal(0.0, 1.0, size=1)  # type: ignore
73        boolean_vector = np.ones(dimension, dtype=bool)
74        while all(boolean_vector) and dimension != 1:
75            boolean_vector = self.random_state.rand(dimension) > float(intensity) / dimension
76        return [s if b else self.significantly_mutate(s, arity) for (b, s) in zip(boolean_vector, parent)]
77
78    def coordinatewise_mutation(
79        self, parent: tp.ArrayLike, velocity: tp.ArrayLike, boolean_vector: tp.ArrayLike, arity: int
80    ) -> tp.ArrayLike:
81        """This is the anisotropic counterpart of the classical 1+1 mutations in discrete domains
82        with tunable intensity: it is useful for anisotropic adaptivity."""
83        dimension = len(parent)
84        boolean_vector = np.zeros(dimension, dtype=bool)
85        while not any(boolean_vector):
86            boolean_vector = self.random_state.rand(dimension) < (1.0 / dimension)
87        discrete_data = discretization.threshold_discretization(parent, arity=arity)
88        discrete_data = np.where(
89            boolean_vector,
90            discrete_data + self.random_state.choice([-1.0, 1.0], size=dimension) * velocity,
91            discrete_data,
92        )
93        return discretization.inverse_threshold_discretization(discrete_data)
94
95    def discrete_mutation(self, parent: tp.ArrayLike, arity: int = 2) -> tp.ArrayLike:
96        """This is the most classical discrete 1+1 mutation of the evolution literature."""
97        dimension = len(parent)
98        boolean_vector = np.ones(dimension, dtype=bool)
99        while all(boolean_vector):
100            boolean_vector = self.random_state.rand(dimension) > (1.0 / dimension)
101        return [s if b else self.significantly_mutate(s, arity) for (b, s) in zip(boolean_vector, parent)]
102
103    def crossover(self, parent: tp.ArrayLike, donor: tp.ArrayLike) -> tp.ArrayLike:
104        mix = [self.random_state.choice([d, p]) for (p, d) in zip(parent, donor)]
105        return self.discrete_mutation(mix)
106
107    def get_roulette(self, archive: utils.Archive[utils.MultiValue], num: tp.Optional[int] = None) -> tp.Any:
108        """Apply a roulette tournament selection."""
109        if num is None:
110            num = int(0.999 + np.sqrt(len(archive)))
111        # the following sort makes the line deterministic, and function seedable, at the cost of complexity!
112        my_keys = sorted(archive.bytesdict.keys())
113        my_keys_indices = self.random_state.choice(len(my_keys), size=min(num, len(my_keys)), replace=False)
114        my_keys = [my_keys[i] for i in my_keys_indices]
115        # best pessimistic value in a random set of keys
116        return np.frombuffer(min(my_keys, key=lambda x: archive.bytesdict[x].pessimistic_confidence_bound))
117