Answers.Body: <p>How do you calculate fitness for your organism if there are only two states? I would think it would be a solution to work on combinations of cells:</p>
  
  <p>If you have blocks of, say, 4x4 cells, then each organism would be encoded using 16 bits. A crossover then is like overlaying two 4x4 blocks, picking the new block from either the first or the second parent. Effectively you are doing this:</p>
  
  <pre><code>0011                   1111                 xx11
  0001  combined with    0000  would become   000x
  1001                   0000                 x00x
  1111                   0000                 xxxx
  </code></pre>
  
  <p>(this would be a bottom-right corner combined with a top wall segment)</p>
  
  <p>or, as a single bit-string:</p>
  
  <pre><code>0011000110011111 +
  1111000000000000 =
  xx11000xx00xxxxx
  </code></pre>
  
  <p>where 'x' can be either 0 or 1, as this is where the two organisms are different.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-30T13:45:05.930Z
Answers.Text: This is why I was considering the idea of rating neighbourhoods as a whole for fitness, though I can't find any examples of people doing this so it makes me very unsure. So, let's say I have a 3x3 grid and I rate cells with alive cells in the corner highly. Would that be reasonable?
Answers.UserDisplayName: Ryan
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-30T13:46:28.250Z
Answers.Text: Yes, that would be an option. It really depends on what you want to achieve!
Answers.UserDisplayName: Oliver Mason
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-30T13:28:15.513Z
Answers.LastActivityDate: 2020-04-30T13:28:15.513Z
Answers.UserDisplayName: Oliver Mason
Body: <p>I'm currently working on a project where I am using a basic cellular automata and a genetic algorithm to create dungeon-like maps. Currently, I'm having an incredibly hard time understanding how exactly crossover works when my output can only be two states: DEAD or ALIVE (1 or 0).</p>
  
  <p>I understand crossover conceptually - you find two fit members of the population and they exchange genetic material, hopefully producing a fitter offspring. I also understand this is usually done by performing k-point crossover on bit strings (but can also be done with real numbers). </p>
  
  <p><em>However, even if I encode my DEAD/ALIVE cells into bits and cross them over, what do I end up with?</em> The cell can <em>only</em> be DEAD or ALIVE. <em>Will the crossover give me some random value that is outside this range?</em></p>
  
  <p><em>And even if I were to work on floating-point numbers, wouldn't I just end up with a 1 or 0 anyway?</em> In that case, it seems like it would be better to just randomly mutate DEAD cells into ALIVE cells, or vice versa.</p>
  
  <p>I've read several papers on the topic, but none seem to explain this particular issue (in a language I can understand, anyway). Intuitively, I thought maybe I can perform crossover on a <em>neighbourhood</em> of cells - so I find 2 fit neighbourhoods, and then they exchange members (for example, neighbourhood A gives 4 of its neighbours to neighbourhood B). However, I have not seen this idea anywhere, which leads me to believe it must be fundamentally wrong.</p>
  
  <p>Any help would be greatly appreciated, I'm really stuck on this one.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-30T13:41:44.337Z
