Meta Genetic Programming

[m...@helpmefigurethisout.com]

Using a genetic programming program to evolve a genetic programming
program has been thought of before. But, to my knowledge it has only
been applied to certain limited parameters (such as mutation rate and
population size), not to the entire thing. By genetic programming
program, I mean the program that you wrote yourself, that mutates and
crosses over parse trees then assesses their fitness.

So, right now we are using our brains as the meta-genetic programmer.
We are using our brain to evolve (in a sense) the genetic programming
program. But seeing as how the whole point of genetic programming is to
imagine things that would not normally be thought up by the human
brain, why is it being done this way? If we can get a genetic
programming program to evolve on its own, we will take the limitations
of the brain's creativity out of the equation.

The process is simple in theory. Evolve a program that takes an
input-output table as the input, and outputs a program that
successfully runs this input output table as the output. This is after
all what your manually written genetic programming program does.

As we all know, the scalability problems of genetic programming would
make this impossible if it were started from a random seed. So, instead
it should be started from a population of genetic programming programs.
For example, the one you wrote yourself. Ones that other people have
written. Slight variations on each of those.

I would have already tried this out myself. But my intellect is
gradually beginning to fail me and I can only work at a snail's pace.
If this is a good idea I want to do it justice by testing it out as
soon as possible. I hope that one of you can help.

--

My Genetic Programming Web Site:
http://www.helpmefigurethisout.com

[Michael Lones]

Hi,

You might want to take a look at Lee Spector's "autoconstructive
evolution" work if you haven't already. It seems very relevant to what
you are talking about.

Mic

[m...@helpmefigurethisout.com]

Thank you for the information. His idea is described similarly to the
one I have presented, but the implementation is very different, and in
my opinion very much like the currently available genetic programming
programs.

My idea is to evolve a genetic programming program that can replace the
ones that are programmed by hand. I think this genetic programming
program will be faster or otherwise more efficient than the currently
available hand-programmed ones. In turn, you will use it to evolve a
genetic programming program that is even better. In other words:

1. Use your hand programmed genetic programming program to evolve a
better one. To do this, give it a population of various hand-programmed
genetic programming programs. Measure the fitness of each one by the
time it takes to solve a set of simple problems. Then, mutate and
crossover these programs until you have created a new one with a
greater fitness then any of the hand programmed ones from the initial
pool of offspring.

2. You will be left with a genetic programming program (or some
as-yet-unknown type of program) that is programmed by the computer,
rather than by hand. It will take a description of a problem (and
optionally, an initial population) as input, and produce a program that
solves that problem as output. Exactly like your hand programmed
genetic programming program that you were using in step 1. Immediately
begin to use it, in the exact same manner that I described in step 1.
Feed it an initial population of the best programs created in step 1,
and the same set of simple problems. Then, mutate and crossover these
programs until you have created a new one with a greater fitness then
any of the computer programmed ones from the initial pool of offspring.

3. Take the best from step 2, and in turn use it to create something
even faster.

4. Repeat until no further improvement can be achieved. Then start over
at step 2, using the best population from your final step. But this
time to make it more challenging, present it with sets of more complex
problems, or start without any initial population.

Finally, what I mean by the term "genetic programming program" is this:

Discipulus http://www.aimlearning.com/
lil-gp http://garage.cse.msu.edu/software/lil-gp/
GPsys http://www.cs.ucl.ac.uk/external/A.Qureshi/gpsys_doc.html

....are all genetic programming programs.

Here is another example of a genetic programming program, in the C
programming language mixed with pseudocode:

solution_to_the_described_problem main(description_of_a_problem,
[optional:initial_population])
{

Repeat
Evaluate each individual's fitness
Select best-ranking individuals to reproduce
Mate pairs at random
Apply crossover operator
Apply mutation operator
Until terminating condition

}

[m...@helpmefigurethisout.com]

On a side note, all of the repetition from step 2 forward could be done
automatically. The genetic programming program could be instructed to
run for a certain time, after which it would replace itself with the
best of its offspring, then continue on.

