Re: [Haskell-cafe] [Haskell] ANNOUNCE: genprog-0.1

[Brandon S Allbery KF8NH]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

On 12/8/10 12:57 , Andrew Coppin wrote:
> inherited a knackered L-gulonolactone oxidase enzyme.

L-gluconolactone oxidase maybe?

(pedants-R-us...)

- -- 
brandon s. allbery [linux,solaris,freebsd,perl]  allb...@kf8nh.com
system administrator  [openafs,heimdal,too many hats]  allb...@ece.cmu.edu
electrical and computer engineering, carnegie mellon university  KF8NH
-BEGIN PGP SIGNATURE-
Version: GnuPG v2.0.10 (Darwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAk0D6vEACgkQIn7hlCsL25WTVgCgk39LETHHkzZElEVLZKCzt1KQ
YhcAoKaevErIsoPx69Vkn8B0TK271beB
=LEGS
-END PGP SIGNATURE-

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] [Haskell] ANNOUNCE: genprog-0.1

[Alberto G. Corona]

>
> Hi!
>>
>> On Thu, Dec 9, 2010 at 1:48 PM, Alberto G. Corona 
>> wrote:
>> > assign rates of mutation for each statement,
>>
>> This could be assigned by evolution itself. If "if" will have high
>> probability of mutation then resulting programs will not survive. So
>> those probabilities can be assigned by evolution itself and be also
>> something which is passed on with generations (with again possibility
>> of mutations of those probabilities itself).
>>
>
> As any part in a genetic algoritm, it is a trading of flexibility for huge
> gains of speed. take into accout that some of these tricks neded a
> subtantial fraction of the age of the universe to evolve using massively
> paralell hardware (ecosystems).
>
>
>
>> What would be interesting is to have an evolution algorithm which
>> would allow such protections to evolve during its run. So some kind of
>> protection which would lower the rate of mutation for some code part.
>>
>> > Species of programs means that the seed of the genetic algoritm must not
>> be
>> > turing comoplete I guess. It must be specific for each problem.
>>
>> I do not see this as necessity. Just that those specimens which would
>> use this power too much would probably not survive. (If they would
>> remove protection for some sentences they have build before.)
>>
>
>
The mutation weigths are something conventional for coventional languages.
 Another option is to design an automodifying evolving language from
scratch. That "software DNA"
I guess, should follow closely the techniques of the real DNA. Your idea
fits more here

In the conventional approach, the turing incomplete templates can have
pre-assigned mutation weights for each statement. These mutation rates can
evolve too.

However, nothing prevents from having an additional level for selecting the
appropriate template for each problem.

>
>>
>> Mitar
>>
>
> Alberto
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] [Haskell] ANNOUNCE: genprog-0.1

[Mitar]

Hi!

On Thu, Dec 9, 2010 at 1:48 PM, Alberto G. Corona  wrote:
> assign rates of mutation for each statement,

This could be assigned by evolution itself. If "if" will have high
probability of mutation then resulting programs will not survive. So
those probabilities can be assigned by evolution itself and be also
something which is passed on with generations (with again possibility
of mutations of those probabilities itself).

What would be interesting is to have an evolution algorithm which
would allow such protections to evolve during its run. So some kind of
protection which would lower the rate of mutation for some code part.

> Species of programs means that the seed of the genetic algoritm must not be
> turing comoplete I guess. It must be specific for each problem.

I do not see this as necessity. Just that those specimens which would
use this power too much would probably not survive. (If they would
remove protection for some sentences they have build before.)


Mitar

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] [Haskell] ANNOUNCE: genprog-0.1

[Alberto G. Corona]

Hi Ketil,


2010/12/9 Ketil Malde 

