TheAlgorithms-Python

1
# https://en.wikipedia.org/wiki/Hill_climbing
2
import math
3

4

5
class SearchProblem:
6
    """
7
    An interface to define search problems.
8
    The interface will be illustrated using the example of mathematical function.
9
    """
10

11
    def __init__(self, x: int, y: int, step_size: int, function_to_optimize):
12
        """
13
        The constructor of the search problem.
14

15
        x: the x coordinate of the current search state.
16
        y: the y coordinate of the current search state.
17
        step_size: size of the step to take when looking for neighbors.
18
        function_to_optimize: a function to optimize having the signature f(x, y).
19
        """
20
        self.x = x
21
        self.y = y
22
        self.step_size = step_size
23
        self.function = function_to_optimize
24

25
    def score(self) -> int:
26
        """
27
        Returns the output of the function called with current x and y coordinates.
28
        >>> def test_function(x, y):
29
        ...     return x + y
30
        >>> SearchProblem(0, 0, 1, test_function).score()  # 0 + 0 = 0
31
        0
32
        >>> SearchProblem(5, 7, 1, test_function).score()  # 5 + 7 = 12
33
        12
34
        """
35
        return self.function(self.x, self.y)
36

37
    def get_neighbors(self):
38
        """
39
        Returns a list of coordinates of neighbors adjacent to the current coordinates.
40

41
        Neighbors:
42
        | 0 | 1 | 2 |
43
        | 3 | _ | 4 |
44
        | 5 | 6 | 7 |
45
        """
46
        step_size = self.step_size
47
        return [
48
            SearchProblem(x, y, step_size, self.function)
49
            for x, y in (
50
                (self.x - step_size, self.y - step_size),
51
                (self.x - step_size, self.y),
52
                (self.x - step_size, self.y + step_size),
53
                (self.x, self.y - step_size),
54
                (self.x, self.y + step_size),
55
                (self.x + step_size, self.y - step_size),
56
                (self.x + step_size, self.y),
57
                (self.x + step_size, self.y + step_size),
58
            )
59
        ]
60

61
    def __hash__(self):
62
        """
63
        hash the string representation of the current search state.
64
        """
65
        return hash(str(self))
66

67
    def __eq__(self, obj):
68
        """
69
        Check if the 2 objects are equal.
70
        """
71
        if isinstance(obj, SearchProblem):
72
            return hash(str(self)) == hash(str(obj))
73
        return False
74

75
    def __str__(self):
76
        """
77
        string representation of the current search state.
78
        >>> str(SearchProblem(0, 0, 1, None))
79
        'x: 0 y: 0'
80
        >>> str(SearchProblem(2, 5, 1, None))
81
        'x: 2 y: 5'
82
        """
83
        return f"x: {self.x} y: {self.y}"
84

85

86
def hill_climbing(
87
    search_prob,
88
    find_max: bool = True,
89
    max_x: float = math.inf,
90
    min_x: float = -math.inf,
91
    max_y: float = math.inf,
92
    min_y: float = -math.inf,
93
    visualization: bool = False,
94
    max_iter: int = 10000,
95
) -> SearchProblem:
96
    """
97
    Implementation of the hill climbling algorithm.
98
    We start with a given state, find all its neighbors,
99
    move towards the neighbor which provides the maximum (or minimum) change.
100
    We keep doing this until we are at a state where we do not have any
101
    neighbors which can improve the solution.
102
        Args:
103
            search_prob: The search state at the start.
104
            find_max: If True, the algorithm should find the maximum else the minimum.
105
            max_x, min_x, max_y, min_y: the maximum and minimum bounds of x and y.
106
            visualization: If True, a matplotlib graph is displayed.
107
            max_iter: number of times to run the iteration.
108
        Returns a search state having the maximum (or minimum) score.
109
    """
110
    current_state = search_prob
111
    scores = []  # list to store the current score at each iteration
112
    iterations = 0
113
    solution_found = False
114
    visited = set()
115
    while not solution_found and iterations < max_iter:
116
        visited.add(current_state)
117
        iterations += 1
118
        current_score = current_state.score()
119
        scores.append(current_score)
120
        neighbors = current_state.get_neighbors()
121
        max_change = -math.inf
122
        min_change = math.inf
123
        next_state = None  # to hold the next best neighbor
124
        for neighbor in neighbors:
125
            if neighbor in visited:
126
                continue  # do not want to visit the same state again
127
            if (
128
                neighbor.x > max_x
129
                or neighbor.x < min_x
130
                or neighbor.y > max_y
131
                or neighbor.y < min_y
132
            ):
133
                continue  # neighbor outside our bounds
134
            change = neighbor.score() - current_score
135
            if find_max:  # finding max
136
                # going to direction with greatest ascent
137
                if change > max_change and change > 0:
138
                    max_change = change
139
                    next_state = neighbor
140
            elif change < min_change and change < 0:  # finding min
141
                # to direction with greatest descent
142
                min_change = change
143
                next_state = neighbor
144
        if next_state is not None:
145
            # we found at least one neighbor which improved the current state
146
            current_state = next_state
147
        else:
148
            # since we have no neighbor that improves the solution we stop the search
149
            solution_found = True
150

151
    if visualization:
152
        from matplotlib import pyplot as plt
153

154
        plt.plot(range(iterations), scores)
155
        plt.xlabel("Iterations")
156
        plt.ylabel("Function values")
157
        plt.show()
158

159
    return current_state
160

161

162
if __name__ == "__main__":
163
    import doctest
164

165
    doctest.testmod()
166

167
    def test_f1(x, y):
168
        return (x**2) + (y**2)
169

170
    # starting the problem with initial coordinates (3, 4)
171
    prob = SearchProblem(x=3, y=4, step_size=1, function_to_optimize=test_f1)
172
    local_min = hill_climbing(prob, find_max=False)
173
    print(
174
        "The minimum score for f(x, y) = x^2 + y^2 found via hill climbing: "
175
        f"{local_min.score()}"
176
    )
177

178
    # starting the problem with initial coordinates (12, 47)
179
    prob = SearchProblem(x=12, y=47, step_size=1, function_to_optimize=test_f1)
180
    local_min = hill_climbing(
181
        prob, find_max=False, max_x=100, min_x=5, max_y=50, min_y=-5, visualization=True
182
    )
183
    print(
184
        "The minimum score for f(x, y) = x^2 + y^2 with the domain 100 > x > 5 "
185
        f"and 50 > y > - 5 found via hill climbing: {local_min.score()}"
186
    )
187

188
    def test_f2(x, y):
189
        return (3 * x**2) - (6 * y)
190

191
    prob = SearchProblem(x=3, y=4, step_size=1, function_to_optimize=test_f1)
192
    local_min = hill_climbing(prob, find_max=True)
193
    print(
194
        "The maximum score for f(x, y) = x^2 + y^2 found via hill climbing: "
195
        f"{local_min.score()}"
196
    )
197