Newer
Older
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
"<div class=\"highlight\"><pre><span></span><span class=\"k\">def</span> <span class=\"nf\">recursive_best_first_search</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"p\">,</span> <span class=\"n\">h</span><span class=\"o\">=</span><span class=\"bp\">None</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""[Figure 3.26] Recursive best-first search (RBFS) is an</span>\n",
"<span class=\"sd\"> informative search algorithm. Like A*, it uses the heuristic</span>\n",
"<span class=\"sd\"> f(n) = g(n) + h(n) to determine the next node to expand, making</span>\n",
"<span class=\"sd\"> it both optimal and complete (iff the heuristic is consistent).</span>\n",
"<span class=\"sd\"> To reduce memory consumption, RBFS uses a depth first search</span>\n",
"<span class=\"sd\"> and only retains the best f values of its ancestors."""</span>\n",
" <span class=\"n\">h</span> <span class=\"o\">=</span> <span class=\"n\">memoize</span><span class=\"p\">(</span><span class=\"n\">h</span> <span class=\"ow\">or</span> <span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">h</span><span class=\"p\">,</span> <span class=\"s1\">'h'</span><span class=\"p\">)</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">RBFS</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"p\">,</span> <span class=\"n\">node</span><span class=\"p\">,</span> <span class=\"n\">flimit</span><span class=\"p\">):</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">goal_test</span><span class=\"p\">(</span><span class=\"n\">node</span><span class=\"o\">.</span><span class=\"n\">state</span><span class=\"p\">):</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">node</span><span class=\"p\">,</span> <span class=\"mi\">0</span> <span class=\"c1\"># (The second value is immaterial)</span>\n",
" <span class=\"n\">successors</span> <span class=\"o\">=</span> <span class=\"n\">node</span><span class=\"o\">.</span><span class=\"n\">expand</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"p\">)</span>\n",
" <span class=\"k\">if</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"n\">successors</span><span class=\"p\">)</span> <span class=\"o\">==</span> <span class=\"mi\">0</span><span class=\"p\">:</span>\n",
" <span class=\"k\">return</span> <span class=\"bp\">None</span><span class=\"p\">,</span> <span class=\"n\">infinity</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">s</span> <span class=\"ow\">in</span> <span class=\"n\">successors</span><span class=\"p\">:</span>\n",
" <span class=\"n\">s</span><span class=\"o\">.</span><span class=\"n\">f</span> <span class=\"o\">=</span> <span class=\"nb\">max</span><span class=\"p\">(</span><span class=\"n\">s</span><span class=\"o\">.</span><span class=\"n\">path_cost</span> <span class=\"o\">+</span> <span class=\"n\">h</span><span class=\"p\">(</span><span class=\"n\">s</span><span class=\"p\">),</span> <span class=\"n\">node</span><span class=\"o\">.</span><span class=\"n\">f</span><span class=\"p\">)</span>\n",
" <span class=\"k\">while</span> <span class=\"bp\">True</span><span class=\"p\">:</span>\n",
" <span class=\"c1\"># Order by lowest f value</span>\n",
" <span class=\"n\">successors</span><span class=\"o\">.</span><span class=\"n\">sort</span><span class=\"p\">(</span><span class=\"n\">key</span><span class=\"o\">=</span><span class=\"k\">lambda</span> <span class=\"n\">x</span><span class=\"p\">:</span> <span class=\"n\">x</span><span class=\"o\">.</span><span class=\"n\">f</span><span class=\"p\">)</span>\n",
" <span class=\"n\">best</span> <span class=\"o\">=</span> <span class=\"n\">successors</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">best</span><span class=\"o\">.</span><span class=\"n\">f</span> <span class=\"o\">></span> <span class=\"n\">flimit</span><span class=\"p\">:</span>\n",
" <span class=\"k\">return</span> <span class=\"bp\">None</span><span class=\"p\">,</span> <span class=\"n\">best</span><span class=\"o\">.</span><span class=\"n\">f</span>\n",
" <span class=\"k\">if</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"n\">successors</span><span class=\"p\">)</span> <span class=\"o\">></span> <span class=\"mi\">1</span><span class=\"p\">:</span>\n",
" <span class=\"n\">alternative</span> <span class=\"o\">=</span> <span class=\"n\">successors</span><span class=\"p\">[</span><span class=\"mi\">1</span><span class=\"p\">]</span><span class=\"o\">.</span><span class=\"n\">f</span>\n",
" <span class=\"k\">else</span><span class=\"p\">:</span>\n",
" <span class=\"n\">alternative</span> <span class=\"o\">=</span> <span class=\"n\">infinity</span>\n",
" <span class=\"n\">result</span><span class=\"p\">,</span> <span class=\"n\">best</span><span class=\"o\">.</span><span class=\"n\">f</span> <span class=\"o\">=</span> <span class=\"n\">RBFS</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"p\">,</span> <span class=\"n\">best</span><span class=\"p\">,</span> <span class=\"nb\">min</span><span class=\"p\">(</span><span class=\"n\">flimit</span><span class=\"p\">,</span> <span class=\"n\">alternative</span><span class=\"p\">))</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">result</span> <span class=\"ow\">is</span> <span class=\"ow\">not</span> <span class=\"bp\">None</span><span class=\"p\">:</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">result</span><span class=\"p\">,</span> <span class=\"n\">best</span><span class=\"o\">.</span><span class=\"n\">f</span>\n",
"\n",
" <span class=\"n\">node</span> <span class=\"o\">=</span> <span class=\"n\">Node</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">initial</span><span class=\"p\">)</span>\n",
" <span class=\"n\">node</span><span class=\"o\">.</span><span class=\"n\">f</span> <span class=\"o\">=</span> <span class=\"n\">h</span><span class=\"p\">(</span><span class=\"n\">node</span><span class=\"p\">)</span>\n",
" <span class=\"n\">result</span><span class=\"p\">,</span> <span class=\"n\">bestf</span> <span class=\"o\">=</span> <span class=\"n\">RBFS</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"p\">,</span> <span class=\"n\">node</span><span class=\"p\">,</span> <span class=\"n\">infinity</span><span class=\"p\">)</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">result</span>\n",
"</pre></div>\n",
"</body>\n",
"</html>\n"
],
"text/plain": [
"<IPython.core.display.HTML object>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This is how `recursive_best_first_search` can solve the `romania_problem`"
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['Sibiu', 'Rimnicu', 'Pitesti', 'Bucharest']"
]
},
"execution_count": 37,
"metadata": {},
"output_type": "execute_result"
}
],
"recursive_best_first_search(romania_problem).solution()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"`recursive_best_first_search` can be used to solve the 8 puzzle problem too, as discussed later."
]
},
{
"cell_type": "code",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['UP', 'LEFT', 'UP', 'LEFT', 'DOWN', 'RIGHT', 'RIGHT', 'DOWN']"
]
},
"execution_count": 38,
"metadata": {},
"output_type": "execute_result"
"puzzle = EightPuzzle((2, 4, 3, 1, 5, 6, 7, 8, 0))\n",
"assert puzzle.check_solvability((2, 4, 3, 1, 5, 6, 7, 8, 0))\n",
"recursive_best_first_search(puzzle).solution()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## A* HEURISTICS\n",
"\n",
"Different heuristics provide different efficiency in solving A* problems which are generally defined by the number of explored nodes as well as the branching factor. With the classic 8 puzzle we can show the efficiency of different heuristics through the number of explored nodes.\n",
"\n",
"### 8 Puzzle Problem\n",
"\n",
"The *8 Puzzle Problem* consists of a 3x3 tray in which the goal is to get the initial configuration to the goal state by shifting the numbered tiles into the blank space.\n",
"\n",
"example:- \n",
"\n",
" Initial State Goal State\n",
" | 7 | 2 | 4 | | 1 | 2 | 3 |\n",
" | 5 | 0 | 6 | | 4 | 5 | 6 |\n",
" | 8 | 3 | 1 | | 7 | 8 | 0 |\n",
" \n",
"We have a total of 9 blank tiles giving us a total of 9! initial configuration but not all of these are solvable. The solvability of a configuration can be checked by calculating the Inversion Permutation. If the total Inversion Permutation is even then the initial configuration is solvable else the initial configuration is not solvable which means that only 9!/2 initial states lead to a solution.\n",
"<br>\n",
"Let's define our goal state."
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {},
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Heuristics :-\n",
"\n",
"1) Manhattan Distance:- For the 8 puzzle problem Manhattan distance is defined as the distance of a tile from its goal state( for the tile numbered '1' in the initial configuration Manhattan distance is 4 \"2 for left and 2 for upward displacement\").\n",
"\n",
"2) No. of Misplaced Tiles:- The heuristic calculates the number of misplaced tiles between the current state and goal state.\n",
"\n",
"3) Sqrt of Manhattan Distance:- It calculates the square root of Manhattan distance.\n",
"\n",
"4) Max Heuristic:- It assign the score as the maximum between \"Manhattan Distance\" and \"No. of Misplaced Tiles\"."
]
},
{
"cell_type": "code",
"execution_count": 40,
"metadata": {},
"# Heuristics for 8 Puzzle Problem\n",
"def linear(node):\n",
" return sum([1 if node.state[i] != goal[i] else 0 for i in range(8)])\n",
"\n",
"def manhattan(node):\n",
" state = node.state\n",
" index_goal = {0:[2,2], 1:[0,0], 2:[0,1], 3:[0,2], 4:[1,0], 5:[1,1], 6:[1,2], 7:[2,0], 8:[2,1]}\n",
" index_state = {}\n",
" index = [[0,0], [0,1], [0,2], [1,0], [1,1], [1,2], [2,0], [2,1], [2,2]]\n",
" x, y = 0, 0\n",
" for i in range(len(state)):\n",
" index_state[state[i]] = index[i]\n",
" mhd = 0\n",
" \n",
" for i in range(8):\n",
" for j in range(2):\n",
" mhd = abs(index_goal[i][j] - index_state[i][j]) + mhd\n",
" \n",
" return mhd\n",
"def sqrt_manhattan(node):\n",
" state = node.state\n",
" index_goal = {0:[2,2], 1:[0,0], 2:[0,1], 3:[0,2], 4:[1,0], 5:[1,1], 6:[1,2], 7:[2,0], 8:[2,1]}\n",
" index_state = {}\n",
" index = [[0,0], [0,1], [0,2], [1,0], [1,1], [1,2], [2,0], [2,1], [2,2]]\n",
" x, y = 0, 0\n",
" for i in range(len(state)):\n",
" index_state[state[i]] = index[i]\n",
" \n",
" mhd = 0\n",
" \n",
" for i in range(8):\n",
" for j in range(2):\n",
" mhd = (index_goal[i][j] - index_state[i][j])**2 + mhd\n",
" \n",
" return math.sqrt(mhd)\n",
"\n",
"def max_heuristic(node):\n",
" score1 = manhattan(node)\n",
" score2 = linear(node)\n",
" return max(score1, score2)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can solve the puzzle using the `astar_search` method."
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 41,
"metadata": {},
"output_type": "execute_result"
}
],
"# Solving the puzzle \n",
"puzzle = EightPuzzle((2, 4, 3, 1, 5, 6, 7, 8, 0))\n",
"puzzle.check_solvability((2, 4, 3, 1, 5, 6, 7, 8, 0)) # checks whether the initialized configuration is solvable or not"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This case is solvable, let's proceed.\n",
"<br>\n",
"The default heuristic function returns the number of misplaced tiles."
]
},
{
"cell_type": "code",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['UP', 'LEFT', 'UP', 'LEFT', 'DOWN', 'RIGHT', 'RIGHT', 'DOWN']"
"metadata": {},
"output_type": "execute_result"
}
],
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In the following cells, we use different heuristic functions.\n",
"<br>"
"cell_type": "code",
"execution_count": 43,
"outputs": [
{
"data": {
"text/plain": [
"['UP', 'LEFT', 'UP', 'LEFT', 'DOWN', 'RIGHT', 'RIGHT', 'DOWN']"
]
},
"execution_count": 43,
"metadata": {},
"output_type": "execute_result"
}
],
"astar_search(puzzle, linear).solution()"
]
},
{
"cell_type": "code",
2298
2299
2300
2301
2302
2303
2304
2305
2306
2307
2308
2309
2310
2311
2312
2313
2314
2315
2316
2317
2318
2319
2320
"execution_count": 44,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/plain": [
"['LEFT', 'UP', 'UP', 'LEFT', 'DOWN', 'RIGHT', 'DOWN', 'RIGHT']"
]
},
"execution_count": 44,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"astar_search(puzzle, manhattan).solution()"
]
},
{
"cell_type": "code",
"execution_count": 45,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['LEFT', 'UP', 'UP', 'LEFT', 'DOWN', 'RIGHT', 'DOWN', 'RIGHT']"
}
],
"source": [
2335
2336
2337
2338
2339
2340
2341
2342
2343
2344
2345
2346
2347
2348
2349
2350
2351
2352
2353
2354
2355
"astar_search(puzzle, sqrt_manhattan).solution()"
]
},
{
"cell_type": "code",
"execution_count": 46,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['LEFT', 'UP', 'UP', 'LEFT', 'DOWN', 'RIGHT', 'DOWN', 'RIGHT']"
]
},
"execution_count": 46,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"astar_search(puzzle, max_heuristic).solution()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"And here's how `recursive_best_first_search` can be used to solve this problem too."
]
},
{
"cell_type": "code",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['LEFT', 'UP', 'UP', 'LEFT', 'DOWN', 'RIGHT', 'DOWN', 'UP', 'DOWN', 'RIGHT']"
}
],
"source": [
"recursive_best_first_search(puzzle, manhattan).solution()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Even though all the heuristic functions give the same solution, the difference lies in the computation time.\n",
"<br>\n",
"This might make all the difference in a scenario where high computational efficiency is required.\n",
"<br>\n",
"Let's define a few puzzle states and time `astar_search` for every heuristic function.\n",
"We will use the %%timeit magic for this."
]
},
{
"cell_type": "code",
"execution_count": 48,
"metadata": {},
"outputs": [],
"source": [
"puzzle_1 = EightPuzzle((2, 4, 3, 1, 5, 6, 7, 8, 0))\n",
"puzzle_2 = EightPuzzle((1, 2, 3, 4, 5, 6, 0, 7, 8))\n",
"puzzle_3 = EightPuzzle((1, 2, 3, 4, 5, 7, 8, 6, 0))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The default heuristic function is the same as the `linear` heuristic function, but we'll still check both."
]
},
{
"cell_type": "code",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"3.24 ms ± 190 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
]
}
],
"source": [
"%%timeit\n",
"astar_search(puzzle_1)\n",
"astar_search(puzzle_2)\n",
"astar_search(puzzle_3)"
]
},
{
"cell_type": "code",
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"3.68 ms ± 368 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
]
}
],
"%%timeit\n",
"astar_search(puzzle_1, linear)\n",
"astar_search(puzzle_2, linear)\n",
"astar_search(puzzle_3, linear)"
]
},
{
"cell_type": "code",
"execution_count": 51,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"3.12 ms ± 88.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
]
}
],
"%%timeit\n",
"astar_search(puzzle_1, manhattan)\n",
"astar_search(puzzle_2, manhattan)\n",
"astar_search(puzzle_3, manhattan)"
]
},
{
"cell_type": "code",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"22.7 ms ± 1.69 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
]
}
],
"source": [
"%%timeit\n",
"astar_search(puzzle_1, sqrt_manhattan)\n",
"astar_search(puzzle_2, sqrt_manhattan)\n",
"astar_search(puzzle_3, sqrt_manhattan)"
"cell_type": "code",
"execution_count": 53,
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"3.91 ms ± 434 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
]
}
],
"%%timeit\n",
"astar_search(puzzle_1, max_heuristic)\n",
"astar_search(puzzle_2, max_heuristic)\n",
"astar_search(puzzle_3, max_heuristic)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can infer that the `manhattan` heuristic function works the fastest.\n",
"<br>\n",
"`sqrt_manhattan` has an extra `sqrt` operation which makes it quite a lot slower than the others.\n",
"<br>\n",
"`max_heuristic` should have been a bit slower as it calls two functions, but in this case, those values were already calculated which saved some time.\n",
"Feel free to play around with these functions."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For comparison, this is how RBFS performs on this problem."
]
},
{
"cell_type": "code",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"140 ms ± 9.89 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
]
}
],
"source": [
"%%timeit\n",
"recursive_best_first_search(puzzle_1, linear)\n",
"recursive_best_first_search(puzzle_2, linear)\n",
"recursive_best_first_search(puzzle_3, linear)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"It is quite a lot slower than `astar_search` as we can see."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## HILL CLIMBING\n",
"\n",
"Hill Climbing is a heuristic search used for optimization problems.\n",
"Given a large set of inputs and a good heuristic function, it tries to find a sufficiently good solution to the problem. \n",
"This solution may or may not be the global optimum.\n",
"The algorithm is a variant of generate and test algorithm. \n",
"As a whole, the algorithm works as follows:\n",
"- Evaluate the initial state.\n",
"- If it is equal to the goal state, return.\n",
"- Find a neighboring state (one which is heuristically similar to the current state)\n",
"- Evaluate this state. If it is closer to the goal state than before, replace the initial state with this state and repeat these steps.\n",
"<br>"
]
},
{
"cell_type": "code",
"metadata": {},
"outputs": [
{
2586
2587
2588
2589
2590
2591
2592
2593
2594
2595
2596
2597
2598
2599
2600
2601
2602
2603
2604
2605
2606
2607
2608
2609
2610
2611
2612
2613
2614
2615
2616
2617
2618
2619
2620
2621
2622
2623
2624
2625
2626
2627
2628
2629
2630
2631
2632
2633
2634
2635
2636
2637
2638
2639
2640
2641
2642
2643
2644
2645
2646
2647
2648
2649
2650
2651
2652
2653
2654
2655
2656
2657
2658
2659
2660
2661
2662
2663
2664
2665
2666
2667
2668
2669
2670
2671
2672
2673
2674
2675
2676
2677
2678
2679
2680
2681
2682
2683
2684
2685
2686
2687
2688
2689
2690
2691
2692
2693
2694
2695
2696
2697
"data": {
"text/html": [
"<!DOCTYPE html PUBLIC \"-//W3C//DTD HTML 4.01//EN\"\n",
" \"http://www.w3.org/TR/html4/strict.dtd\">\n",
"\n",
"<html>\n",
"<head>\n",
" <title></title>\n",
" <meta http-equiv=\"content-type\" content=\"text/html; charset=None\">\n",
" <style type=\"text/css\">\n",
"td.linenos { background-color: #f0f0f0; padding-right: 10px; }\n",
"span.lineno { background-color: #f0f0f0; padding: 0 5px 0 5px; }\n",
"pre { line-height: 125%; }\n",
"body .hll { background-color: #ffffcc }\n",
"body { background: #f8f8f8; }\n",
"body .c { color: #408080; font-style: italic } /* Comment */\n",
"body .err { border: 1px solid #FF0000 } /* Error */\n",
"body .k { color: #008000; font-weight: bold } /* Keyword */\n",
"body .o { color: #666666 } /* Operator */\n",
"body .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
"body .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
"body .cp { color: #BC7A00 } /* Comment.Preproc */\n",
"body .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
"body .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
"body .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
"body .gd { color: #A00000 } /* Generic.Deleted */\n",
"body .ge { font-style: italic } /* Generic.Emph */\n",
"body .gr { color: #FF0000 } /* Generic.Error */\n",
"body .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
"body .gi { color: #00A000 } /* Generic.Inserted */\n",
"body .go { color: #888888 } /* Generic.Output */\n",
"body .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
"body .gs { font-weight: bold } /* Generic.Strong */\n",
"body .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
"body .gt { color: #0044DD } /* Generic.Traceback */\n",
"body .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
"body .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
"body .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
"body .kp { color: #008000 } /* Keyword.Pseudo */\n",
"body .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
"body .kt { color: #B00040 } /* Keyword.Type */\n",
"body .m { color: #666666 } /* Literal.Number */\n",
"body .s { color: #BA2121 } /* Literal.String */\n",
"body .na { color: #7D9029 } /* Name.Attribute */\n",
"body .nb { color: #008000 } /* Name.Builtin */\n",
"body .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
"body .no { color: #880000 } /* Name.Constant */\n",
"body .nd { color: #AA22FF } /* Name.Decorator */\n",
"body .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
"body .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
"body .nf { color: #0000FF } /* Name.Function */\n",
"body .nl { color: #A0A000 } /* Name.Label */\n",
"body .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
"body .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
"body .nv { color: #19177C } /* Name.Variable */\n",
"body .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
"body .w { color: #bbbbbb } /* Text.Whitespace */\n",
"body .mb { color: #666666 } /* Literal.Number.Bin */\n",
"body .mf { color: #666666 } /* Literal.Number.Float */\n",
"body .mh { color: #666666 } /* Literal.Number.Hex */\n",
"body .mi { color: #666666 } /* Literal.Number.Integer */\n",
"body .mo { color: #666666 } /* Literal.Number.Oct */\n",
"body .sa { color: #BA2121 } /* Literal.String.Affix */\n",
"body .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
"body .sc { color: #BA2121 } /* Literal.String.Char */\n",
"body .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
"body .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
"body .s2 { color: #BA2121 } /* Literal.String.Double */\n",
"body .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
"body .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
"body .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
"body .sx { color: #008000 } /* Literal.String.Other */\n",
"body .sr { color: #BB6688 } /* Literal.String.Regex */\n",
"body .s1 { color: #BA2121 } /* Literal.String.Single */\n",
"body .ss { color: #19177C } /* Literal.String.Symbol */\n",
"body .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
"body .fm { color: #0000FF } /* Name.Function.Magic */\n",
"body .vc { color: #19177C } /* Name.Variable.Class */\n",
"body .vg { color: #19177C } /* Name.Variable.Global */\n",
"body .vi { color: #19177C } /* Name.Variable.Instance */\n",
"body .vm { color: #19177C } /* Name.Variable.Magic */\n",
"body .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
"\n",
" </style>\n",
"</head>\n",
"<body>\n",
"<h2></h2>\n",
"\n",
"<div class=\"highlight\"><pre><span></span><span class=\"k\">def</span> <span class=\"nf\">hill_climbing</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""From the initial node, keep choosing the neighbor with highest value,</span>\n",
"<span class=\"sd\"> stopping when no neighbor is better. [Figure 4.2]"""</span>\n",
" <span class=\"n\">current</span> <span class=\"o\">=</span> <span class=\"n\">Node</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">initial</span><span class=\"p\">)</span>\n",
" <span class=\"k\">while</span> <span class=\"bp\">True</span><span class=\"p\">:</span>\n",
" <span class=\"n\">neighbors</span> <span class=\"o\">=</span> <span class=\"n\">current</span><span class=\"o\">.</span><span class=\"n\">expand</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"p\">)</span>\n",
" <span class=\"k\">if</span> <span class=\"ow\">not</span> <span class=\"n\">neighbors</span><span class=\"p\">:</span>\n",
" <span class=\"k\">break</span>\n",
" <span class=\"n\">neighbor</span> <span class=\"o\">=</span> <span class=\"n\">argmax_random_tie</span><span class=\"p\">(</span><span class=\"n\">neighbors</span><span class=\"p\">,</span>\n",
" <span class=\"n\">key</span><span class=\"o\">=</span><span class=\"k\">lambda</span> <span class=\"n\">node</span><span class=\"p\">:</span> <span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">value</span><span class=\"p\">(</span><span class=\"n\">node</span><span class=\"o\">.</span><span class=\"n\">state</span><span class=\"p\">))</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">value</span><span class=\"p\">(</span><span class=\"n\">neighbor</span><span class=\"o\">.</span><span class=\"n\">state</span><span class=\"p\">)</span> <span class=\"o\"><=</span> <span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">value</span><span class=\"p\">(</span><span class=\"n\">current</span><span class=\"o\">.</span><span class=\"n\">state</span><span class=\"p\">):</span>\n",
" <span class=\"k\">break</span>\n",
" <span class=\"n\">current</span> <span class=\"o\">=</span> <span class=\"n\">neighbor</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">current</span><span class=\"o\">.</span><span class=\"n\">state</span>\n",
"</pre></div>\n",
"</body>\n",
"</html>\n"
],
"text/plain": [
"<IPython.core.display.HTML object>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"psource(hill_climbing)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We will find an approximate solution to the traveling salespersons problem using this algorithm.\n",
"<br>\n",
"We need to define a class for this problem.\n",
"<br>\n",
"`Problem` will be used as a base class."
]
},
{
"cell_type": "code",
2721
2722
2723
2724
2725
2726
2727
2728
2729
2730
2731
2732
2733
2734
2735
2736
2737
2738
2739
2740
2741
2742
2743
2744
2745
2746
2747
2748
2749
2750
2751
2752
2753
"class TSP_problem(Problem):\n",
"\n",
" \"\"\" subclass of Problem to define various functions \"\"\"\n",
"\n",
" def two_opt(self, state):\n",
" \"\"\" Neighbour generating function for Traveling Salesman Problem \"\"\"\n",
" neighbour_state = state[:]\n",
" left = random.randint(0, len(neighbour_state) - 1)\n",
" right = random.randint(0, len(neighbour_state) - 1)\n",
" if left > right:\n",
" left, right = right, left\n",
" neighbour_state[left: right + 1] = reversed(neighbour_state[left: right + 1])\n",
" return neighbour_state\n",
"\n",
" def actions(self, state):\n",
" \"\"\" action that can be excuted in given state \"\"\"\n",
" return [self.two_opt]\n",
"\n",
" def result(self, state, action):\n",
" \"\"\" result after applying the given action on the given state \"\"\"\n",
" return action(state)\n",
"\n",
" def path_cost(self, c, state1, action, state2):\n",
" \"\"\" total distance for the Traveling Salesman to be covered if in state2 \"\"\"\n",
" cost = 0\n",
" for i in range(len(state2) - 1):\n",
" cost += distances[state2[i]][state2[i + 1]]\n",
" cost += distances[state2[0]][state2[-1]]\n",
" return cost\n",
"\n",
" def value(self, state):\n",
" \"\"\" value of path cost given negative for the given state \"\"\"\n",
" return -1 * self.path_cost(None, None, None, state)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We will use cities from the Romania map as our cities for this problem.\n",
"A list of all cities and a dictionary storing distances between them will be populated."
]
},
{
"cell_type": "code",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"['Arad', 'Bucharest', 'Craiova', 'Drobeta', 'Eforie', 'Fagaras', 'Giurgiu', 'Hirsova', 'Iasi', 'Lugoj', 'Mehadia', 'Neamt', 'Oradea', 'Pitesti', 'Rimnicu', 'Sibiu', 'Timisoara', 'Urziceni', 'Vaslui', 'Zerind']\n"
]
}
],
"source": [
"distances = {}\n",
"all_cities = []\n",
"\n",
"for city in romania_map.locations.keys():\n",
" distances[city] = {}\n",
" all_cities.append(city)\n",
" \n",
"all_cities.sort()\n",
"print(all_cities)"
"metadata": {},
"source": [
"Next, we need to populate the individual lists inside the dictionary with the manhattan distance between the cities."
"cell_type": "code",
"execution_count": 58,
"import numpy as np\n",
"for name_1, coordinates_1 in romania_map.locations.items():\n",
" for name_2, coordinates_2 in romania_map.locations.items():\n",
" distances[name_1][name_2] = np.linalg.norm(\n",
" [coordinates_1[0] - coordinates_2[0], coordinates_1[1] - coordinates_2[1]])\n",
" distances[name_2][name_1] = np.linalg.norm(\n",
" [coordinates_1[0] - coordinates_2[0], coordinates_1[1] - coordinates_2[1]])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The way neighbours are chosen currently isn't suitable for the travelling salespersons problem.\n",
"We need a neighboring state that is similar in total path distance to the current state.\n",
"<br>\n",
"We need to change the function that finds neighbors."
]
},
{
"cell_type": "code",
"execution_count": 59,
"metadata": {},
"outputs": [],
"source": [
2828
2829
2830
2831
2832
2833
2834
2835
2836
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
2848
2849
2850
2851
2852
2853
2854
2855
2856
2857
2858
2859
"def hill_climbing(problem):\n",
" \n",
" \"\"\"From the initial node, keep choosing the neighbor with highest value,\n",
" stopping when no neighbor is better. [Figure 4.2]\"\"\"\n",
" \n",
" def find_neighbors(state, number_of_neighbors=100):\n",
" \"\"\" finds neighbors using two_opt method \"\"\"\n",
" \n",
" neighbors = []\n",
" \n",
" for i in range(number_of_neighbors):\n",
" new_state = problem.two_opt(state)\n",
" neighbors.append(Node(new_state))\n",
" state = new_state\n",
" \n",
" return neighbors\n",
"\n",
" # as this is a stochastic algorithm, we will set a cap on the number of iterations\n",
" iterations = 10000\n",
" \n",
" current = Node(problem.initial)\n",
" while iterations:\n",
" neighbors = find_neighbors(current.state)\n",
" if not neighbors:\n",
" break\n",
" neighbor = argmax_random_tie(neighbors,\n",
" key=lambda node: problem.value(node.state))\n",
" if problem.value(neighbor.state) <= problem.value(current.state):\n",
" current.state = neighbor.state\n",
" iterations -= 1\n",
" \n",
" return current.state"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"An instance of the TSP_problem class will be created."
]
},
{
"cell_type": "code",
"metadata": {},
"outputs": [],
"source": [
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can now generate an approximate solution to the problem by calling `hill_climbing`.\n",
"The results will vary a bit each time you run it."
]
},
{
"cell_type": "code",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['Arad',\n",
" 'Timisoara',\n",
" 'Lugoj',\n",
" 'Mehadia',\n",
" 'Drobeta',\n",
" 'Craiova',\n",
" 'Pitesti',\n",
" 'Giurgiu',\n",
" 'Bucharest',\n",
" 'Urziceni',\n",
" 'Eforie',\n",
" 'Hirsova',\n",
" 'Vaslui',\n",
" 'Iasi',\n",
" 'Neamt',\n",
" 'Fagaras',\n",
" 'Rimnicu',\n",
" 'Sibiu',\n",
" 'Oradea',\n",
" 'Zerind']"
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The solution looks like this.\n",
"It is not difficult to see why this might be a good solution.\n",
]
},
{
"cell_type": "markdown",
"The intuition behind Hill Climbing was developed from the metaphor of climbing up the graph of a function to find its peak. \n",
"There is a fundamental problem in the implementation of the algorithm however.\n",
"To find the highest hill, we take one step at a time, always uphill, hoping to find the highest point, \n",
"but if we are unlucky to start from the shoulder of the second-highest hill, there is no way we can find the highest one. \n",
"The algorithm will always converge to the local optimum.\n",
"Hill Climbing is also bad at dealing with functions that flatline in certain regions.\n",
"If all neighboring states have the same value, we cannot find the global optimum using this algorithm.\n",
"<br>\n",
"<br>\n",
"Let's now look at an algorithm that can deal with these situations.\n",
"<br>\n",
"Simulated Annealing is quite similar to Hill Climbing, \n",
"but instead of picking the _best_ move every iteration, it picks a _random_ move. \n",
"If this random move brings us closer to the global optimum, it will be accepted, \n",
"but if it doesn't, the algorithm may accept or reject the move based on a probability dictated by the _temperature_. \n",
"When the `temperature` is high, the algorithm is more likely to accept a random move even if it is bad.\n",
"At low temperatures, only good moves are accepted, with the occasional exception.\n",
"This allows exploration of the state space and prevents the algorithm from getting stuck at the local optimum.\n"
]
},
{
"cell_type": "code",
2964
2965
2966
2967
2968
2969
2970
2971
2972
2973
2974
2975
2976
2977
2978
2979
2980
2981
2982
2983
2984
2985
2986
2987
2988
2989
2990
2991
2992
2993
2994
2995
2996
2997
2998
2999
3000
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"<!DOCTYPE html PUBLIC \"-//W3C//DTD HTML 4.01//EN\"\n",
" \"http://www.w3.org/TR/html4/strict.dtd\">\n",
"\n",
"<html>\n",
"<head>\n",
" <title></title>\n",
" <meta http-equiv=\"content-type\" content=\"text/html; charset=None\">\n",
" <style type=\"text/css\">\n",
"td.linenos { background-color: #f0f0f0; padding-right: 10px; }\n",
"span.lineno { background-color: #f0f0f0; padding: 0 5px 0 5px; }\n",
"pre { line-height: 125%; }\n",
"body .hll { background-color: #ffffcc }\n",
"body { background: #f8f8f8; }\n",
"body .c { color: #408080; font-style: italic } /* Comment */\n",
"body .err { border: 1px solid #FF0000 } /* Error */\n",
"body .k { color: #008000; font-weight: bold } /* Keyword */\n",
"body .o { color: #666666 } /* Operator */\n",
"body .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
"body .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
"body .cp { color: #BC7A00 } /* Comment.Preproc */\n",
"body .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
"body .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
"body .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
"body .gd { color: #A00000 } /* Generic.Deleted */\n",
"body .ge { font-style: italic } /* Generic.Emph */\n",
"body .gr { color: #FF0000 } /* Generic.Error */\n",
"body .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
"body .gi { color: #00A000 } /* Generic.Inserted */\n",
"body .go { color: #888888 } /* Generic.Output */\n",
"body .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
"body .gs { font-weight: bold } /* Generic.Strong */\n",
"body .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",