![]() ![]() The idea is that some places on the board are more suitable than others. But how to determine in what way to place each piece on the board? Optimal Placement Algorithm This chromosome is unique to this individual, and means that we start solving the puzzle by putting the piece with ID = 4 on the board first, then 3, then 6 and so on. This hints into the direction that the order sequence is a good candidate for the representation of genetic information of our individual - the chromosome. The holes represent the white checkers from the initial image.Ī lot of very useful information on how to go about solving this problem has been pulled from this article, so kudos to the author! The article states that the order, in which we put in the pieces, is of great importance. ![]() Let’s jump into the juicy details and the actual implementation of the code. So far this whole post has been quite abstract. Lastly, crossover plays an important role of introducing variation in the step of generating new offspring from selected parent individuals, where their genetic information is distributed onward. The phrase “survival of the fittest” comes to mind. Selection is the stage where individuals are chosen for later breeding based on their fitness level. Mutation represents a small change in the configuration of an individual, meaning that the individual mutates into a different individual with a similar configuration setup, albeit with a potentially very different fitness level (better or worse, nature doesn’t really care). Genetic algorithms commonly rely on biologically inspired operators such as mutation, selection and crossover. the smaller the number of pieces left), the closer we are to finding the best individual, in other words, the solution. In our case, let’s call such a candidate an individual. In the context of our puzzle, each configuration of all the pieces represents a potential candidate with a certain level of fitness. The LogicĪ genetic algorithm is a method of searching for solutions, inspired by the process of natural selection. If you ask why, I can’t really give you a good answer, besides the fact that it just sounded really cool. The idea is that we can build a solution step by step using recursion if during the process we realise that is not going to be a valid solution, then we stop computing that solution and we return back to the step before ( backtrack).īut I wanted to play around with the application of a genetic algorithm (GA). You can read more about it here, where the author sums it up nicely: There is already a post on medium, solving the same puzzle with this algorithm. In a glimpse of a second we discard HUGE subsets of cases, which make no sense in solving the puzzle, taking into account overlaps, out-of-bounds positions, empty space, checkers alignment and so on.Ī more similar approach to the one our brain takes, is a backtracking algorithm. There are methods - implemented by our brains - which we may take for granted, but as soon as you try to write code for it, you see the complexity hidden behind. Of course, blindly checking each combination is not something we do. Oh… sorry, does this number mean nothing to you? Then what if I tell you that the age of the freaking universe is 13.8×10⁹ years? Yeah? I thought so… ![]() If you were to blindly check each configuration separately at a speed of a million cases per second, it would still take you more than 10²¹ years. 2 flip orientations (the original or the mirrored version)ĭoing some “ quick mafs”, this equals to (8×8×4×2)¹³ = (512)¹³ ~10³⁵ combinations to try out.So all in all we have 13 pieces of the puzzle and the following degrees of freedom for each piece: In our problem, there is a large variability, since each piece can be translated, rotated, flipped… doing this for multiple pieces quickly becomes problematic. ![]() Such problems are easy to verify if someone comes up to you and claims that they have the solution, but they aren’t so easy to solve, as they normally require exponential time as the size of the problem increases.įor example, if this puzzle consists of 3 pieces, you can quickly solve it, but if it consists of more, then the number of variations that you have to try out (worst case scenario) quickly starts to rise exponentially! There are many variations, where one can focus on the volume, weight, cost, etc. This is actually a variation of the Knapsack problem, which is a standard computational problem, where items of different shapes and sizes must be optimally packed into a container of a fixed given volume.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |