genetic programming

[alan2here]

My program creates many instances of a structure I call a "program" to compare and evolve to create an optimal program for a specified task. It uses integer sequances as inputs and outputs, the goal is to create the simplest program that produces an integer sequance starting with the input sequance.

 

For example:

 

Input 2, 4, 6

Output 2, 4, 6, 8, 10 ...

 

A program consists of a list of 8bit unsigned integer units. Running a program starts the program at the first unit reading it as an instruction. The instruction may take parameters, thease are the subseqent few units. After the instruction has finished then the program moves on to reading the next instruction, moving forward one unit and if the instruction takes parameters then skipping over them as well. Some instructions change the program but the changes are not perminent, the changes are discarded in the next generation of the program.

 

The program is written in C++. PM me for source code.

 

The scoring of programs is hard coded to 0, 1, 2, 3, 4 ... for as long as the number of outputs each program produces.

 

Having descovered the search space was larger and the programs ran slower that I expected iv'e tried to optimise the program for speed. Although I have still opted for good abstraction instead in places, for example in making the program object robust.

 

The instructions are currently:

 

"value" refers to the value of a parameter. "value at absolute" refers to an absolute position in the program (from the start of the program) defined by the value of a parameter. "value at relative" refers to a relative position in the program (from the current position) defined by the value of a parameter. Each time one of thease three elments is mentioned it shows that the instruction takes another parameter that will be read and acted upon and that the programs execution position will move forward that many units after the instruction has been executed.

 

end

1 byte absolute goto

1 byte relative goto

if then 1 byte absolute goto

if then 1 byte relative goto

1 byte 'value at absolute = value'

1 byte 'value at relative = value'

1 byte 'value at absolute = value at absolute'

1 byte 'value at relative = value at relative'

1 byte 'value at absolute = value at relative'

1 byte 'value at relative = value at absolute'

1 byte 'value at absolute = value + value'

1 byte 'value at relative = value + value'

1 byte 'value at absolute = value at absolute + value at absolute'

1 byte 'value at relative = value at relative + value at relative'

1 byte 'value at absolute = value - value'

1 byte 'value at relative = value - value'

1 byte 'value at absolute = value at absolute - value at absolute'

1 byte 'value at relative = value at relative - value at relative'

toggle value at absolute - 1 becomes 0, 0 becomes 1

toggle value at relative

output value - add the parameters value to the output, increasing the outputs size by 1.

output value at absolute

output value at relative

increase size - increases the size of the program by 1 adding a "0" unit to the end.

 

It probbably can't be determined if a given unit (8-bit unsigned integer) in the program is an instruction, parameter or both without runing the program or performing a similar amount of computation.

 

When the programs mutate as part of the evolution process then they mutate a random amount where larger mutations are progressively less likely.

 

Completely useless programs (that score 0) are not mutated but instead replaced with new random programs, otherwise the programs are duplicated into two mutated coppies of the original for the next generation. At most half the target population count number of programs are chosen to contribute to the next generation, as a result the number of programs during evolution successively through generations starts low and increases up to to the target population count untill the best program is sufficently good to stop the evolution.

Edited June 16, 2011 by alan2here

[alan2here]

bump

Edited July 24, 2011 by alan2here

[khaled]

So, simply you are working on Genetic Programming, so what is the search you are using ? .. ex: Simulated Annealing

 

and this search is to optimize a Program, where a Program is a set of Instructions, an Instruction is an unsigned 8-bit Integer

 

Number of Instruction types = 2^8 = 256

 

Program [math]P = \{ I_1, I_2 .., I_m \}[/math] where [math]m = ?[/math]

 

So, what is the value of m, is it static, dynamic, or a range of values ?

 

-- is your search linear, exponential, local, or guided ?

 

-- what is the size of your buffer, queue, list .. in terms of Max Number of Programs ?

 

-- do you keep previously processed states (Programs) ? .. so that you don't go over the same one once again, & don't get stuck in loops

 

-- how did you define SELECTION, MERGE, and MUTATION functions, in terms of algorithm ?

 

good luck

Edited July 24, 2011 by khaled

[alan2here]

Thanks :¬)

 

So, simply you are working on Genetic Programming, so what is the search you are using ? .. ex: Simulated Annealing

I'm afraid I don't know, there isn't much beyond what I have described as to how it works.

 

 

and this search is to optimize a Program, where a Program is a set of Instructions, an Instruction is an unsigned 8-bit Integer

 

Number of Instruction types = 2^8 = 256

yes

 

 

Program [math]P = \{ I_1, I_2 .., I_m \}[/math] where [math]m = ?[/math]

 

So, what is the value of m, is it static, dynamic, or a range of values?

'm' can change while running (evaluating) the program but the changes won't stick for future generations. It can also change size during mutation between generations. If 'm' ever exceeds 200 then the program stops and scores 0 making it unable to continue to the next generation. Also a program cannot mutate to a larger size than 200.

 

 

-- is your search linear, exponential, local, or guided ?

Again I'm not sure what thease terms are.

 

 

-- what is the size of your buffer, queue, list .. in terms of Max Number of Programs?

At most and most of the time 1000 programs per generation although this is easily changed.

 

 

-- do you keep previously processed states (Programs) ? .. so that you don't go over the same one once again, & don't get stuck in loops

No, between each generation the previous generations programs are lost except those that get mutated.

 

This is however an intresting idea though that I've considered. While it would cause a huge amount of extra information to be stored it could be stored intelligently. For example where programs mutates back to as it was in a previous generation then that program (state) wouldn't have to be stored twice, even a mutation could just be stored as exactly how and to what program it mutates. There is a lot of potential complexity here but I'm probbably going to keep it simple for now and not do this for now.

 

 

