We are currently solving the following issue within our repository. Here is the issue text:
--- BEGIN ISSUE ---
`GridSearchSampler` raises `TypeError` when `choices` of `CategoricalDistribution` are not comparable
### Expected behavior

The folliwing grid search based optimisation works without any error because default sampler works fine.
```python
import optuna


def objective(trial):
    x = trial.suggest_float("x", -100, 100)
    y = trial.suggest_categorical("y", [None, 1])
    if y is None:
        y = -1
    return x ** 2 + y

# Grid search.
search_space = {"x": [-50, 0, 50], "y": [None, 1]}
study = optuna.create_study(sampler=optuna.samplers.GridSampler(search_space))
study.optimize(objective, n_trials=20)


# Note Random search + TPE works well.
# study.optimize(objective, n_trials=20)
```

### Environment

- Optuna version: 3.0.0b1.dev
- Python version: 3.9.12
- OS: macOS-10.16-x86_64-i386-64bit
- (Optional) Other libraries and their versions:


### Error messages, stack traces, or logs

```shell
TypeError                                 Traceback (most recent call last)
Input In [15], in <cell line: 17>()
     14 study.optimize(objective, n_trials=20)
     16 # Grid search
---> 17 study = optuna.create_study(sampler=optuna.samplers.GridSampler(search_space))
     18 study.optimize(objective, n_trials=20)

File ~/Documents/optuna/optuna/samplers/_grid.py:112, in GridSampler.__init__(self, search_space)
    109 for param_name, param_values in sorted(search_space.items(), key=lambda x: x[0]):
    110     param_values = cast(SortableParamValueSequenceType, param_values)
--> 112     self._search_space[param_name] = sorted(param_values)
    114 self._all_grids = list(itertools.product(*self._search_space.values()))
    115 self._param_names = sorted(search_space.keys())

TypeError: '<' not supported between instances of 'int' and 'NoneType'
```



### Steps to reproduce

1. Run the code above
2.
3.
```python
# python code
```


### Additional context (optional)

Since grid search sampler implementation sorts `choices`, the current implementation assumes the choices are sortable. 

--- END ISSUE ---

