From: Tom
Subject: OT: Newbie question re: genetic algorithms/AI
Date: 
Message-ID: <dNbUb.402840$ts4.328152@pd7tw3no>
Hi,

I'm very sorry that this post is off-topic somewhat, but Jens recently said
"The main use of artificial intelligence is as an excuse to do Lisp
programming." :) so I thought maybe I'd try posting my question here. I
recently posted the same question to comp.ai.genetic but only a few people
seem to read that newsgroup (70 posts per month vs. over 2000 here in .lisp)

I'll warn you ahead of time that I'm a newbie in the field of AI/genetic
algorithms. I'm reading everything I can find on the subject trying to teach
myself, but I'm still confused about certain things. The following is an
unfortunately long summary of what I've learned and where I'm confused ...

If anyone feels like reading it and helping me that would be great, if not
that's fine! Don't blame me if you feel like you wasted 5 minutes of your
life after reading this... :)

Here is the text of the message:

Hello everyone,

I've recently started trying to put some of my ideas regarding programming
artificial intelligence on paper and lack some of the
skills/knowledge/higher math education to accomplish some of it. I'm trying
to create a very simple example and implementation of a genetic algorithm
for a layman/novice in the field.

I'm hoping some people with more skill in the field can review the scenario
below I have created in an attempt to understand some of these issues
better. Any thoughts or comments would be much appreciated!

As I understand it, the goal of genetic algorithms and evolutionary
computing involves essentially determining the best possible solution to a
problem, not by determining the best solution in advance and programming
your creature to do that solution, but to create a ton of creatures with
varying responses to stimuli and preserving the ones that survive the best,
that prove to be the "fittest". Then saving the best via "elitisim", and
mutating that one into a new population and running the situation/scenario
again.

So for my example, I am imagining a small robot. It's only goal is to
survive as long as possible. The only thing that affects its survival, at
least initially, is the ambient temperature around it. The robot doesn't
realize it, but the further from 50 degrees celcius in either direction, the
shorter its lifespan. Thus its ideal operating environment is 50 degrees.

Let's say that our robot has 10000 "life units". For every second it is in a
condition higher or lower than 50 degrees, it loses one "life unit" for each
degree. So, for example, for every second it sits in 100 degree conditions,
it loses 50 "life units" off its life span. If it can learn to find and stay
on an area of 50 degrees, it will live forever.

As for the environment our robot lives in, and the abilities of our robot,
they are as simple as I can make them:

Our robot:
Our robot lives in a grid of infinite size;
Our robot takes up 1 unit and begins its life in a random portion of the
grid;
Our robot can scan the temperature of all eight squares around it in one
second;
Our robot can move to any of the eight squares around it in one second;
Our robot can choose not to move.


Our environment, while randomly created, has these characteristics:
1 It varies in temperature from 0 to 100 degrees
2. At least one grid square is 0 degrees, at least one is 100, and at least
one is every degree in between.
3. Adjacent grid squares must either be the same degree as an adjacent
square, or else +-(1-10) degrees. (the idea being that this is similar to an
earth-type environment, simulating hills, mountains, valleys, icy tundra and
deserts, rather than random temperatures in each cell with no relation to
its neighbors.)


-----

Ok, I guess that's it. My question is, is this the sort of scenario genetic
algortithms and evolutionary computing would tackle? As far as I can tell it
is. Maybe I'm totally off base but as I understand it I seem to be on the
right track

I have some different thoughts on this (sorry if I'm thinking out loud at
this point). My robot doesn't know that 50 degrees is its ideal environment.
It doesn't know whether to sit, scan or move. There are at least two things
going on here that make this a situation in need of a genetic algorithm.
One, first and foremost I believe, is the fact that the robot doesn't know
what is best for it, and two (and taking the first into account) the size of
the grid. For example, let's argue that the robot knows that 50 degrees is
best for it, AND it is in the center of a grid that is only 3x3 squares. It
would be simple for a programmer to say, SCAN, MOVE to temperature closest
to 50 degrees IF temperature is less than LOCAL temperature, STOP. Since
there are only 8 squares to choose from, this process only has to be done
once to ensure moving to and/or staying on the best local ambient
temperature. Essentially, I can easily preprogram this robot due to the
simplicity of the scenario. Genetic algorithms are needed for more complex
situations. In this same situation, on a grid of 1000x1000, this simple
programming would not work. If the robot were sitting on a 90 degree square
and the 8 squares around it were 100 degree squares, it would choose to sit
still rather than "making a break" for it, essentially running over the 100
degree squares in the hopes of finding a square closer to 50 degrees. In
this case, the programming requirements become considerably more difficult
to predetermine, so genetic algorithms become necessary.

