TheAlgorithms-Python

1
# https://en.wikipedia.org/wiki/Simulated_annealing
2
import math
3
import random
4
from typing import Any
5

6
from .hill_climbing import SearchProblem
7

8

9
def simulated_annealing(
10
    search_prob,
11
    find_max: bool = True,
12
    max_x: float = math.inf,
13
    min_x: float = -math.inf,
14
    max_y: float = math.inf,
15
    min_y: float = -math.inf,
16
    visualization: bool = False,
17
    start_temperate: float = 100,
18
    rate_of_decrease: float = 0.01,
19
    threshold_temp: float = 1,
20
) -> Any:
21
    """
22
    Implementation of the simulated annealing algorithm. We start with a given state,
23
    find all its neighbors. Pick a random neighbor, if that neighbor improves the
24
    solution, we move in that direction, if that neighbor does not improve the solution,
25
    we generate a random real number between 0 and 1, if the number is within a certain
26
    range (calculated using temperature) we move in that direction, else we pick
27
    another neighbor randomly and repeat the process.
28

29
    Args:
30
        search_prob: The search state at the start.
31
        find_max: If True, the algorithm should find the minimum else the minimum.
32
        max_x, min_x, max_y, min_y: the maximum and minimum bounds of x and y.
33
        visualization: If True, a matplotlib graph is displayed.
34
        start_temperate: the initial temperate of the system when the program starts.
35
        rate_of_decrease: the rate at which the temperate decreases in each iteration.
36
        threshold_temp: the threshold temperature below which we end the search
37
    Returns a search state having the maximum (or minimum) score.
38
    """
39
    search_end = False
40
    current_state = search_prob
41
    current_temp = start_temperate
42
    scores = []
43
    iterations = 0
44
    best_state = None
45

46
    while not search_end:
47
        current_score = current_state.score()
48
        if best_state is None or current_score > best_state.score():
49
            best_state = current_state
50
        scores.append(current_score)
51
        iterations += 1
52
        next_state = None
53
        neighbors = current_state.get_neighbors()
54
        while (
55
            next_state is None and neighbors
56
        ):  # till we do not find a neighbor that we can move to
57
            index = random.randint(0, len(neighbors) - 1)  # picking a random neighbor
58
            picked_neighbor = neighbors.pop(index)
59
            change = picked_neighbor.score() - current_score
60

61
            if (
62
                picked_neighbor.x > max_x
63
                or picked_neighbor.x < min_x
64
                or picked_neighbor.y > max_y
65
                or picked_neighbor.y < min_y
66
            ):
67
                continue  # neighbor outside our bounds
68

69
            if not find_max:
70
                change = change * -1  # in case we are finding minimum
71
            if change > 0:  # improves the solution
72
                next_state = picked_neighbor
73
            else:
74
                probability = (math.e) ** (
75
                    change / current_temp
76
                )  # probability generation function
77
                if random.random() < probability:  # random number within probability
78
                    next_state = picked_neighbor
79
        current_temp = current_temp - (current_temp * rate_of_decrease)
80

81
        if current_temp < threshold_temp or next_state is None:
82
            # temperature below threshold, or could not find a suitable neighbor
83
            search_end = True
84
        else:
85
            current_state = next_state
86

87
    if visualization:
88
        from matplotlib import pyplot as plt
89

90
        plt.plot(range(iterations), scores)
91
        plt.xlabel("Iterations")
92
        plt.ylabel("Function values")
93
        plt.show()
94
    return best_state
95

96

97
if __name__ == "__main__":
98

99
    def test_f1(x, y):
100
        return (x**2) + (y**2)
101

102
    # starting the problem with initial coordinates (12, 47)
103
    prob = SearchProblem(x=12, y=47, step_size=1, function_to_optimize=test_f1)
104
    local_min = simulated_annealing(
105
        prob, find_max=False, max_x=100, min_x=5, max_y=50, min_y=-5, visualization=True
106
    )
107
    print(
108
        "The minimum score for f(x, y) = x^2 + y^2 with the domain 100 > x > 5 "
109
        f"and 50 > y > - 5 found via hill climbing: {local_min.score()}"
110
    )
111

112
    # starting the problem with initial coordinates (12, 47)
113
    prob = SearchProblem(x=12, y=47, step_size=1, function_to_optimize=test_f1)
114
    local_min = simulated_annealing(
115
        prob, find_max=True, max_x=100, min_x=5, max_y=50, min_y=-5, visualization=True
116
    )
117
    print(
118
        "The maximum score for f(x, y) = x^2 + y^2 with the domain 100 > x > 5 "
119
        f"and 50 > y > - 5 found via hill climbing: {local_min.score()}"
120
    )
121

122
    def test_f2(x, y):
123
        return (3 * x**2) - (6 * y)
124

125
    prob = SearchProblem(x=3, y=4, step_size=1, function_to_optimize=test_f1)
126
    local_min = simulated_annealing(prob, find_max=False, visualization=True)
127
    print(
128
        "The minimum score for f(x, y) = 3*x^2 - 6*y found via hill climbing: "
129
        f"{local_min.score()}"
130
    )
131

132
    prob = SearchProblem(x=3, y=4, step_size=1, function_to_optimize=test_f1)
133
    local_min = simulated_annealing(prob, find_max=True, visualization=True)
134
    print(
135
        "The maximum score for f(x, y) = 3*x^2 - 6*y found via hill climbing: "
136
        f"{local_min.score()}"
137
    )
138