Answers.Body: <p>There are multiple ways to handle 'illegal' individuals, each one with pros and cons:</p>
  <ul>
  <li><p><strong>Abortive methods</strong>: The individuals that violate constraints are eliminated as soon as discovered (i.e. after crossover or mutation) and new individuals are generated in order to keep the population stable. This usually implies a slower creation of new generations, as some individuals are discarded.</p>
  </li>
  <li><p><strong>Contraceptive methods</strong>: The crossover and mutation are written in such a way to make it impossible for a newly generated individual to violate any constraints. This way to act is usually more efficient, as no individuals are discarded, but it might not be possible.</p>
  </li>
  <li><p><strong>Penalization function</strong>: The fitness function gives a huge penalization to the individuals that violate constraints (usually proportionally to the constraints it violates). In this way they usually do not get to reproduce and their genes are eventually lost. You'd go this way if illegal individuals are very rare and there is no possibility for them to take over the full population (causing the algorithm to fail).</p>
  </li>
  </ul>
  <p>By experience, try to act on the crossover algorithm first (<em>contraceptive way</em>), it is the best way to exclude constraints violations. If this is not possible, pick one of the other two methods, depending on how often the illegal individuals are generated (not so often -&gt; <em>penalization</em>, very ofter -&gt; <em>abortive</em>)  and on how easy it is to penalize individuals that violate constraints (easy -&gt; <em>penalization</em>, not easy -&gt; <em>abortive</em>).</p>
  <hr />
  <p>A contraceptive way to handle your example is writing the crossover as following:</p>
  <pre><code>const crossover = (p1: boolean[], p2: boolean[]) =&gt;
  {
      // simple crossover, getting half genome from each parent
      const child: boolean[] = [...p1.slice(0,3), ...p2.slice(3,6)];
  
      // contraceptive part
      while (countEnabledGenes(child) &gt; 3) child[getRandomIndex()] = false
  
      return child
  }
  
  const countEnabledGenes = (genome: boolean[]) =&gt; genome.filter(gene =&gt; gene).length;
  const getRandomIndex = () =&gt; Math.round(Math.random() * 6);
  
  </code></pre>
  <p>But this is a fairly complex problem and each scenario has its own specifications.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-08T09:13:40.347Z
Answers.LastActivityDate: 2023-07-04T18:25:51.330Z
Answers.LastEditDate: 2023-07-04T18:25:51.330Z
Answers.UserDisplayName: Alvin Sartor
Body: <p>I'm working on a genetic algorithm with a constraint on the sum of the alleles, e.g. if we use regular binary coding and a chromosome is 5-bits long I'd like to constrain it so that the sum of the bits has to be 3 or less (011100 is valid but 011110 is not). Moreover, the fitness function is such that invalid chromosomes cannot be evaluated.</p>
  
  <p>Any ideas on how this problem could be approached? </p>
  
  <p>I've started looking into the direction of messy GAs (since those can be over-specified) but I'm not sure if there's anything there.</p>
  
Tags: <genetic-algorithms><genetic-programming><constraint-satisfaction-problems>
Title: How can I develop a genetic algorithm with a constraint on the sum of alleles?
UserDisplayName: Mark
ThreadText: # How can I develop a genetic algorithm with a constraint on the sum of alleles?
  
  (Asked by: username_0 on 2020-01-07)
  
  I'm working on a genetic algorithm with a constraint on the sum of the alleles, e.g. if we use regular binary coding and a chromosome is 5-bits long I'd like to constrain it so that the sum of the bits has to be 3 or less (011100 is valid but 011110 is not). Moreover, the fitness function is such that invalid chromosomes cannot be evaluated.
  
  Any ideas on how this problem could be approached?
  
  I've started looking into the direction of messy GAs (since those can be over-specified) but I'm not sure if there's anything there.
  
  **Tags:** genetic-algorithms, genetic-programming, constraint-satisfaction-problems
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-01-08. Score: 2
  
  There are multiple ways to handle 'illegal' individuals, each one with pros and cons:
  
  Abortive methods: The individuals that violate constraints are eliminated as soon as discovered (i.e. after crossover or mutation) and new individuals are generated in order to keep the population stable. This usually implies a slower creation of new generations, as some individuals are discarded.
  
  Contraceptive methods: The crossover and mutation are written in such a way to make it impossible for a newly generated individual to violate any constraints. This way to act is usually more efficient, as no individuals are discarded, but it might not be possible.
  
  Penalization function: The fitness function gives a huge penalization to the individuals that violate constraints (usually proportionally to the constraints it violates). In this way they usually do not get to reproduce and their genes are eventually lost. You'd go this way if illegal individuals are very rare and there is no possibility for them to take over the full population (causing the algorithm to fail).
  
  
  By experience, try to act on the crossover algorithm first (contraceptive way), it is the best way to exclude constraints violations. If this is not possible, pick one of the other two methods, depending on how often the illegal individuals are generated (not so often -> penalization, very ofter -> abortive)  and on how easy it is to penalize individuals that violate constraints (easy -> penalization, not easy -> abortive).
  
  A contraceptive way to handle your example is writing the crossover as following:
  const crossover = (p1: boolean[], p2: boolean[]) =>
  {
      // simple crossover, getting half genome from each parent
      const child: boolean[] = [...p1.slice(0,3), ...p2.slice(3,6)];
  
      // contraceptive part
      while (countEnabledGenes(child) > 3) child[getRandomIndex()] = false
  
      return child
  }
  
  const countEnabledGenes = (genome: boolean[]) => genome.filter(gene => gene).length;
  const getRandomIndex = () => Math.round(Math.random() * 6);
  
  
  But this is a fairly complex problem and each scenario has its own specifications.
  
  
  ---
  
  