---

So my next question is, how does one go about populating the environment
with robots that actually do things?

On its first move, our robot can only do one of 10 things:

1-8 = (MOVE NORTH) (MOVE SOUTH) (MOVE EAST) (MOVE WEST) (MOVE NORTH EAST)
etc...
9= SCAN
10=(SIT STILL)

On its second move, it can do one of the above, or it now seems it can
EVALUATE its situation and do one of the above based on that evaluation.
Which leads me to realize that my robot can do things either: for a reason,
or for no reason. In other words, my robot can (MOVE NORTH) no matter what,
or it can (MOVE NORTH) because it's colder/hotter/(the same temperature)
that way. Likewise, my robot, I suppose, should likewise be able to SCAN for
a reason or for no reason (foolishly or not as the case may be), and should
be able to (SIT STILL) for a reason or for no reason.

Now there seems to be a bit of a philosophical question...my robot's goal is
survival, but it doesn't know that ambient temperature has anything to do
with its survival, nor does it know that 50 degrees is its ideal living
environment. I'm wondering if my robot needs to have a "preferred local
ambient temperature" variable that is a random number from 0 - 100. This
seems to raise many more questions and I'm not sure if it is even necessary
or makes sense. If a person/robot doesn't know that a certain temperature
range is good for them or care how it "feels", why would they move based on
that temperature except for personal preference ... the answer seems to be
inherited genetic tendencies... will those tendencies to 50 degrees evolve
naturally? It seems, the more I think about it, somewhere in the programming
of a successful robot, the local ambient temperature must be measured,
evaluated and reacted to. I'm not sure that a successful algorithm will be
able to be repeated without some sort of "memory" of the ambient temperature
... my question is, does the algorithm generate the fact that 50 is desired,
or do I need to program that into the algorithm myself? For example, suppose
my robots can not move at all. I plunk them down in my environment and I
come back a year later. The ones sitting on the 50 degree squares are still
alive, the rest are dead. Therefore, obviously, 50 degrees is the preferred
ambient temperature for survival. On the next pass through will this 50
degree preference be retained?

Anyway, to continue...

Now lets say my robot can (MOVE SOME DIRECTION) for the following reasons:
1. No reason
2. Scanned Grid is Colder than local temperature
3. "" ... Hotter than local temperature
4. "" ... Same as local temperature
5. "" ... Closer to (some ambient temperature) than Local temperature
6. "" ... Further from (some ambient temperature) than Local temperature
7. "" ... Equal to (some ambient temperature)
8. Local temperature is too hot (i.e. too far from some ambient temperature)
9. Local temperature is too cold ...""

Am I missing anything? I just thought of  8 & 9, which would enable a robot
to move into a position of greater danger than its local temperature in an
attempt to find a preferred ambient temperature. For example, suppose we
have a relatively "smart" robot that  knows it prefers an ambient
temperature of 50 degrees. It finds itself in a grid square of 99 degrees,
fully surrounded by squares of 100 degrees. The robot is so far from its
preferred temperature it has to move. Lacking a better route out of danger,
it has to go to a higher temperature area in the hopes of finding a better
(cooler) area further in that direction.

At this point it seems I also need some sort of "memory of actions taken".
In the previous situation, if the robot moved from the 99 degree square to a
100 degree square and did a scan, it would report back that there was a 99
degree square directly behind it. Assuming all other squares were 100
degrees, the robot would go back to its original location and have to start
over. It also seems I need a "memory" so that future populations know and
can replicate the basic survival tactics.

---

Well, that is about as far as I can go with my knowledge of the issues here.
I'm a programmer and can write a program that generates the world, and I can
program the robots in that world to follow instructions, but I don't know
enough (hardly anything) about generating populations with basically random
actions, and then preserving the fittest and repopulating the world with
variations of that survivor.

I would love to hear any suggestions or comments,

Thanks,

Tom

From: Tom
Subject: Re: OT: Newbie question re: genetic algorithms/AI
Date: 
Message-ID: <j%dUb.400700$X%5.110792@pd7tw2no>
Thanks very much for the helpful insights Klaus!

