Implementation of the simulated annealing algorithm. We start with a given state, find all its neighbors. Pick a random neighbor, if that neighbor improves the solution, we move in that direction, if that neighbor does not improve the solution, we generate a random real number betwe
(
search_prob,
find_max: bool = True,
max_x: float = math.inf,
min_x: float = -math.inf,
max_y: float = math.inf,
min_y: float = -math.inf,
visualization: bool = False,
start_temperate: float = 100,
rate_of_decrease: float = 0.01,
threshold_temp: float = 1,
)
| 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 | ): |
no test coverage detected