An investigation about the genetic operators in the Evolutionary Algorithm applied to the Knight’s Tour

Abstract

Bioinspired Computing is an area of research focused on developing techniques inspired by natural phenomena to solve computational optimization problems, classified as NP problems. In this work, EA (Evolutionary Algorithm) is implemented to solve the Knight’s Tour. This algorithm is strongly based on Darwin’s Evolutionary Theory, in particular, Natural Selection. The Knight’s Tour, in turn, is a combinatorial problem widely used as a basis for improving or developing algorithms and for solving real problems, such as image encryption. Leonhard Euler was the first to formally study it. The Knight’s Tour consists of finding a sequence ofmoves—made by the chess piece corresponding to the knight -- that travels across the entire board without visiting a squaremore than once. Therefore, this work aimed to implement EA for the Knight’s Tour solution, improving the results found in the literature, through the implementation of new operators (selection,mutation) and the central initialization. The first is based on the exploration of a larger search field through the crossing of dissimilar parents, the second is the exchange of
genes (pathways) for valid neighbours, and the third, the initialization in the central (or approximate) square of the
board was used. The experiments showed that the implemented EA was able to solve Knight’s Tour for nxn boards, with 5 ≤ n ≤ 20.