(Though strangely your message came through as an attachment)

Genetic programming does seem to be what I need to get a better grasp on,
and finding a program I can understand and see work will I'm sure be very
helpful in eventually writing my own.

As far as genetic algorithms go, I am still trying to find or formulate a
very simple example of one that I can understand.

The simplest idea I can come up with that might be one is the following:

I have a creature with four possible actions
1=sit still
2=walk away
3=run away
4=attack

It has a "lifetime" of four turns. It does one of the actions every turn.

You say:
>In a genetic algorithm you have to encode your individuals (in your
>case the programs which operate the robots) into fixed length
>bitstrings. These bitstrings are then modified by the above mentioned
>crossover and mutation operators.

Therefore I have (4x4x4x4=256) possible DNA strings... (1111 1112 1113 1114
2111 ... 4443 4444).

Now I put four of my creatures into an environment. In this case we'll say
my creature is facing a cheetah that will only attack if the creature either
attacks or attempts to escape. Sitting still is the only thing that will
save my creatures life. So I put creature 1111, 2222, 3333, and 4444 into
the ring. After one turn, 1111 is still alive, 2222 is still alive (the
cheetah is chasing him), 3333 is still alive, and 4444 is dead. After the
second turn, 1111 is still alive, 2222 is dead (the cheetah caught him),
3333 is still alive (it takes a little longer for the cheetah to catch him
as he's running). After the third turn, only 1111 is alive as the cheetah
has caught creature 3333 who was  running away.

So we know, of this group: 1111 is the fittest, 3333 is second best, 2222 is
third best and 4444 is the least fittest. Now we generate four more
creatures. We keep 1111 (elitism) and combine 1111 and 3333 and get 1133,
3311. Finally we mutate 1111 and get 1211. Now these guys go back in the
ring...and we repeat this for n number of generations.

Is that pretty much a genetic algorithm at its simplest?



"Klaus Uhl" <····@u-h-l.de> wrote in message
···················@ulm.my.lan...
From: Frank A. Adrian
Subject: Re: OT: Newbie question re: genetic algorithms/AI
Date: 
Message-ID: <pan.2004.02.04.23.38.02.664161@ancar.org>
On Thu, 05 Feb 2004 00:04:42 +0100, Klaus Uhl wrote:

> BTW. If you really implement the robot problem (some time in the
> future ;-)) don't forget to set a limit for the number of timesteps
> the fitness evaluation function considers. If you forget this you will
> find your genetic programming kernel evaluate the fitness of some
> robot infinitely as soon as it manages to create an optimally behaving
> one.

The other thing to remember is to change the environment every few
generations. Otherwise, you might breed individuals who are "overtrained"
to a specific environment, i.e., being able to survive in one environment
because they learned the perfect set of steps to survive there, but unable
to survive general environments because their algorithms are too specific. 

faa
From: Jeff Silverman
Subject: Re: OT: Newbie question re: genetic algorithms/AI
Date: 
Message-ID: <c0959r$plk$1@nntp6.u.washington.edu>
Tom wrote:
> Thanks very much for the helpful insights Klaus!
> 

I did not see Klaus' helpful insights -  could you repost them or E-mail 
them (convert the dashes to dots, remove the NOSPAM- and that should 
make a proper E-mail address)

Thank you



Jeff



-- 
Jeff Silverman,
Senior Computing Specialist 3, Fire and Environmental Research Applications
(FERA) team.  College of Forest Resources
jeffsilv at NOSPAM,PLEASE-u-washington-edu   (206) 732-7815
http://duet.cfr.washington.edu/~jeffs
From: RSM
Subject: Re: OT: Newbie question re: genetic algorithms/AI
Date: 
Message-ID: <AqGdnbDJ-rpei7TdRVn-hg@comcast.com>
Jeff,

I have some code for doing genetic algorithms/genetic programming. It is at
the Source Forge site:
http://sourceforge.net/projects/com-lisp-utils/

The genetic algorithm package is in the directory rsm/ga
The genetic programming package is in the directory rsm/gp.

-R. Scott McIntire