> Mitar  writes:
>
> >> Neither Haskell nor any conventional language has [evolved to evolve]
>
> > True.
>
> Well - thinking about it, there's no fundamental difference between
> genetic algorithms - where you have a "genome" in the form of a set of
> parameters and genetic programming - where the "genome" is a program of
> some sort, typically Lisp code, since the syntax tree is so accessible
> and malleable.
>
> In either case, you have an interpreter that interprets the genome, the
> difference is mainly in the expressive power of the language.  I haven't
> looked closely, but I suspect you might not want Turing-completeness in
> either case (Alberto?



> ).
>

I´m not sure. (answer at the bottom). There are some characteristics on DNA
code that are there just to evolve some parts of the code while maintaining
safe some others. There are sequences that are extraordinarily stable for
millions of years across species, while others change very often. Some
others are in the middle. This is not arbitrary. Let´s say that the stable
parts are the IF statements while the changing parts are the parameter
values. Doing so, the species explores the safe part of the fitness
landscape without wasting effort in experiments that have 99% chance to
fail.

Females will evolve whatever mechanism to avoid these experiments as soon as
possible.
However risky experiments shoud be taken from time to time, to explore new
zones of the fitness landscape.

Another  characteristic of evolution, is its multilevel nature. There are
selection of genes. Selection of gene replication alternatives, selection of
reproduction alternatives. procariotic, eucariotic, multicelular
(individual), social levels of  selection.

Not only that. During ovulation there is a selection of good eggs, as I
mentioned. And this selection is related with the stability of critical gene
sequences.  this test for stability is regulated by other supervisor genes
that  test with different degrees of accuracy the absence of mutations in
these protected sequences. This  internal checking for consistency can be
considered a level of selection, or autoselection if you like. . selective
checking has evolved as a metalevel. But you can alternatively consider this
consistency check  as a set of rules written in the genetic code by
selection itself .  Rules are a form ofselection mechanisms after all.

All of these "Rules" have evolved because the genetic code executes over
itself  using its own code as data: Some genes activate others. some others
check for absence of mutations and so on. That is, some metalevel selection
are carried out by the same code that is evolving. Moreover some rules are
different for each genera or specie son it is  not possible to extract (and
abstract) out certain chekings from the code that is checked.

If evolution is search for local maximums in a tree, the rules/metalevels
are heuristic rules that guide the strategy of exploration.



Another

>
> But yes, by designing the language to evolve, we can get a head start
> compared to nature.
>
> Yes.
What means what I said above for evolving programs? First that a simple
genetic algorithm operating on auto modifying code can generate any solution
if we wait a few billion of years.  But we can help  to do it faster by
studying the DNA code, learn their already evolved techniques and use them
to design languages,  assign rates of mutation for each statement, discover
rules, selection mechanism, species of programs (or design patterns)  that
acts as templates for each problem etc.

Species of programs means that the seed of the genetic algoritm must not be
turing comoplete I guess. It must be specific for each problem.

 -k
> --
> If I haven't seen further, it is by standing in the footprints of giants
>
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] [Haskell] ANNOUNCE: genprog-0.1

[Ketil Malde]

Mitar  writes:

>> Neither Haskell nor any conventional language has [evolved to evolve]

> True.

Well - thinking about it, there's no fundamental difference between
genetic algorithms - where you have a "genome" in the form of a set of
parameters and genetic programming - where the "genome" is a program of
some sort, typically Lisp code, since the syntax tree is so accessible
and malleable.

In either case, you have an interpreter that interprets the genome, the
difference is mainly in the expressive power of the language.  I haven't
looked closely, but I suspect you might not want Turing-completeness in
either case (Alberto?).

But yes, by designing the language to evolve, we can get a head start
compared to nature.

-k
-- 
If I haven't seen further, it is by standing in the footprints of giants

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] [Haskell] ANNOUNCE: genprog-0.1

[Ketil Malde]

Andrew Coppin  writes:

>> A change to a gene does not make you to have a extra bone. It can
>> make you to have your hand slighltly longer. or shorter. 

> Actually I suspect it does - or at least can do. It's just a rather
> rare event.

