Skip to content

golden_section

GoldenSection

Bases: Search

A search class that performs the golden-section search on a single variable.

Golden-section search is good at finding minimal or maximal values of a unimodal function. Each search step reduces the search range by a constant factor: the inverse of golden ratio. More details are available at: https://en.wikipedia.org/wiki/Golden-section_search.

search = GoldenSection(eval_fn=lambda search_idx, n: (n - 3)**2, x_min=0, x_max=6, max_iter=10, best_mode="min")
search.fit()
print(search.get_best_parameters()) # {'param': {'n': 3, 'search_idx': 2}, 'result': {'value': 0}}

Parameters:

Name Type Description Default
eval_fn Callable[[int, Union[int, float]], float]

Function that evaluates result given parameter. One of its arguments must be 'search_idx' which will be automatically provided by the search routine. This can help with file saving / logging during the search. The eval_fn should return a dictionary, or else the return would be wrapped inside one. The other argument should be the variable to be searched over.

 required
x_min Union[int, float]

Lower limit (inclusive) of the search space.

 required
x_max Union[int, float]

Upper limit (inclusive) of the search space.

 required
max_iter int

Maximum number of iterations to run. The range at a given iteration i is 0.618**i * (x_max - x_min). Note that the eval_fn will always be evaluated twice before any iterations begin.

 required
best_mode str

Whether maximal or minimal objective is desired. Must be either 'min' or 'max'.

 required
optimize_field Optional[str]

the key corresponding to the target value when deciding the best. If None and multiple keys exist in result dictionary, the optimization is ambiguous therefore an error will be raised.

 None
integer bool

Whether the optimized variable is a discrete integer.

 True
best_mode str

Whether maximal or minimal fitness is desired. Must be either 'min' or 'max'.

 required
name str

The name of the search instance. This is used for saving and loading purposes.

 'golden_section_search'

Raises:

Type Description
AssertionError

If eval_fn, x_min, x_max, or max_iter are invalid.
Source code in fastestimator/fastestimator/search/golden_section.py 
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 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
 83
 84
 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
class GoldenSection(Search):
    """A search class that performs the golden-section search on a single variable.

    Golden-section search is good at finding minimal or maximal values of a unimodal function. Each search step reduces
    the search range by a constant factor: the inverse of golden ratio. More details are available at:
    https://en.wikipedia.org/wiki/Golden-section_search.

    ```python
    search = GoldenSection(eval_fn=lambda search_idx, n: (n - 3)**2, x_min=0, x_max=6, max_iter=10, best_mode="min")
    search.fit()
    print(search.get_best_parameters()) # {'param': {'n': 3, 'search_idx': 2}, 'result': {'value': 0}}
    ```

    Args:
        eval_fn: Function that evaluates result given parameter. One of its arguments must be 'search_idx' which will
            be automatically provided by the search routine. This can help with file saving / logging during the search.
            The eval_fn should return a dictionary, or else the return would be wrapped inside one. The other
            argument should be the variable to be searched over.
        x_min: Lower limit (inclusive) of the search space.
        x_max: Upper limit (inclusive) of the search space.
        max_iter: Maximum number of iterations to run. The range at a given iteration i is 0.618**i * (x_max - x_min).
            Note that the eval_fn will always be evaluated twice before any iterations begin.
        best_mode: Whether maximal or minimal objective is desired. Must be either 'min' or 'max'.
        optimize_field: the key corresponding to the target value when deciding the best. If None and multiple keys
            exist in result dictionary, the optimization is ambiguous therefore an error will be raised.
        integer: Whether the optimized variable is a discrete integer.
        best_mode: Whether maximal or minimal fitness is desired. Must be either 'min' or 'max'.
        name: The name of the search instance. This is used for saving and loading purposes.

    Raises:
        AssertionError: If `eval_fn`, `x_min`, `x_max`, or `max_iter` are invalid.
    """
    def __init__(self,
                 eval_fn: Callable[[int, Union[int, float]], float],
                 x_min: Union[int, float],
                 x_max: Union[int, float],
                 max_iter: int,
                 best_mode: str,
                 optimize_field: Optional[str] = None,
                 integer: bool = True,
                 name: str = "golden_section_search"):
        super().__init__(eval_fn=eval_fn, name=name)
        assert best_mode in ["max", "min"], "best_mode must be either 'max' or 'min'"
        assert x_min < x_max, "x_min must be smaller than x_max"
        if integer:
            assert isinstance(x_min, int) and isinstance(x_max, int), \
                "x_min and x_max must be integers when searching in integer mode"
        args = set(inspect.signature(eval_fn).parameters.keys()) - {'search_idx'}
        assert len(args) == 1, "the score function should only contain one argument other than 'search_idx'"
        assert max_iter > 0, "max_iter should be greater than 0"
        self.x_min = x_min
        self.x_max = x_max
        self.max_iter = max_iter
        self.best_mode = best_mode
        self.optimize_field = optimize_field
        self.integer = integer
        self.arg_name = args.pop()

    def _convert(self, x: Union[float, int]) -> Union[int, float]:
        return int(x) if self.integer else x

    def _is_better(self, a: float, b: float) -> bool:
        return a > b if self.best_mode == "max" else a < b

    def _fit(self):
        a, b, h = self.x_min, self.x_max, self.x_max - self.x_min
        invphi, invphi2 = (math.sqrt(5) - 1) / 2, (3 - math.sqrt(5)) / 2
        c, d = self._convert(a + invphi2 * h), self._convert(a + invphi * h)
        yc = self._get_value_from_result(self.evaluate(**{self.arg_name: c}))
        yd = self._get_value_from_result(self.evaluate(**{self.arg_name: d}))
        for _ in range(self.max_iter):
            if self._is_better(yc, yd):
                b, d, yd = d, c, yc
                h = invphi * h
                c = self._convert(a + invphi2 * h)
                yc = self._get_value_from_result(self.evaluate(**{self.arg_name: c}))
            else:
                a, c, yc = c, d, yd
                h = invphi * h
                d = self._convert(a + invphi * h)
                yd = self._get_value_from_result(self.evaluate(**{self.arg_name: d}))
        best_results = self.get_best_results()
        print("FastEstimator-Search: Golden Section Search Finished, best parameters: {}, best result: {}".format(
            best_results['param'], best_results['result']))

    def _get_value_from_result(self, result: Dict[str, Any]) -> Union[int, float]:
        optimize_field = self.optimize_field
        if optimize_field is None:
            optimize_field = self._infer_optimize_field(result)
        return result[optimize_field]