[Fidel Viegas]

Hi there,

If you are already providing the solution to your problem, than that
isn't genetic programming. To my knowledge, genetic programming is
associated to automatic programming. That is, you don't know before hand
the solution to your problem, and you want the computer to solve it. If
you are already solving it, then that isn't automatic programming. You
are still providing the solutions.

The problem you are trying to solve has to do with optimization. You
provide the solutions, but you want better solutions in terms of efficiency.

That is how I see it. I may be wrong, but the whole purpose of genetic
programming or any automatic programming approach is to let the computer
solve the problem for you.

All the best

Fidel

[m...@helpmefigurethisout.com]

Well, it looks like I am on my own. I will implement this system and
post my results when it is complete, hopefully within 1-2 years.

[m...@helpmefigurethisout.com]

Yes, and the problem is, how do I create a genetic programming system
without explicitly programming it?

[m...@helpmefigurethisout.com]

I just rewrote my website http://www.helpmefigurethisout.com to better
explain the idea of Meta Genetic Programming, in case anyone is
interested.

[Gangadhar NPK]

Hi,
Please clarify, if this is what you mean:
a genetic algo/program which uses existing GA programs to find the best
strategy for a problem and evolve that particular strategy/algo using
the usual GA strategies.
Is that what you mean ? But doesn't this particular assumption hinge on
the fact that all the GA implementations out there are simialr (equally
good or bad). And in case that GAs are written for specific
applications, then using them for generic applications might not
produce the intended result. Don't you think so ?

[m...@helpmefigurethisout.com]

I don't know if we understand each other. What I mean is:

1. Every GA program is itself a computer program.

2. Computer programs can be evolved using genetic programming.

3. We should use genetic programming to evolve a GA program.

This is in contrast to the current strategy, which suggests that only
humans should create GA programs. I am saying that computers, instead
of humans, should create GA programs.

[Patrick May]

