Genetics algorithms theoretical question

Question

Hi All!

I'm currently reading "Artificial Intelligence: A Modern Approach" (Russell+Norvig) and "Machine Learning" (Mitchell) - and trying to learn basics of AINN.

In order to understand few basic things I have two 'greenhorn' questions:

Q1: In a genetic algorithm given the two parents A and B with the chromosomes 001110 and 101101, respectively, which of the following offspring could have resulted from a one-point crossover?

a: 001101

b: 001110

Q2: Which of the above offspring could have resulted from a two-point crossover? and why?

Please advise.

Answer 1

One point crossover is when you make one join from each parent, two point crossover is when you make two joins. i.e. two from one parent and one from the others.

See crossover (wikipedia) for further info.

Answer 2

Regarding Q1, (a) could have been produced by a one-point crossover, taking bits 0-4 from parent A and bit 5 from parent B. (b) could not unless your crossover algorithm allows for null contributions, i.e. parent contributions of null weight. In that case, parent A could contribute its full chromosome (bits 0-5) and parent B would contribute nil, yielding (b).

Regarding Q2, both (a) and (b) are possible. There are a few combinations to test; too tedious to write, but you can do the work with pen and paper. :-)

Answer 3

It is not possible to find parents if you do not know the inverse-crossover function (so that AxB => (a,b) & (any a) => (A,B)).

Usually the 1-point crossover function is:

a = A1 + B2
b = B1 + A2

Even if you know a and b you cannot solve the system (system of 2 equations with 4 variables).

If you know any 2 parts of any A or/and B then it can be solved (system of 2 equations with 2 variables). This is the case for your question as you provide both A and B.

Generally crossover function does not have inverse function and you just need to find the solution logically or, if you know parents, perform the crossover and compare.

So to make a generic formula for you we should know 2 things:

1. Crossover function.
2. Inverse-crossover function.

The 2nd one is not usually used in GAs as it is not required.

---

Now, I'll just answer your questions.

Q1: In a genetic algorithm given the two parents A and B with the chromosomes 001110 and 101101, respectively, which of the following offspring could have resulted from a one-point crossover?

Looking at the a and b I can see the crossover point is here:

    1    2
A: 00 | 1110
B: 10 | 1101

Usually the crossover is done using this formula:

a = A1 + B2
b = B1 + A2

so that possible children are:

a: 00 | 1101
b: 10 | 1110

which excludes option b from the question.
So the answer to Q1 is the result child is a: 001101 assuming given crossover function

Q2: Which of the above offspring could have resulted from a two-point crossover? and why?

Looking at the a and b I can see the crossover points can be here:

    1   2    3
A: 00 | 11 | 10
B: 10 | 11 | 01

Usual formula for 2-point crossover is:

a = A1 + B2 + A3
b = B1 + A2 + B3

So the children would be:

a = 00 | 11 | 10
b = 10 | 11 | 01

Comparing them to the options you asked (small a and b) we can say the answer:

Q2. A: Neither of a or b could be result of 2-point crossover with AxB according to the given crossover function.

---

Again it is not possible to answer your questions without knowing the crossover function.

The functions I provided are common in GA, but you can invent so many of them so they could answer the question (see the comment below):