Answers.Body: <p>Yes it has been tried. In fact there is a whole field, dubbed <a href="https://en.wikipedia.org/wiki/Genetic_programming" rel="nofollow noreferrer">Genetic Programming</a>.</p>
  
  <p>There is an <a href="http://www.human-competitive.org/awards" rel="nofollow noreferrer">annual competition</a> to obtain "Human-Competitive" algorithms, and many instances of those have been found over the years.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-22T23:26:57.727Z
Answers.LastActivityDate: 2019-12-22T23:26:57.727Z
Answers.UserDisplayName: Rexcirus
Body: <p>Thomas Ray's <a href="https://www.google.com/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=5&amp;ved=2ahUKEwjIl_S1w4njAhV1sHEKHSt3DbYQFjAEegQIAxAC&amp;url=https%3A%2F%2Fwww.cc.gatech.edu%2F~turk%2Fbio_sim%2Farticles%2Ftierra_thomas_ray.pdf&amp;usg=AOvVaw26-NAiCH4NxxWbXKEK20r5" rel="nofollow noreferrer">Tierra</a> is a computer program which simulates life.</p>
  
  <p>In the linked paper, he argues how this simulation may have real-world applications, showing how his digital organisms (computer programs) evolve in an interesting way: they develop novel ways of replicating themselves and become faster at it (he argues that the evolved organisms employ an algorithm which is 5 times faster than the original one he wrote).</p>
  
  <p>Tierra's approach is different from standard GAs:</p>
  
  <ul>
  <li>While in GAs usually there is a set of genomes manipulated, copied and mutated by the program, in Tierra everything is done by the programs themselves: they self-replicate.</li>
  <li>There is no explicit fitness function: instead, digital organisms compete for energy resources (CPU time) and space resources (memory). </li>
  <li>Organisms which take a long time to replicate reproduce less frequently, and organisms who create many errors are penalized (they die out faster).</li>
  <li>Tierran machine language is extremely small: operands included, it only has 32 instructions. Oftentimes, so called RISC instruction sets have a limited set of opcodes, but if you consider the operands, you get billions of possible instructions.</li>
  <li>Consequentially, Tierran code is less brittle, and you can mutate it without breaking the code. In contrast, usually, if you mutate randomly some machine code, you get a broken program.</li>
  </ul>
  
  <p>I was wondering if we could use this approach to optimize machine code. For instance, let's assume we have some assembly-like program which computes a certain function <span class="math-container">$f$</span>. We could link reproduction time with efficiently computing <span class="math-container">$f$</span>, and life-span with correctly computing it. This could motivate programs to find novel and faster ways to compute <span class="math-container">$f$</span>.</p>
  
  <p>Has anything similar ever been tried? Could it work? Where should I look into?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-06-27T11:48:25.270Z
Comments.Text: "There is no explicit fitness function: instead, digital organisms compete for energy resources (CPU time) and space resources (memory).", the competition for resources is the fitness function here, so, from your description, this looks like a genetic algorithm, even though, you say, the author does not want to admit it or wants to make it seem as he created something novel.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-06-27T11:53:01.973Z
Comments.Text: @nbro Technically yes, there is a fitness function. This is just a variation on the "standard" GA approach I think. Still I think this paper brings some interesting ideas to the table (like the extremely small Instruction Set and all the life-death cycle thing). Too bad I can't find anything online about this
Comments.UserDisplayName: olinarr
Tags: <genetic-algorithms><optimization><genetic-programming><artificial-life>
Title: Can we use the Tierra approach to optimize machine code?
UserDisplayName: olinarr
ThreadText: # Can we use the Tierra approach to optimize machine code?
  
  (Asked by: username_0 on 2019-06-27)
  
  Thomas Ray's [Tierra](https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=5&ved=2ahUKEwjIl_S1w4njAhV1sHEKHSt3DbYQFjAEegQIAxAC&url=https%3A%2F%2Fwww.cc.gatech.edu%2F~turk%2Fbio_sim%2Farticles%2Ftierra_thomas_ray.pdf&usg=AOvVaw26-NAiCH4NxxWbXKEK20r5) is a computer program which simulates life.
  
  In the linked paper, he argues how this simulation may have real-world applications, showing how his digital organisms (computer programs) evolve in an interesting way: they develop novel ways of replicating themselves and become faster at it (he argues that the evolved organisms employ an algorithm which is 5 times faster than the original one he wrote).
  
  Tierra's approach is different from standard GAs:
  
  * While in GAs usually there is a set of genomes manipulated, copied and mutated by the program, in Tierra everything is done by the programs themselves: they self-replicate.
  * There is no explicit fitness function: instead, digital organisms compete for energy resources (CPU time) and space resources (memory).
  * Organisms which take a long time to replicate reproduce less frequently, and organisms who create many errors are penalized (they die out faster).
  * Tierran machine language is extremely small: operands included, it only has 32 instructions. Oftentimes, so called RISC instruction sets have a limited set of opcodes, but if you consider the operands, you get billions of possible instructions.
  * Consequentially, Tierran code is less brittle, and you can mutate it without breaking the code. In contrast, usually, if you mutate randomly some machine code, you get a broken program.
  
  I was wondering if we could use this approach to optimize machine code. For instance, let's assume we have some assembly-like program which computes a certain function $f$. We could link reproduction time with efficiently computing $f$, and life-span with correctly computing it. This could motivate programs to find novel and faster ways to compute $f$.
  
  Has anything similar ever been tried? Could it work? Where should I look into?
  
  **Tags:** genetic-algorithms, optimization, genetic-programming, artificial-life
  > **Comments:**
  > **username_1**: "There is no explicit fitness function: instead, digital organisms compete for energy resources (CPU time) and space resources (memory).", the competition for resources is the fitness function here, so, from your description, this looks like a genetic algorithm, even though, you say, the author does not want to admit it or wants to make it seem as he created something novel.  
  > **username_0**: @nbro Technically yes, there is a fitness function. This is just a variation on the "standard" GA approach I think. Still I think this paper brings some interesting ideas to the table (like the extremely small Instruction Set and all the life-death cycle thing). Too bad I can't find anything online about this  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2019-12-22. Score: 3 | Accepted answer
  
  Yes it has been tried. In fact there is a whole field, dubbed [Genetic Programming](https://en.wikipedia.org/wiki/Genetic_programming).
  
  There is an [annual competition](http://www.human-competitive.org/awards) to obtain "Human-Competitive" algorithms, and many instances of those have been found over the years.
  
  
  ---
  
  