473,605 Members | 2,531 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Genetic programming: pygene, pygp, AST, or (gasp) Lisp?

Hi folks,

I've played around with neural nets for a while. I wrote my own slow,
pure-Python NN package. I knew that there were Python NN packages out
there -- but I couldn't really understand their features and
documentation at first, not without some hands-on experience.

I haven't yet solved any interesting problems with NN, but I learned a
lot about both NN and about Python along the way. One of the
unpleasant things I learned about NN was their propensity for becoming
trapped in local minima. I also learned about overfitting, wasting
many hours of CPU time in the process. In short, simple neural nets
have disappointed me.

I have now asked myself: wouldn't it be cool if, when you ceased to
make progress on an optimization algorithm, you could divide your data
set with an "if" statement, which would evolve a useful dividing line
through your data set -- and then, develop divergent solutions to
explain each subset better?

In mathematical terms:

Round 1 of evolutionary programming leads to a single, but sub-optimal
solution, probably a solution in a local minimum:

b = f(a)

Round 2 would start by elaborating the solution of round 1, adding a
condition that is initially meaningless:

if disc(a) < c:
b = f1(a)
else:
b = f2(a)

Initially, f1() = f2() = the original f(). Therefore, the output of
the starting state of round 2 will be identical to the output of the
final state of round 1, regardless of the initial state of the
discriminant function, disc(). But then, f1(), f2(), and disc() will
all be permitted to evolve. This may provide a chance to "pop out" of
the local minimum, without sacrificing any of the progress made in
defining the solution of round 1.

