Answers.Body: <p>First of all, for a lot of realistic problems, the fitness function evaluation is usually orders of magnitude greater in complexity than the rest of the genetic algorithm. This is not always true, but often is true (e.g. imagine trying to optimise a simulation where you need to execute the simulation completely to obtain the fitness). So optimising the GA itself might only be helpful when the fitness function is lightweight (e.g. it's a mathematical function as used in some competitions).</p>
  <p>While your diagram shows a lot of operators, it doesn't show variations of the GA itself. Here are two:</p>
  <ul>
  <li>generational: selects a new population at each iteration after performing mutation and crossover on the existing population to generate offspring (which are usually more in number than the population size)</li>
  <li>steady state: maintains a single population and replaces only individuals during each iteration with their offspring according to selection/replacement rules, so uses less memory than a traditional GA</li>
  </ul>
  <p>If you really wanted to maximise efficiency in the GA, a steady state approach would probably work best combined with tournament selection, as tournament selection does not require any sorting. The mutation/crossover operators you list are likely to all be quite efficient, but simpler methods are likely to to be the most efficient (e.g. bit flip mutation+1 point crossover). For a realistic problem, however, problem-specific operators usually work best.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-25T20:48:32.163Z
Answers.LastActivityDate: 2021-04-25T21:26:22.277Z
Answers.LastEditDate: 2021-04-25T21:26:22.277Z
Answers.UserDisplayName: Mike NZ
Body: <p>In researching genetic algorithms, it seems that there are various methods of <a href="https://ai.stackexchange.com/q/9077/2444">selection</a> and other operator methods that can significantly change the performance. For example, this picture contains <em>some</em> of the methods that could be used:</p>
  <p><a href="https://i.sstatic.net/zG4Mp.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/zG4Mp.png" alt="generic algorithm operators" /></a></p>
  <p>Presumably, you can mix &amp; match these operators to optimize whatever problem you're trying to solve.</p>
  <p>What most people care about is <em>how many iterations</em> it takes to get to the target. This is understandable, but I've seen things that would be inefficient in real systems such as:</p>
  <ul>
  <li><p>using sort on the current population <span class="math-container">$\mathcal{O}(n \log n)$</span> and picking the first n members for the mating pool</p>
  </li>
  <li><p>appending to a constantly resizing slice to create a mating pool instead of rewriting on the current array</p>
  </li>
  </ul>
  <p>What I am looking for is, how can I arrive at the target using the <strong>least amount of computation and memory</strong> possible. The number of iterations and the time taken to get there is still a secondary priority.</p>
  <p>It's possible that it may be the process of picking the right operators, but what I am also considering is how parallelizable the implementation could be as well.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-25T22:31:10.003Z
Comments.Text: To me, what you are asking is a variation of the traveling salesman problem.  You can only know you have found the best way if you have tried all of the ways, which is the key challenge and why we use heuristics rather than algorithms for this type of problem.  Genetic search algorithms seem to be this type of optimization approach.
Comments.UserDisplayName: David Hoelzer
Tags: <genetic-algorithms><evolutionary-algorithms><time-complexity><crossover-operators><selection-operators>
Title: What is the most computationally efficient genetic algorithm?
UserDisplayName: Ron Germano
ThreadText: # What is the most computationally efficient genetic algorithm?
  
  (Asked by: username_0 on 2021-04-24)
  
  In researching genetic algorithms, it seems that there are various methods of [selection](https://ai.stackexchange.com/q/9077/2444) and other operator methods that can significantly change the performance. For example, this picture contains *some* of the methods that could be used:
  
  [![generic algorithm operators](https://i.sstatic.net/zG4Mp.png)](https://i.sstatic.net/zG4Mp.png)
  
  Presumably, you can mix & match these operators to optimize whatever problem you're trying to solve.
  
  What most people care about is *how many iterations* it takes to get to the target. This is understandable, but I've seen things that would be inefficient in real systems such as:
  
  * using sort on the current population $\mathcal{O}(n \log n)$ and picking the first n members for the mating pool
  * appending to a constantly resizing slice to create a mating pool instead of rewriting on the current array
  
  What I am looking for is, how can I arrive at the target using the **least amount of computation and memory** possible. The number of iterations and the time taken to get there is still a secondary priority.
  
  It's possible that it may be the process of picking the right operators, but what I am also considering is how parallelizable the implementation could be as well.
  
  **Tags:** genetic-algorithms, evolutionary-algorithms, time-complexity, crossover-operators, selection-operators
  
  > **Comments:**
  > **username_1**: To me, what you are asking is a variation of the traveling salesman problem.  You can only know you have found the best way if you have tried all of the ways, which is the key challenge and why we use heuristics rather than algorithms for this type of problem.  Genetic search algorithms seem to be this type of optimization approach.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2021-04-25. Score: 2 | Accepted answer
  
  First of all, for a lot of realistic problems, the fitness function evaluation is usually orders of magnitude greater in complexity than the rest of the genetic algorithm. This is not always true, but often is true (e.g. imagine trying to optimise a simulation where you need to execute the simulation completely to obtain the fitness). So optimising the GA itself might only be helpful when the fitness function is lightweight (e.g. it's a mathematical function as used in some competitions).
  
  While your diagram shows a lot of operators, it doesn't show variations of the GA itself. Here are two:
  
  * generational: selects a new population at each iteration after performing mutation and crossover on the existing population to generate offspring (which are usually more in number than the population size)
  * steady state: maintains a single population and replaces only individuals during each iteration with their offspring according to selection/replacement rules, so uses less memory than a traditional GA
  
  If you really wanted to maximise efficiency in the GA, a steady state approach would probably work best combined with tournament selection, as tournament selection does not require any sorting. The mutation/crossover operators you list are likely to all be quite efficient, but simpler methods are likely to to be the most efficient (e.g. bit flip mutation+1 point crossover). For a realistic problem, however, problem-specific operators usually work best.
  
  
  ---
  
  