Comments.Text: You mention both "fitness of cells" and "fitness of individuals" - you should be using the latter to select individuals for crossover, not the former. A cell can only be dead or alive, but the whole individual has more than 2 states - its fitness could be defined as the sum of "alive" cells. If your fitness function of individuals truly only has 2 states, then you have a problem that's not well suited to genetic algorithms.
Comments.UserDisplayName: Nuclear Hoagie
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-30T13:45:55.813Z
Comments.Text: What is the difference between "fitness of cells" and "fitness of individuals" in my context? I am using a 100x100 grid, which is full of cells that are either dead or alive. What is a 'whole individual'? A neighbourhood around a single cell? 3x3 for example?
Comments.UserDisplayName: Ryan
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-30T13:57:26.693Z
Comments.Text: Your goal is to find a 100x100 grid that meets some criterion. How close the whole grid is to meeting that criterion is your fitness function of individuals. If your goal was to turn the whole grid to 1's, your fitness function would be simply the count of how many 1's you have. If your goal was to have no 1's adjacent, your fitness function might be some large number minus the count of adjacent 1's. Once you have scored each 100x100 grid (each individual), you choose the best ones to "mate" and crossover.
Comments.UserDisplayName: Nuclear Hoagie
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-30T13:59:52.090Z
Comments.Text: Once you pick what individuals to mate based on their fitness, you do crossover by selecting parts of each - maybe you take the left half of one parent and the right half of the other, or maybe one quadrant from each of 4 parents. The crossover just copies different parts of the parent individuals, it doesn't combine them in any way by "averaging" the values. Crossover should leave you with identifiable parts from each parent, but nothing that wasn't in either parent.
Comments.UserDisplayName: Nuclear Hoagie
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-30T14:16:34.727Z
Comments.Text: This is considered to be 'Generational' evolution, right? I was originally planning to do a 'Steady' evolution where I only generate one map and mutate the cells within it many times. Would you say it's better to generate many maps? If I were aiming to create, for example, a 100x100 grid that has several 'room like' sections.
Comments.UserDisplayName: Ryan
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-30T14:38:11.010Z
Comments.Text: I'm not terribly familiar with the "Steady" methodology. One of the things I like about generational GAs is that you can explore many parts of the solution space at once in the beginning, and hone in the promising ones, which is achieved by generating many maps and iterating over them. It's not clear to me how crossover would even work in the Steady method, since you only have a single map - you can mutate the cells, and you can copy information from one part of the map to another, but your next iteration will have only the information that came from the previous one, plus random differences.
Comments.UserDisplayName: Nuclear Hoagie
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-30T15:06:59.483Z
Comments.Text: I like the idea of a generational GA, but I imagine storage would be an issue. With a 100x100 grid, I'd be storing arrays/lists of 10,000 cells - wouldn't that be very awkward to deal with/slow?
Comments.UserDisplayName: Ryan
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-30T15:25:27.430Z
Comments.Text: Depends on what you're running on, but that doesn't seem like an outrageous size - even a population of 100 individuals would give you some variation. I often work with data that has 1000 samples and 10000 features, which would be the same as a 100x100 grid with 1000 individuals. If storage is a big issue, it looks like you can encode your grid variables as boolean, which will give you significant space savings in most languages.
Comments.UserDisplayName: Nuclear Hoagie
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-30T15:49:03.370Z
Comments.Text: OK, sounds good. This has been very useful - thank you for the responses.
Comments.UserDisplayName: Ryan
Tags: <genetic-algorithms><crossover-operators><genetic-operators>
Title: How does the crossover operator work when my output contains only 2 states?
UserDisplayName: Ryan
ThreadText: # How does the crossover operator work when my output contains only 2 states?
  
  (Asked by: username_0 on 2020-04-30)
  
  I'm currently working on a project where I am using a basic cellular automata and a genetic algorithm to create dungeon-like maps. Currently, I'm having an incredibly hard time understanding how exactly crossover works when my output can only be two states: DEAD or ALIVE (1 or 0).
  
  I understand crossover conceptually - you find two fit members of the population and they exchange genetic material, hopefully producing a fitter offspring. I also understand this is usually done by performing k-point crossover on bit strings (but can also be done with real numbers).
  
  *However, even if I encode my DEAD/ALIVE cells into bits and cross them over, what do I end up with?* The cell can *only* be DEAD or ALIVE. *Will the crossover give me some random value that is outside this range?*
  
  *And even if I were to work on floating-point numbers, wouldn't I just end up with a 1 or 0 anyway?* In that case, it seems like it would be better to just randomly mutate DEAD cells into ALIVE cells, or vice versa.
  
  I've read several papers on the topic, but none seem to explain this particular issue (in a language I can understand, anyway). Intuitively, I thought maybe I can perform crossover on a *neighbourhood* of cells - so I find 2 fit neighbourhoods, and then they exchange members (for example, neighbourhood A gives 4 of its neighbours to neighbourhood B). However, I have not seen this idea anywhere, which leads me to believe it must be fundamentally wrong.
  
  Any help would be greatly appreciated, I'm really stuck on this one.
  
  **Tags:** genetic-algorithms, crossover-operators, genetic-operators
  
  > **Comments:**
  > **username_1**: You mention both "fitness of cells" and "fitness of individuals" - you should be using the latter to select individuals for crossover, not the former. A cell can only be dead or alive, but the whole individual has more than 2 states - its fitness could be defined as the sum of "alive" cells. If your fitness function of individuals truly only has 2 states, then you have a problem that's not well suited to genetic algorithms.  
  > **username_0**: What is the difference between "fitness of cells" and "fitness of individuals" in my context? I am using a 100x100 grid, which is full of cells that are either dead or alive. What is a 'whole individual'? A neighbourhood around a single cell? 3x3 for example?  
  > **username_1**: Your goal is to find a 100x100 grid that meets some criterion. How close the whole grid is to meeting that criterion is your fitness function of individuals. If your goal was to turn the whole grid to 1's, your fitness function would be simply the count of how many 1's you have. If your goal was to have no 1's adjacent, your fitness function might be some large number minus the count of adjacent 1's. Once you have scored each 100x100 grid (each individual), you choose the best ones to "mate" and crossover.  
  > **username_1**: Once you pick what individuals to mate based on their fitness, you do crossover by selecting parts of each - maybe you take the left half of one parent and the right half of the other, or maybe one quadrant from each of 4 parents. The crossover just copies different parts of the parent individuals, it doesn't combine them in any way by "averaging" the values. Crossover should leave you with identifiable parts from each parent, but nothing that wasn't in either parent.  
  > **username_0**: This is considered to be 'Generational' evolution, right? I was originally planning to do a 'Steady' evolution where I only generate one map and mutate the cells within it many times. Would you say it's better to generate many maps? If I were aiming to create, for example, a 100x100 grid that has several 'room like' sections.  
  > **username_1**: I'm not terribly familiar with the "Steady" methodology. One of the things I like about generational GAs is that you can explore many parts of the solution space at once in the beginning, and hone in the promising ones, which is achieved by generating many maps and iterating over them. It's not clear to me how crossover would even work in the Steady method, since you only have a single map - you can mutate the cells, and you can copy information from one part of the map to another, but your next iteration will have only the information that came from the previous one, plus random differences.  
  > **username_0**: I like the idea of a generational GA, but I imagine storage would be an issue. With a 100x100 grid, I'd be storing arrays/lists of 10,000 cells - wouldn't that be very awkward to deal with/slow?  
  > **username_1**: Depends on what you're running on, but that doesn't seem like an outrageous size - even a population of 100 individuals would give you some variation. I often work with data that has 1000 samples and 10000 features, which would be the same as a 100x100 grid with 1000 individuals. If storage is a big issue, it looks like you can encode your grid variables as boolean, which will give you significant space savings in most languages.  
  > **username_0**: OK, sounds good. This has been very useful - thank you for the responses.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2020-04-30. Score: 0 | Accepted answer
  
  How do you calculate fitness for your organism if there are only two states? I would think it would be a solution to work on combinations of cells:
  
  If you have blocks of, say, 4x4 cells, then each organism would be encoded using 16 bits. A crossover then is like overlaying two 4x4 blocks, picking the new block from either the first or the second parent. Effectively you are doing this:
  
  ```
  0011                   1111                 xx11
  0001  combined with    0000  would become   000x
  1001                   0000                 x00x
  1111                   0000                 xxxx
  
  ```
  
  (this would be a bottom-right corner combined with a top wall segment)
  
  or, as a single bit-string:
  
  ```
  0011000110011111 +
  1111000000000000 =
  xx11000xx00xxxxx
  
  ```
  
  where 'x' can be either 0 or 1, as this is where the two organisms are different.
  
  > **Comments:**
  > **username_0**: This is why I was considering the idea of rating neighbourhoods as a whole for fitness, though I can't find any examples of people doing this so it makes me very unsure. So, let's say I have a 3x3 grid and I rate cells with alive cells in the corner highly. Would that be reasonable?  
  > **username_2**: Yes, that would be an option. It really depends on what you want to achieve!  
  
  ---
  
  