Below are some code segments, each from a relevant file. One or more of these files may contain bugs.
--- BEGIN FILES ---
Path: `optuna/samplers/_grid.py`
Content:
```
1 import collections
2 import itertools
3 import random
4 from typing import Any
5 from typing import cast
6 from typing import Dict
7 from typing import List
8 from typing import Mapping
9 from typing import Optional
10 from typing import Sequence
11 from typing import Union
12 import warnings
13 
14 from optuna.distributions import BaseDistribution
15 from optuna.logging import get_logger
16 from optuna.samplers import BaseSampler
17 from optuna.study import Study
18 from optuna.trial import FrozenTrial
19 from optuna.trial import TrialState
20 
21 
22 GridValueType = Union[str, float, int, bool, None]
23 SortableParamValueSequenceType = Union[List[str], List[float], List[int], List[bool]]
24 
25 
26 _logger = get_logger(__name__)
27 
28 
29 class GridSampler(BaseSampler):
30     """Sampler using grid search.
31 
32     With :class:`~optuna.samplers.GridSampler`, the trials suggest all combinations of parameters
33     in the given search space during the study.
34 
35     Example:
36 
37         .. testcode::
38 
39             import optuna
40 
41 
42             def objective(trial):
43                 x = trial.suggest_float("x", -100, 100)
44                 y = trial.suggest_int("y", -100, 100)
45                 return x**2 + y**2
46 
47 
48             search_space = {"x": [-50, 0, 50], "y": [-99, 0, 99]}
49             study = optuna.create_study(sampler=optuna.samplers.GridSampler(search_space))
50             study.optimize(objective)
51 
52     Note:
53 
54         :class:`~optuna.samplers.GridSampler` automatically stops the optimization if all
55         combinations in the passed ``search_space`` have already been evaluated, internally
56         invoking the :func:`~optuna.study.Study.stop` method.
57 
58     Note:
59 
60         :class:`~optuna.samplers.GridSampler` does not take care of a parameter's quantization
61         specified by discrete suggest methods but just samples one of values specified in the
62         search space. E.g., in the following code snippet, either of ``-0.5`` or ``0.5`` is
63         sampled as ``x`` instead of an integer point.
64 
65         .. testcode::
66 
67             import optuna
68 
69 
70             def objective(trial):
71                 # The following suggest method specifies integer points between -5 and 5.
72                 x = trial.suggest_float("x", -5, 5, step=1)
73                 return x**2
74 
75 
76             # Non-int points are specified in the grid.
77             search_space = {"x": [-0.5, 0.5]}
78             study = optuna.create_study(sampler=optuna.samplers.GridSampler(search_space))
79             study.optimize(objective, n_trials=2)
80 
81     Note:
82         A parameter configuration in the grid is not considered finished until its trial is
83         finished. Therefore, during distributed optimization where trials run concurrently,
84         different workers will occasionally suggest the same parameter configuration.
85         The total number of actual trials may therefore exceed the size of the grid.
86 
87     Note:
88         The grid is randomly shuffled and the order in which parameter configurations are
89         suggested may vary. This is to reduce duplicate suggestions during distributed
90         optimization.
91 
92     Note:
93         All parameters must be specified when using :class:`~optuna.samplers.GridSampler` with
94         :meth:`~optuna.study.Study.enqueue_trial`.
95 
96     Args:
97         search_space:
98             A dictionary whose key and value are a parameter name and the corresponding candidates
99             of values, respectively.
100     """
101 
102     def __init__(self, search_space: Mapping[str, Sequence[GridValueType]]) -> None:
103 
104         for param_name, param_values in search_space.items():
105             for value in param_values:
106                 self._check_value(param_name, value)
107 
108         self._search_space = collections.OrderedDict()
109         for param_name, param_values in sorted(search_space.items(), key=lambda x: x[0]):
110             param_values = cast(SortableParamValueSequenceType, param_values)
111 
112             self._search_space[param_name] = sorted(param_values)
113 
114         self._all_grids = list(itertools.product(*self._search_space.values()))
115         self._param_names = sorted(search_space.keys())
116         self._n_min_trials = len(self._all_grids)
117 
118     def infer_relative_search_space(
119         self, study: Study, trial: FrozenTrial
120     ) -> Dict[str, BaseDistribution]:
121 
122         return {}
123 
124     def sample_relative(
125         self, study: Study, trial: FrozenTrial, search_space: Dict[str, BaseDistribution]
126     ) -> Dict[str, Any]:
127         # Instead of returning param values, GridSampler puts the target grid id as a system attr,
128         # and the values are returned from `sample_independent`. This is because the distribution
129         # object is hard to get at the beginning of trial, while we need the access to the object
130         # to validate the sampled value.
131 
132         # When the trial is created by RetryFailedTrialCallback or enqueue_trial, we should not
133         # assign a new grid_id.
134         if "grid_id" in trial.system_attrs or "fixed_params" in trial.system_attrs:
135             return {}
136 
137         target_grids = self._get_unvisited_grid_ids(study)
138 
139         if len(target_grids) == 0:
140             # This case may occur with distributed optimization or trial queue. If there is no
141             # target grid, `GridSampler` evaluates a visited, duplicated point with the current
142             # trial. After that, the optimization stops.
143 
144             _logger.warning(
145                 "`GridSampler` is re-evaluating a configuration because the grid has been "
146                 "exhausted. This may happen due to a timing issue during distributed optimization "
147                 "or when re-running optimizations on already finished studies."
148             )
149 
150             # One of all grids is randomly picked up in this case.
151             target_grids = list(range(len(self._all_grids)))
152 
153         # In distributed optimization, multiple workers may simultaneously pick up the same grid.
154         # To make the conflict less frequent, the grid is chosen randomly.
155         grid_id = random.choice(target_grids)
156 
157         study._storage.set_trial_system_attr(trial._trial_id, "search_space", self._search_space)
158         study._storage.set_trial_system_attr(trial._trial_id, "grid_id", grid_id)
159 
160         return {}
161 
162     def sample_independent(
163         self,
164         study: Study,
165         trial: FrozenTrial,
166         param_name: str,
167         param_distribution: BaseDistribution,
168     ) -> Any:
169 
170         if "grid_id" not in trial.system_attrs:
171             message = "All parameters must be specified when using GridSampler with enqueue_trial."
172             raise ValueError(message)
173 
174         if param_name not in self._search_space:
175             message = "The parameter name, {}, is not found in the given grid.".format(param_name)
176             raise ValueError(message)
177 
178         # TODO(c-bata): Reduce the number of duplicated evaluations on multiple workers.
179         # Current selection logic may evaluate the same parameters multiple times.
180         # See https://gist.github.com/c-bata/f759f64becb24eea2040f4b2e3afce8f for details.
181         grid_id = trial.system_attrs["grid_id"]
182         param_value = self._all_grids[grid_id][self._param_names.index(param_name)]
183         contains = param_distribution._contains(param_distribution.to_internal_repr(param_value))
184         if not contains:
185             warnings.warn(
186                 f"The value `{param_value}` is out of range of the parameter `{param_name}`. "
187                 f"The value will be used but the actual distribution is: `{param_distribution}`."
188             )
189 
190         return param_value
191 
192     def after_trial(
193         self,
194         study: Study,
195         trial: FrozenTrial,
196         state: TrialState,
197         values: Optional[Sequence[float]],
198     ) -> None:
199         target_grids = self._get_unvisited_grid_ids(study)
200 
201         if len(target_grids) == 0:
202             study.stop()
203         elif len(target_grids) == 1:
204             grid_id = study._storage.get_trial_system_attrs(trial._trial_id)["grid_id"]
205             if grid_id == target_grids[0]:
206                 study.stop()
207 
208     @staticmethod
209     def _check_value(param_name: str, param_value: Any) -> None:
210 
211         if param_value is None or isinstance(param_value, (str, int, float, bool)):
212             return
213 
214         raise ValueError(
215             "{} contains a value with the type of {}, which is not supported by "
216             "`GridSampler`. Please make sure a value is `str`, `int`, `float`, `bool`"
217             " or `None`.".format(param_name, type(param_value))
218         )
219 
220     def _get_unvisited_grid_ids(self, study: Study) -> List[int]:
221 
222         # List up unvisited grids based on already finished ones.
223         visited_grids = []
224         running_grids = []
225 
226         # We directly query the storage to get trials here instead of `study.get_trials`,
227         # since some pruners such as `HyperbandPruner` use the study transformed
228         # to filter trials. See https://github.com/optuna/optuna/issues/2327 for details.
229         trials = study._storage.get_all_trials(study._study_id, deepcopy=False)
230 
231         for t in trials:
232             if "grid_id" in t.system_attrs and self._same_search_space(
233                 t.system_attrs["search_space"]
234             ):
235                 if t.state.is_finished():
236                     visited_grids.append(t.system_attrs["grid_id"])
237                 elif t.state == TrialState.RUNNING:
238                     running_grids.append(t.system_attrs["grid_id"])
239 
240         unvisited_grids = set(range(self._n_min_trials)) - set(visited_grids) - set(running_grids)
241 
242         # If evaluations for all grids have been started, return grids that have not yet finished
243         # because all grids should be evaluated before stopping the optimization.
244         if len(unvisited_grids) == 0:
245             unvisited_grids = set(range(self._n_min_trials)) - set(visited_grids)
246 
247         return list(unvisited_grids)
248 
249     def _same_search_space(self, search_space: Mapping[str, Sequence[GridValueType]]) -> bool:
250 
251         if set(search_space.keys()) != set(self._search_space.keys()):
252             return False
253 
254         for param_name in search_space.keys():
255             if len(search_space[param_name]) != len(self._search_space[param_name]):
256                 return False
257 
258             param_values = cast(SortableParamValueSequenceType, search_space[param_name])
259             for i, param_value in enumerate(sorted(param_values)):
260                 if param_value != self._search_space[param_name][i]:
261                     return False
262 
263         return True
264
```
--- END FILES ---

