-
Exercise implementing the Simulated Annealing algorithm in a Jupyter Notebook App (acronym for first set of targeted languages Julia, Python, and R) that combines code and rich text elements for data science analysis in real-time, and includes an IPython kernel back-end. Apply the implementation to solve the Traveling Salesman Problem (TSP) between US state capitals.
-
Guide on Jupiter Notebook https://www.datacamp.com/community/tutorials/tutorial-jupyter-notebook#gs.WPbJuKE
-
Install Jupyter Notebook App with Miniconda http://jupyter.readthedocs.io/en/latest/install.html
pip3 install --upgrade pip setuptools pip3 install jupyter pip3 install json copy numpy matplotlib sys math
-
Launch Jupyter Notebook App
jupyter notebook AIND-Simulated_Annealing.ipynb
-
Run code:
- Click any section containing a code snippet and go to menu: Cells > Run All, then view the outputs shown below the code snippets
# show Python version being used
import sys
!pip3 install math
import math
print("{}".format(sys.version))
# show Python 2.7 and 3.6 executable directories
!which pip
!which pip3
# show jupyter config paths http://jupyter.readthedocs.io/en/latest/projects/jupyter-directories.html
!jupyter --paths
!pip3 install math
import math
min_T = 1e-10 # 0.0000000001
ct = 1 # iteration
current_state = problem # initial problem state
delta_E = 0 # represents change in the score E
def random_pick_for_probability(states, probabilities):
x = random.uniform(0, 1)
cumulative_probability = 0.0
for item, item_probability in zip(states, probabilities):
cumulative_probability += item_probability
if x < cumulative_probability: break
return item
while True:
T = schedule(ct)
# as temperature approaches 0 return early when temperature
# falls below termination condition value
# (since temperature reaching 0 gives undefined answer)
if T < min_T:
return current_state
successors = problem.successors()
# select positions randomly from neighboring region
next_index = random.randint(0, len(successors))
next_state = successors[next_index]
delta_E = next_state.get_value() - current_state.get_value()
# if new random position improves score E (up the gradient)
# then select it (up the gradient)
if delta_E > 0:
current_state = next_state
# if new random position lessons score E (down the gradient)
# then select it based on a probability
# reference: https://www.safaribooksonline.com/library/view/python-cookbook-2nd/0596007973/ch04s22.html
else:
prob = math.exp(delta_E/T)
current_state = random_pick_for_probability( \
[current_state, next_state], [1-prob, prob])
ct += 1
successor_problems = []
current_path = self.path
path_length = len(current_path)
for i in range(0, path_length):
new_path = copy.deepcopy(self.path)
new_path[i], new_path[(i + 1) % path_length] = new_path[(i + 1) % path_length], new_path[i]
successor_problems.append(TravelingSalesmanProblem(new_path))
return successor_problems
current_path = self.path
path_length = len(current_path)
cost_total = 0
for i in range(0, path_length):
current_city_coords = np.array(current_path[i % path_length][1])
next_city_coords = np.array(current_path[(i + 1) % path_length][1])
cost_total += np.sqrt(np.sum(np.square(current_city_coords - next_city_coords)))
# Alternative #1:
# x1, y1 = self.coords[i]
# x2, y2 = self.coords[(i + 1) % path_length]
# cost_total += math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
# Alternative #2:
# coords = zip(self.coords, self.coords[1:] + self.coords[0:1])
# for c1, c2 in coords:
# x1, y1 = c1
# x2, y2 = c2
# cost_total += np.hypot(x1 - x2, y1 - y2)
return -1 * cost_total
- Merge all code snippets into single code snippet to overcome error