Repository: optuna/optuna
Pull request: Add a sampler class based on grid search.
Resolves #656

Problem statement:
Feature request: Simple brute force of parameter grid
Hola! 

As I understand from the docs, there is no any methods for trial that simply iteratively do through parameter grid.
The closest one is `suggest_discrete_uniform(name, low, high, q)`, but it samples values from the distribution.

What I need: simple brute force of such grids.
For example, for grid `(low=1, high=5, q=1)` it produces 5 trials with parameter values of `[1, 2, 3, 4, 5]` (exclusive or inclusive end). Or the same behaviour with `suggest_categorical(name, [1, 2, 3, 4, 5])`.

Details:
Why I need this: for heavy models I want to see the dependancy of target metrics on simple parameters which behaviour I can predict. For example, if `param=0` metrics will be low and if `param=1000` metrics should be high and I run study for 3-4 values of `param` and see that whether it's true or not. It is also useful when you don't know even the rough the boundaries of given parameter.

So the main reason is just to give Optuna predefined grid, run trials on its values and save results. No sampling, no pruning, just brute force controlled by user. 

Why `suggest_discrete_uniform` is not good for this: it _samples_ values, so for `(low=1, high=5, q=1)` I can have `[1, 2, 2, 5, 4]` (in general case not complete and with duplicates).

What I do now: several runs of mentioned `suggest_discrete_uniform` with proper boundaries (for value of 5 it will be `suggest_discrete_uniform(low=5, high=5, q=1)`, and so on for each value I need). Of course, I can just do this by myself but I don't want write another messy optimiser along with Optuna :)

One of the problems (I can see as a user) for this feature is that `n_trials` should be compatible with number of values in the resulting grid. 

If you think it's bad/not useful feature, please let me know before deleting the issue :)


Thanks!

Hints from issue discussion:
Hi @roseaysina ,

Thanks for your feature request!

We’ve got similar requests even from other users and been planning to implement `GridSearchSampler`, whose interface will be something like: 

```python
import optuna

def objective(trial):
    x = trial.suggest_uniform('x', -100, 100)
    y = trial.suggest_int('y', -100, 100)
    return x ** 2 + y ** 2

grid = {
    'x': [-50, 0, 50],
    'y': [-99, 0, 99]
}
study = optuna.create_study(sampler=GridSearchSampler(grid))
study.optimize(objective)
```
Hi @g-votte,

Thanks for reply! I am glad that there are another similar requests) 

The code snippet looks great. The only question is that for several parameters is it going to be cartesian product of corresponding grids (like all combinations)?

Commit message: Add the experimental decorator to GridSampler.

Patch to review:
diff --git a/docs/source/reference/samplers.rst b/docs/source/reference/samplers.rst
index d608b8d97f0..0b3ea83ff85 100644
--- a/docs/source/reference/samplers.rst
+++ b/docs/source/reference/samplers.rst
@@ -6,6 +6,10 @@ Samplers
 .. autoclass:: BaseSampler
     :members:
 
+.. autoclass:: GridSampler
+    :members:
+    :exclude-members: infer_relative_search_space, sample_relative, sample_independent
+
 .. autoclass:: RandomSampler
     :members:
     :exclude-members: infer_relative_search_space, sample_relative, sample_independent
diff --git a/optuna/samplers/__init__.py b/optuna/samplers/__init__.py
index d47cc4b349d..4f2e03ecd5f 100644
--- a/optuna/samplers/__init__.py
+++ b/optuna/samplers/__init__.py
@@ -1,5 +1,6 @@
 import optuna
 from optuna.samplers.base import BaseSampler  # NOQA
+from optuna.samplers.grid import GridSampler  # NOQA
 from optuna.samplers.random import RandomSampler  # NOQA
 from optuna.samplers.tpe import TPESampler  # NOQA
 
