2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Nuclear Wang Apr 30 at 13:41
  • $\begingroup$ 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? $\endgroup$ – Ryan Apr 30 at 13:45
  • $\begingroup$ 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. $\endgroup$ – Nuclear Wang Apr 30 at 13:57
  • $\begingroup$ 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. $\endgroup$ – Nuclear Wang Apr 30 at 13:59
  • $\begingroup$ 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. $\endgroup$ – Ryan Apr 30 at 14:16
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Ryan Apr 30 at 13:45
  • $\begingroup$ Yes, that would be an option. It really depends on what you want to achieve! $\endgroup$ – Oliver Mason Apr 30 at 13:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.