"Jeff Silverman" <········@NOSPAM-u-washington.edu> wrote in message
·················@nntp6.u.washington.edu...
> Tom wrote:
> > Thanks very much for the helpful insights Klaus!
> >
>
> I did not see Klaus' helpful insights -  could you repost them or E-mail
> them (convert the dashes to dots, remove the NOSPAM- and that should
> make a proper E-mail address)
>
> Thank you
>
>
>
> Jeff
>
>
>
> --
> Jeff Silverman,
> Senior Computing Specialist 3, Fire and Environmental Research
Applications
> (FERA) team.  College of Forest Resources
> jeffsilv at NOSPAM,PLEASE-u-washington-edu   (206) 732-7815
> http://duet.cfr.washington.edu/~jeffs
>
From: Tom
Subject: Re: OT: Newbie question re: genetic algorithms/AI
Date: 
Message-ID: <af8Wb.462213$X%5.352536@pd7tw2no>
"Jeff Silverman" <········@NOSPAM-u-washington.edu> wrote in message
·················@nntp6.u.washington.edu...
> Tom wrote:
> > Thanks very much for the helpful insights Klaus!
> >
>
> I did not see Klaus' helpful insights -  could you repost them or E-mail
> them (convert the dashes to dots, remove the NOSPAM- and that should
> make a proper E-mail address)
>
> Thank you
> Jeff


Sure thing:

Message 1:

"Tom" writes:

> Hello everyone,
>
> I've recently started trying to put some of my ideas regarding programming
> artificial intelligence on paper and lack some of the
> skills/knowledge/higher math education to accomplish some of it. I'm
trying
> to create a very simple example and implementation of a genetic algorithm
> for a layman/novice in the field.
>
> I'm hoping some people with more skill in the field can review the
scenario
> below I have created in an attempt to understand some of these issues
> better. Any thoughts or comments would be much appreciated!
>
> As I understand it, the goal of genetic algorithms and evolutionary
> computing involves essentially determining the best possible solution to a
> problem, not by determining the best solution in advance and programming
> your creature to do that solution, but to create a ton of creatures with
> varying responses to stimuli and preserving the ones that survive the
best,
> that prove to be the "fittest". Then saving the best via "elitisim", and
> mutating that one into a new population and running the situation/scenario
> again.

This is partially correct. Yes, initially you create a number of
random creatures (about 100 to 100000 depending on the problem I
think). Then you evaluate the fitness of each of these creatures
according to the fitness measure you are interested in (this would be
the lieftime of the robot in your example below).

But then you become somewhat vague in your statement above. You want
to create the next generation of creatures (named individuals in the
following). But therefore you do not simply choose the fittest ones
and "mutate" them into the new population (whatever you mean with
"mutate"). There are two basic operation which can be performed to
create candidates for the new population:

1. Mutation. This means that you randomly change parts of an
   individual.

2. Crossover. Here you choose _two_ individuals of your - population,
   usually with a probability proportional to its fitness, and
   recombine them to a new one.

>
> So my next question is, how does one go about populating the environment
> with robots that actually do things?
>
> On its first move, our robot can only do one of 10 things:
>
> 1-8 = (MOVE NORTH) (MOVE SOUTH) (MOVE EAST) (MOVE WEST) (MOVE NORTH EAST)
> etc...
> 9= SCAN
> 10=(SIT STILL)

This looks more like genetic programming than like a genetic algorithm.

In a genetic algorithm you have to encode your individuals (in your
case the programs which operate the robots) into fixed length
bitstrings. These bitstrings are then modified by the above mentioned
crossover and mutation operators.

In genetic programming you start with a random program (that could
directly operate the robots in your case) and modify these
programs. This can easily be done in Lisp as here a program is
_explicitly_ a tree and you can directly insert/remove/change parts of
this tree. You cannot do this with a language like Java or C++.

>
> ...
>
> Anyway, to continue...
>
> Now lets say my robot can (MOVE SOME DIRECTION) for the following reasons:
> 1. No reason
> 2. Scanned Grid is Colder than local temperature
> 3. "" ... Hotter than local temperature
> 4. "" ... Same as local temperature
> 5. "" ... Closer to (some ambient temperature) than Local temperature
> 6. "" ... Further from (some ambient temperature) than Local temperature
> 7. "" ... Equal to (some ambient temperature)
> 8. Local temperature is too hot (i.e. too far from some ambient
temperature)
> 9. Local temperature is too cold ...""
>
> ...
>
> At this point it seems I also need some sort of "memory of actions taken".
> In the previous situation, if the robot moved from the 99 degree square to
a
> 100 degree square and did a scan, it would report back that there was a 99
> degree square directly behind it. Assuming all other squares were 100
> degrees, the robot would go back to its original location and have to
start
> over. It also seems I need a "memory" so that future populations know and
> can replicate the basic survival tactics.