-- how did you define SELECTION, MERGE, and MUTATION functions, in terms of algorithm?

 

The programs that scored more than 0 and are in the top half of the scores are selected with at most half the intended population selected. There is no breeding between programs (cross-slicing) it's all just mutation. 2 mutated verstion of each of thease programs are then created and taken forward to the next generation.

 

 

As we have covered limits a lot, also programs are alloud to run (evaluate) for at most 100 steps.

Edited July 24, 2011 by alan2here

[khaled]

Let's talk about limits and bounds,

 

Program size = m Bytes, Max Program size = 200 Bytes

 

Max Expansion size = Max(m) x Max Elements = 200 x 1000 = 200,000 Bytes ~ 195.3 KB

 

If you keep all data, without removing past states, your space complexity becomes exponential

 

and your search continue only for 100 steps only ...

 

So, if you keep all data, for R runs, Total Size = [math]\sum_{i = 0}^{R}{d^i} = \sum_{i = 0}^{100}{{(195.3)}^{i}} = 1.1 E 220 TB[/math] -- which is a tremendous space

 

if you keep only a branch of the tree, Total Size = [math]d \times R = 195.3 \times 100 = 19 MB[/math] -- reasonable

 

Advice: try to minimize Expansion Size, Increase Max number of steps,

 

-- Consider Progressive Merge and Semi-Random Mutation, that way your search covers a wide area of possibilities, and it allows random progression limited by general direction

 

good luck

[pwagen]

I'm interested in the source. So feel free to PM it to me, or post it in a public place such as http://pastebin.com/.

[alan2here]

195.3 KB per generation. If I kept all data (which I'm not doing atm and probably won't) then it would still only add another 195.3 KB each generation as you say my population is capped at a maximum size and only the best half go though and are doubled each generation, the other half die out each generation and don't contribute to subsequent ones, thats a linear size over time not exponential.

 

The source code is here: with-logic.co.uk/a/main.cpp

Edited July 24, 2011 by alan2here

[khaled]

So, in this case, you are not doing a Tree Search, you are doing a Local Optimization over a Function [math]f(P) = \; how \; optimal \; is \; program \; P[/math]

 

I'd call it Local Random Genetic Optimization, but you might get stuck in loops, with no use of history .. the other solution around is to provide

an incremental progressive algorithm, or else just stay with the random mutations .. and make some constraints to guide it,

 

good luck

Edited July 24, 2011 by khaled

[alan2here]

Yes.

 

To be optimal the start of the series of numbers the program outputs when evaluated should be as close as possible to the input series.

 

Of lower importance but that when most programs output series starts correctly becomes significant is program length which should be as short as possible.

 

Have I made it clear what happens inside a program when it runs? The list of instructions in my first post.

Edited July 25, 2011 by alan2here

[khaled]

Yes.

 

To be optimal the start of the series of numbers the program outputs when evaluated should be as close as possible to the input series.

 

Of lower importance but that when most programs output series starts correctly becomes significant is program length which should be as short as possible.

 

Have I made it clear what happens inside a program when it runs? The list of instructions in my first post.

 

I'm afraid it's not, you have to show your algorithms:

- the algorithm to obtain an initial solution

- the algorithm of the expansion

- the algorithm of the mutation process

- the algorithm for f(P): evaluating how optimal is program P

[alan2here]

Initially (unevolved programs) every byte is random.

 

I don't understand the 2nd question.

 

I needn't go into mutation is detail but it's based on changing a small number of randomly chosen bytes of the program to random values and\or expanding\contracting the length of the program a byte. The larger the mutation the less likely it is to happen, normally mutation is verry small.

 

Programs are scored based on how well they match the input series. Values output can still contribute some points if they are wrong by a small amount, but not as many as if they are correct or closer to the target values.

Edited July 25, 2011 by alan2here

[khaled]

first .. the expansion is the step of moving from one solution to another, one program to another

 

second, are you aware that you are not really doing genetic programming, you only do "random mutation optimization", because

genetic programming is not random walks, or just mutations

 

also, you have to be aware that all methods, including this, are used to find an approximated solution .. because N != NP

Edited July 26, 2011 by khaled

[alan2here]

Does the term "random mutation optimization" take into account that programs in the population can die out and others can duplicate in future generations of the populus?

 

This term then could be a good one. What I'm doing is similar to genetic algorythms but not the same and with programs instead of data. I consider the term genetic programming to be fairly accurate but it's usefull to now have the more accurate term "random mutation optimization".

 

Brute force would eventually find the best solution\s. This system of evolving would find gradually improved solutions for as long as it's left to run.

 

I expect to be able to evolve correct solutions in that a program can be evolved to start by outputing the correct integers. The exact solutions of the smallest possible program to achieve this might not ever be found, although close is not bad.

 

Below are some examples, in these examples I've simplified the way the algorythm computes to plain english.

 

input: 1, 2, 4, 8

 

program A outputs 1, 5, 2, 0 and is wrong

program B outputs 1, 2, 4, 8 by "output 1 then output 2 then output 3 then output 4" and is correct but long

program C is the best, it outputs 1, 2, 4, 8 which is correct by "start with 1 and repeatedly double and output"

 

Therefore program C:

is extremely small

always produces the correct output

isn't actually a program like a piace of software, it's just data and is safe to run to produce the output even if it comes from an untrusted source

and can predict future values although may not always be accurate depending on how often the simplest correct solution is the best

 

Whats more both programs B and C can be further optimised at a later date with no input from the user.

[khaled]

you can then call it "Random Genetic Programming", since the genetic evolution process is fully random

[alan2here]

ty