Bodily development is regulated by a cluster of genes (the HOX
cluster).  The modern-day Galvani experiment is reshuffling this in
fruit fly to make antenna into legs.

I don't think it happens all that much in nature, and I guess any
resulting offspring would have reduced fitness.

-k
-- 
If I haven't seen further, it is by standing in the footprints of giants

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] [Haskell] ANNOUNCE: genprog-0.1

[Andrew Coppin]

On 08/12/2010 02:40 PM, Alberto G. Corona wrote:
A change to a gene does not make you to have a extra bone. It can make 
you to have your hand slighltly longer. or shorter. 


Actually I suspect it does - or at least can do. It's just a rather rare 
event.


In fact there are metalevels of selection that discard abrupt changes. 
For example, when females ovulate there are a strong selection where 
thounsands of candidate cell ovules are tested and discarded. This is 
one of the reasons why anomalous mutations are scarce.


I won't claim to be an expert in genetics, but I was under the 
impression that "big" changes to an organism's genetic code are usually 
fatal. This is the mechanism that "discards" any "abrupt" changes; they 
tend to not work properly.


The situation is a little different with evolving computer programs, 
since it isn't the computer program itself that makes the copies, it's 
some external entity "analysing" the programs and "deciding" which ones 
to copy.


Random example: Most animals can synthesize vitamin C. But humans and a 
handful of other related species can't. We have the whole metabolic 
pathway, it's all there, it's still working, except that the gene for 
the final enzyme in the sequence is busted. The enzyme transcribed from 
it doesn't actually work at all. Now, if you were born with a busted 
rhodopsin gene, you'd be blind, and probably wouldn't remain alive very 
long. However, since the stuff we eat has a fair amount of vitamin C in 
it anyway, apparently being biologically incapable of synthesizing it 
isn't actually a very big deal. (Unless you try to sail across the 
Atlantic Ocean...) Thus, almost nobody inherits a busted rhodopsin gene, 
but the entire human species has inherited a knackered L-gulonolactone 
oxidase enzyme.


Make of that what you will...


___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] [Haskell] ANNOUNCE: genprog-0.1

[Mitar]

Hi!

On Wed, Dec 8, 2010 at 4:51 PM, Alberto G. Corona  wrote:
> Of course there are smooth zones in the fitness landscape of any code. what
> is necessary is to direct the process by avoiding absurd replacements
> (mutations that goes straight to dead zones) and rules for changing from a
> smooth to another smooth area once the local maximum is not satisfactory. Or
> to detect them as early as possible (that is, rules again). That is what I
> mentioned before.

But this is not blind evolution as we know it. Of course, if you want
to speed up things you can use such techniques you are mentioning. But
this techniques use prior knowledge for this particular set of
problems. Evolution in general does not care about this. It has all
the time it needs.

>  Moreover, the genetic code has evolved to evolve.

I agree with that.

> Neither Haskell nor any conventional language has.

True. We should evolve also the language itself, not just programs.


Mitar

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] [Haskell] ANNOUNCE: genprog-0.1

[Alberto G. Corona]

Hi ;)

2010/12/8 Mitar 

> Hi!
>
> On Wed, Dec 8, 2010 at 3:39 PM, Alberto G. Corona 
> wrote:
> > DNK? I think you mean DNA.
>
> Sorry. In my native language it is DNK. ;-)
>
> > the genotype program  that develips the  fenotype is much more smooth and
> > granular than a computer program. A chante un a gen does not make you to
> > have a extra bone. It can make you to have your hand slighltly longer. or
> > shorter.
>
> Because we are using very small programs. A change of one constant in
> a Linux kernel would also be a very small change in general. Maybe
> some esoteric device would not function anymore, but this is it. Of
> course there would be also changes which would make whole kernel
> dysfunctional.
>
> Of course there are smooth zones in the fitness landscape of any code. what
is necessary is to direct the process by avoiding absurd replacements
(mutations that goes straight to dead zones) and rules for changing from a
smooth to another smooth area once the local maximum is not satisfactory. Or
to detect them as early as possible (that is, rules again). That is what I
mentioned before.


