Repository: optuna/optuna

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. 

Discussion:
codecov-commenter: # [Codecov](https://codecov.io/gh/optuna/optuna/pull/3544?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None) Report
> Merging [#3544](https://codecov.io/gh/optuna/optuna/pull/3544?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None) (6e5992b) into [master](https://codecov.io/gh/optuna/optuna/commit/f00abac7d53bb29e53e7c8bd13e9b4be9e0f9d44?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None) (f00abac) will **not change** coverage.
> The diff coverage is `100.00%`.

```diff
@@           Coverage Diff           @@
##           master    #3544   +/-   ##
=======================================
  Coverage   91.49%   91.49%           
=======================================
  Files         158      158           
  Lines       12245    12245           
=======================================
  Hits        11203    11203           
  Misses       1042     1042           
```


| [Impacted Files](https://codecov.io/gh/optuna/optuna/pull/3544?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None) | Coverage Δ | |
|---|---|---|
| [optuna/samplers/\_grid.py](https://codecov.io/gh/optuna/optuna/pull/3544/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None#diff-b3B0dW5hL3NhbXBsZXJzL19ncmlkLnB5) | `100.00% <100.00%> (ø)` | |

:mega: Codecov can now indicate which changes are the most critical in Pull Requests. [Learn more](https://about.codecov.io/product/feature/runtime-insights/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None)

HideakiImamura: @contramundum53 Could you review this PR?

Patch:
diff --git a/optuna/samplers/_grid.py b/optuna/samplers/_grid.py
index 4673185db..699d33d6a 100644
--- a/optuna/samplers/_grid.py
+++ b/optuna/samplers/_grid.py
@@ -2,7 +2,6 @@ import collections
 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 @@ from optuna.trial import TrialState
 
 
 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 @@ class GridSampler(BaseSampler):
                 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 @@ class GridSampler(BaseSampler):
             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
 


Test patch:
diff --git a/tests/samplers_tests/test_grid.py b/tests/samplers_tests/test_grid.py
index 466598995..efa764f59 100644
--- a/tests/samplers_tests/test_grid.py
+++ b/tests/samplers_tests/test_grid.py
@@ -22,7 +22,7 @@ def test_study_optimize_with_single_search_space() -> None:
 
         a = trial.suggest_int("a", 0, 100)
         b = trial.suggest_float("b", -0.1, 0.1)
-        c = trial.suggest_categorical("c", ("x", "y"))
+        c = trial.suggest_categorical("c", ("x", "y", None, 1, 2.0))
         d = trial.suggest_float("d", -5, 5, step=1)
         e = trial.suggest_float("e", 0.0001, 1, log=True)
 
@@ -34,7 +34,7 @@ def test_study_optimize_with_single_search_space() -> None:
     # Test that all combinations of the grid is sampled.
     search_space = {
         "b": np.arange(-0.1, 0.1, 0.05),
-        "c": ["x", "y"],
+        "c": ("x", "y", None, 1, 2.0),
         "d": [-0.5, 0.5],
         "e": [0.1],
         "a": list(range(0, 100, 20)),
@@ -163,8 +163,8 @@ def test_has_same_search_space() -> None:
     sampler = samplers.GridSampler(search_space)
     assert sampler._same_search_space(search_space)
     assert sampler._same_search_space({"x": [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({"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"]})