Genetic Algorithm to Solve 2D Mazes

In this article, as a sequel to Genetic algorithm for icon generation in Visual Basic, we'll see how genetic algorithms can be applied to solve problems. The approach is particularly suited to a requirement where we don't have a prior model (or, an ideal target to reach), but know the optimal parameters that tend to a solution. In other words, we'll discuss Genetic Algorithms (GA) in the solutions optimization context. The language in which we'll develop a sample application will be Visual Basic .NET again.

In the last article we considered how, starting from a given graphical model, it's possible to generate a set of random and chaotic solutions that will evolve towards our target through the constant selection of the best samples from each set, crossing their information to create new champions, perhaps better. Though those are interesting ways to explore GAs, when we discuss those coded to grow towards a strict model have the obvious need of a starting complete and ideal solution. That means if we don't have a final result to match each solution we create, we won't have any way to evolve beyond chaos, closing our algorithm in an infinite loop of random samples, because they won't be oriented to any specificity.

Obviously, a GA must always have a target, in one way or another. However, a monolithic model isn't always necessary, but after we have defined the optimal conditions we expect, we let the algorithm find solutions that meet those requirements (or, the optimal solution to a given problem). There are many practical applications for that, regarding many fields of human knowledge. But since we learn better when we play with something, we'll see here an example of a Visual Basic GA oriented to solve a 2D maze, trying, using previously seen functionalities, to not only join two points in space, but to do it in one of the better ways, in other words searching for the shorter path.

Let's review the main concepts to refresh your memory.

A GA is so named because it tries to mimic those biological processes at the core of species evolution. We could say it attempts to create a computer model able to auto-tune itself to a specific context, generating individuals (solutions to a given problem) that will be used to evaluate a real goal of a given objective. The problem to be solved is the digital equivalent of the biological context in which individuals move, obeying the "fittest's survive" tenet. In the previous article I've used the example of a world filled with predators, in which the fastest inhabitants (more apt to an efficient flight) or the more pugnacious (mode apt to an efficient fight) represents the best candidates to survive, if compared with slower o weaker samples. In the same way, if we have a digital target (equivalent of the base parameter of biological survival), we could tell about "apt individuals" in the measure in which potential solutions get nearer to the given objective. Among them, in the same way nature does, we'll try to identify the best solutions to get them to reproduce, generating new solutions that will bear their parent's peculiarities. A quick sample about it has been shown in the first article. Given a certain graphical icon (an array of bytes that produces an image), starting from a fixed number of chaotic solutions, in each generation the best solutions are those akin to the model at which they aim.

The biological inspiration of GA passes through its terminology, too. In it, we'll speak of:

• The concept of individual/chromosome, of a single solution to a given problem
• Population, or the entire set of possible solutions
• Gene, or a parte (byte) of an individual
• Fitness, to be intended as the rate of validity in a solution/individual
• Crossing-over, or the solutions recombination to produce new models, new chromosomes/individuals
• Mutation, to be intended as random changes (or pseudo-random) that can occur inside a solution

All those concepts are valid in a digital world and must be implemented in some way to speak about a real GA-based solution, or a solution which can autoevolve. The developer must define each one of them, in theoretical and practical means to deal with each phase.

Optimizing a solution

In principle, when dealing with the case of image replication too, when taling about GAs we could always think about optimization. In fact, each GA case is, ultimately, the search for the best solution, whenever it refers to reach the ideal target or falling in a satisfying local optimum. With the term "local optimum", we indicate the inability to progress further ta a given precision rate, due to certain population characteristics that, after recombination, doesn't produce improvements. A method to prevent stagnation is possibly applied through mutation, using which we introduce, on a random basis, changes in the newly created solutions, to maintain a little constant of chaos in transmitting information from a generation to the next one.

Despite that, we could always refer to the concept of optimization, it becomes more evident when applied to a logistical problem. Let's suppose we are inside a maze that provides several ways to reach the destination. In it we could move as the internal topography allows and it is possible to repeat a path or never reach the destination. Essentially, in such a labyrinth there are many ways to reach a solution, but a solution that will be better compared to others exists, too. In such a place, the best road is the one that leads us from the start point to the end in a straight way, in the least steps possible (in other words, the optimal solution). A GA could help us to spot that path, without previously knowing what the possibilities are. We note it isn't just about finding a way to arrive, but to test its validity, considering what will be better.