You think too much in an operational manner. Genetic algorithms and
genetic programming are a variant of what is called "reinforcement
learning". (I know that this statement could annoy people who are
active in either the genetic algorithm/programming or the
reinforcement learning community but I state it this way as I think of
reinforcement learning as a generic term for a whole family of
learning algorithms, so don't blame me, please).

As the term "learning" implies, when you run a genetic (programming)
algorithm there is some knowledge accumulated in the individuals. In
your robot world the robots, or more precisely the inidividual robot
programs _learn_ the correct temperature to live in and they will also
_learn_ how to find a cell with a good temperature. You do not have to
put any thoughts into how the robots should/might behave. Just state
the problem and let it run through your genetic programming kernel and
enjoy what resulting robot control programs you get.

I know this was a bit fast and a bit short. But the best way to learn
about genetic programming (I think this is what you need for your
robot domain) is to see it working on some simple problems and I
cannot give you that in this group. So let me guide you to a good book
about genetic programming (I think it is even something like the bible
of genetic programming): "Genetic Programming" by John R. Koza (MIT
Press, 1992). It also contains a genetic programming kernel but I'm
not sure if you will find the code on the internet but
www.genetic-programming.com should be a reasonable place to start
searching.

Klaus

-- 

                 God is real ...
\|/ ____ \|/     ... unless declared integer.
·@'/ ,. ··@"
\_| \__/ |_/     Mail me : ····@u-h-l.de
   \__U_/        WWW     : www.u-h-l.de
                 PGP     : 0x128F9DEC
From: Tom
Subject: Re: OT: Newbie question re: genetic algorithms/AI
Date: 
Message-ID: <6g8Wb.462219$X%5.268187@pd7tw2no>
"Jeff Silverman" <········@NOSPAM-u-washington.edu> wrote in message
·················@nntp6.u.washington.edu...
> Tom wrote:
> > Thanks very much for the helpful insights Klaus!
> >
>
> I did not see Klaus' helpful insights -  could you repost them or E-mail
> them (convert the dashes to dots, remove the NOSPAM- and that should
> make a proper E-mail address)
>
> Thank you
> Jeff

Message 2:

"Tom" <······@notarealaddress.com> writes:

> The simplest idea I can come up with that might be one is the following:
>
> I have a creature with four possible actions
> 1=sit still
> 2=walk away
> 3=run away
> 4=attack
>
> It has a "lifetime" of four turns. It does one of the actions every turn.
>
> You say:
>>In a genetic algorithm you have to encode your individuals (in your
>>case the programs which operate the robots) into fixed length
>>bitstrings. These bitstrings are then modified by the above mentioned
>>crossover and mutation operators.
>
> Therefore I have (4x4x4x4=256) possible DNA strings... (1111 1112 1113
1114
> 2111 ... 4443 4444).
>
> Now I put four of my creatures into an environment. In this case we'll say
> my creature is facing a cheetah that will only attack if the creature
either
> attacks or attempts to escape. Sitting still is the only thing that will
> save my creatures life. So I put creature 1111, 2222, 3333, and 4444 into
> the ring. After one turn, 1111 is still alive, 2222 is still alive (the
> cheetah is chasing him), 3333 is still alive, and 4444 is dead. After the
> second turn, 1111 is still alive, 2222 is dead (the cheetah caught him),
> 3333 is still alive (it takes a little longer for the cheetah to catch him
> as he's running). After the third turn, only 1111 is alive as the cheetah
> has caught creature 3333 who was  running away.
>
> So we know, of this group: 1111 is the fittest, 3333 is second best, 2222
is
> third best and 4444 is the least fittest. Now we generate four more
> creatures. We keep 1111 (elitism) and combine 1111 and 3333 and get 1133,
> 3311. Finally we mutate 1111 and get 1211. Now these guys go back in the
> ring...and we repeat this for n number of generations.
>
> Is that pretty much a genetic algorithm at its simplest?

Yes, that is a very simple genetic algorithm. It is not that hard to
understand, isn't it?

I thought about how to "convert" this into a genetic programming
example but I did not find a solution. Your robot problem seems to be
much more suited for a genetic programming algorithm because you can
sense the temperature of adjacent cells and take conditional action
according to these. The problem is that the fitness in both cases is
defined as the number of timesteps the creature/robot lives and thus
one should be able to rerun the program for every timestep and then
test if the creature still lives (or update the robot's life points).

BTW. If you really implement the robot problem (some time in the
future ;-)) don't forget to set a limit for the number of timesteps
the fitness evaluation function considers. If you forget this you will
find your genetic programming kernel evaluate the fitness of some
robot infinitely as soon as it manages to create an optimally behaving
one.

- Klaus

P.S.: If you find this message only as an attachment this might be due
to the fact that I singed it with PGP/MIME so that it became a
multipart MIME message. Maybe Outlook Express cannot handle this. If
other people encounter the same problem then mail me, please. I will
consider to use plain PGP then (but don't post this to the group but
send it directly to me).

-- 

                 God is real ...
\|/ ____ \|/     ... unless declared integer.
·@'/ ,. ··@"
\_| \__/ |_/     Mail me : ····@u-h-l.de
   \__U_/        WWW     : www.u-h-l.de
                 PGP     : 0x128F9DEC
From: Ray Dillinger
Subject: Re: OT: Newbie question re: genetic algorithms/AI
Date: 
Message-ID: <40217FCE.66EBF041@sonic.net>
Well, I'm going to be a noodge here and point out something you may not have 
considered.  

Consider the virtue of not moving, in the system you have described.  If the 
robot happens to occupy a fifty-degree square, and never moves, then it lives
forever, and occasionally reproduces, flooding your environment with a whole 
herd of not-moving robots.  Of these, most will die off since they are not in
the magical places whose temperature is fifty, but if you're giving the 
immortal, immobile one a billion tries, eventually every space on the board 
that is fifty degrees will be occupied with another, immortal, immobile, robot. 

This will mean that no other robot may ever achieve immortality because all
squares where immortality is available are occupied by immortal, immobile 
robots.  When this happens, the next optimal strategy is to occupy the squares
that are 49 or 51 degrees -- and not move.  However, these robots, while 
their optimal strategy is also to remain immobile, are not immortal.  They 
will die occasionally, opening up a space that a neighboring robot could move 
into.  

But by that time, if you have been evolving according to a model of there 
being few survivors in each generation, there are likely to be no robots 
left who know how to move.  At all.  

Pitfalls of genetic algorithms include:

   1) static fitness landscapes tend to beget static solutions
      (ie, the temperature in each square does not change, so the 
       robots don't move.)

   2) if there's any "cheap trick" that satisfies your fitness function,
      your beasties will discover and exploit it, regardless of whether 
      it's interesting or useful.

   3) Don't make the genomes too simple; it seems like they never 
      usefully evolve unless the genome is at least ten times bigger
      than any simple solution to the problem would need (Google 
      for the word "Introns" if you want to read papers on this). 

Now, to talk more specifically about your problem, consider a function 
that takes a single argument named EXPERIENCE and returns one of nine 
symbols each corresponding with one of the robot actions (8 compass 
directions and standing still). 

EXPERIENCE is a linked list of arrays.  Each array represents the state
of the simulation visible to the robot at some time in the past, and is
probably 11 elements long;  that is, 9 elements correspond to the temps 
the robot was able to measure or probe, and 2 correspond to the robot's 
X,Y coordinates at that time (absolute, or relative to the location of 
its "birth"). And the first element of EXPERIENCE, of course, is the 
current situation.  

It sounds like you're trying to derive this function.  

If that's the case, then what you want to do is genetic programming, 
rather than some other kind of genetic algorithm.  The easiest way 
to do this requires you to think of functions as a tree data structure, 
like the syntax tree of the expression that gives it.  This is the 
"natural" form of LISP programs. 

For genetic programming, you set up primitives and combinators you 
think might be generally useful for the problem and and you build 
a bunch of random trees of combinators with primitives at the root 
nodes.

In order to do mutation, you change any primitive or combinator for 
a different primitive or combinator of the same type.  For example
you could change > with < or =, because they are all the same type:
they take two numeric arguments and return a boolean.  You could also
change 30 for 92, because they are also the same type: they take no 
arguments and return a number.

In order to do crossover, you replace one randomly selected subtree 
of one parent with any randomly selected subtree of the other parent
that returns the same type. 