Have you looked at Koza's work in genetic programming
(http://www.genetic-programming.com)? His book "Genetic Programming:
On the Programming of Computers by Means of Natural Selection" and its
sequels are fascinating. The use of Common Lisp allows programs' ASTs
to be manipulated directly, realizing at least some of your goals.

Regards,

Patrick

------------------------------------------------------------------------
S P Engineering, Inc. | The experts in large scale distributed OO
| systems design and implementation.
p...@spe.com | (C++, Java, ObjectStore, Oracle, CORBA, UML)

[Gangadhar NPK]

Exactly, I also was saying the same thing. GA's evolving GA strategies.
And the genesis of the strategies is going to be the existing
strategies. But what if the existing strategies are tailored for
specific applications. In that case one can't generalize can they ?

[m...@helpmefigurethisout.com]

I still don't think we are seeing on the same page, because of the
ambiguity of written language. I will make a flash movie to describe
this concept visually.

[Fidel Viegas]

Let me see if I got this right. What you are trying to create is a GP
program that evolves GP programs (or GAs), is that it? If that is the
case, then I don't know of any research on this topic. Maybe, the PushGP
system. Even so, that is quite a task. How do you assess your GP or GA
programs?
It is quite hard to picture a GA that evolves GAs, but nonetheless I
figure it isn't impossible. There must be a way of doing this.

Anyway, I wish you success with your research.

All the best

Fidel.

[Fidel Viegas]

They always say: a picture is worth a thousand words

[m...@helpmefigurethisout.com]

Yes! That is exactly what I mean. I know it is a huge task, but the
idea is too appealing to pass up.

The GP will be assessed in the same way that humans manually assess
their GP programs. I.E., give it a bunch of different problems and look
for what fitness level (averaged over a series of runs) is reached in a
set amount of time.

There are two researchers interested in this topic, Lee Spector and
Juergen Schmidhuber (the inventor of the idea). Lee Spector's system is
very different from what I have envisioned, because it is always
dependent on human written code. I am corresponding with Juergen
Schmidhuber and he says that he wrote a Meta-GP system many years ago,
but has not yet answered my email asking for details.

Assuming he does not wish to provide his source code, there is
effectively no research done on this topic. To rectify this, I will
offer source code as well as a writeup on my web page (
helpmefigurethisout.com/metagp.html ) once my project is complete.

P.S. I will still make a flash video describing this idea, for anyone
who is interested. I have no flash experience so it could take up to
several weeks.

[Fidel Viegas]

Hi, I have played with this algorithm before, but never had realised
that there were people using it to do what you are actually talking
about. Have a look at this site, they are doing research and that field.
http://www.eea.cs.ubbcluj.ro/

Hope that helps

All the best

Fidel.

[m...@helpmefigurethisout.com]

Thanks, I will contact Mihai Oltean as it looks like his research is
similar.

[m...@helpmefigurethisout.com]

But, there is one thing. Dr. Oltean's most recent paper is called
"Evolving Evolutionary Algorithms using Linear Genetic Programming". If
I understand correctly, he is taking steps to make sure that only
Evolutionary Algorithms, and not other kinds of algorithms, evolve from
his program.

The goal of my project is not necessarily to evolve an optimized
genetic programming system. In fact i am hoping it will move away from
genetic programming systems and into the unknown, finding something
even better that is as of yet undiscovered by humans.

I will not take any steps to make sure that the evolved program uses
genetic programming strategies. It will just be a black box, accepting
a string of bits representing the description of a problem as inputs,
and producing a string of bits representing a computer program as
output.

Of course I could be misinterpreting Dr. Oltean's intentions, I will
need to contact him for more information.

[Gangadhar NPK]

So, your strategy is to present a generic problem as a string of bits
(in some meta-language assumingly) and the algorithm evaluates various
strategies and decides upon the best one, and then creates the program
for the end user to use. Please correct me if I am wrong.

[Fidel Viegas]

He has other papers using MEP. I guess that is a starting point for you
research. If you understand his way of doing it, I guess you can come up
with some general method. I don't know, as I haven't tried it, but I
guess that gives you an idea.

Anyway, good luck with that.

All the best

Fidel.

[m...@helpmefigurethisout.com]

I think I now understand what you mean here. That genetic programming
works best when tailored for specific applications, and not for general
problem solving. But Meta-genetic programming is not necessarily for
general problem solving, it can be used for specific applications as
well, in finding the best genetic programming system for that specific
type of problem.

You are right. However, the algorithm does not necessarily evaluate
various strategies, it might do that and it might do something totally
different. It will be a black box so I will not know what goes on
inside, only that I present it with a problem and it outputs a program.

[xant...@well.com]

m...@helpmefigurethisout.com wrote:
> But seeing as how the whole point of genetic programming is to
> imagine things that would not normally be thought up by the human
> brain, why is it being done this way? If we can get a genetic
> programming program to evolve on its own, we will take the limitations
> of the brain's creativity out of the equation.

The problem is that by saying, "I want my evolutionary algorithm to
evolve evolutionary algorithms that solve this (class of) problem(s)",
you have fallen into a common trap. You have overspecified the
solution, imposing _your_ expectation (that an evolutionary algorithm
will be the best solution, and the one to which the process converges)
on the solution space, when if run without your unproven constraint,
the converged solution might be an algorithm of another type entirely,
a hill climbing algorithm, perhaps, or a simulated annealing algorithm.

xanthian.

[m...@helpmefigurethisout.com]

I would not necessarily want a genetic algorithm to result from the
process. Any algorithm will do, as long as it can solve the problems I
present it with.

You are right that starting out with a genetic programming system does
constrain things, but only at first. Once I get past a few hundred
generations of evolving new systems with higher fitness, and replacing
my current system with each new system, I may no longer be using a
genetic programming system.

Are you saying that if I seed the initial population with genetic
programming systems alone, it will converge upon these as the best
solution for problem solving and never find anything better? Because
that is what I am afraid will happen. Probably a better idea would be
to seed the initial population with genetic programming systems in
addition to hill-climbing systems, simulated annealing systems, etc. I
don't know much about using the latter two to produce computer programs
so I will have to learn more before I can include them as part of the
initial population.

[xant...@well.com]

m...@helpmefigurethisout.com wrote:
> You are right that starting out with a genetic programming system does
> constrain things, but only at first. Once I get past a few hundred
> generations of evolving new systems with higher fitness, and replacing
> my current system with each new system, I may no longer be using a
> genetic programming system.

Umm, I think you have some conceptual issues, here.

You won't be "replacing my current system"; your "current system"
is the genetic algorithm trying to evolve other algorithms, and
that system is a constant, because that problem is its task.

The algorithms evolved will typically apply to some completely
other problem, IC design perhaps, and will compete within the
supervisory genetic algorithm as to which member of the population
of algorithms designs ICs most fitly.

xanthian.

[m...@helpmefigurethisout.com]

I'm not sure I understand, but you do say that there is a supervisory
genetic algorithm. Wouldn't it be possible to evolve a better version
of this (the supervisory genetic algorithm)?

And then once you had evolved a better version, to replace your
current, human programmed supervisory genetic algorithm with it?

[Inman Harvey]

... it would indeed be possible to evolve a better version of the
supervisory genetic algorithm, using a meta-1-GA to do this evolution.
Further, you could evolve a better meta-1-GA by using a meta-2-GA to do
this evolution, and so on. But you can only go out to a finite n, and
the meta-n-GA will be human programmed.

What holds the world up? It is the god Atlas holding the world on his
shoulders?

Ah, but what holds Atlas up? He is standing on a turtle.

Ah, but what holds the turtle up? It is standing on another turtle --
and it is turtles all the way down!

Turtles all the way down (or meta-GAs all the way up) do not solve the
problem of earth-support (or eliminating the human element from a GA),
they merely defer the problem indefinitely.

--

Inman Harvey >> Evolutionary and Adaptive Systems Group (EASy) <<
COGS/CCNR/CSE >> Informatics, Univ. of Sussex, Brighton BN1 9QH, UK <<
inm...@susx.ac.uk >> www.informatics.susx.ac.uk/users/inmanh/ <<

[m...@helpmefigurethisout.com]

I respectfully disagree - I believe it is possible to evolve a better
version of the supervisory genetic algorithm using just the regular,
non meta genetic programming system you would use for any other
purpose.

But, I find it increasingly difficult to support my position with
words. I am making a flash video to demonstrate my idea, and it should
be ready in a couple weeks. And more importantly, after that I will
begin the task of implementing meta-gp in software. The results of
which will be more authoritative than any video or description, whether
it is a success or a failure.

--

My Genetic Programming Website
http://www.helpmefigurethisout.com

[m...@helpmefigurethisout.com]

Here is the video demonstration:

http://www.helpmefigurethisout.com/metagpvideo.html

It looks horrible, but I think it gets the point across.

[Fidel Viegas]

m...@helpmefigurethisout.com wrote:
> I'm not sure I understand, but you do say that there is a supervisory
> genetic algorithm. Wouldn't it be possible to evolve a better version
> of this (the supervisory genetic algorithm)?

I guess what he meant is that you need an algorithm that will work as an
arbiter for your solution. You need something to compare with. How would
you know that the solution to the problem is good or not if you aren't
providing a target? Unless you are thinking of using an interactive
evolutionary algorithm. In that case, you would require a human rater to
rate your solutions. But that is a very tedious process.

> And then once you had evolved a better version, to replace your
> current, human programmed supervisory genetic algorithm with it?
>

Wouldn't that be the solution?

[m...@helpmefigurethisout.com]

Yes, you would need to check the quality of your results using a human
programmed algorithm that is held constant. It would be very simple
however.

Whether or not this proves to be the downfall of my idea, I will soon
find out. I am starting on the first step right now, writing a compiler
that will translate the delphi/pascal code my genetic programming
system is written in, into the virtual machine assembly language that
is used within the system to evolve programs.

[Fidel Viegas]

m...@helpmefigurethisout.com wrote:
> Yes, you would need to check the quality of your results using a human
> programmed algorithm that is held constant. It would be very simple
> however.
>
> Whether or not this proves to be the downfall of my idea, I will soon
> find out. I am starting on the first step right now, writing a compiler
> that will translate the delphi/pascal code my genetic programming
> system is written in, into the virtual machine assembly language that
> is used within the system to evolve programs.
>
>

Let us know the outcome.

Good luck with that!

[Gangadhar NPK]

As was pointed by others too, at one point you will require human
intervention regarding what is the choice to be taken. From your end,
the GA can be done in such a way that the final choice be pared to very
simple choices. So, you are now going to try to write a compiler which
will convert your pascal code (the genetic program generator) to a
virtual machine assembly code. Correct me if I am wrong : the idea
behind this would be to get a representation of the GA in your VM
instruction set, and similarly for the various other GAs too. And
finally, you will convert your compiler also into the VM instructions
and using the compiler, you will evaluate the fitness of the fitness
comparision program. Is that what is the logical conclusion to your
endeavor ?

p.s: the flash presentation is good. it does get the point across.

[m...@helpmefigurethisout.com]

Yes, that is right, except for the part about the compiler. There is no
need to translate the compiler into the virtual machine instruction
set, it is just a tool for producing virtual machine code from
human-written GA's.

Nor do I need the compiler to evaluate the fitness of the fitness
comparison program. To do that I will use my human written GA. If this
does not make sense, it will become clear once you are able to see the
source code, which will soon be posted to my web site.

Also I hope to try including other programs besides GA's in my initial
population, as suggested by xanthian. Hill climbing, simulated
annealing, neural networks and others are some that I would like to
include.

[xant...@well.com]

m...@helpmefigurethisout.com wrote:
> Here is the video demonstration:

> http://www.helpmefigurethisout.com/metagpvideo.html

> It looks horrible, but I think it gets the point across.

Well, no, it just shows that you didn't bother to understand
Inman Harvey's objection.

There _isn't any such thing_ as a "The Genetic Programming
Algorithm", there's just a whole lot of "A Genetic Programming
Algorithm"s, each one (exquisitely, and in great detail) tailored for a
particular problem or class of problems.

Thus, you do indeed need the _hierarchy_ of genetic algorithms Inman
described, and this is simply inescapable.

I'm pretty sure the beast you attempt to describe could be mapped onto
a solver for The Halting Problem fairly easily, and the latter is an
entity well known to be impossible to create.

FWIW

xanthian.

[m...@helpmefigurethisout.com]

Then I will still proceed, with the goal of proving my idea to be
wrong.

[Kent Paul Dolan]

"me" <m...@helpmefigurethisout.com> wrote:

> Then I will still proceed, with the
> goal of proving my idea to be wrong.

"Insanity" is often defined as "expecting
different results from unchanged behavior".

You have not yet invested the intellectual
effort to understand, at a gut level, the
cogent objections Inman Harvey raised to
your plan of attack.

Until you do, "floundering" is your only
likely result and output.

"A word to the wise is sufficient", the
ancients said, but a slap upside the head
with a construction timber seems to be the
more appropriate tool for the mule-like
rest of us, to get sufficient attention
focused on why "what we want to do" is not
"what we should do".

FWIW

xanthian.

--
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG

[Gangadhar NPK]

Kent,
Correct me if I am wrong in the derviation of Harvey's post. To create
a generic Genetic Algorithm, to evaluate any human written Genetic
Algorithm is an ardous task (not to mention, tried and not succeeded).
The closest anyone can get to a task such as this, is a solution to a
particular kind of problem, and in this case the algorithm turns to be
a specific one, rather than a generic one.
Also, since I am at it, do you know of any newsgroups which discuss
genetic algorithms and machine learning ? The google group has hardly
any posts.

Thanks
Gangadhar

[xant...@well.com]

Gangadhar NPK wrote:
> Kent,

> Correct me if I am wrong in the derviation of Harvey's post. To create
> a generic Genetic Algorithm, to evaluate any human written Genetic
> Algorithm is an ardous task (not to mention, tried and not succeeded).
> The closest anyone can get to a task such as this, is a solution to a
> particular kind of problem, and in this case the algorithm turns to be
> a specific one, rather than a generic one.

The language to make the distinction isn't easy, and I skipped sleeping
last night, so this won't help all that much, but anyway...

The objection Inman raised was, IIUC, that while at the bottom level
your GA would be solving some practical problem, and the fitness of
that GA's population thus measurable in terms of that practical
problem,
at the next level up the GA would be solving a "meta problem" of
creating a more efficient GA to solve that practical problem, and it's
population members' fitness would need to be done by doing a whole run
of each member against (probably many) random starting populations of
the practical problem, and then adjudging which of those sets of
solution attempts on average was best, a completely different fitness
measure.

You can't take that genetic algorithm which is working with populations
of genetic algorithms and plug a random initialization of _it_ into the
chore of solving the next lower level problem, it is some other animal
completely.

Similarly, to improve the engine that is looking for the "best meta",
you have to go "meta meta", with still another fitness measure. Since
the fitness measure is part and parcel of the GA, you cannot plug the
"meta meta"'s population into the "meta" algorithm and produce better
"meta meta"s, you have to go meta^3, et cetera.

> Also, since I am at it, do you know of any newsgroups which discuss
> genetic algorithms and machine learning ? The google group has hardly
> any posts.

There is a cross discipline between comp.ai.genetic and
comp.ai.neural-net(s?) where most of the "how to use GAs to design NN
weights" is described in the latter newsgroup, not, particularly often,
here in comp.ai.genetic. That might be a place to look.

FWIW

xanthian.

[danc]

Hi there,

Very interesting idea, it reminded me of some work carried out by Mike
O'Neill at UL. It's not GP, but a close relative. The following
reference may be useful:

Michael O'Neill (HP) and Conor Ryan (HP)
Grammatical Evolution by Grammatical Evolution: The Evolution of
Grammar and Genetic Code
Genetic Programming 7th European Conference, EuroGP 2004, Proceedings,
LNCS, Vol. 3003, pp. 138-149, Springer-Verlag, 5-7 April 2004.

Hope this helps,

Dan

[midh...@gmail.com]

On Thursday, May 26, 2005 at 10:08:32 AM UTC+5:30, m...@helpmefigurethisout.com wrote:
> Using a genetic programming program to evolve a genetic programming
> program has been thought of before. But, to my knowledge it has only
> been applied to certain limited parameters (such as mutation rate and
> population size), not to the entire thing. By genetic programming
> program, I mean the program that you wrote yourself, that mutates and
> crosses over parse trees then assesses their fitness.
>
> So, right now we are using our brains as the meta-genetic programmer.
> We are using our brain to evolve (in a sense) the genetic programming
> program. But seeing as how the whole point of genetic programming is to

> imagine things that would not normally be thought up by the human
> brain, why is it being done this way? If we can get a genetic
> programming program to evolve on its own, we will take the limitations
> of the brain's creativity out of the equation.
>

> The process is simple in theory. Evolve a program that takes an
> input-output table as the input, and outputs a program that
> successfully runs this input output table as the output. This is after
> all what your manually written genetic programming program does.
>
> As we all know, the scalability problems of genetic programming would
> make this impossible if it were started from a random seed. So, instead
> it should be started from a population of genetic programming programs.
> For example, the one you wrote yourself. Ones that other people have
> written. Slight variations on each of those.
>
> I would have already tried this out myself. But my intellect is
> gradually beginning to fail me and I can only work at a snail's pace.
> If this is a good idea I want to do it justice by testing it out as
> soon as possible. I hope that one of you can help.
>
> --
>
> My Genetic Programming Web Site:
> http://www.helpmefigurethisout.com


Hi everyone. Any update on this project? (I know this is 2018.)