Overview

Search for #TODO tags to quickly find the functions you are required to implement. Descriptions and pseudocode for each function are provided in the notebook, along with links to external readings.

Complete the TravelingSalesmanProblem class by implementing the successors$(),$ get$\_$successor$(),$ and $\_\_$get$\_$value$()$ methods

Complete the HillClimbingSolver class

Complete the LocalBeamSolver class

Complete the SimulatedAnnealingSolver class

Complete the LAHCSolver class

In $[]$:

import json

import math # contains sqrt$,$ exp, pow, etc.

import random

import time

$$

from collections import deque

from helpers import $*$

$$

import matplotlib.pyplot as plt

import matplotlib.image as mpimg

$\%$matplotlib inlineI. Hill Climbing

Next, complete the solve$()$ method for the HillClimbingSolver class below.

The hill$-$climbing search algorithm is the most basic local search technique. At each step the current node is replaced by the neighbor with the highest value. $[$AIMA $3$rd ed$,$ Chapter $4]$

Pseudocode for the hill climbing function from the AIMA textbook. Note that our Problem class is already a "node", so the MAKE$-$NODE line is not required.

In $[]$:

class HillClimbingSolver:

$"""$

Parameters

$----------$

epochs : int

The upper limit on the number of rounds to perform hill climbing; the

algorithm terminates and returns the best observed result when this

iteration limit is exceeded.

$"""$

def $\_\_$init$\_\_($self$,$ epochs$=100)$:

self.epochs $=$ epochs

def solve$($self$,$ problem$)$:

$"""$ Optimize the input problem by applying greedy hill climbing.

$$

Parameters

$----------$

problem : Problem

An initialized instance of an optimization problem. The Problem class

interface must implement a callable method "successors$()"$ which returns

a iterable sequence $($i$.$e$.,$ a list or generator$)$ of the states in the

neighborhood of the current state, and a property "utility" which returns

a fitness score for the state. $($See the $`$TravelingSalesmanProblem$`$ class

for more details.$)$

$$

Returns

$-------$

Problem

The resulting approximate solution state of the optimization problem

Notes

$-----$

$(1)$ DO NOT include the MAKE$-$NODE line from the AIMA pseudocode

$"""$

# TODO: Implement this function!

for $\_$ in $(3)$:

neihbor $=$ max$($problem$.$successors$(),)$

if$($neihbor$.$some $<$ problem.something$)$:

raise NotImplementedError

$$

Run the Hill Climbing Solver

In $[]$:

solver $=$ HillClimbingSolver$($epochs$=100)$

start$\_$time $=$ time.perf$\_$counter$()$

result $=$ solver.solve$($capitals$\_$tsp$)$

stop$\_$time $=$ time.perf$\_$counter$()$

print$("$solution$\_$time: $\{$:$\mathrm{.}2$f$\}$ milliseconds".format$(($stop$\_$time $-$ start$\_$time$)*1000))$

print$("$Initial path length: $\{$:$\mathrm{.}2$f$\}".$format$(-$capitals$\_$tsp$.$utility$))$

print$("$Final path length: $\{$:$\mathrm{.}2$f$\}".$format$(-$result.utility$))$

print$($result$.$path$)$

show$\_$path$($result$.$coords, starting$\_$city$)$