Geek Answers Handbook

Theoretical Genetics Algorithm

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

To understand a few basic things, I have two greenhorn questions:

Q1: In the genetic algorithm indicated by two parents A and B with chromosomes 001110 and 101101, respectively, which of the following descendants could be the result of a single-point crossover?

a: 001101

b: 001110

Q2: Which of the above descendants could be the result of a two-point crossover? and why?

Please inform.

+4
source share
3 answers

It is impossible to find parents if you do not know the function of the reverse crossover (so AxB => (a, b) and (any a) => (A, B)).

Usually 1-point crossover function:

a = A1 + B2 b = B1 + A2

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

If you know any 2 parts of any A or / and B, then it can be solved (a system of two equations with 2 variables). This is relevant to your question since you provide A and B.

In general, the crossover function does not have an inverse function, and you just need to find a solution logically or , if you know the parents, do a crossover and compare .

So, to make a general formula for you, we need to know 2 things:

  • Crossover function.
  • Inverse crossover function.

The second option is usually not used in GA, because it is not required.

Now I will just answer your questions.

Q1: in the genetic algorithm, taking into account two parents A and B from chromosome 001110 and 101101, respectively, from the following offspring could be the result of a single-point crossover?

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

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

Typically, crossover is performed using this formula :

 a = A1 + B2 b = B1 + A2

to possible children:

 a: 00 | 1101 b: 10 | 1110

which excludes option b from the question.
Thus, the answer to Q1 is the result: a: 001101, assuming this crossover function

Q2: which of the above descendants could have been the result of a two-point crossover? and why?

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

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

The usual formula for a two-point crossover:

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

So, the children will:

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

Comparing them with the parameters you requested (small a and b), we can say the answer:

Q2. A: None of a or b can be the result of a point-to-point crossover with AxB in accordance with this crossover function.

Again, it is impossible to answer your questions without knowing the crossover function.

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

+7
source

A single-point crossover is when you make one connection from each parent, a two-point crossover is when you make two joins. that is, two from one parent and one from the other.

See crossover (wikipedia) for more information.

+2
source

As for Q1, (a) could be produced using a single-point crossover, taking bits 0-4 from parent A and bit 5 from parent B. (b) could not, if your crossover algorithm does not allow zero contributions, i.e. parental contributions of zero weight. In this case, parent A can contribute its full chromosome (bits 0-5), and parent B will contribute nil, which gives (b).

As for Q2, both options (a) and (b) are possible. There are several combinations for testing; it is too tedious to write, but you can do work with a pen and paper. :-)

+2
source

More articles:


All Articles