diff --git a/optuna/samplers/grid.py b/optuna/samplers/grid.py
new file mode 100644
index 00000000000..2fe22c87060
--- /dev/null
+++ b/optuna/samplers/grid.py
@@ -0,0 +1,177 @@
+import collections
+import itertools
+import random
+
+from optuna._experimental import experimental
+from optuna.samplers.base import BaseSampler
+from optuna import type_checking
+
+if type_checking.TYPE_CHECKING:
+    from typing import Any  # NOQA
+    from typing import Dict  # NOQA
+    from typing import List  # NOQA
+    from typing import Union
+
+    from optuna.distributions import BaseDistribution  # NOQA
+    from optuna.structs import FrozenTrial  # NOQA
+    from optuna.study import Study  # NOQA
+
+    GridValueType = Union[str, float, int, bool, None]
+
+
+@experimental('1.2.0')
+class GridSampler(BaseSampler):
+    """Sampler using grid search.
+
+    With :class:`~optuna.samplers.GridSampler`, the trials suggest all combinations of parameters
+    in the given search space during the study.
+
+    Example:
+
+        .. testcode::
+
+            import optuna
+
+            def objective(trial):
+                x = trial.suggest_uniform('x', -100, 100)
+                y = trial.suggest_int('y', -100, 100)
+                return x ** 2 + y ** 2
+
+            search_space = {
+                'x': [-50, 0, 50],
+                'y': [-99, 0, 99]
+            }
+            study = optuna.create_study(sampler=optuna.samplers.GridSampler(search_space))
+            study.optimize(objective, n_trials=3*3)
+
+    Note:
+
+        :class:`~optuna.samplers.GridSampler` does not take care of a parameter's quantization
+        specified by discrete suggest methods but just samples one of values specified in the
+        search space. E.g., in the following code snippet, either of ``-0.5`` or ``0.5`` is
+        sampled as ``x`` instead of an integer point.
+
+        .. testcode::
+
+            import optuna
+
+            def objective(trial):
+                # The following suggest method specifies integer points between -5 and 5.
+                x = trial.suggest_discrete_uniform('x', -5, 5, 1)
+                return x ** 2
+
+            # Non-int points are specified in the grid.
+            search_space = {'x': [-0.5, 0.5]}
+            study = optuna.create_study(sampler=optuna.samplers.GridSampler(search_space))
+            study.optimize(objective, n_trials=2)
+
+    Args:
+        search_space:
+            A dictionary whose key and value are a parameter name and the corresponding candidates
+            of values, respectively.
+    """
+
+    def __init__(self, search_space):
+        # type: (Dict[str, List[GridValueType]]) -> None
+
+        for param_name, param_values in search_space.items():
+            for value in param_values:
+                self._check_value(param_name, value)
+
+        self._search_space = collections.OrderedDict()
+        for param_name, param_values in sorted(search_space.items(), key=lambda x: x[0]):
+            self._search_space[param_name] = sorted(param_values)
+
+        self._all_grids = list(itertools.product(*self._search_space.values()))
+        self._param_names = sorted(search_space.keys())
+        self._n_min_trials = len(self._all_grids)
+
+    def infer_relative_search_space(self, study, trial):
+        # type: (Study, FrozenTrial) -> Dict[str, BaseDistribution]
+
+        return {}
+
+    def sample_relative(self, study, trial, search_space):
+        # type: (Study, FrozenTrial, Dict[str, BaseDistribution]) -> Dict[str, Any]
+
+        # Instead of returning param values, GridSampler puts the target grid id as a system attr,
+        # and the values are returned from `sample_independent`. This is because the distribution
+        # object is hard to get at the beginning of trial, while we need the access to the object
+        # to validate the sampled value.
+
+        unvisited_grids = self._get_unvisited_grid_ids(study)
+
+        if len(unvisited_grids) == 0:
+            raise ValueError('All grids have been evaluated. If you want to avoid this error, '
+                             'please make sure that unnecessary trials do not run during '
+                             'optimization by properly setting `n_trials` in `study.optimize`.')
+
+        # In distributed optimization, multiple workers may simultaneously pick up the same grid.
+        # To make the conflict less frequent, the grid is chosen randomly.
+        grid_id = random.choice(unvisited_grids)
+
+        study._storage.set_trial_system_attr(trial._trial_id, 'search_space', self._search_space)
+        study._storage.set_trial_system_attr(trial._trial_id, 'grid_id', grid_id)
+
+        return {}
+
+    def sample_independent(self, study, trial, param_name, param_distribution):
+        # type: (Study, FrozenTrial, str, BaseDistribution) -> Any
+
+        if param_name not in self._search_space:
+            message = 'The parameter name, {}, is not found in the given grid.'.format(param_name)
+            raise ValueError(message)
+
+        grid_id = trial.system_attrs['grid_id']
+        param_value = self._all_grids[grid_id][self._param_names.index(param_name)]
+        contains = param_distribution._contains(param_distribution.to_internal_repr(param_value))
+        if not contains:
+            raise ValueError('The value `{}` is out of range of the parameter `{}`. Please make '
+                             'sure the search space of the `GridSampler` only contains values '
+                             'consistent with the distribution specified in the objective '
+                             'function. The distribution is: `{}`.'
+                             .format(param_value, param_name, param_distribution))
+
+        return param_value
+
+    @staticmethod
+    def _check_value(param_name, param_value):
+        # type: (str, Any) -> None
+
+        if param_value is None or isinstance(param_value, (str, int, float, bool)):
+            return
+
+        raise ValueError('{} contains a value with the type of {}, which is not supported by '
+                         '`GridSampler`. Please make sure a value is `str`, `int`, `float`, `bool`'
+                         ' or `None`.'.format(param_name, type(param_value)))
+
+    def _get_unvisited_grid_ids(self, study):
+        # type: (Study) -> List[int]
+
+        # List up all finished trials in the same search space.
+        trials = study.trials
+        trials = [t for t in trials if t.state.is_finished()]
+        trials = [t for t in trials if 'grid_id' in t.system_attrs]
+        trials = [t for t in trials if self._same_search_space(t.system_attrs['search_space'])]
+
+        # List up unvisited trials based on already finished ones.
+        visited_grids = [t.system_attrs['grid_id'] for t in trials]
+        unvisited_grids = set(range(self._n_min_trials)) - set(visited_grids)
+
+        return list(unvisited_grids)
+
+    def _same_search_space(self, search_space):
+        # type: (Dict[str, List[GridValueType]]) -> bool
+
+        if set(search_space.keys()) != set(self._search_space.keys()):
+            return False
+
+        for param_name in search_space.keys():
+            if len(search_space[param_name]) != len(self._search_space[param_name]):
+                return False
+
+            for i, param_value in enumerate(sorted(search_space[param_name])):
+                if param_value != self._search_space[param_name][i]:
+                    return False
+
+        return True
diff --git a/tests/samplers_tests/test_grid.py b/tests/samplers_tests/test_grid.py
new file mode 100644
index 00000000000..69062399a28
--- /dev/null
+++ b/tests/samplers_tests/test_grid.py
@@ -0,0 +1,172 @@
+from collections import OrderedDict
+import itertools
+import numpy as np
+import pytest
+
+import optuna
+from optuna import samplers
+
+if optuna.type_checking.TYPE_CHECKING:
+    from collections import ValuesView  # NOQA
+    from typing import Dict  # NOQA
+    from typing import List  # NOQA
+    from typing import Union  # NOQA
+
+    from optuna.samplers.grid import GridValueType  # NOQA
+    from optuna.trial import Trial  # NOQA
+
+
+def _n_grids(search_space):
+    # type: (Dict[str, List[Union[str, float, None]]]) -> int
+
+    return int(np.prod([len(v) for v in search_space.values()]))
+
+
+def test_grid_sampler_experimental_warning():
+    # type: () -> None
+
+    with pytest.warns(optuna.exceptions.ExperimentalWarning):
+        optuna.samplers.GridSampler({'some_param': [0, 1]})
+
+
+def test_study_optimize_with_single_search_space():
+    # type: () -> None
+
+    def objective(trial):
+        # type: (Trial) -> float
+
+        a = trial.suggest_int('a', 0, 100)
+        b = trial.suggest_uniform('b', -0.1, 0.1)
+        c = trial.suggest_categorical('c', ('x', 'y'))
+        d = trial.suggest_discrete_uniform('d', -5, 5, 1)
+        e = trial.suggest_loguniform('e', 0.0001, 1)
+
+        if c == 'x':
+            return a * d
+        else:
+            return b * e
+
+    # Test that all combinations of the grid is sampled.
+    search_space = {
+        'b': np.arange(-0.1, 0.1, 0.05),
+        'c': ['x', 'y'],
+        'd': [-0.5, 0.5],
+        'e': [0.1],
+        'a': list(range(0, 100, 20)),
+    }
+    n_grids = _n_grids(search_space)
+    study = optuna.create_study(sampler=samplers.GridSampler(search_space))
+    study.optimize(objective, n_trials=n_grids)
+
+    def sorted_values(d):
+        # type: (Dict[str, List[GridValueType]]) -> ValuesView[List[GridValueType]]
+
+        return OrderedDict(sorted(d.items())).values()
+
+    all_grids = itertools.product(*sorted_values(search_space))
+    all_suggested_values = [tuple([p for p in sorted_values(t.params)]) for t in study.trials]
+    assert set(all_grids) == set(all_suggested_values)
+
+    ids = sorted([t.system_attrs['grid_id'] for t in study.trials])
+    assert ids == list(range(n_grids))
+
+    # Test that an optimization fails if the number of trials is more than that of all grids.
+    with pytest.raises(ValueError):
+        study.optimize(objective, n_trials=1)
+
+    # Test a non-existing parameter name in the grid.
+    search_space = {'a': list(range(0, 100, 20))}
+    study = optuna.create_study(sampler=samplers.GridSampler(search_space))
+    with pytest.raises(ValueError):
+        study.optimize(objective)
+
+    # Test a value with out of range.
+    search_space = {
+        'a': [110],  # 110 is out of range specified by the suggest method.
+        'b': [0],
+        'c': ['x'],
+        'd': [0],
+        'e': [0.1]
+    }
+    study = optuna.create_study(sampler=samplers.GridSampler(search_space))
+    with pytest.raises(ValueError):
+        study.optimize(objective)
+
+
+def test_study_optimize_with_multiple_search_spaces():
+    # type: () -> None
+
+    def objective(trial):
+        # type: (Trial) -> float
+
+        a = trial.suggest_int('a', 0, 100)
+        b = trial.suggest_uniform('b', -100, 100)
+
+        return a * b
+
+    # Run 3 trials with a search space.
+    search_space_0 = {
+        'a': [0, 50],
+        'b': [-50, 0, 50]
+    }  # type: Dict[str, List[GridValueType]]
+    sampler_0 = samplers.GridSampler(search_space_0)
+    study = optuna.create_study(sampler=sampler_0)
+    study.optimize(objective, n_trials=3)
+
+    assert len(study.trials) == 3
+    for t in study.trials:
+        sampler_0._same_search_space(t.system_attrs['search_space'])
+
+    # Run 2 trials with another space.
+    search_space_1 = {'a': [0, 25], 'b': [-50]}  # type: Dict[str, List[GridValueType]]
+    sampler_1 = samplers.GridSampler(search_space_1)
+    study.sampler = sampler_1
+    study.optimize(objective, n_trials=2)
+
+    assert not sampler_0._same_search_space(sampler_1._search_space)
+    assert len(study.trials) == 5
+    for t in study.trials[:3]:
+        sampler_0._same_search_space(t.system_attrs['search_space'])
+    for t in study.trials[3:5]:
+        sampler_1._same_search_space(t.system_attrs['search_space'])
+
+    # Run 3 trials with the first search space again.
+    study.sampler = sampler_0
+    study.optimize(objective, n_trials=3)
+
+    assert len(study.trials) == 8
+    for t in study.trials[:3]:
+        sampler_0._same_search_space(t.system_attrs['search_space'])
+    for t in study.trials[3:5]:
+        sampler_1._same_search_space(t.system_attrs['search_space'])
+    for t in study.trials[5:]:
+        sampler_0._same_search_space(t.system_attrs['search_space'])
+
+
+def test_cast_value():
+    # type: () -> None
+
+    samplers.GridSampler._check_value('x', None)
+    samplers.GridSampler._check_value('x', True)
+    samplers.GridSampler._check_value('x', False)
+    samplers.GridSampler._check_value('x', -1)
+    samplers.GridSampler._check_value('x', -1.5)
+    samplers.GridSampler._check_value('x', float('nan'))
+    samplers.GridSampler._check_value('x', 'foo')
+    samplers.GridSampler._check_value('x', '')
+
+    with pytest.raises(ValueError):
+        samplers.GridSampler._check_value('x', [1])
+
+
+def test_has_same_search_space():
+    # type: () -> None
+
+    search_space = {'x': [3, 2, 1], 'y': ['a', 'b', 'c']}  # type: Dict[str, List[GridValueType]]
+    sampler = samplers.GridSampler(search_space)
+    assert sampler._same_search_space(search_space)
+    assert sampler._same_search_space({'x': np.array([3, 2, 1]), 'y': ['a', 'b', 'c']})
+    assert sampler._same_search_space({'y': ['c', 'a', 'b'], 'x': [1, 2, 3]})
+
+    assert not sampler._same_search_space({'x': [3, 2, 1, 0], 'y': ['a', 'b', 'c']})
+    assert not sampler._same_search_space({'x': [3, 2], 'y': ['a', 'b', 'c']})


