Re: GAs for modifying algorithms

Have you considered "Inductive Logic Programming"?. You put in a training
set of positive and negative instances in a relation and it gives you a
prolog program that covers the data. It works for things like inducing
ancestor using a given parent relation ie:

ancestor(X,Y) :- parent(X,Y).

ancestor(X,Y) :- parent(Z,Y), ancestor(X,Z).

i'm not sure though if anyone's got as far as inducing something as complex
as a sorting algorithm - something like bubblesort would be a bit more
complex than ancestor. There's a chapter on this in Tom Mitchell's book
Machine Learning

"(null)" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]
> Hi everyone,
>
> There's a topic I've been interested in lately, but I haven't really
looked into. Do you know any resources (papers, books, websites) for using
genetic algorithms to modify *algorithms*?
>
> For example, I've seens GAs used to construct digital filters:
> (as in Wilson, P. and M. Macleod (1993). Low implementation cost iir
digital filter design using genetic algorithms. IEE/IEEE workshop on Natural
Algorithms in Signal Processing , 1--8)
>
> Is there any interesting work being done to do the same kind of thing for
improving computer science algorithms?
>
> I'd love (as would we all) to be able to let the computer do my coding for
me! For example, I'd love to give a GA a list of numbers, and have it come
up with a sorting algorithm "automatically". The thing that really interests
(and confuses) me is that it's doubtful that it could come up with a correct
solution (in finite time) if the GA had to modify a string of characters in
order to write C++ code:
>
> i.e. MyChromosome = (1000 character array)
> GA mutates/crosses over each letter
> and eventually comes up with:
>
> for (int i=0; i<stringLength; i++) {...
>
> But if you defined the chromosome to be comprised of "alleles" that
evaluated into some language primatives, the GA could have a lot more
success. For example, if an allele = 1 for MyChromosome[0] told some
processor to swap the first number in the list with the second number, an
allele = 64 for MyChromosome[1] did a comparison, etc.
>
> However, it seems that how you set up the language rules limits the
variety of algorithms that you could "invent". With C++, you can do jsut
about anything - with the psuedo-language above, you might develop a sortng
algorithm, but not much else. I'm trying to remember things about cellular
automata, Chomsky grammars, and Turing machines, but I'd love a pointer and
some things to read.
>
> Thanks,
> Patrick Kellogg
> [EMAIL PROTECTED]
> http://www.patrickkellogg.com
>
>