Local Search Algorithms in NetLogo
In the basic search algorithms mentioned in previous posts (BFS and A*), when a goal is found in the search space associated to the problem, the solution is given as a path connecting the initial position with the goal state. In these cases we are interested not only in the structure of the final state (that we can know in advance) but in how to get it by using some operations from a specific (commonly random) initial state.
But in many cases we don't know the structure of the final solution, only some properties to verify, and the path does not matter, and if we use a path it's only as a way to obtain the solution. This fact can be illustrated with the familiar 8 Queens problem:
Given a standard chess board (\(8\times 8\) cells) and 8 queens, locate them in the board in such a way as to have no two queens attacking each other (that is, no queen can be on the same row, column, or diagonal as another).
We can generalize this problem to play with \(N\) queens on a \(N\times N\) board. From a theoretical point of view, it’s a simple problem, but we will see that easily illustrates the importance of having good algorithms. On a small board like \(4\times 4\), a very simple way is to solve it by brute force: test every set of queen positions. In this small case, the state space (the different positions the queens can be) is really small, only \(4!= 24\) positions. When playing in the standard board we obtain \(8!=40,320\) positions, a bigger number that we can still manage by brute force in a short time. However, this simple search rapidly gets much larger space. If we extend the problem to be \(12\) queens, we will get a space with \(12!= 479,001,600\) states, and if we move to \(15\) or \(20\) queens we obtain \(1,307,674,368,000\) or \(2,432,902,008,176,640,000\) states, respectively... which changes the search from seconds to years to find the solution.
Of course, in this particular problem there are ways to reduce the search space by using symmetries or similar tricks, but the problem remains the same: the search space grows at factorial rate, while the reductions only remove a linear fraction of them. We need some other tools to get better algorithms for browsing the space in the search of the solution.
In the previous searching algorithms we use a set of operations that, usually, have a natural meaning in the real world (where the problem is extracted from), and the solution path is in fact a sequence of operations transforming the initial state into the goal state by means of legal moves. Since now we aim to obtain a solution state no mind the way to reach it, we can use operations that probably have no meaning in the real world, but they are only ways to transform states in (hopefully) better states (regarding the goal).
In this post we will see implementations of a couple of methods that, starting from initial states, will search in the state space by local moves that take us closer to the solution. As the space is more complex and bigger, more difficult is to find the solution, hence we will not be interested in the "best" path to reach the goal, and maybe we don't obtain the goal in a minimal optimal time, but frequently is good enough to reach it or find a state that is very similar to one solution (that is, sometimes we change the best solution for a good enough solution).
Hill Climbing Methods
The basic Hill Climbing Algorithm is an iterative algorithm that starts with an random state in the search space and then attempts to find a better solution by changing some parts of the structure of the state. If the change produces a better option, we accept it and we repeat again the procedure until no further improvements can be found.
In order to measure the quality of the states, we need some kind of function that provides this information:
- If we measure how far we are from the best solution, it will be called error or distance and our problem can be rewritten into trying to minimize this function.
- If we measure how good the states are, it will be called fitness and our problem can be rewritten into trying to maximize it.
- In any case, the solution represents now an optimal value of the function, and we have transformed the search problem into an optimization problem.
We can see the problem as an agent that browses the search space moving from states to states improving the function as a climber trying to get higher in a mountain. Of course, this method presents some limitations and it is not efficient, as the climbers can reach a local extreme that is not optimal (that is, the climber will improve the states until it reaches one state that can't change to a better one).
Under some assumptions (if the function to optimize is continuous and derivable on the search space,... think about functions between real numbers if it is easier) the hill climbing algorithm is closely related to Gradient Descent method for optimization.
With this method as basement, we can create slightly variants that improve the results in a several ways. The one that we will implement in NetLogo works with a number of simultaneous climbers that, in any state, look for all the states it can reach from it by simple operations and take the best option regarding the optimization function (in any of the states, they can evaluate this function to compare between neighbour states).
Hill Climbing on Patches (Download Model)
In order to show how to implement this type of searchers in NetLogo, we will work with a very specific and graphical situation: in the patches of the world we will suppose a numerical value, and we aim to search for the patch with the higher value. To simplify the code, we will use pcolor as the value to maximize on patches.
Let's start to comment this Hill Climbing implementation on patches:
We define a breed of agents that will browse the space while searching. As the climber can reach a local maximum, we will store in the agent if it is on a patch that has no better neighbours.
breed [climbers climber]
climbers-own [
on-hill? ; shows if the turtle has reached one hill
]
globals [
num-states ; It will store the number of states that have been visited by the climbers-own
; during the search process
]
In the setup procedure we create a random landscape (by using the diffuse function) that stores values in the pcolor properties of the patches. After that, we create some climbers on random initial positions (they will have the pen down to draw the path they follow during the execution).
to setup ca ; Create a landscape with hills and valleys. The height will be stored in patches color ask n-of 100 patches [ set pcolor 120 ] repeat 20 [ diffuse pcolor 1 ] ; Create some climbers in the ground ask n-of Num-climbers patches [ sprout-climbers 1 [ set on-hill? false set color red set shape "circle" pen-down ] ] set num-states 0 reset-ticks end
In the go procedure we code one step of the iterative algorithm, later we will call it from a forever button. This procedure will stop if all the climbers have reached a local maximum... hopefully, some of them have found the global maximum and, consequently, we have a correct solution to the problem. Otherwise, we will obtain better states than the original ones, and some approximation to the optimal.
For this case NetLogo provides a factory turtle procedure, uphill, that moves the agent to the best patch neighbour regarding a desired property of patches. During this procedure we know that the climber has reached a local maximum if the best neighbour is the patch where the agent is.
to go ; Stop when all the climbers are on a hill ifelse all? climbers [on-hill?] [ ; Highlight the maximum height and the optimum reached by the climbers ask climbers [set label precision pcolor 2] ask one-of climbers with-max [pcolor] [
set size 3
set color blue
] ask patches with-max [pcolor] [ set plabel precision pcolor 2 ] stop ] [ ; Move the climbers uphill ask climbers [ let current-patch patch-here ; Uphill function from NetLogo moves the climber to a higher patch uphill pcolor ifelse current-patch = patch-here [ set on-hill? true ] [ set num-states num-states + 1 ] ] ] tick end
Of course, the efficiency of the algorithm depends on the roughness of the function (that reflects the complexity of the state space) and the number of climbers. In the next plot we can see the ratio of success to find the optimal value while varying the number of climbers from \(0\) to \(100\). In this experiment, for every number of climbers we have performed \(100\) repetitions. Take into account that the size of the space is the number of patches in the world (\(100\times 100= 10,000\)) and that every climber visits an average of \(8\) states before reaching a hill, so the proportion of visited states during the search is really low.
Hill Climbing on Networks (Download Model)
Now, we will present a slightly variant that looks for optimize a height function on a network. The idea is the same, we have climbers on the nodes of the network and they move to neighbours nodes (connected by links of the network) if they have higher values for this function. In the following code we highlight only the differences. You can find the complete code in the model.
Now we have two breeds of agents, one for nodes of the network and one more for climbers. Note that we need a property on the climbers to store the localization (the node) where it is.
breed [nodes node] ; nodes of the network breed [climbers climber] ; agents that will make the search climbers-own [ on-hill? ; shows if the climber has reached one hill localization ; the node where the climber is ] nodes-own [ height ; value of the nodes to optimize ]
We will not show the rest of the code here (download the model file to see it), but only explain its particularities. The process we follow to create a coherent network valid for the use of the algorithm uses a height landscape on patches, and then project these values on a geometrical network built over them. After that, since there is no uphill-like procedure for networks, we must calculate explicitly the best neighbour and move the climber there. Except this, the rest is very similar to the previous patches case.