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.