Search for maximal snake-in-the-box using new genetic algorithm
Kim-Hang Ruiz · 2014
The "Snake-In-The-Box" (SIB) problem is a challenging combinatorial search problem to find the longest constrained open path (k-spread snake) in n-dimensional hypercube (Qn). In addition to constructive techniques, many search algorithms such as Depth First Search (DFS), Genetic Algorithm (GA), hybrid Evolutionary Computation algorithm (EC), and Nested Monte-Carlo Search (NMCS) have been used to tackle this problem. To get better results and to speed up the process, these techniques often used a long snake as the starting point for the search (priming/seeding). This paper reviews the hypercube fundamentals, then presents a new search technique, Mitosis Genetic Algorithm (MGA), which was applied in search for the four different spread snakes (spread 2 to 5) in seven different dimensional hypercubes (Q6 to Q13). The MGA found three new record-breaking 3-spread snakes in Q10, Q11 and Q13, all the previously known optimal snakes from spread 2 to spread 5, and the best previous known maximal 3-S9 snake of length 63. It is remarkable that it found those within minutes to hours without priming, significantly shorter than days to weeks needed in the other techniques.