English 中文(简体)
Genetics algorithms theoretical question
原标题:

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.

最佳回答

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):

问题回答

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.

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. :-)





相关问题
Resample Filter of WEKA - How to interpret the result

I am currently strugeling with a machine learning problem whereas I have to deal with great unbalanced data sets. That is, there are six classes ( 1 , 2 ... 6 ). Unfortunately there are e.g. for class ...

How to recognize rectangles in this image?

I have a image with horizontal and vertical lines. In fact, this image is the BBC website converted to horizontal and vertical lines. My problem is that I want to be able to find all the rectangles in ...

Question About Using Weka, the machine learning tool

I m using the explorer feature of Weka for classification. So I have my .arff file, with 2 features of NUMERIC value, and my class is a binary 0 or 1 (eg {0,1}). Sample: @RELATION summary @...

Implementing a linear, binary SVM (support vector machine)

I want to implement a simple SVM classifier, in the case of high-dimensional binary data (text), for which I think a simple linear SVM is best. The reason for implementing it myself is basically that ...

libsvm model file format

According to this FAQ the model format in libsvm should be straightforward. And in fact it is, when I call just svm-train. As an example, the first SV for the a1a dataset is 1 3:1 11:1 14:1 19:1 39:...

Competitive Learning in Neural Networks

I am playing with some neural network simulations. I d like to get two neural networks sharing the input and output nodes (with other nodes being distinct and part of two different routes) to compete. ...

热门标签