Now, having written your reproduction function and implemented the 
robots' little virtual world to that their EXPERIENCE list gets updated
correctly whenever they move and so their function gets called with it
at each step of the sim, you still have one more thing to do, and 
that is to decide under what circumstances to reproduce.

For the system you've described (breeding for the ability to achieve
long life) it sounds like you need an age criteria for reproducing.
Say, for example, that any critter that has lived longer than N 
turns since its birth (or since its last offspring was produced) 
gets to reproduce.  Then you can adjust N in realtime to keep the 
population relatively stable.

In answer to your question, yes, Lispy languages are the natural form
for any genetic-programming experiment, because the parse trees are 
the primary representation of the languages.  Read in Lisp manuals about 
CAR, CDR, CONS, EVAL, QUOTE, and UNQUOTE, and you will see immediately
how to build data structures, manipulate them, and turn them into 
functions in a program.

				Bear
From: Tom
Subject: Re: OT: Newbie question re: genetic algorithms/AI
Date: 
Message-ID: <wB8Wb.452049$JQ1.218315@pd7tw1no>
"Ray Dillinger" <····@sonic.net> wrote in message
······················@sonic.net...
>
> Well, I'm going to be a noodge here and point out something you may not
have
> considered.

The idea behind the post was to generate responses so you don't have to
worry about that :) The reality of the situation is I don't know that much
about genetic programming or genetic algorithms and hoped people would
respond to my post and basically point out my problems and where to focus my
research. So you're no noodge to me.

However, the scenario I generated I sort of made up "on the fly" in an
effort to create a scenario that was "dumbed down" to my level. Doing a
search for easy/simple genetic algorithms via google found anything but ;)
The scenario was really intended more as a framework or reference for people
to analyze that I could make sense of. My goal was less "I want a robot that
does this" and more about "I want to learn how to use, understand and create
a genetic algorithm or program that could create scenario x". This
admittedly, as you pointed out, resulted in a scenario that was perhaps less
than ideal for creating the fittest creature.

> Consider the virtue of not moving, in the system you have described.  If
the
> robot happens to occupy a fifty-degree square, and never moves, then it
lives
> forever, and occasionally reproduces, flooding your environment with a
whole
> herd of not-moving robots.  Of these, most will die off since they are not
in
> the magical places whose temperature is fifty, but if you're giving the
> immortal, immobile one a billion tries, eventually every space on the
board
> that is fifty degrees will be occupied with another, immortal, immobile,
robot.
>
> This will mean that no other robot may ever achieve immortality because
all
> squares where immortality is available are occupied by immortal, immobile
> robots.  When this happens, the next optimal strategy is to occupy the
squares
> that are 49 or 51 degrees -- and not move.  However, these robots, while
> their optimal strategy is also to remain immobile, are not immortal.  They
> will die occasionally, opening up a space that a neighboring robot could
move
> into.
>
> But by that time, if you have been evolving according to a model of there
> being few survivors in each generation, there are likely to be no robots
> left who know how to move.  At all.

I hadn't fully fleshed out my scenario, but I did envision an infinite grid
populated by, initially perhaps, 1000 or 10000 inhabitants. I couldn't make
up my mind as to whether a 50 degree square would only take away 1 second of
the robots initial 10000 "life units" or no life units at all (resulting in
an immortal robot). However, I did have in mind but didn't mention that the
fitness of the robot would be measured after, say, 5000 seconds. Also, I
didn't have reproduction in mind, just repopulation. After the 5000 seconds
my idea was to pick up/remove the survivors (the fittest) and use them as
the basis for my mutations and crossovers...then I would take those and put
them back in the world. I realized that a robot lucky enough to land on a 50
degree square and not move would live through the first scenario but what I
envisioned as the second generation would have a copy of this survivor that
would likely die quickly unless it was so lucky as to land on a 50 degree
square again. But hopefully the mutations would create robots with a
tendency towards that 50 degree square.

>
> Pitfalls of genetic algorithms include:
>
>    1) static fitness landscapes tend to beget static solutions
>       (ie, the temperature in each square does not change, so the
>        robots don't move.)
>

I had some ideas about a non-static fitness landscape but thought it would
likely add more confusion to my learning process

>    2) if there's any "cheap trick" that satisfies your fitness function,
>       your beasties will discover and exploit it, regardless of whether
>       it's interesting or useful.
>
>    3) Don't make the genomes too simple; it seems like they never
>       usefully evolve unless the genome is at least ten times bigger
>       than any simple solution to the problem would need (Google
>       for the word "Introns" if you want to read papers on this).
>

