Proportions of a schema at time step t+1 with respect to mutation.

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.

Budget Buddy Progress!

This is the current progress of my budgeting program, the code and classes are made up for the accounts, checks, months, everything. The GUI and interlacing it with the underlying modules is all thats left. I've already started doing that, right now the 5 buttons at the top are the only things not working, as well as a few of the menu items.
On the to do list is:
The add items buttons and the other buttons associated with items and the main scroll pane that will hold the items that go into the budgeting for checks.
After thats done, making the GUI change when you select a different month and check and updating the panes that show information.
After that, the menu items such as saving and loading need to be done. After all of the main stuff, I just need to create the other panes such as the graphics and other things.
It will probably be another week or so before it's done.

Budgeter

Hello Everyone!

I've decided on a project to do before I have to go back to school. I'm making a program that is effectively a smart checkbook. Only, right now I'm not making it to keep track of finances, but to budget them effectively.

Basically, When I get my checks from work, I open notepad and a calculator, enter my check amount into it, then slowly subtract out items as I enter them into the notepad document. So, basically I'm wrapping my setup into a program, and it seems like it's a good idea, mainly because 4 of my friends have taken an interest and have already asked to test my program once it's done. (As done as any program can get, aka release version that gets patches)

Right now I'm fighting between the urge to continue working on it, and the urge to go to bed, it is midnight, and I do have to get up at 7 tomorrow.... but when the mood takes one to code, you do not simply ignore it.

Cluster is Done, next project

I  made it about halfway through Cluster Swarm before getting to overwhelmed by work, friends, and readings. So I took a break from it, and never really got back to it. All the pieces are there, all the ideas, it's just a matter of putting the pieces together. However, I feel like my time would be better spent on other projects.

A few things I've considered, a Budgeting program that I could use to do my budgeting, (I do it in notepad right now), I could make it entirely in Java to make it transportable, I could make it customizable, and also include plenty of features that would be useful. I could model the Towers of Hanoi, and perhaps use what I've learned about genetic algorithms and evolutionary programming to evolve strategies and solutions to the towers. Although I'd probably restrict it to n <= 4 disks for the sake of managing bits. One way I thought about doing it was to use 30 bits to represent a solution to n=4 disks, each bit being able to be one of the three towers. I could initialize random bits to a few, then run it through a validity checker, essentially my fitness function, to see how well it does and to make sure it doesnt place a larger disk on a smaller disk. and then could add in how close to the optimal solution it was to determine it's fitness.

I also thought about representing the towers and their moves as a Grammar.

S -> aC | bC
A -> aB | aC
B -> bA | bC
C -> cA | cB | cƛ
ƛ -> null (end of moves)

You could simply build up possible moves, their validity would be checked by running them through a simulation of the towers, and then calculate how well they did. From their you could breed good solutions with other ones using crossover and mutation, or possibly use some type of neural net to 'train' a program to have tendancies to lean towards one change from one move to another. I'm not entirely sure on if I'm going to do this project yet or not. It's still up in the air.

Cluster Goal Driven complete

Just a quick update, the third phase of the cluster project is complete! Only one more phase (albeit large) remains! The documentation im writing up with it is up to date as well!

Cluster AI so far

I realize it has been a while since my last update, I blame this on my poor internet quality and working a full time job. However, Despite these time consuming things, I'm up to the Cluster with Obstacles, which you didn't know. It was quite wonderful how I implemented the obstacles, or at least I think so. I used a splay tree to do it :) coding a splay tree in C++ was pretty interesting, and working out the kinks was a bit time consuming, ubut after a days work and 3 different implementations, I had a working splay tree.

I just started working on Cluster Goal Driven a few days ago but haven't had time to really work on it too much yet, hopefully I can do that on sunday, we'll find out. Stay tuned for few and far between updates!

Cluster Basic Complete

Like I said in my last post, I don't think is going to be a large project at all, but I hope I'm wrong.

So far, it has been as I predicted, the coding took me about 2-3 hours or so of actual coding and testing. I spent more time drinking water and talking to a friend online while I did the code then I actually coded, but it is done.

Cluster Basic is, well, basic. It avoids no obstacles, has no graph/grid structure it needs to index into because it has no obstacles, and it's easy enough to understand. The corner state of the box is there to be used, but isn't really used by the Cluster code. Because the Cluster doesn't actually care too much about where it's putting the members at. Because to it, the members are just a number stored in population that it checks against to make sure it has enough force to push with. You do need 2 members to push the box at all, even if 1 could do it by himself by force alone, in order to push in a horizontal or vertical line you require two members.

I'm going to type up a draft of a paper to accompany this project, and get it to the point where it adequately describes Cluster Basic, and put down all my ideas before I start working on Cluster with Obstacles.