Please first localize the bug based on the issue statement, and then generate a patch according to the `git diff` format fenced by three backticks.

Here is an example:

```diff
diff --git a/examples/server_async.py b/examples/server_async.py
--- a/examples/server_async.py
+++ b/examples/server_async.py
@@ -313,4 +313,4 @@
 
 
 if __name__ == "__main__":
-    asyncio.run(run_async_server("."), debug=True)
+    asyncio.run(run_async_server(), debug=True)
diff --git a/examples/server_sync.py b/examples/server_sync.py
--- a/examples/server_sync.py
+++ b/examples/server_sync.py
@@ -313,5 +313,5 @@
 
 
 if __name__ == "__main__":
-    server = run_sync_server(".")
+    server = run_sync_server()
     server.shutdown()

```

diff --git a/optuna/samplers/_grid.py b/optuna/samplers/_grid.py
--- a/optuna/samplers/_grid.py
+++ b/optuna/samplers/_grid.py
@@ -2,7 +2,6 @@
 import itertools
 import random
 from typing import Any
-from typing import cast
 from typing import Dict
 from typing import List
 from typing import Mapping
@@ -20,7 +19,6 @@
 
 
 GridValueType = Union[str, float, int, bool, None]
-SortableParamValueSequenceType = Union[List[str], List[float], List[int], List[bool]]
 
 
 _logger = get_logger(__name__)
@@ -106,10 +104,8 @@
                 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]):
-            param_values = cast(SortableParamValueSequenceType, param_values)
-
-            self._search_space[param_name] = sorted(param_values)
+        for param_name, param_values in sorted(search_space.items()):
+            self._search_space[param_name] = param_values
 
         self._all_grids = list(itertools.product(*self._search_space.values()))
         self._param_names = sorted(search_space.keys())
@@ -255,8 +251,7 @@
             if len(search_space[param_name]) != len(self._search_space[param_name]):
                 return False
 
-            param_values = cast(SortableParamValueSequenceType, search_space[param_name])
-            for i, param_value in enumerate(sorted(param_values)):
+            for i, param_value in enumerate(search_space[param_name]):
                 if param_value != self._search_space[param_name][i]:
                     return False

