Body: <p>I am using the Fceux emulator to create a Genetic Algorithm in Lua to play the 'Arkanoid' game. It is based on Atari Breakout.</p>
  
  <p>A member of my population contains a string of 0's and 1's.(Population size:200).
  Consider a member
  Every 10 frames a bit is read from the string.(Length of string is about 1000)
  If it is 0 the paddle moves left, If it is 1 the paddle moves right for the next 10 frames.</p>
  
  <p>Now I wrote an genetic algorithm that tries to find the best sequence of inputs to play the game.</p>
  
  <p>I have experimented with three types of fitness, One is to achieve maximum score, one is to try to reduce number of blocks to a minimum and the last one is to try to stay alive as long as possible.</p>
  
  <p>None of the three fitness seem to work.</p>
  
  <p>Then I thought that something with my crossover might be wrong.</p>
  
  <p>Every generation, I print out the average fitness of all members. Some generations it increases, while in some generations it decreases.
  I have tried changing the population size to 50,100,200,300.</p>
  
  <p>Mutation in my algorithm has a 1% Chance(If Mut_rate=1) that each of the bit will be replaced with its opposite bit.</p>
  
  <p>Now coming to the crossover, I have used yet again many methodologies.
  One of them is to just select the top 20% or 30%(cr_rate)(according to their fitness) to pass on to the next generation and killing the remaining ones.</p>
  
  <p>Another method is to add the top percentile to the population and use the remaining population to swap a few bits with top ones and add them into the next generation.</p>
  
  <pre><code>function crossover(population,rate)
      local topp=math.floor(rate*(#population));
      top={}
      for i=1,topp do
          table.insert(top,population[i])
      end
  for i=1, #population do
          local p1 = math.random(1,topp);
          local p2 = math.random(1,topp);
          --print(top[p1]);
          --print(top[p2]);
          if top[p1][2] == top[p2][2] then
              local rval = math.random(1, 10) &gt; 5;
                  if rval then
                      population[i] = top[p1];
                  else
                      population[i] = top[p2];
                  end
              elseif top[p1][2] &gt; top[p2][2] then
                  population[i] = top[p1];
              else
                  population[i] = top[p2];
          end
          population[i][2]=0;
  end
  --[[
  for i=topp+1,#population do
      local p1 = math.random(1,topp);
      local p2 = math.random(1,#population);
      local s='';
      local flag=0;
      s=string.sub(top[p1][1],1,no_controls/2)..string.sub(population[p2][1],(no_controls/2)+1,no_controls);
      population[i][1]=s;
      population[i][2]=0;
   end
    --]]
  end
  </code></pre>
  
  <p>Population is the table of population where each member has an input string and a fitness value.(Sorted , max fitness is first).
  Rate is the percentage to select the top performers.
  no_controls is the size of input string.
  The commented section of the code is where I perform the swap.</p>
  
  <p>Here is the mutation function.</p>
  
  <pre><code>function mutation(population,mut_rate)
  
      local a=0;
      local b=1;
      for i=1, #population do
          for j=1, #(population[i][1]) do
              if math.random(1, 100) &lt;= mut_rate then
                  if string.sub(population[i][1],j,j)=='1' then
                  population[i][1] = string.sub(population[i][1],1,j-1)..a..string.sub(population[i][1],j+1);
              else
                  population[i][1] = string.sub(population[i][1],1,j-1)..b..string.sub(population[i][1],j+1);
              end
              end
          end
      end
  end
  </code></pre>
  
  <p>Mut_rate is 1. And crossover rate is 0.2 or 0.5.</p>
  
  <p>I have tried changing the mutation rate from 0 to 20.
  I have also tried to change the crossover rate  as 0.2,0.5,0.7.
  And the fitness using no_blocks, score, time_alive.
  When I run the algorithm, the average fitness of the population first increases slightly , then decreases after a few generations and then remains constant forever.</p>
  
  <p>The paddle also seems to be performing  the same moves over and over again, which made be think that there might not be enough variation.</p>
  
  <p>I need help, because I have been stuck on this for a few days now.
  I need suggestions on what would be a suitable crossover and mutation function and a perfect fitness function.</p>
  
  <p>Thanks.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-05-31T09:08:31.077Z
Comments.Text: What you call a crossover sounds like a selection (likely close to the truncation selection). I may be wrong, but check your implementation and/or understanding.
  
  Apart from that, when the average fitness across the population stops changing it most likely means that the population has converged to a very small region of the search space and now consists of very similar individuals.
Comments.UserDisplayName: werediver
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-06-02T15:48:03.780Z
Comments.Text: Hey, thanks for the reply, if you look closely at the crossover code, i have commented out a section there. That crosses over some members with members of population which adds some variation. and with mutation I think the similar individuals should dissapear slowly.
Comments.UserDisplayName: Surender Harsha
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-06-02T16:18:57.790Z
Comments.Text: Selection pressure leads to convergence, unless you select for diversity (novelty search). Convergence on a local optimum is a common problem with generic algorithms. Your may try to mitigate this by enlarging the population size and/or increasing mutation rate (crossover is not considered to be an explorative operator).
Comments.UserDisplayName: werediver
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-06-03T17:10:16.413Z
Comments.Text: Increasing the mutation rate, causes the population to become more random, thereby decreasing the average fitness. I have tried using a population of 400. But it still doesn't make a difference. Even though it has nothing to do with crossover, I think selecting the right crossover method will help to converge to an optimal solution faster.
Comments.UserDisplayName: Surender Harsha
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-06-03T19:25:06.363Z
Comments.Text: A high average fitness should not be the goal, because it provides no guarantees about the best solution present, which is usually the most interesting, and a low average fitness does not mean you don't have great solutions. A higher mutation rate will bring you more diversity, thus raising chances to get into a good area of the search space, that's it. A larger population size does the same (don't put duplicates in the initial population).
Comments.UserDisplayName: werediver
Tags: <genetic-algorithms>
Title: Genetic Algorithm to Play Arkanoid(Nes) Possible Crossover and Fitness?
UserDisplayName: Surender Harsha
ThreadText: # Genetic Algorithm to Play Arkanoid(Nes) Possible Crossover and Fitness?
  
  (Asked by: username_0 on 2018-05-30)
  
  I am using the Fceux emulator to create a Genetic Algorithm in Lua to play the 'Arkanoid' game. It is based on Atari Breakout.
  A member of my population contains a string of 0's and 1's.(Population size:200).
  Consider a member
  Every 10 frames a bit is read from the string.(Length of string is about 1000)
  If it is 0 the paddle moves left, If it is 1 the paddle moves right for the next 10 frames.
  Now I wrote an genetic algorithm that tries to find the best sequence of inputs to play the game.
  I have experimented with three types of fitness, One is to achieve maximum score, one is to try to reduce number of blocks to a minimum and the last one is to try to stay alive as long as possible.
  None of the three fitness seem to work.
  Then I thought that something with my crossover might be wrong.
  Every generation, I print out the average fitness of all members. Some generations it increases, while in some generations it decreases.
  I have tried changing the population size to 50,100,200,300.
  Mutation in my algorithm has a 1% Chance(If Mut_rate=1) that each of the bit will be replaced with its opposite bit.
  Now coming to the crossover, I have used yet again many methodologies.
  One of them is to just select the top 20% or 30%(cr_rate)(according to their fitness) to pass on to the next generation and killing the remaining ones.
  Another method is to add the top percentile to the population and use the remaining population to swap a few bits with top ones and add them into the next generation.
  function crossover(population,rate)
      local topp=math.floor(rate*(#population));
      top={}
      for i=1,topp do
          table.insert(top,population[i])
      end
  for i=1, #population do
          local p1 = math.random(1,topp);
          local p2 = math.random(1,topp);
          --print(top[p1]);
          --print(top[p2]);
          if top[p1][2] == top[p2][2] then
              local rval = math.random(1, 10) > 5;
                  if rval then
                      population[i] = top[p1];
                  else
                      population[i] = top[p2];
                  end
              elseif top[p1][2] > top[p2][2] then
                  population[i] = top[p1];
              else
                  population[i] = top[p2];
          end
          population[i][2]=0;
  end
  --[[
  for i=topp+1,#population do
      local p1 = math.random(1,topp);
      local p2 = math.random(1,#population);
      local s='';
      local flag=0;
      s=string.sub(top[p1][1],1,no_controls/2)..string.sub(population[p2][1],(no_controls/2)+1,no_controls);
      population[i][1]=s;
      population[i][2]=0;
   end
    --]]
  end
  
  Population is the table of population where each member has an input string and a fitness value.(Sorted , max fitness is first).
  Rate is the percentage to select the top performers.
  no_controls is the size of input string.
  The commented section of the code is where I perform the swap.
  Here is the mutation function.
  function mutation(population,mut_rate)
  
      local a=0;
      local b=1;
      for i=1, #population do
          for j=1, #(population[i][1]) do
              if math.random(1, 100) <= mut_rate then
                  if string.sub(population[i][1],j,j)=='1' then
                  population[i][1] = string.sub(population[i][1],1,j-1)..a..string.sub(population[i][1],j+1);
              else
                  population[i][1] = string.sub(population[i][1],1,j-1)..b..string.sub(population[i][1],j+1);
              end
              end
          end
      end
  end
  
  Mut_rate is 1. And crossover rate is 0.2 or 0.5.
  I have tried changing the mutation rate from 0 to 20.
  I have also tried to change the crossover rate  as 0.2,0.5,0.7.
  And the fitness using no_blocks, score, time_alive.
  When I run the algorithm, the average fitness of the population first increases slightly , then decreases after a few generations and then remains constant forever.
  The paddle also seems to be performing  the same moves over and over again, which made be think that there might not be enough variation.
  I need help, because I have been stuck on this for a few days now.
  I need suggestions on what would be a suitable crossover and mutation function and a perfect fitness function.
  Thanks.
  
  **Tags:** genetic-algorithms
  > **Comments:**
  > **username_1**: What you call a crossover sounds like a selection (likely close to the truncation selection). I may be wrong, but check your implementation and/or understanding.  Apart from that, when the average fitness across the population stops changing it most likely means that the population has converged to a very small region of the search space and now consists of very similar individuals.  
  > **username_0**: Hey, thanks for the reply, if you look closely at the crossover code, i have commented out a section there. That crosses over some members with members of population which adds some variation. and with mutation I think the similar individuals should dissapear slowly.  
  > **username_1**: Selection pressure leads to convergence, unless you select for diversity (novelty search). Convergence on a local optimum is a common problem with generic algorithms. Your may try to mitigate this by enlarging the population size and/or increasing mutation rate (crossover is not considered to be an explorative operator).  
  > **username_0**: Increasing the mutation rate, causes the population to become more random, thereby decreasing the average fitness. I have tried using a population of 400. But it still doesn't make a difference. Even though it has nothing to do with crossover, I think selecting the right crossover method will help to converge to an optimal solution faster.  
  > **username_1**: A high average fitness should not be the goal, because it provides no guarantees about the best solution present, which is usually the most interesting, and a low average fitness does not mean you don't have great solutions. A higher mutation rate will bring you more diversity, thus raising chances to get into a good area of the search space, that's it. A larger population size does the same (don't put duplicates in the initial population).  
  
  ---
  
  ## 0 answers
  
  