|
1
|
|
|
# Author: ... |
|
2
|
|
|
# Email: ... |
|
3
|
|
|
# License: MIT License |
|
4
|
|
|
|
|
5
|
|
|
import numpy as np |
|
6
|
|
|
|
|
7
|
|
|
try: |
|
8
|
|
|
from fractions import gcd |
|
9
|
|
|
except: |
|
10
|
|
|
from math import gcd |
|
11
|
|
|
|
|
12
|
|
|
from ..base_optimizer import BaseOptimizer |
|
13
|
|
|
|
|
14
|
|
|
|
|
15
|
|
|
class GridSearchOptimizer(BaseOptimizer): |
|
16
|
|
|
name = "Grid Search" |
|
17
|
|
|
_name_ = "grid_search" |
|
18
|
|
|
__name__ = "GridSearchOptimizer" |
|
19
|
|
|
|
|
20
|
|
|
optimizer_type = "global" |
|
21
|
|
|
computationally_expensive = False |
|
22
|
|
|
|
|
23
|
|
|
def __init__(self, *args, step_size=1, **kwargs): |
|
24
|
|
|
super().__init__(*args, **kwargs) |
|
25
|
|
|
self.initial_position = np.zeros((self.conv.n_dimensions,), dtype=int) |
|
26
|
|
|
# current position mapped in [|0,search_space_size-1|] (1D) |
|
27
|
|
|
self.high_dim_pointer = 0 |
|
28
|
|
|
# direction is a generator of our search space (prime with search_space_size) |
|
29
|
|
|
self.direction = None |
|
30
|
|
|
# step_size describes how many steps of size direction are jumped at each iteration |
|
31
|
|
|
self.step_size = step_size |
|
32
|
|
|
|
|
33
|
|
|
def get_direction(self): |
|
34
|
|
|
""" |
|
35
|
|
|
Aim here is to generate a prime number of the search space size we call our direction. |
|
36
|
|
|
As direction is prime with the search space size, we know it is |
|
37
|
|
|
a generator of Z/(search_space_size*Z). |
|
38
|
|
|
""" |
|
39
|
|
|
n_dims = self.conv.n_dimensions |
|
40
|
|
|
search_space_size = self.conv.search_space_size |
|
41
|
|
|
|
|
42
|
|
|
# Find prime number near search_space_size ** (1/n_dims) |
|
43
|
|
|
dim_root = int(np.round(np.power(search_space_size, 1 / n_dims))) |
|
44
|
|
|
is_prime = False |
|
45
|
|
|
|
|
46
|
|
|
while not is_prime: |
|
47
|
|
|
if gcd(int(search_space_size), int(dim_root)) == 1: |
|
48
|
|
|
is_prime = True |
|
49
|
|
|
else: |
|
50
|
|
|
dim_root += -1 |
|
51
|
|
|
|
|
52
|
|
|
return dim_root |
|
53
|
|
|
|
|
54
|
|
|
def grid_move(self): |
|
55
|
|
|
""" |
|
56
|
|
|
We convert our pointer of Z/(search_space_size * Z) in a position of our search space. |
|
57
|
|
|
This algorithm uses a bijection from Z/(search_space_size * Z) -> (Z/dim_1*Z)x...x(Z/dim_n*Z). |
|
58
|
|
|
""" |
|
59
|
|
|
new_pos = [] |
|
60
|
|
|
dim_sizes = self.conv.dim_sizes |
|
61
|
|
|
pointer = self.high_dim_pointer |
|
62
|
|
|
|
|
63
|
|
|
# The coordinate of our new position for each dimension is |
|
64
|
|
|
# the quotient of the pointer by the product of remaining dimensions |
|
65
|
|
|
# Describes a bijection from Z/search_space_size*Z -> (Z/dim_1*Z)x...x(Z/dim_n*Z) |
|
66
|
|
|
for dim in range(len(dim_sizes) - 1): |
|
67
|
|
|
new_pos.append(pointer // np.prod(dim_sizes[dim + 1 :]) % dim_sizes[dim]) |
|
68
|
|
|
pointer = pointer % np.prod(dim_sizes[dim + 1 :]) |
|
69
|
|
|
new_pos.append(pointer) |
|
70
|
|
|
|
|
71
|
|
|
return np.array(new_pos) |
|
72
|
|
|
|
|
73
|
|
|
@BaseOptimizer.track_new_pos |
|
74
|
|
|
def iterate(self): |
|
75
|
|
|
# while loop for constraint opt |
|
76
|
|
|
while True: |
|
77
|
|
|
# If this is the first iteration: |
|
78
|
|
|
# Generate the direction and return initial_position |
|
79
|
|
|
if self.direction is None: |
|
80
|
|
|
self.direction = self.get_direction() |
|
81
|
|
|
|
|
82
|
|
|
pos_new = self.initial_position |
|
83
|
|
|
if self.conv.not_in_constraint(pos_new): |
|
84
|
|
|
return pos_new |
|
85
|
|
|
else: |
|
86
|
|
|
return self.move_random() |
|
87
|
|
|
|
|
88
|
|
|
# If this is not the first iteration: |
|
89
|
|
|
# Update high_dim_pointer by taking a step of size step_size * direction. |
|
90
|
|
|
|
|
91
|
|
|
# Multiple passes are needed in order to observe the entire search space |
|
92
|
|
|
# depending on the step_size parameter. |
|
93
|
|
|
_, current_pass = self.nth_trial, self.high_dim_pointer % self.step_size |
|
94
|
|
|
current_pass_finished = ( |
|
95
|
|
|
(self.nth_trial + 1) * self.step_size // self.conv.search_space_size |
|
96
|
|
|
> self.nth_trial * self.step_size // self.conv.search_space_size |
|
97
|
|
|
) |
|
98
|
|
|
# Begin the next pass if current is finished. |
|
99
|
|
|
if current_pass_finished: |
|
100
|
|
|
self.high_dim_pointer = current_pass + 1 |
|
101
|
|
|
else: |
|
102
|
|
|
# Otherwise update pointer in Z/(search_space_size*Z) |
|
103
|
|
|
# using the prime step direction and step_size. |
|
104
|
|
|
self.high_dim_pointer = ( |
|
105
|
|
|
self.high_dim_pointer + self.step_size * self.direction |
|
106
|
|
|
) % self.conv.search_space_size |
|
107
|
|
|
|
|
108
|
|
|
# Compute corresponding position in our search space. |
|
109
|
|
|
|
|
110
|
|
|
pos_new = self.grid_move() |
|
111
|
|
|
pos_new = self.conv2pos(pos_new) |
|
112
|
|
|
|
|
113
|
|
|
if self.conv.not_in_constraint(pos_new): |
|
114
|
|
|
return pos_new |
|
115
|
|
|
|
|
116
|
|
|
@BaseOptimizer.track_new_score |
|
117
|
|
|
def evaluate(self, score_new): |
|
118
|
|
|
BaseOptimizer.evaluate(self, score_new) |
|
119
|
|
|
|
SimonBlanke /
Gradient-Free-Optimizers
