2

When encoding our chromosome's characteristics (for want of a better word), binary seems to be the favoured method. I understand that this gives the maximum possibilities for crossover and mutation, but it also seems to have a serious limitation.

For example, suppose I am trying to solve the problem described here, given the digits 0 through 9 and the operators +, -, * and /, find a sequence that will represent a given target number. The operators will be applied sequentially from left to right as you read. This requires the digits 1 to 9, as well as the four operators, giving 13 characters to be encoded. Thus, I need to use a binary representation with a length of 4, with a total of 16 possible binary strings.

Now, for a sequence to be valid in that problem, it would need to be of the form...

d o d o d ... o d

...where d means a digit and o means an operator. Suppose you are looking at a sequence of length 5 (eg 1 + 2 * 3). There are 9 binary representations that are valid for digits (ie probability 0.5625) and 4 that are valid for operators (probability 0.25). Thus, there is only a probability of 0.5625 * 0.25 * 0.5625 * 0.25 * 0.5625 = 0.011124 of a random binary string being a valid sequence. In other words, only about 1% of the strings will be valid.

This seems hugely inefficient. Crossover and mutation are going to invalidate any existing valid strings, so I don't see how the GA would ever converge.

Related to this is the question of how to handle invalid binary strings. Suppose you've crossed and mutated, and you end up with an invalid string. Do you just assign a huge fitness value, so it will be discarded as soon as possible, or do you throw it away and try and find a valid child chromosome? The former option sounds inefficient as you would have very few valid chromosomes in your population, and the latter sounds just as inefficient, as you would spend ages trying to find valid binary strings.

Forgive me if this is a dumb question, but I'm still quite new to GAs, and am struggling to understand what you would do in a case like this.

  • 1
    It seems no one understands what you are asking. Maybe because your statement is wrong, genetic encoding generally is not expressed in a binary format. en.wikipedia.org/wiki/Genetic_code Please try to eliminate anything not relevant from your question. – Martin Maat Jan 8 '17 at 16:53
  • 3
    "binary seems to be the favoured method" What makes you think so? – Euphoric Jan 8 '17 at 16:53
  • @Euphoric My comment was based purely on what I've read. Maybe that was all just introductory stuff, which clouded my view, but I got the strong impression that binary was preferred because it allowed a lot of flexibility in crossover and mutation. My only experience with non-binary encoding failed fairly badly, and I was led to believe that this was because it didn't give enough flexibility on those areas. Do you have any links to info that will explain how to do non-binary encoding properly? Maybe that would answer my question – Avrohom Yisroel Jan 8 '17 at 18:14
  • For example here : obitko.com/tutorials/genetic-algorithms/encoding.php – Euphoric Jan 9 '17 at 8:49
6

Picking the right way to represent the genotype is quite important when using a genetic algorithm. There are many ways to do it, binary being one of them.

The reason why you might think that binary is most used is because it is simplest to implement and often used in academic settings. But in real world, lots of work goes into creating proper genotype representation as to solve the exact problems you are describing.

There is also some historical baggage. Binary can be made quite space-efficient, so it would be used in times, where memory was hard to come by. So it would be good pick when genetic algorithms were first explored, which was pretty much when computers became more academically available. But this is not really a problem now, when you have access to gigabytes of memory and main problem is often time it takes to calculate the fitness, not how much memory the genotype takes.

Some more details on wikipedia.

Finding a suitable representation of the problem domain for a chromosome is an important consideration, as a good representation will make the search easier by limiting the search space; similarly, a poorer representation will allow a larger search space. The mutation operator and crossover operator employed by the genetic algorithm must also take into account the chromosome's design.

3

As others have said, binary is useful for efficient manipulation of the representation. It has also been pointed out that how you encode the representation is important.

To bring these two together, I'd like to offer a representative of your length 5 example that should give you a flavour of how the representation can affect the efficiency.