> > In fact there are metalevels of selection that discard abrupt changes.
> For
> > example, when females ovulate there are a strong selection where
> thounsands
> > of candidate cell ovules are tested and discarded. This is one of the
> > reasons why anomalous mutations are scarce.
>
> I doubt that. Aren't female eggs made while she is still a fetus? And
> they do not divide anymore later on?
>

This selection of candidate eggs happens each month within each ovulation
period. It is mentioned in this superb conference series by Yale university.
It is a very good introduction. I don´t remember the exact chapter. sorry:

http://www.youtube.com/watch?v=VjgHd6HKtvE

 Moreover, the genetic code has evolved to evolve. For many reasons. Neither
Haskell nor any conventional language has. One of the safety measures of the
genetic code is protectin itself against undesired mutations. This is
something vital for life. Cancer is one consequence. but another
consequences are more deadly: If a mother spend nine months to produce an
unfit child this is a dead end for the mother´s genome line.  For this
reason,  undesired mutations, specially in reproductive cells are either
repaired or discarded. This selection is more strong in females than in
males (for investment reasons) .

The rate of mutations in living beings is equal to the theorical optimum for
procariots and eucariouts. This is another examople of how finely tuned the
DNA has evolved for evolution. The molecular bonds are strong enough just to
permit the right rate of mutation . But the DNA i´m sure, has much more
secrets to learn and discover.

So in conclusion there are much details to learn and to implement to have
sucessful general genetic algorithms for genetic programming. But the
research promises a lot of fun.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] [Haskell] ANNOUNCE: genprog-0.1

[Alberto G. Corona]

DNK? I think you mean DNA.
the genotype program  that develips the  fenotype is much more smooth and
granular than a computer program. A chante un a gen does not make you to
have a extra bone. It can make you to have your hand slighltly longer. or
shorter.

In fact there are metalevels of selection that discard abrupt changes. For
example, when females ovulate there are a strong selection where thounsands
of candidate cell ovules are tested and discarded. This is one of the
reasons why anomalous mutations are scarce.


>
> 2010/12/8 Mitar 
>
> Hi!
>>
>> On Wed, Dec 8, 2010 at 12:33 PM, Alberto G. Corona 
>> wrote:
>> > But programs are non lineal.
>>
>> And DNK is? I doubt. ;-)
>>
>> I think the approach is valid, it simulates what is happening in
>> nature (random insertions, deletions, changes, translations, copies,
>> etc, without any "higher" meaning and guiding). Only problem is that
>> people often do not want to wait millions of years for evolution of
>> programs to achieve their goal.
>>
>> Of course mutations are only part of the story. Also combining
>> different parents' genes in a way to get functional offsprings is also
>> a question how to do with programs.
>>
>>
>> Mitar
>>
>
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] [Haskell] ANNOUNCE: genprog-0.1

[Mitar]

Hi!

On Wed, Dec 8, 2010 at 12:33 PM, Alberto G. Corona  wrote:
> But programs are non lineal.

And DNK is? I doubt. ;-)

I think the approach is valid, it simulates what is happening in
nature (random insertions, deletions, changes, translations, copies,
etc, without any "higher" meaning and guiding). Only problem is that
people often do not want to wait millions of years for evolution of
programs to achieve their goal.

Of course mutations are only part of the story. Also combining
different parents' genes in a way to get functional offsprings is also
a question how to do with programs.


Mitar

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] [Haskell] ANNOUNCE: genprog-0.1

[Alberto G. Corona]

Off topic

I was deeply involved in genetic programming in the past (in fact I
discovered Haskell on looking for a functional language  for genetic
programing with better syntax than LISP).

But I soon realized that GP was not the holy grial after all. The problem
with evolving arbitrary  programming code is the fitness
landscape.
 Any evolutionary process needs a way to produce small changes that produces