{"golden_diff": "diff --git a/optuna/samplers/_grid.py b/optuna/samplers/_grid.py\n--- a/optuna/samplers/_grid.py\n+++ b/optuna/samplers/_grid.py\n@@ -2,7 +2,6 @@\n import itertools\n import random\n from typing import Any\n-from typing import cast\n from typing import Dict\n from typing import List\n from typing import Mapping\n@@ -20,7 +19,6 @@\n \n \n GridValueType = Union[str, float, int, bool, None]\n-SortableParamValueSequenceType = Union[List[str], List[float], List[int], List[bool]]\n \n \n _logger = get_logger(__name__)\n@@ -106,10 +104,8 @@\n                 self._check_value(param_name, value)\n \n         self._search_space = collections.OrderedDict()\n-        for param_name, param_values in sorted(search_space.items(), key=lambda x: x[0]):\n-            param_values = cast(SortableParamValueSequenceType, param_values)\n-\n-            self._search_space[param_name] = sorted(param_values)\n+        for param_name, param_values in sorted(search_space.items()):\n+            self._search_space[param_name] = param_values\n \n         self._all_grids = list(itertools.product(*self._search_space.values()))\n         self._param_names = sorted(search_space.keys())\n@@ -255,8 +251,7 @@\n             if len(search_space[param_name]) != len(self._search_space[param_name]):\n                 return False\n \n-            param_values = cast(SortableParamValueSequenceType, search_space[param_name])\n-            for i, param_value in enumerate(sorted(param_values)):\n+            for i, param_value in enumerate(search_space[param_name]):\n                 if param_value != self._search_space[param_name][i]:\n                     return False\n", "issue": "`GridSearchSampler` raises `TypeError` when `choices` of `CategoricalDistribution` are not comparable\n### Expected behavior\r\n\r\nThe folliwing grid search based optimisation works without any error because default sampler works fine.\r\n```python\r\nimport optuna\r\n\r\n\r\ndef objective(trial):\r\n    x = trial.suggest_float(\"x\", -100, 100)\r\n    y = trial.suggest_categorical(\"y\", [None, 1])\r\n    if y is None:\r\n        y = -1\r\n    return x ** 2 + y\r\n\r\n# Grid search.\r\nsearch_space = {\"x\": [-50, 0, 50], \"y\": [None, 1]}\r\nstudy = optuna.create_study(sampler=optuna.samplers.GridSampler(search_space))\r\nstudy.optimize(objective, n_trials=20)\r\n\r\n\r\n# Note Random search + TPE works well.\r\n# study.optimize(objective, n_trials=20)\r\n```\r\n\r\n### Environment\r\n\r\n- Optuna version: 3.0.0b1.dev\r\n- Python version: 3.9.12\r\n- OS: macOS-10.16-x86_64-i386-64bit\r\n- (Optional) Other libraries and their versions:\r\n\r\n\r\n### Error messages, stack traces, or logs\r\n\r\n```shell\r\nTypeError                                 Traceback (most recent call last)\r\nInput In [15], in <cell line: 17>()\r\n     14 study.optimize(objective, n_trials=20)\r\n     16 # Grid search\r\n---> 17 study = optuna.create_study(sampler=optuna.samplers.GridSampler(search_space))\r\n     18 study.optimize(objective, n_trials=20)\r\n\r\nFile ~/Documents/optuna/optuna/samplers/_grid.py:112, in GridSampler.__init__(self, search_space)\r\n    109 for param_name, param_values in sorted(search_space.items(), key=lambda x: x[0]):\r\n    110     param_values = cast(SortableParamValueSequenceType, param_values)\r\n--> 112     self._search_space[param_name] = sorted(param_values)\r\n    114 self._all_grids = list(itertools.product(*self._search_space.values()))\r\n    115 self._param_names = sorted(search_space.keys())\r\n\r\nTypeError: '<' not supported between instances of 'int' and 'NoneType'\r\n```\r\n\r\n\r\n\r\n### Steps to reproduce\r\n\r\n1. Run the code above\r\n2.\r\n3.\r\n```python\r\n# python code\r\n```\r\n\r\n\r\n### Additional context (optional)\r\n\r\nSince grid search sampler implementation sorts `choices`, the current implementation assumes the choices are sortable. \n", "before_files": [{"content": "import collections\nimport itertools\nimport random\nfrom typing import Any\nfrom typing import cast\nfrom typing import Dict\nfrom typing import List\nfrom typing import Mapping\nfrom typing import Optional\nfrom typing import Sequence\nfrom typing import Union\nimport warnings\n\nfrom optuna.distributions import BaseDistribution\nfrom optuna.logging import get_logger\nfrom optuna.samplers import BaseSampler\nfrom optuna.study import Study\nfrom optuna.trial import FrozenTrial\nfrom optuna.trial import TrialState\n\n\nGridValueType = Union[str, float, int, bool, None]\nSortableParamValueSequenceType = Union[List[str], List[float], List[int], List[bool]]\n\n\n_logger = get_logger(__name__)\n\n\nclass GridSampler(BaseSampler):\n    \"\"\"Sampler using grid search.\n\n    With :class:`~optuna.samplers.GridSampler`, the trials suggest all combinations of parameters\n    in the given search space during the study.\n\n    Example:\n\n        .. testcode::\n\n            import optuna\n\n\n            def objective(trial):\n                x = trial.suggest_float(\"x\", -100, 100)\n                y = trial.suggest_int(\"y\", -100, 100)\n                return x**2 + y**2\n\n\n            search_space = {\"x\": [-50, 0, 50], \"y\": [-99, 0, 99]}\n            study = optuna.create_study(sampler=optuna.samplers.GridSampler(search_space))\n            study.optimize(objective)\n\n    Note:\n\n        :class:`~optuna.samplers.GridSampler` automatically stops the optimization if all\n        combinations in the passed ``search_space`` have already been evaluated, internally\n        invoking the :func:`~optuna.study.Study.stop` method.\n\n    Note:\n\n        :class:`~optuna.samplers.GridSampler` does not take care of a parameter's quantization\n        specified by discrete suggest methods but just samples one of values specified in the\n        search space. E.g., in the following code snippet, either of ``-0.5`` or ``0.5`` is\n        sampled as ``x`` instead of an integer point.\n\n        .. testcode::\n\n            import optuna\n\n\n            def objective(trial):\n                # The following suggest method specifies integer points between -5 and 5.\n                x = trial.suggest_float(\"x\", -5, 5, step=1)\n                return x**2\n\n\n            # Non-int points are specified in the grid.\n            search_space = {\"x\": [-0.5, 0.5]}\n            study = optuna.create_study(sampler=optuna.samplers.GridSampler(search_space))\n            study.optimize(objective, n_trials=2)\n\n    Note:\n        A parameter configuration in the grid is not considered finished until its trial is\n        finished. Therefore, during distributed optimization where trials run concurrently,\n        different workers will occasionally suggest the same parameter configuration.\n        The total number of actual trials may therefore exceed the size of the grid.\n\n    Note:\n        The grid is randomly shuffled and the order in which parameter configurations are\n        suggested may vary. This is to reduce duplicate suggestions during distributed\n        optimization.\n\n    Note:\n        All parameters must be specified when using :class:`~optuna.samplers.GridSampler` with\n        :meth:`~optuna.study.Study.enqueue_trial`.\n\n    Args:\n        search_space:\n            A dictionary whose key and value are a parameter name and the corresponding candidates\n            of values, respectively.\n    \"\"\"\n\n    def __init__(self, search_space: Mapping[str, Sequence[GridValueType]]) -> None:\n\n        for param_name, param_values in search_space.items():\n            for value in param_values:\n                self._check_value(param_name, value)\n\n        self._search_space = collections.OrderedDict()\n        for param_name, param_values in sorted(search_space.items(), key=lambda x: x[0]):\n            param_values = cast(SortableParamValueSequenceType, param_values)\n\n            self._search_space[param_name] = sorted(param_values)\n\n        self._all_grids = list(itertools.product(*self._search_space.values()))\n        self._param_names = sorted(search_space.keys())\n        self._n_min_trials = len(self._all_grids)\n\n    def infer_relative_search_space(\n        self, study: Study, trial: FrozenTrial\n    ) -> Dict[str, BaseDistribution]:\n\n        return {}\n\n    def sample_relative(\n        self, study: Study, trial: FrozenTrial, search_space: Dict[str, BaseDistribution]\n    ) -> Dict[str, Any]:\n        # Instead of returning param values, GridSampler puts the target grid id as a system attr,\n        # and the values are returned from `sample_independent`. This is because the distribution\n        # object is hard to get at the beginning of trial, while we need the access to the object\n        # to validate the sampled value.\n\n        # When the trial is created by RetryFailedTrialCallback or enqueue_trial, we should not\n        # assign a new grid_id.\n        if \"grid_id\" in trial.system_attrs or \"fixed_params\" in trial.system_attrs:\n            return {}\n\n        target_grids = self._get_unvisited_grid_ids(study)\n\n        if len(target_grids) == 0:\n            # This case may occur with distributed optimization or trial queue. If there is no\n            # target grid, `GridSampler` evaluates a visited, duplicated point with the current\n            # trial. After that, the optimization stops.\n\n            _logger.warning(\n                \"`GridSampler` is re-evaluating a configuration because the grid has been \"\n                \"exhausted. This may happen due to a timing issue during distributed optimization \"\n                \"or when re-running optimizations on already finished studies.\"\n            )\n\n            # One of all grids is randomly picked up in this case.\n            target_grids = list(range(len(self._all_grids)))\n\n        # In distributed optimization, multiple workers may simultaneously pick up the same grid.\n        # To make the conflict less frequent, the grid is chosen randomly.\n        grid_id = random.choice(target_grids)\n\n        study._storage.set_trial_system_attr(trial._trial_id, \"search_space\", self._search_space)\n        study._storage.set_trial_system_attr(trial._trial_id, \"grid_id\", grid_id)\n\n        return {}\n\n    def sample_independent(\n        self,\n        study: Study,\n        trial: FrozenTrial,\n        param_name: str,\n        param_distribution: BaseDistribution,\n    ) -> Any:\n\n        if \"grid_id\" not in trial.system_attrs:\n            message = \"All parameters must be specified when using GridSampler with enqueue_trial.\"\n            raise ValueError(message)\n\n        if param_name not in self._search_space:\n            message = \"The parameter name, {}, is not found in the given grid.\".format(param_name)\n            raise ValueError(message)\n\n        # TODO(c-bata): Reduce the number of duplicated evaluations on multiple workers.\n        # Current selection logic may evaluate the same parameters multiple times.\n        # See https://gist.github.com/c-bata/f759f64becb24eea2040f4b2e3afce8f for details.\n        grid_id = trial.system_attrs[\"grid_id\"]\n        param_value = self._all_grids[grid_id][self._param_names.index(param_name)]\n        contains = param_distribution._contains(param_distribution.to_internal_repr(param_value))\n        if not contains:\n            warnings.warn(\n                f\"The value `{param_value}` is out of range of the parameter `{param_name}`. \"\n                f\"The value will be used but the actual distribution is: `{param_distribution}`.\"\n            )\n\n        return param_value\n\n    def after_trial(\n        self,\n        study: Study,\n        trial: FrozenTrial,\n        state: TrialState,\n        values: Optional[Sequence[float]],\n    ) -> None:\n        target_grids = self._get_unvisited_grid_ids(study)\n\n        if len(target_grids) == 0:\n            study.stop()\n        elif len(target_grids) == 1:\n            grid_id = study._storage.get_trial_system_attrs(trial._trial_id)[\"grid_id\"]\n            if grid_id == target_grids[0]:\n                study.stop()\n\n    @staticmethod\n    def _check_value(param_name: str, param_value: Any) -> None:\n\n        if param_value is None or isinstance(param_value, (str, int, float, bool)):\n            return\n\n        raise ValueError(\n            \"{} contains a value with the type of {}, which is not supported by \"\n            \"`GridSampler`. Please make sure a value is `str`, `int`, `float`, `bool`\"\n            \" or `None`.\".format(param_name, type(param_value))\n        )\n\n    def _get_unvisited_grid_ids(self, study: Study) -> List[int]:\n\n        # List up unvisited grids based on already finished ones.\n        visited_grids = []\n        running_grids = []\n\n        # We directly query the storage to get trials here instead of `study.get_trials`,\n        # since some pruners such as `HyperbandPruner` use the study transformed\n        # to filter trials. See https://github.com/optuna/optuna/issues/2327 for details.\n        trials = study._storage.get_all_trials(study._study_id, deepcopy=False)\n\n        for t in trials:\n            if \"grid_id\" in t.system_attrs and self._same_search_space(\n                t.system_attrs[\"search_space\"]\n            ):\n                if t.state.is_finished():\n                    visited_grids.append(t.system_attrs[\"grid_id\"])\n                elif t.state == TrialState.RUNNING:\n                    running_grids.append(t.system_attrs[\"grid_id\"])\n\n        unvisited_grids = set(range(self._n_min_trials)) - set(visited_grids) - set(running_grids)\n\n        # If evaluations for all grids have been started, return grids that have not yet finished\n        # because all grids should be evaluated before stopping the optimization.\n        if len(unvisited_grids) == 0:\n            unvisited_grids = set(range(self._n_min_trials)) - set(visited_grids)\n\n        return list(unvisited_grids)\n\n    def _same_search_space(self, search_space: Mapping[str, Sequence[GridValueType]]) -> bool:\n\n        if set(search_space.keys()) != set(self._search_space.keys()):\n            return False\n\n        for param_name in search_space.keys():\n            if len(search_space[param_name]) != len(self._search_space[param_name]):\n                return False\n\n            param_values = cast(SortableParamValueSequenceType, search_space[param_name])\n            for i, param_value in enumerate(sorted(param_values)):\n                if param_value != self._search_space[param_name][i]:\n                    return False\n\n        return True\n", "path": "optuna/samplers/_grid.py"}], "after_files": [{"content": "import collections\nimport itertools\nimport random\nfrom typing import Any\nfrom typing import Dict\nfrom typing import List\nfrom typing import Mapping\nfrom typing import Optional\nfrom typing import Sequence\nfrom typing import Union\nimport warnings\n\nfrom optuna.distributions import BaseDistribution\nfrom optuna.logging import get_logger\nfrom optuna.samplers import BaseSampler\nfrom optuna.study import Study\nfrom optuna.trial import FrozenTrial\nfrom optuna.trial import TrialState\n\n\nGridValueType = Union[str, float, int, bool, None]\n\n\n_logger = get_logger(__name__)\n\n\nclass GridSampler(BaseSampler):\n    \"\"\"Sampler using grid search.\n\n    With :class:`~optuna.samplers.GridSampler`, the trials suggest all combinations of parameters\n    in the given search space during the study.\n\n    Example:\n\n        .. testcode::\n\n            import optuna\n\n\n            def objective(trial):\n                x = trial.suggest_float(\"x\", -100, 100)\n                y = trial.suggest_int(\"y\", -100, 100)\n                return x**2 + y**2\n\n\n            search_space = {\"x\": [-50, 0, 50], \"y\": [-99, 0, 99]}\n            study = optuna.create_study(sampler=optuna.samplers.GridSampler(search_space))\n            study.optimize(objective)\n\n    Note:\n\n        :class:`~optuna.samplers.GridSampler` automatically stops the optimization if all\n        combinations in the passed ``search_space`` have already been evaluated, internally\n        invoking the :func:`~optuna.study.Study.stop` method.\n\n    Note:\n\n        :class:`~optuna.samplers.GridSampler` does not take care of a parameter's quantization\n        specified by discrete suggest methods but just samples one of values specified in the\n        search space. E.g., in the following code snippet, either of ``-0.5`` or ``0.5`` is\n        sampled as ``x`` instead of an integer point.\n\n        .. testcode::\n\n            import optuna\n\n\n            def objective(trial):\n                # The following suggest method specifies integer points between -5 and 5.\n                x = trial.suggest_float(\"x\", -5, 5, step=1)\n                return x**2\n\n\n            # Non-int points are specified in the grid.\n            search_space = {\"x\": [-0.5, 0.5]}\n            study = optuna.create_study(sampler=optuna.samplers.GridSampler(search_space))\n            study.optimize(objective, n_trials=2)\n\n    Note:\n        A parameter configuration in the grid is not considered finished until its trial is\n        finished. Therefore, during distributed optimization where trials run concurrently,\n        different workers will occasionally suggest the same parameter configuration.\n        The total number of actual trials may therefore exceed the size of the grid.\n\n    Note:\n        The grid is randomly shuffled and the order in which parameter configurations are\n        suggested may vary. This is to reduce duplicate suggestions during distributed\n        optimization.\n\n    Note:\n        All parameters must be specified when using :class:`~optuna.samplers.GridSampler` with\n        :meth:`~optuna.study.Study.enqueue_trial`.\n\n    Args:\n        search_space:\n            A dictionary whose key and value are a parameter name and the corresponding candidates\n            of values, respectively.\n    \"\"\"\n\n    def __init__(self, search_space: Mapping[str, Sequence[GridValueType]]) -> None:\n\n        for param_name, param_values in search_space.items():\n            for value in param_values:\n                self._check_value(param_name, value)\n\n        self._search_space = collections.OrderedDict()\n        for param_name, param_values in sorted(search_space.items()):\n            self._search_space[param_name] = param_values\n\n        self._all_grids = list(itertools.product(*self._search_space.values()))\n        self._param_names = sorted(search_space.keys())\n        self._n_min_trials = len(self._all_grids)\n\n    def infer_relative_search_space(\n        self, study: Study, trial: FrozenTrial\n    ) -> Dict[str, BaseDistribution]:\n\n        return {}\n\n    def sample_relative(\n        self, study: Study, trial: FrozenTrial, search_space: Dict[str, BaseDistribution]\n    ) -> Dict[str, Any]:\n        # Instead of returning param values, GridSampler puts the target grid id as a system attr,\n        # and the values are returned from `sample_independent`. This is because the distribution\n        # object is hard to get at the beginning of trial, while we need the access to the object\n        # to validate the sampled value.\n\n        # When the trial is created by RetryFailedTrialCallback or enqueue_trial, we should not\n        # assign a new grid_id.\n        if \"grid_id\" in trial.system_attrs or \"fixed_params\" in trial.system_attrs:\n            return {}\n\n        target_grids = self._get_unvisited_grid_ids(study)\n\n        if len(target_grids) == 0:\n            # This case may occur with distributed optimization or trial queue. If there is no\n            # target grid, `GridSampler` evaluates a visited, duplicated point with the current\n            # trial. After that, the optimization stops.\n\n            _logger.warning(\n                \"`GridSampler` is re-evaluating a configuration because the grid has been \"\n                \"exhausted. This may happen due to a timing issue during distributed optimization \"\n                \"or when re-running optimizations on already finished studies.\"\n            )\n\n            # One of all grids is randomly picked up in this case.\n            target_grids = list(range(len(self._all_grids)))\n\n        # In distributed optimization, multiple workers may simultaneously pick up the same grid.\n        # To make the conflict less frequent, the grid is chosen randomly.\n        grid_id = random.choice(target_grids)\n\n        study._storage.set_trial_system_attr(trial._trial_id, \"search_space\", self._search_space)\n        study._storage.set_trial_system_attr(trial._trial_id, \"grid_id\", grid_id)\n\n        return {}\n\n    def sample_independent(\n        self,\n        study: Study,\n        trial: FrozenTrial,\n        param_name: str,\n        param_distribution: BaseDistribution,\n    ) -> Any:\n\n        if \"grid_id\" not in trial.system_attrs:\n            message = \"All parameters must be specified when using GridSampler with enqueue_trial.\"\n            raise ValueError(message)\n\n        if param_name not in self._search_space:\n            message = \"The parameter name, {}, is not found in the given grid.\".format(param_name)\n            raise ValueError(message)\n\n        # TODO(c-bata): Reduce the number of duplicated evaluations on multiple workers.\n        # Current selection logic may evaluate the same parameters multiple times.\n        # See https://gist.github.com/c-bata/f759f64becb24eea2040f4b2e3afce8f for details.\n        grid_id = trial.system_attrs[\"grid_id\"]\n        param_value = self._all_grids[grid_id][self._param_names.index(param_name)]\n        contains = param_distribution._contains(param_distribution.to_internal_repr(param_value))\n        if not contains:\n            warnings.warn(\n                f\"The value `{param_value}` is out of range of the parameter `{param_name}`. \"\n                f\"The value will be used but the actual distribution is: `{param_distribution}`.\"\n            )\n\n        return param_value\n\n    def after_trial(\n        self,\n        study: Study,\n        trial: FrozenTrial,\n        state: TrialState,\n        values: Optional[Sequence[float]],\n    ) -> None:\n        target_grids = self._get_unvisited_grid_ids(study)\n\n        if len(target_grids) == 0:\n            study.stop()\n        elif len(target_grids) == 1:\n            grid_id = study._storage.get_trial_system_attrs(trial._trial_id)[\"grid_id\"]\n            if grid_id == target_grids[0]:\n                study.stop()\n\n    @staticmethod\n    def _check_value(param_name: str, param_value: Any) -> None:\n\n        if param_value is None or isinstance(param_value, (str, int, float, bool)):\n            return\n\n        raise ValueError(\n            \"{} contains a value with the type of {}, which is not supported by \"\n            \"`GridSampler`. Please make sure a value is `str`, `int`, `float`, `bool`\"\n            \" or `None`.\".format(param_name, type(param_value))\n        )\n\n    def _get_unvisited_grid_ids(self, study: Study) -> List[int]:\n\n        # List up unvisited grids based on already finished ones.\n        visited_grids = []\n        running_grids = []\n\n        # We directly query the storage to get trials here instead of `study.get_trials`,\n        # since some pruners such as `HyperbandPruner` use the study transformed\n        # to filter trials. See https://github.com/optuna/optuna/issues/2327 for details.\n        trials = study._storage.get_all_trials(study._study_id, deepcopy=False)\n\n        for t in trials:\n            if \"grid_id\" in t.system_attrs and self._same_search_space(\n                t.system_attrs[\"search_space\"]\n            ):\n                if t.state.is_finished():\n                    visited_grids.append(t.system_attrs[\"grid_id\"])\n                elif t.state == TrialState.RUNNING:\n                    running_grids.append(t.system_attrs[\"grid_id\"])\n\n        unvisited_grids = set(range(self._n_min_trials)) - set(visited_grids) - set(running_grids)\n\n        # If evaluations for all grids have been started, return grids that have not yet finished\n        # because all grids should be evaluated before stopping the optimization.\n        if len(unvisited_grids) == 0:\n            unvisited_grids = set(range(self._n_min_trials)) - set(visited_grids)\n\n        return list(unvisited_grids)\n\n    def _same_search_space(self, search_space: Mapping[str, Sequence[GridValueType]]) -> bool:\n\n        if set(search_space.keys()) != set(self._search_space.keys()):\n            return False\n\n        for param_name in search_space.keys():\n            if len(search_space[param_name]) != len(self._search_space[param_name]):\n                return False\n\n            for i, param_value in enumerate(search_space[param_name]):\n                if param_value != self._search_space[param_name][i]:\n                    return False\n\n        return True\n", "path": "optuna/samplers/_grid.py"}]}