To be able to think about a labyrinth, we must have a labyrinth. Here we'll see the basis I've used in my example, to briefly explain what will be the ground on which we will work. As usual, at the end of the article you'll find a link to download the source code of the example that I invite you to consult for a detailed view about those aspects that won't be treated in this article. Running the sample code, we'll see a window like this:

The program will create two windows with 20 cells per side that will be used as a graphical representation on the elements constituting the user-defined labyrinth (on the left) and the one that will show the found solutions (on the right). In the left panel, the user can click each cell a given number of times. The following is a short table to explain what each click will produce on a cell:

• 1 Click = "Wall" cell (Gray, it wil be impassable)
• 2 Click = Start point (Green, the entering point of the labyrinth)
• 3 Click = End point (Red, the exit point of the labyrinth)
• 4 Click = Valid cell (not used in labyrinth creating, it will belong to the GA)
• 5 Click = "Free" cell (Black, a cell that can be crossed)

We can immediately see there are many possible solutions between the start and end point. Before getting into the GA part, I will spend some words about the creation of the labyrinth, to explain its underlying logic. That will be useful for a better understanding of the algorithm itself.

Our labyrinth has a base made by a bidimensional byte array, named sourceMaze(). Each cell of it represents an array position, in the form (X,Y). Each of those bytes is set to a value that represents the current state of a specific cell. Those values are associated with an enumeration, visible in the Globals.vb file:

There is an additional value compared to the values discussed above, namely FakeWall = 5. We will talk about it soon, when we'll analyze how the solutions are created.

During the Form load, a call to the routine that draws the labyrinths is made. Drawing operations are done using MazeCell controls that are PictureBox extensions created to contain data from the data array as in the following:

The present structure allows the user to define his own base labyrinth, to be then passed as a base for the GA, or saving it for future reference. (I've implemented, but not optimized, basic routines to save and load labyrinth data, but I won't discuss them here, to focus on the topic's fundamentals.)

Now that we have an operative context, we can start reasoning about the explorative possibilities of an automaton. We've mentioned above about the rules to be applied for each type of cell and consequently we know what the basic prequisites are that a generic explorative algorithm must possess (please note: generic, not genetic). We know it must start moving from the Green cell, trying to reach the Red one, without crossing Grey ones. All the Black cells can be explored/stepped over. We can think about a routine which, given a start point, evaluates the status of the four adjacent cells, to recursively cross those that will be considered free.

In other words, being solverBytes() and an array containing a given solution, a function like this will do:

As can be noted, giving a start point ad [_X,_Y] coordinates results in looping through the function (and recursively into it) until all the cells that leads to the solution are crossed. In other words, the algorithm will explore the entire solution domain. Applying the function to our labyrinth, we will obtain a solution like this:

Obviously, that will be an encompassing solution, with the sole purpose of tracking down all possibilities. It is the most dispersive solution. Nonetheless, it could have its usefulness in a specific context (please note that, at a conceptual level, our function is a trivial graphical floodfill, given drawing margins), but that's not what we desire to obtain here. We are starting to see what the peculiarities are of a GA, what it must be able to do. In our case, it must try to solve a labyrinth, without trying to taking out a massive amount of space. So, generating individuals capable of solving our problem, we can introduce a kind of limiter.

We saw the limiter above, in the CELLSTATE enumeration, with the value of FakeWall = 5. When we'll generate a new individual, we'll introduce in it some "dirt", to alter the results of the Solve() function with fake walls, precisely, or walls that are not in the base labyrinth structure, having the same behavior of a standard wall.

To be spotted more easily, we'll draw them using the color Yellow. As said, those are arbitrary limiters that respond to the same impossability laws as traditional walls and are useful to delimiter, for each related individual, the solution domain. In fact, we can note that, where a Yellow wall is present, the exploration of the maze is blocked from that spot on. Such randomness allows us to generate a manifold population of individuals. It will contain elements that will solve the maze and elements unable to reach the exit (for example, think about a Yellow cell standing right in front of a Red one). Next, each solution will arrive to its conclusion in a given number of steps. There will be elements that will arrive to the Red cell in a more straight way, whereas another will follow more convoluted paths, being more dispersive.

Let's now see the code of the GASolver class that represents the single individual or solution. Please note it has a generic constructor, with a parameter that expects the array of the user-defined maze, to replicate in each solution the bytes representing walls, starting point and an end point that are essential prerequisites to solve the maze, since they are fixed. With some probability, one or more cells will take the FakeWall value, to add limiters where, in drawing the maze, the user has left free cells.

A Solve() function is also present, to be able to determine if a solution can reach the exit cell, or if it fails somewhere else. There are other properties and functions that will be analyzed soon.

As we saw in the previous article, an essential part of a GA is the one that allows a determination of an adaptability score when confronted with a given problem. It goes without saying that the way in which that score will be calculated rests on the problem's tipology. Fitness is essential, because when we have a population made of a solution more or less close to our target, it allows the extraction of some champions with potential characterics we can desire to try to imrove the individual's generation. It is therefore evident that an error in designing a fitness calculator's function will be the foundation stone to build a failure in a GA realization.

In trying to limit problems laying on an eroneous fitness attribution to one or more solutions, deep problems analyzing is a requirement. In cases as an image replication is simpler, we know it is, at the core, an array of bytes ordered in a given way and the fitness of a solution passes by checking how many bytes are shared between our target and the solutions. When confronted with open problems, like the present one, a step forward is needed. Here we aren't interested in evaluating the affinity with a predefined model, but we want to discuss the potential effctiveness of a solution.

Simplifying, in the case of a maze, we are interested in the following two aspects, already mentioned previously:

1. The solution must lead to a valid end, it must reach the destination
2. The solution must be quick; having satisfied the prerequisite 1), it must be able to obtain it in the most neat way