Of course, f(), f1(), f2(), and disc() could be complex functions.
They would best be described with parse trees, which I've just
discovered (I'm not formally trained in computer science).

Some reading has led me to conclude that what I'm proposing is
basically genetic programming.

http://en.wikipedia.org/wiki/Genetic_programming

I've tried my hand at this already in Python. I have devised a code
tree class, which functions as a parse tree for functions and also
handles multiple-line statements. I've tried cobbling together program
strings from code trees, and then using the exec() function to run
them. This is all very cool, but I'm finding it VERY cumbersome!

As with neural nets, I know that there are genetic programming
packages offered for Python:

http://www.freenet.org.nz/python/pygene/
http://sourceforge.net/projects/pygp/

But I can't really understand what they do -- both of these packages
are, alas, minimally documented. Is anyone out there using either of
these? I can't tell whether they will implement algorithms of the
type I've described here. Specifically, I don't know if conditional
statements are included in their repertoire. Also, Pygene SEEMS to
have a bent toward Boolean logic. I'm working with analog data, and I
want complex, nonlinear functions.

So, as with neural nets, shall I once again proceed on my own? There
is apparently a layer in the Python interpreter at which code is
represented as an abstract syntax tree (AST).

http://docs.python.org/lib/ast.html

Why not do genetic programming directly on Python code? Maybe my code
tree data structure is redundant to something which already exists?
But apparently Python's "_ast" module offers only one-way access -- it
will generate an AST from a piece of code, but you can't modify an
AST, and turn it back into executable code? I would definitely need
this latter feature.

ALTERNATELY -- and I don't mention this to start a flame war -- in
pondering this problem I've noticed the frightening fact that Lisp
seems set up to handle genetic programming by design. The s-
expression syntax IS essentially a parse tree. Now, I've spent a few
hours with Lisp so far, and I can't make it do much of anything -- but
I DO see how Lisp could be helpful. Still, I'm reluctant to pursue a
language I don't know, and which I'm finding much harder to grasp than
any language I've tried before.

Is there a way to interface Lisp to Python, so that I can do all the
interface programming in the language I already know best -- and just
do the genetic parts in Lisp? I haven't seen exception handling in
Lisp, a feature I've come to love in Python. Since it is fairly easy
for a randomly-generated program to generate illegal output (I already
know this from my initial experiments in Python), I don't think I can
live without exception handling.

I also think that Python has a higher-level understanding of a
variable's "type" or an object's "class" than Lisp does -- if I'm
hacking at a parse tree and I want to minimize syntax errors, I need
to know more than the fact that an element in an expression is an atom
or a list.

Producing human-readable code from my genetic programming search would
be a great bonus -- and for me, at this moment, this seems to mean
Algol-style syntax. (Sigh.) But it's not a requirement.

Thanks for your advice!
Jul 20 '08 #1
6 4876
On 20 Jul., 09:52, John Ladasky <lada...@my-deja.comwrote:
Why not do genetic programming directly on Python code? Maybe my code
tree data structure is redundant to something which already exists?
But apparently Python's "_ast" module offers only one-way access -- it
will generate an AST from a piece of code, but you can't modify an
AST, and turn it back into executable code?
Why not? You can compile ASTs.

Another option is to use EasyExtend

http://www.fiber-space.de/EasyExtend/doc/EE.html

which is a bit heavyweight though without prior knowledge of the
framework.

EE provides some generic functions over languages like parse/unparse.
Python is just a special case. So you can do the following

from EasyExtend.lang lets.zero.langl et import parse, unparse

src = """
if disc(a) < c:
b = f1(a)
else:
b = f2(a)
"""

parse(src) # yields a parse tree
unparse(parse(s rc)) # yields the source code of the parse tree

Here `zero` means Python which is just the trivial/featureless langlet
of the system or some kind of embedding.

For meshing fragments together on random one can use cst.py.

For each rule in Pythons grammar cst.py implements a corresponding
function that produces the parse tree accordingly. So if there is a
rule

test: or_test ['if' or_test 'else' test] | lambdef

a corresponding function test(*args) exists that produces a parse tree
from components that were built using or_test(), test() or lambdef().
chaining these functions is just like building s-expr.
I would definitely need
this latter feature.

ALTERNATELY -- and I don't mention this to start a flame war -- in
pondering this problem I've noticed the frightening fact that Lisp
seems set up to handle genetic programming by design.
Definitely. But this is nothing new. Lisp was the original language
used by John Koza to implement GP.
The s-
expression syntax IS essentially a parse tree. Now, I've spent a few
hours with Lisp so far, and I can't make it do much of anything -- but
I DO see how Lisp could be helpful. Still, I'm reluctant to pursue a
language I don't know, and which I'm finding much harder to grasp than
any language I've tried before.
You can write a primitive s-expr evaluator/manipulator using Pythons
overloading capabilities. But this way you will just produce s-expr
and not Python functions.

Kay
Jul 20 '08 #2
On Sunday 20 July 2008 09:52, John Ladasky wrote:
Is there a way to interface Lisp to Python, so that I can do all the
interface programming in the language I already know best -- and just
do the genetic parts in Lisp? I haven't seen exception handling in
Lisp, a feature I've come to love in Python. Since it is fairly easy
for a randomly-generated program to generate illegal output (I already
know this from my initial experiments in Python), I don't think I can
live without exception handling.
Just searching the Web for Python and Lisp yielded some interesting
projects:

http://www.biostat.wisc.edu/~annis/creations/PyLisp/
http://www.livelogix.net/logix/

I've no idea if they're really that relevant to your problem, but they
might lead somewhere useful.

David
Jul 20 '08 #3
John Ladasky wrote:
Why not do genetic programming directly on Python code? Maybe my code
tree data structure is redundant to something which already exists?
But apparently Python's "_ast" module offers only one-way access -- it
will generate an AST from a piece of code, but you can't modify an
AST, and turn it back into executable code? I would definitely need
this latter feature.

ALTERNATELY -- and I don't mention this to start a flame war -- in
pondering this problem I've noticed the frightening fact that Lisp
seems set up to handle genetic programming by design. The s-
expression syntax IS essentially a parse tree. Now, I've spent a few
hours with Lisp so far, and I can't make it do much of anything -- but
I DO see how Lisp could be helpful. Still, I'm reluctant to pursue a
language I don't know, and which I'm finding much harder to grasp than
any language I've tried before.
The main advantages that Lisp has to a structural language like Python
are that in Lisp there is no distinction between code and data --
they're represented in the same way -- and the syntatic uniformity of
the language. Originally the idea with Lisp was that s-expressions were
a lower-level syntax that a more Algol-like syntax would be translated
to ... then it became aware that the syntax was actually a benefice in
many ways, not a hindrance.
Is there a way to interface Lisp to Python, so that I can do all the
interface programming in the language I already know best -- and just
do the genetic parts in Lisp? I haven't seen exception handling in
Lisp, a feature I've come to love in Python. Since it is fairly easy
for a randomly-generated program to generate illegal output (I already
know this from my initial experiments in Python), I don't think I can
live without exception handling.
It is not likely you want to do this. Genetic programming systems are
probably best run in a sandbox, for reasons which should be pretty
reasonable. The point of genetic programming is to manipulate programs
into new programs; thus, complicated syntax for those programs only
increases the chances that either 1. you have to do an awful lot of
extra work to make sure that you end up with valid programs or 2. you
end up with an awful lot of syntactically invalid programs. Both of
these waste large amounts of processing cycles that you could be
focusing on creating new, valid programs from old ones.
I also think that Python has a higher-level understanding of a
variable's "type" or an object's "class" than Lisp does -- if I'm
hacking at a parse tree and I want to minimize syntax errors, I need
to know more than the fact that an element in an expression is an atom
or a list.
If you're interested in typed genetic programming systems, then you
might want to check out some of the stack-based genetic programming
languages like Push or PushGP. These are in effect a stack-based form
of Lisp, but which use different data stacks for different types.
Producing human-readable code from my genetic programming search would
be a great bonus -- and for me, at this moment, this seems to mean
Algol-style syntax. (Sigh.) But it's not a requirement.
Well, you could always translate s-expressions into m-expressions ...

--
Erik Max Francis && ma*@alcyone.com && http://www.alcyone.com/max/
San Jose, CA, USA && 37 18 N 121 57 W && AIM, Y!M erikmaxfrancis
It isn't important to come out on top, what matters is to be the one
who comes out alive. -- Bertolt Brecht, 1898-1956
Jul 21 '08 #4
John Ladasky said:
Why not do genetic programming directly on Python code?

maybe Dione is what you are looking for - it seems to manipulate
Python asts directly

http://sourceforge.net/projects/dione/
Jul 21 '08 #5
also, you could look at the simple openopt example provided by GA
"galileo" solver (connected to OO framework)
http://projects.scipy.org/scipy/scik...mples/glp_1.py
http://scipy.org/scipy/scikits/wiki/GLP
Regards, D
Jul 21 '08 #6
Thanks to everyone who replied. I haven't chosen a definite direction
for my project yet. But you have given me some good leads.

Google Books offers previews of many pages of John Koza's book,
published in the early 1990's. I'm reading through the preview pages,
with the idea of purchasing a more recent book on the subject once I
understand the subject a bit better.

Apropos to Python, I've had a quick look at the parse and compile
functions in Python's compiler module. The Python AST is MUCH longer
than I expected it to be, for just a few lines of code. It may
contain more information than I need. I'll see whether I can make
sense of EasyExtend or Dione next.
Aug 3 '08 #7

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

34
2663
by: nobody | last post by:
This article is posted at the request of C.W. Yang who asked me to detail my opinion of Lisp, and for the benefit of people like him, who may find themselves intrigued by this language. The opinions expressed herein are my personal ones, coming from several years of experience with Lisp. I did plenty of AI programming back in the day, which is what would now be called "search" instead.
0
1797
by: Jelle Feringa / EZCT Architecture & Design Researc | last post by:
Could anyone recommend me a genetic algorithm package? So far I have found a few, such as GAS, pyGP, Genetic, and of course scipy.ga My problem is that most of the development of these packages seems to be stalled, or that in scipy.ga's case, the module seems huge and somewhat overly complicated. Could someone recommend me a module, which is still being developed, somewhat more concurrent than the stuff I'm finding? Any recommendations,...
3
1481
by: ThanhVu Nguyen | last post by:
Hi, I am looking for a forumn or newgroups that is about Genetic Programming. Since this group probably is the most active and and largest programming ng so I thought probably someone will know where I can find places for GP. Currently I am doing some GP projects and would like to ask questions or discuss about it. Not really sure where to go. I know there is comp.ai.genetic but it seems mostly for conference papers. I am looking...
10
2684
by: Ruben Hoste | last post by:
Hello, I'm currently looking for more information on Genetic Algorithms and more specifficaly on how to program them in Java or C++. This is all concerning my thesis. A lot of general information about GA's, what they are and how they generally work I already found on the web, but I'm looking for some more information on how to actually program them. Is there a certain programming language preferably to use to program the GA? Has anyone...
80
5228
by: Bibby | last post by:
Hi, I'm interested in getting started in the programming world. I've dabbled in C, C++ and VB6. Which would be the best language to focus my attention to regarding the following considerations: Hireability Portability Flexibility The likely candidates seem to be Java, VB.Net, C, C++, C#.
134
7948
by: evolnet.regular | last post by:
I've been utilising C for lots of small and a few medium-sized personal projects over the course of the past decade, and I've realised lately just how little progress it's made since then. I've increasingly been using scripting languages (especially Python and Bourne shell) which offer the same speed and yet are far more simple and safe to use. I can no longer understand why anyone would willingly use C to program anything but the lowest...
2
3676
by: Xiao Jianfeng | last post by:
Hi all, I am looking for a genetic algorithms package for Python. I have googled the web before posting and found some links. The link of pygene(http://www.freenet.org.nz/python/pygene) cannot be opened. I also tried the recipe on ASPN, but it is too simple for my application, and the ga model in SciPy, which is in testing in the "sandbox".
0
1161
by: arbogast | last post by:
I've downloaded the GASP package (from http://pypi.python.org/pypi/gasp/0.4.5 as I want to follow this tutorial http://openbookproject.net/thinkCS/python2e.php but I simply can't figure out how to install the GASP-package & google hasn't been helping. I'm sure there's a really simple solution to this but I can't figure it out.
0
8004
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
8418
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
0
8288
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
1
5886
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
5445
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
3912
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
1
2438
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
1
1541
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
0
1271
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.