small increases or decreases of fitness (parsimony). This is why it is
relatively easy to evolve a continuous function towards a desired value. A
smal change in a parameter has a small effect in the resulting fitness, so
the algoritm can step up trough the smooth fitness landscape upto a local
maximum.

But programs are non lineal. If I change  the expression in a conditional,
the flow of the program becomes radically different, so the fitness
landscape, instead of a smoth continuous surface is a fractal where there
are no way to climb up the mount improbable (Dawkins dixit).

http://www.google.com/search?hl=en&q=mount+improbable+dawkins

The only way to overcome this is to indentify the smooth parts of the
fitness landscape and restrict the exploration to them trough some
techniques such is the use of rules, division of the problem in subproblems
and ...well any trick programmers use in their ordinary work to restrict and
direct the  program mutations.

 It is theoretically possilble to define metalevels of genetic algoritms
where rules and strategies are selected by extracting sucessful patterns
after evolving a big number of sucessful programs, These metaleves can
discover from simple rules such are "if a push is inserted, a pop must be
inserted somewhere else (push-pop gene mutation rule), upto the re-discovery
of complex rules above mentioned. These rules later would be used to
restrict the mutations of the lower levels. Finally the rules could become
so accurate that no mutation at the lower level is necessary because the
evolved higuer level rules give the solution at the first try.  So the
genetic algoritms have the potential to design arbitrary complex programs
right from scratch, but it may require a few billion years of computing.

Anyway this stuff is really interesting and I suspect that the combination
of rules and metalevels has some future, at least for helping programmers
with intelligent IDEs.

2010/12/8 Kenneth Hoste 

> Hi Jan,
>
> Hi Jan,
>
> On 11/29/2010 12:55 PM, Jan Snajder wrote:
> > Dear Haskellers,
> >
> > I am pleased to announce the release of genprog-0.1, a genetic
> > programming library.
> >
> > (snip)
>
> Very interesting, and nice job on the code (elegant, well-structured,
> well-documented, ...)!
>
> Genetic programming recently got my attention because one of the bots in
> the Google AI contest was built using this technique (see
> http://ai-contest.com/forums/viewtopic.php?f=17&t=1136), and it
> performed really well (way better than my hand-crafted bot).
>
> I have a bit of experience with genetic algorithms, on a practical and
> pragmatic level. The field of genetic programming is something I hope to
> look at and play with in the upcoming months (just for fun).
>
> I was kind of planning to implement my own genetic programming library
> in Haskell as I became familiar with the field, but after diving into
> your code it quickly became clear to me you've done a way better job
> than I would have.
>
> I really like the example you provided for evolving an expression that
> computes a specified integer value. I plan to start playing with that
> and improve the example (faster convergence to a perfect solution, and
> also tweaking the current GP config to obtain smaller solutions).
>
>
> A couple of questions (some fairly unrelated to Haskell):
>
> How hard would it be to extend the current version to support the
> evolution of actual Haskell programs? As far as I can tell, the current
> version has support for (simple?) self-defined expressions, but this
> seems like a long way from supporting Haskell programs with
> multi-argument functions that operate on lists, etc., even if you just
> limit it to non-monadic Haskell98 code.
>
> Have you considered playing with dynamic values for the various
> parameters that steer the evolution, i.e. population size,
> crossover/mutation probabilities, etc.?
> One thing I've always wanted to try (but never really got to it) is e.g.
> increasing the mutation probability as the evolution seems to be getting
> stuck in a (local?) optimum. Also, shrinking the population size if
> enough progress is being made could be interesting, to speed up the
> evolutionary process. Are you aware of studies that do such a thing?
>
> Are you planning to actively maintain and extend this library? Are you
> using it for research purposes, or did you hack this together just for
> fun (if so, nice job!). What do you plan to use it for?
>
>
> Anyway, great job, I hope I'll find the time to play ar