We all know that Genetic Algorithms can give an optimal or near-optimal solution. So, in some problems like NP-hard ones, with a trade-off between time and optimal solution the near-optimal solution is good enough.
Since there is no guarantee to find the optimal solution, is GA considered to be a good choice for solving the Knuth problem?
According to Artificial intelligence: A modern approach (third edition), section 3.2 (p. 73):
Knuth conjectured that, starting with the number 4, a sequence of factorial, square root, and floor operations will reach any desired positive integer.
For example, 5 can be reached from 4:
So, if we have a number (5) and we want to know the sequence of the operations of the 3 mentioned ones to reach the given number, each gene of the chromosome will be a number that represents a certain operation with an additional number for (no operation) and the fitness function will be the absolute difference between the given number and the number we get from applying the operations in a certain order for each the chromosome (to min). Let's consider that the number of the iterations (generations) is done with no optimal solution and the nearest number we have is 4 ( with fitness 1), the problem is that we can get 4 from applying no operation on 4 while for 5 we need many operations, so the near-optimal solution is not even near to the solution.
So, is GA is not suitable for this kind of problems? Or the suggested chromosome representation and fitness function are not good enough?