Firstly, I'd like to say that this is in no way linked to the Budget Project that has been on hold since my semester started again, this little gem comes from my own musings during a homework assignment for my evolutionary computation class.
Background knowledge for this piece of work:
Read up on Holland's Schema Theorem: Wikipedia Page on it
Understand how to multiply vectors, or at least take their dot product.
Moving on,
For a given population, at time step t, the number of schema's represented in the population is given by a vector of values between 0 and 1. We can compute the expected number of individuals from extending Holland's schema theorem with our own intuitive (and correct) terms. Doing this now, for a 2 bit problem:
(meaning that each schema in the population is only 2 bits long, and when I say schema here, I do not mean templates, I mean the actual members of the population of say, schema 00 or schema 11, NO wildcards.)
The probability of a schema surviving is the probability of both it's bits not being mutated. If we were mutating with probability Pm, then we can determine this survival rate as (1-Pm) squared.
The probability of a schema's complement (Think a standard not gate applied to all the bits, aka inverting, or flipping the bits, like twos complement but without the plus 1...) mutating into the given schema is the probability that it gets both bits flipped, or Pm squared.
The probability of terms representing half or partial complements being mutated is the probability of the bits matching the schema to not be mutated multiplied by the probability of the schema's non matching bits to be mutated into them. In short, (1-Pm)(Pm) and each term is raised by whatever bits match, and not match respectfully. (If this makes no sense, for a 2 bit problem, this would be (1-Pm)(Pm) or (Pm)(1-Pm) for the schema 01 and 10 if the desired schema was 00)
Now that we have those probabilities, we recognize that those probabilities multiplied by the number of the matching schema (not desired in most cases), and then summed, will give us the expected number of schema in the next generation at time t.
Now, my 'theorem' I suppose.
Let (1-Pm) = A, and (Pm)= B, o=number of bits, P= proportions of population
number of expected schema H at time t+1 = V((A+B)^n) dot P
Where V is a vector where each element i is the i-th term in the binomial expansion of (A+B)
We use the dot product to multiply the corresponding schema with the right probabilities and then tada, we're done. doing this for each schema in the population results in 2^n equations being calculated and the proportions of a generation at the next time step has been calculated.
Because this might not be very clear, due to my lack of knowledge if blogger supports latex or not, heres a bit more elaboration.
Expansions of a binomial are usually simplified, and then their coefficients make what is known as pascals triangle, however, in this theorem, the vector is composed of the UN-simplified version of the expansion, why? Because the proportions of the population can be different from one another, so you can't simply factor out the expansion, get the coefficients and multiply by the population now can you?
Also, the population vector goes from the desired schema up to the one previous to it. How? modulo arithmatic and mathematical trickery of course.
if we want schema 00, then our vector would be [00 01 10 11 ]. if we wanted 01? [01 00 11 10], what about 10? [10 11 00 01]
The goal of course of any population vector is to have the desired on the left, and the complement on the right, any bits between must correspond to their proper probability. This is the difficult part of any implementation, However consider this
000 A^3
001 A^2B
010 A^2B
011 AB^2
100 A^2B
101 AB^2
110 AB^2
111 B^3
Take the first, 000 as the desired bit string, and the other column as the probabilities assigned to it by the theorem, well we can notice that the number of complementary bits in the schema indicate how many times we should apply B, and the number of bits matching the schema apply to how many times A is multiplied by itself. Extrapolating from this, we could produce an implentation if we wanted to.
That is all.
No comments:
Post a Comment