2
$\begingroup$

I have a problem whose solution can be written as a binary string with a given length $N$, where $N$ is a given parameter. Standard GA works well on this problem. From runs of small values $N$, I found that optimal solutions are binary strings that contain only 01 or 011. For example, the optimal solution for $N=16$ is 0101011010101101. So I think it would be a good idea to only search the solutions space where all solutions/chromosomes only contain 01 or 011. But clearly the standard GA cannot restrict the search in the subspace I desire. One mutation or one crossover will make the new solution go into the larger solution space.

My question is: is there a way to adapt the standard GA to restrict its solution space to one where the chromosomes contain only 01 or 011?

$\endgroup$
3
  • $\begingroup$ I don't think there's any "standard GA". You could start out by creating a population that only contains individuals that have "01" or "011" (or both), and define mutation/crossover operations so that they always maintain the invariant every individual contains either substring at least once. But I'm not totally convinced any of this is a good idea -- are you absolutely sure it wouldn't hurt the performance of your search? $\endgroup$
    – Juho
    Jan 3 '14 at 13:09
  • $\begingroup$ @Juho, I think I wouldn't know the impact on performance before trying out a particular implementation. $\endgroup$
    – wdg
    Jan 3 '14 at 13:11
  • 2
    $\begingroup$ That's most probably true. Why not start with a population that contains only "good" substrings, and see what happens without any modification to other genetic operators? That might very well be enough too. Intuitively, it would take many generations to "lose" all of those good substrings, and because the search is not blind, it should not do that. $\endgroup$
    – Juho
    Jan 3 '14 at 13:12
3
$\begingroup$

Start with a population, where every candidate is "good", where "good" means they contain at least one occurrence of substrings "01" and "011".

For the mutation operator, flip a coin. If the result is heads, choose a random substring of length 2 and change it to "01". If the result is tails, choose a random substring of length 3 and change it to "011".

For the crossover operator, let $A$ and $B$ be two parents. Find say the first occurrence of substring "01" or "011" from $A$, that occurs starting from index $i$. Check if in $B$ there is an occurrence of "01" or "011" before $i$. If so, choose $i$ as your crossover point. If not, find the next occurrence from $A$, and repeat. This process will terminate at some point, because you start out with individuals containing "good" substrings, and your operators maintain an invariant that all individuals are "good".

Please note that this only really answers your question of "how do I modify my GA", and does not address whether this works performance-wise. However, this should give you ideas as to what kind of operators you can experiment with.

$\endgroup$
0
2
$\begingroup$

Here is one candidate way to impose the restriction you have in mind.

There is an isomorphism between strings in $(a|b)^*$ and strings in $(01|011)^*$: each $a$ corresponds to a $01$, and each $b$ corresponds to a $011$. For instance, the string $ab$ corresponds to $01011$, and $abb$ corresponds to $01011011$.

Now apply your genetic algorithm to the strings over $(a|b)^*$. In other words, the chromosome is a string like $abb$, not a binary string like $01011011$. For instance, you'll apply mutation and cross-over to the $abb\cdots $ strings, not the $0110\cdots$ strings. Then, when you want to evaluate the fitness of a $abb\cdots$ string, you just convert it to the corresponding $0110\cdots$ string and evaluate its fitness.

This ensures that all new chromosomes generated by your genetic algorithm obey the restriction that they are composed solely of binary strings containing $01$ or $011$.

$\endgroup$
1
  • 1
    $\begingroup$ It looks like that your proposed method does not conserve $N$, the length of the binary string. Is it possible to also conserve $N$ as well? $\endgroup$
    – wdg
    Jan 4 '14 at 9:43
1
$\begingroup$

in GA you start with population then you try to evolve or generate other populations by the two operations: crossover and mutation. If you want to restrict the search space to strings containing only $01,011$, you can alter the operations accordingly. However, make sure your statement

I found that optimal solutions are binary strings that contain only 01 or 011

is correct for all problem instances (or at least characterise the subclass where this is true).

$\endgroup$
2
  • $\begingroup$ I'm more interested in the implement of restriction. Could you suggest such an implementation? $\endgroup$
    – wdg
    Jan 4 '14 at 4:41
  • $\begingroup$ @wdg I believe this depends upon your problem and parameters setting: when you do crossover? when you do mutation? are there constraints on population generation? what are you trying to optimise? Regardless, I think the problem is much easier when you know the shape of the optimal (i.e combinations of $01,011$). In nutshell, when you encounter a string $N$, you try to mutate it to be closer to the optimal (i.e changing non $01$ entry to $01$ or $011$). $\endgroup$
    – seteropere
    Jan 4 '14 at 4:59

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.