In the process of my search I turned up an interesting looking "genetic
algorithm viewer" at http://www.rennard.org/alife/english/gavintrgb.html .
Haven't had a chance to play with it yet though (have to get dinner in the
oven :)


> Now, to talk more specifically about your problem, consider a function
> that takes a single argument named EXPERIENCE and returns one of nine
> symbols each corresponding with one of the robot actions (8 compass
> directions and standing still).
>
> EXPERIENCE is a linked list of arrays.  Each array represents the state
> of the simulation visible to the robot at some time in the past, and is
> probably 11 elements long;  that is, 9 elements correspond to the temps
> the robot was able to measure or probe, and 2 correspond to the robot's
> X,Y coordinates at that time (absolute, or relative to the location of
> its "birth"). And the first element of EXPERIENCE, of course, is the
> current situation.
>
> It sounds like you're trying to derive this function.

That sounds about right.

So then the first array (representing the first second of the scenario or
(Time=1) might look like: (N=70, NW=75, W=65, SW=65, S=60, SE=60, E=65,
NE=65, LOCAL=70, XLocation=300, YLocation=250).


I've been thinking about what you wrote after this for awhile ... why its
taken so long to reply. I was still having some difficulty figuring out how
to apply/understand certain aspects of what you wrote so I finally found a
book at the library that wasn't checked out, called "The Importance of Being
Fuzzy (and other insights from the border between math and computers)" by
Arturo Sangalli. It had a very good section on fuzzy logic, a very difficult
section on Neural Nets (I was hoping this section would be a bit simpler),
and so far has had a very good section on Genetic Algorithms. I'm hoping it
will eventually help clarify some of the issues you raised regarding genetic
programming.


>what you want to do is genetic programming,
rather than some other kind of genetic algorithm.  The easiest way
to do this requires you to think of functions as a tree data structure,
like the syntax tree of the expression that gives it.  This is the
"natural" form of LISP programs.

This was a bit unclear to me...I don't really know what "tree data
structure/systax tree" means yet...I can sort of visualize what it means but
otherwise I am not sure.

You also wrote:

>For genetic programming, you set up primitives and combinators you
think might be generally useful for the problem and and you build
a bunch of random trees of combinators with primitives at the root
nodes.

I also have to figure out what primitives and combinators are ... I've only
just begun to learn lisp ... as I said, once I do some more research
hopefully things will fall into place a little more clearly.

Thanks very much for your help,

Tom
From: Ray Dillinger
Subject: Re: OT: Newbie question re: genetic algorithms/AI
Date: 
Message-ID: <4029229C.F4102057@sonic.net>
Tom wrote:
> 
> "Ray Dillinger" <····@sonic.net> wrote in message

> >what you want to do is genetic programming,
> rather than some other kind of genetic algorithm.  The easiest way
> to do this requires you to think of functions as a tree data structure,
> like the syntax tree of the expression that gives it.  This is the
> "natural" form of LISP programs.
> 
> This was a bit unclear to me...I don't really know what "tree data
> structure/systax tree" means yet...I can sort of visualize what it means but
> otherwise I am not sure.

For an example, consider an expression like (3+2)/5.  
This expression is representable as a syntax tree like this: 
(use a monospaced font)

               /
            Division
             /    \
         Addition  5
           /  \
          3    2


In this syntax tree, 3, 2, and 5 are leaf nodes because they don't 
combine anything.  The addition and division operators both combine 
two numbers and return another number; structurally, they are 
combinators of type (number*number->number). 

In Lisp, you would write the above expression using the syntax 

(/ (+ 3 2) 5)


Which, if quoted, can be read DIRECTLY as data, a list having 
exactly the same structure as the syntax tree.

If this list is then eval'd, it becomes executable code which 
you may run.

But while it is a list, you can change it around using list 
operators before you eval it.

Since you can build syntax trees from scratch, or copy them, 
or create changed versions of them, using list operations like 
car, cdr, and cons, and convert them from structured trees 
directly into code using eval, Lisp gives you an environment
where you can manipulate trees that correspond to expressions,
and then evaluate those expressions, arbitrarily.  That is why 
almost all genetic programming is done using Lisps. 

				Bear