The initialization's concept follows simple rules that are about creating a first generation of solutions, using standard constructors. In the attached source code, the operation happens at the btnInit button's Click:

We reset a counter that will be used to count the generations, then we save the cells that the user has defined as the start and end points. In a List (OF GASolver), that we will query via LINQ, we'll add the desired number of newly created GASolvers (in our case, 1000 units), to proced to their graphical representation. Each initial solution, as we saw, will be initialized by adding dummy delimiters into the spaces the user has kept clear, to create variety in the population.

By pressing the btnStart button, the seach for solutions will start. Note that we will extract, during each loop, those elements that solve the maze (ga.isSolved = True), ordered by the number of steps used to complete the task (ordered by ga.Steps Ascending). That way, we will be sure to extract the two best solutions at the moment. Those elements will be recombined, producing two new elements, following the rules we'll see in a moment. Lastly, ordering our list for a descending amount of steps, we can discard the two worst elements. Please note that we won't apply any discriminant on the solution's quality and it is possible to discard elements that arrivees at a valid solution, but having the flaw to be, among all solutions, the most dispersive ones.

Cross-over generates two new elements as explained using the four-argument constructor of the GASolver class, as follows:

Essentially, it requires two arrays, referred to the bytes of the elements to be recombined and two pairs of coordinates, namely the start and exit points of the maze.

Looping through the two matrices, a matrix is generated, putting in it the combination of Wall and FakeWall types. A Wall cell will be the same between the two, but a FakeWall will possibily differ. If the two solutions come to a valid end, in other words the FakeWall from both matrices can be applied without affect the solution, then it is made better by removing a potentially free cell to be considered valid steps. When the process ends, an additional mutation loop calculates the eventual transformation of non-Wall cells in Wall or FakeWall cells. The newly created solution will then have the same Walls as the parents, the same start/end point, but the virtual walls from both, plus some mutation (if they occur).

The logic is simple: the thing that determines a more economic solution, is the freedom of movement. The more the free cells are, the greater the solution's domain will be, and consequently the steps towards the exit point. In the described way, we apply a progressive limiter towards a basic path that will be constituted by the sum of the limiters that, in past generations, had represented and helped that objective.

Making the algorithm run, alternating generations, in a few hundreds of epochs we'll have the optimal solution, or the solution that leads from the start point to the end without "indecisions". At the same time, the progressive discarding of poor solutions, in favor of those with higher performances, will lead to an entire population of acceptable solutions.

In the preceding example, it's possible to see that after about 14000 generations of solutions, the result is really close to the optimal one. There is room to improve, and proceeding though epochs it's possible to reach better results, though slow due to the recombination of nearly-ideal solutions (that can count almost exclusively on mutation to improve further). Lastly, please note that, with a given number of potential solutions, the path chosen by the algorithm will be affected by the elaborations themselves. For example, if a mutation inhibits a certain path, the algorithm will focus on the remaining solutions. So, we won't obtain the ultimately better overall solution, but the better depending on the current context and the agents at our disposal, miming at a conceptual level what happens in biology too.

• Genetic algorithm for 2D-Mazes solving and path optimization

• A sample video about a session from the program is available here: http://youtu.be/4cqsjThCrRA