Answers.Body: <p>Before trying to answer your question more directly, let me clarify something.</p>
  <p>People often use the term <em>genetic algorithms</em> (GAs), but, in many cases, what they really mean is <em>evolutionary algorithms</em> (EAs), which is a collection of population-based (i.e. multiple solutions are maintained at the same time) optimization algorithms and approaches that are inspired by <a href="https://en.wikipedia.org/wiki/Darwinism" rel="nofollow noreferrer">Darwinism</a> and <a href="https://en.wikipedia.org/wiki/Survival_of_the_fittest" rel="nofollow noreferrer"><em>survival of the fittest</em></a>. GAs is one of these approaches, where the chromosomes are binary and you have both the mutation and cross-over operation. There are other approaches, such as <em>evolution strategies</em> or <em>genetic programming</em>.</p>
  <p>As you also noticed, EAs are meta-heuristics, and, although there is some research on their convergence properties [<a href="https://www.researchgate.net/publication/3642792_Convergence_of_evolutionary_algorithms_in_general_search_spaces" rel="nofollow noreferrer">1</a>], in practice, they may not converge. However, when any other potential approach has failed, EAs can be definitely useful.</p>
  <p>In your case, the problem is really to find a <strong>closed-form</strong> (or <strong>analytical</strong>) <strong>expression</strong> of a function, which is composed of other smaller functions. This really is what <a href="http://www0.cs.ucl.ac.uk/staff/W.Langdon/ftp/papers/poli08_fieldguide.pdf" rel="nofollow noreferrer"><strong>genetic programming</strong></a> (in particular, tree-based GP) was created for. In fact, the Knuth problem is a particular instance of the <a href="https://en.wikipedia.org/wiki/Symbolic_regression" rel="nofollow noreferrer"><strong>symbolic regression problem</strong></a>, which is a typical problem that GP is applied to. So, GP is probably the first approach you should try.</p>
  <p>Meanwhile, I have implemented a simple program in DEAP that tries to solve the Knuth problem. Check it <a href="https://gist.github.com/nbro/dfdf39b6fe98e96c61d164dd3f6bd177" rel="nofollow noreferrer">here</a>. The fitness of the best solution that it has found so far (with some seed) is 4 and the solution is <code>floor(sqrt(float(sqrt(4))))</code> (here <code>float</code> just converts the input to a floating-point number, to ensure type safety).  I used the <em>difference</em> as the fitness function and ran the GP algorithm for 100 generations with 100 individuals for each generation (which is <em>not</em> a lot!). I didn't tweak much the hyper-parameters, so, maybe, with the right seed and hyper-parameters, you can find the right solution.</p>
  <p>To address your concerns, in principle, you could use that encoding, but, as you note, the GA could indeed return <span class="math-container">$4$</span> as the best solution (which isn't actually that far away from <span class="math-container">$5$</span>), which you could avoid my killing, at every generation, any individuals that have just that value.</p>
  <p>I didn't spend too much time on <a href="https://gist.github.com/nbro/dfdf39b6fe98e96c61d164dd3f6bd177" rel="nofollow noreferrer">my implementation</a> and thinking about this problem, but, as I said above, even with genetic programming and using only Knuth's operations, it could get stuck in local optima. You could try to augment my (or your) implementation with other operations, such as the multiplication and addition, and see if something improves.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-23T11:33:54.083Z
Answers.Text: Thank you very much, I checked the code so thank you again, so in summary it is better to use other approach (not GA) to solve this problem
Answers.UserDisplayName: yaminoyuki
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-23T14:52:07.387Z
Answers.Text: @yaminoyuki I'm not sure which other approach would work better than GA or GP for this problem. So, I think that GP is probably your best bet, if you want to find a reasonable solution, but you have to tweak my implementation.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-22T17:48:40.627Z
Answers.LastActivityDate: 2021-01-23T04:53:36.103Z
Answers.LastEditDate: 2021-01-23T04:53:36.103Z
Answers.UserDisplayName: nbro
Body: <p>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.</p>
  <p>Since there is no guarantee to find the optimal solution, is GA considered to be a good choice for solving the Knuth problem?</p>
  <p>According to Artificial intelligence: A modern approach (third edition), section 3.2 (p. 73):</p>
  <blockquote>
  <p>Knuth conjectured that, starting with the number 4, a sequence of
  factorial, square root, and floor operations will reach any desired
  positive integer.</p>
  </blockquote>
  <p>For example, 5 can be reached from 4:</p>
  <blockquote>
  <p>floor(sqrt(sqrt(sqrt(sqrt(sqrt((4!)!))))))</p>
  </blockquote>
  <p>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.</p>
  <p>So, is GA is not suitable for this kind of problems? Or the suggested chromosome representation and fitness function are not good enough?</p>
  
Tags: <genetic-algorithms><evolutionary-algorithms><genetic-programming><norvig-russell>
Title: Are Genetic Algorithms suitable for problems like the Knuth problem?
UserDisplayName: yaminoyuki
ThreadText: # Are Genetic Algorithms suitable for problems like the Knuth problem?
  
  (Asked by: username_0 on 2021-01-22)
  
  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:
  
  > floor(sqrt(sqrt(sqrt(sqrt(sqrt((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?
  
  **Tags:** genetic-algorithms, evolutionary-algorithms, genetic-programming, norvig-russell
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-01-22. Score: 1 | Accepted answer
  
  Before trying to answer your question more directly, let me clarify something.
  
  People often use the term *genetic algorithms* (GAs), but, in many cases, what they really mean is *evolutionary algorithms* (EAs), which is a collection of population-based (i.e. multiple solutions are maintained at the same time) optimization algorithms and approaches that are inspired by [Darwinism](https://en.wikipedia.org/wiki/Darwinism) and [*survival of the fittest*](https://en.wikipedia.org/wiki/Survival_of_the_fittest). GAs is one of these approaches, where the chromosomes are binary and you have both the mutation and cross-over operation. There are other approaches, such as *evolution strategies* or *genetic programming*.
  
  As you also noticed, EAs are meta-heuristics, and, although there is some research on their convergence properties [[1](https://www.researchgate.net/publication/3642792_Convergence_of_evolutionary_algorithms_in_general_search_spaces)], in practice, they may not converge. However, when any other potential approach has failed, EAs can be definitely useful.
  
  In your case, the problem is really to find a **closed-form** (or **analytical**) **expression** of a function, which is composed of other smaller functions. This really is what [**genetic programming**](http://www0.cs.ucl.ac.uk/staff/W.Langdon/ftp/papers/poli08_fieldguide.pdf) (in particular, tree-based GP) was created for. In fact, the Knuth problem is a particular instance of the [**symbolic regression problem**](https://en.wikipedia.org/wiki/Symbolic_regression), which is a typical problem that GP is applied to. So, GP is probably the first approach you should try.
  
  Meanwhile, I have implemented a simple program in DEAP that tries to solve the Knuth problem. Check it [here](https://gist.github.com/nbro/dfdf39b6fe98e96c61d164dd3f6bd177). The fitness of the best solution that it has found so far (with some seed) is 4 and the solution is `floor(sqrt(float(sqrt(4))))` (here `float` just converts the input to a floating-point number, to ensure type safety). I used the *difference* as the fitness function and ran the GP algorithm for 100 generations with 100 individuals for each generation (which is *not* a lot!). I didn't tweak much the hyper-parameters, so, maybe, with the right seed and hyper-parameters, you can find the right solution.
  
  To address your concerns, in principle, you could use that encoding, but, as you note, the GA could indeed return $4$ as the best solution (which isn't actually that far away from $5$), which you could avoid my killing, at every generation, any individuals that have just that value.
  
  I didn't spend too much time on [my implementation](https://gist.github.com/nbro/dfdf39b6fe98e96c61d164dd3f6bd177) and thinking about this problem, but, as I said above, even with genetic programming and using only Knuth's operations, it could get stuck in local optima. You could try to augment my (or your) implementation with other operations, such as the multiplication and addition, and see if something improves.
  
  > **Comments:**
  > **username_0**: Thank you very much, I checked the code so thank you again, so in summary it is better to use other approach (not GA) to solve this problem  
  > **username_1**: @yaminoyuki I'm not sure which other approach would work better than GA or GP for this problem. So, I think that GP is probably your best bet, if you want to find a reasonable solution, but you have to tweak my implementation.  
  
  ---
  
  