Implementation of the hill climbling algorithm. We start with a given state, find all its neighbors, move towards the neighbor which provides the maximum (or minimum) change. We keep doing this until we are at a state where we do not have any neighbors which can improve the solu
(
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,
max_iter: int = 10000,
)
| 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 |
no test coverage detected