So, we are looking for a binary representation for d o d o d where d is in (0-9) and o is in (+ - x /).

We start by noting that there are 4 operators in o, so we could encode each in 2 bits.

Secondly, are looking for a Binary Coded Decimal representation for d. We note that there are 3 decimal numbers. If we were to encode these together, we would find that we have 10^3 (1000) combinations which can be encoded in 10 bits (2^10=1024). There are well known encodings of BCD for 3 numbers e.g. Chen-Ho Encoding that do indeed use 10 bits.

So, for this example representation, we could encode as 3 decimals using Chen-Ho plus 2 2-bit operators. This would give us an encoding efficiency of 1000/1024 (x1x1) ~= 97.7%. Somewhat better than the 1% in the candidate encoding.

This encoding is not perfect, of course. In particular it doesn't trivially scale to arbitrary sequences. But hopefully it gives a sense of how the encoding representation can markedly affect the encoding efficiency.

  • It looks like you're saying that the trick is to pick an encoding that most efficiently encodes the range of values. Is that right? What do you do if crossover and mutation produce an invalid encoding? Do you just give that chromosome an arbitrarily high fitness so it gets dropped from the next generation? Thanks for the reply. – Avrohom Yisroel Jan 9 '17 at 14:44
  • 1
    @Avrohom Yisroel Pretty much.You can do that or just check it and throw it out of the next population (and replace with another if necessary). Whatever works. – Alex Jan 9 '17 at 19:08
2

We used ASCII to solve a number of problems in my AI class, so it's not like we always use binary.

Using binary encoding is just a cheap way to keep the odds of producing meaningless nonsense chromosomes to a minimum. If you have 15 symbols 4 random bits have a 15/16 chance of being meaningful. 8 have a 15/256 chance.

If you don't like having to decode the binary, that whole problem can be avoided by being a little smarter about what you randomize (mutate) in the first place. Do this right and you can work in ASCII almost as efficiently as binary.

Some explanations of genetic algorithms stick to binary just because they don't want to distract you with the ASCII encoding shenanigans. There are many ways to encode. There is no reason to think perfectly packed binary is always best. O(1/2 n) is still just O(n). Beware of micro-optimizations.

  • Thanks for the reply, but it wasn't really the encoding and decoding that I was questioning. I was more bothered about the fact that using binary meant that the number of possibilities in your representation was restricted to powers of 2, which rarely matches the number of possibilities in the actual problem. Do you know where I'd find more info about crossover and mutation in (say) ASCII? My only attempt at this was a dismal failure, and I was told it was because not using binary restricted the GA from exploring the solution space effectively. – Avrohom Yisroel Jan 8 '17 at 18:20
  • Meh that's just a lazy way to say your mutator sucks. Which might not even be the problem. These can be hard to debug. Post you mutator design. We might be able to turn this into a good stack exchange question. – candied_orange Jan 8 '17 at 19:08
  • The way I understood it was that mutating made some random change to the genes. If the number of symbols you're using falls short of the possible number (eg you have 9 symbols, but need 4 bits to encode) then a random mutation is likely to produce a meaningless gene string. It looks like either I need a more efficient encoding (in which case I need to know how to find one), or I need to know how to mutate in a way that produces valid genes, ie not a completely random mutation. Either way, could you explain more? I think that was the underlying point of my question. – Avrohom Yisroel Jan 9 '17 at 17:36
0

Binary enconding is:

  1. (oftentimes) the most memory-efficient one as most genes can be expressed as single boolean,
  2. the most efficient for most popular crossover algorithms (require very few boolean algebra operations).
  • Why is that so? – qwerty_so Jan 8 '17 at 20:32
  • @ThomasKilian I supplemented the answer. It is more clear now? – Maciej Chałapuk Jan 8 '17 at 21:52
  • 1
    Still very terse, but since this is not my main subject I'll not getting picky. – qwerty_so Jan 8 '17 at 22:36

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.