Code review comments:
diff_hunk: @@ -0,0 +1,177 @@
+import collections
+import itertools
+import random
+
+from optuna._experimental import experimental
+from optuna.samplers.base import BaseSampler
+from optuna import type_checking
+
+if type_checking.TYPE_CHECKING:
+    from typing import Any  # NOQA
+    from typing import Dict  # NOQA
+    from typing import List  # NOQA
+    from typing import Union
+
+    from optuna.distributions import BaseDistribution  # NOQA
+    from optuna.structs import FrozenTrial  # NOQA
+    from optuna.study import Study  # NOQA
+
+    GridValueType = Union[str, float, int, bool, None]
+
+
+@experimental('1.2.0')
+class GridSampler(BaseSampler):
+    """Sampler using grid search.
+
+    With :class:`~optuna.samplers.GridSampler`, the trials suggest all combinations of parameters
+    in the given search space during the study.
+
+    Example:
+
+        .. testcode::
+
+            import optuna
+
+            def objective(trial):
+                x = trial.suggest_uniform('x', -100, 100)
+                y = trial.suggest_int('y', -100, 100)
+                return x ** 2 + y ** 2
+
+            search_space = {
+                'x': [-50, 0, 50],
+                'y': [-99, 0, 99]
+            }
+            study = optuna.create_study(sampler=optuna.samplers.GridSampler(search_space))
+            study.optimize(objective, n_trials=3*3)
+
+    Note:
+
+        :class:`~optuna.samplers.GridSampler` does not take care of a parameter's quantization
+        specified by discrete suggest methods but just samples one of values specified in the
+        search space. E.g., in the following code snippet, either of ``-0.5`` or ``0.5`` is
+        sampled as ``x`` instead of an integer point.
+
+        .. testcode::
+
+            import optuna
+
+            def objective(trial):
+                # The following suggest method specifies integer points between -5 and 5.
+                x = trial.suggest_discrete_uniform('x', -5, 5, 1)
+                return x ** 2
+
+            # Non-int points are specified in the grid.
+            search_space = {'x': [-0.5, 0.5]}
+            study = optuna.create_study(sampler=optuna.samplers.GridSampler(search_space))
+            study.optimize(objective, n_trials=2)
+
+    Args:
+        search_space:
+            A dictionary whose key and value are a parameter name and the corresponding candidates
+            of values, respectively.
+    """
+
+    def __init__(self, search_space):
+        # type: (Dict[str, List[GridValueType]]) -> None
+
+        for param_name, param_values in search_space.items():
+            for value in param_values:
+                self._check_value(param_name, value)
+
+        self._search_space = collections.OrderedDict()
+        for param_name, param_values in sorted(search_space.items(), key=lambda x: x[0]):
+            self._search_space[param_name] = sorted(param_values)
+
+        self._all_grids = list(itertools.product(*self._search_space.values()))
+        self._param_names = sorted(search_space.keys())
+        self._n_min_trials = len(self._all_grids)
+
+    def infer_relative_search_space(self, study, trial):
+        # type: (Study, FrozenTrial) -> Dict[str, BaseDistribution]
+
+        return {}
+
+    def sample_relative(self, study, trial, search_space):
+        # type: (Study, FrozenTrial, Dict[str, BaseDistribution]) -> Dict[str, Any]
+
+        # Instead of returning param values, GridSampler puts the target grid id as a system attr,
+        # and the values are returned from `sample_independent`. This is because the distribution
+        # object is hard to get at the beginning of trial, while we need the access to the object
+        # to validate the sampled value.
+
+        unvisited_grids = self._get_unvisited_grid_ids(study)
+
+        if len(unvisited_grids) == 0:
+            raise ValueError('All grids have been evaluated. If you want to avoid this error, '
+                             'please make sure that unnecessary trials do not run during '
+                             'optimization by properly setting `n_trials` in `study.optimize`.')
+
+        # In distributed optimization, multiple workers may simultaneously pick up the same grid.
+        # To make the conflict less frequent, the grid is chosen randomly.
+        grid_id = random.choice(unvisited_grids)
+
+        study._storage.set_trial_system_attr(trial._trial_id, 'search_space', self._search_space)
+        study._storage.set_trial_system_attr(trial._trial_id, 'grid_id', grid_id)
+
+        return {}
+
+    def sample_independent(self, study, trial, param_name, param_distribution):
+        # type: (Study, FrozenTrial, str, BaseDistribution) -> Any
+
+        if param_name not in self._search_space:
+            message = 'The parameter name, {}, is not found in the given grid.'.format(param_name)
+            raise ValueError(message)
+
+        grid_id = trial.system_attrs['grid_id']
+        param_value = self._all_grids[grid_id][self._param_names.index(param_name)]
+        contains = param_distribution._contains(param_distribution.to_internal_repr(param_value))
+        if not contains:
+            raise ValueError('The value `{}` is out of range of the parameter `{}`. Please make '
+                             'sure the search space of the `GridSampler` only contains values '
+                             'consistent with the distribution specified in the objective '
+                             'function. The distribution is: `{}`.'
+                             .format(param_value, param_name, param_distribution))
+
+        return param_value
+
+    @staticmethod
+    def _check_value(param_name, param_value):
+        # type: (str, Any) -> None
+
+        if param_value is None or isinstance(param_value, (str, int, float, bool)):
+            return
+
+        raise ValueError('{} contains a value with the type of {}, which is not supported by '
+                         '`GridSampler`. Please make sure a value is `str`, `int`, `float`, `bool`'
+                         ' or `None`.'.format(param_name, type(param_value)))
+
+    def _get_unvisited_grid_ids(self, study):
+        # type: (Study) -> List[int]
+
+        # List up all finished trials in the same search space.
+        trials = study.trials
+        trials = [t for t in trials if t.state.is_finished()]
+        trials = [t for t in trials if 'grid_id' in t.system_attrs]
+        trials = [t for t in trials if self._same_search_space(t.system_attrs['search_space'])]
+
+        # List up unvisited trials based on already finished ones.
+        visited_grids = [t.system_attrs['grid_id'] for t in trials]
path: optuna/samplers/grid.py
text: @user1:
I believe you could construct `visited_grids` with a single loop over all trials (instead of 4). What do you think?

@author:
Replaced the logic with a single for loop.