Self-Improving Systems

Roland Olsson writes "A relatively easy way to construct "intelligent" systems that improve themselves practically ad infinitum is described at http://www-ia.hiof.no/~rolando/SIG/ Maybe Steven Spielberg's AI film is closer to reality than the general public knows *smile*?"

Comments

if only it were that simple

[rossjudson]

Please. Two notes on a page? Breakthrough? Hah. It's a hell of a lot tougher than it looks.
Read Koza's three tomes for extensive research on genetic programming (the art of developing programs through genetic-evolutionary techniques).
Read about particle swarms if you want to learn about an evolutionary technique that is quietly kicking the ass of most others wherever it is used.
From a theoretical point of view, this feels like it won't solve or do anything that can't be found within the solution space anyway, by another technique.

Re:if only it were that simple

[jayant_techguy]

sort of

Re:if only it were that simple

[xmedar]

The main problem is what is not shown, i.e. the fitness function, for those that don't agree I challenge you to derive a fitness function for human beings, when you start finding that the fitness function is partially given by the humans themselves and the technologies and social organisations they adopt (i.e. humans are part of the problem space too) you suddenly find that what looked easy is actually not. The system described on the webpage is a "solution" in the same way that economics has a "solution" by specifying that supply/demand curves are given and not derivable and therefore misses the point. Certainly genetic algorithms are useful for well defined fitness criteria, unfortunately much of life is so intertwined that actually defining it is not possible.

Re:if only it were that simple

[Alsee]

The main problem is what is not shown, i.e. the fitness function

I've programmed some genetic projects myself, and your right. In some cases the hardest part is creating an effective fitness function.

This leads me to an interesting insight. In some cases it may be worth evolving the fitness function. It may be easier to write a fitness function for a fitness function. A fitness function should return maximum value on correct data, minimum value on random data, and intermediate values for data with varying amounts of random errors. Creating a variety of degrees of random errors as test cases would usually be pretty easy.

This technique would approximately double the time to solve a problem. For hard problems, double running time is a heck of a lot better than unsolvable.

Interesting project, I'll have to give this a try. I haven't programmed any genetics in ages.

Re:if only it were that simple

[Alsee]

P.S.
I wasn't reffering to the fitness function for humans, though that's an easy one. The fitness function for humans is how many decendants they have.

Re:if only it were that simple

[manyoso]

Sorry, that is _not_ a fitness function for humans... The number of offspring any given human has does not affect there probability of survival rather it speaks to the probability of there descendants survival. Again, a _fit_ person may have many kids, but having many kids does not make a person _fit_!

Re:if only it were that simple

[shibboleth]

A fitness function should return maximum value on correct data, minimum value on random data, and intermediate values for data with varying amounts of random errors.

If you had code that could determine how correct your data is that's all the fitness function you need.

The problem of how to break down complex programming tasks into GA-buildable algorithms is often very difficult for a knowledgable and intelligent person much less a computer program. Therefore an automagic general case solution is in my opinion impossible until there is a general and flexible art. intelligence, something I believe no one has much of clue how to build. The good news: it's fun to try in the meantime.

Re:if only it were that simple

[xmedar]

So if we had 100 trillion decendents from a generation then we would have good fitness even though we would not be able to feed all but a few billion of them? Worst case people start lobing weapons of mass destruction around to get their fill of food and wipe out the human race. Like I said, fitness in human beings is not just a biological one, it is social and technological one as well. Humans are part of their own fitness function, therefore it is not possible to describe that fitness function without refering to the system itself, there will be lots of recursion involved and inflection points and discontinuities when we hit the introduction of new social organisations (like cities) and technologies (like the Net). In essence what I am saying is that the fitness function is at best chaotic and at worst a social/technological form of Heisenbergs uncertainty principle.

Re:if only it were that simple

[xmedar]

The number of offspring any given human has does not affect there probability of survival rather it speaks to the probability of there descendants survival.

Depends, if the descendents say take on the belief system of their parents, like for example an apocalypic cult like Aum Shinrikyo in Japan, the number of offspring could be inversely related to their survival (more people to cause the apocalyse, more chance of it happening, more chance of them and the rest of us being killed)

Re:if only it were that simple

[JesseL]

Most people seem to agree that the ultimate survial probability for humans is 0% ;-)

Re:if only it were that simple

[Alsee]

Sorry, that is _not_ a fitness function for humans
In the context of evolution, number of decendants is the definition of fitness.

but having many kids does not make a person _fit_
In the context of evolution it does. Everyone dies. The genes of people with decendants survive.

Economic success may give a competitive/survival edge, but it tends to correlate with lower birth rate. Mental instability and drug abuse may threaten survival, but they tend to correlate with higher birth rates. Nature's finess function has nothing to do with rational judgment.

Re:if only it were that simple

[Alsee]

so if we had 100 trillion decendents from a generation then we would have good fitness even though we would not be able to feed all but a few billion of them?
Evolution doesn't give a damn about human ideas of good or bad. If you have 100 trillion people, and food for 10 billion, then 999.99 trillion would die. By definition the living ones are fit and the dead ones are not.

Attempting to apply fitness to groups is usually ill-defined.

Worst case people start lobing weapons of mass destruction around to get their fill of food and wipe out the human race.
That is called extinction. Nature does not care. Any organism that cannot survive in it's enviornment(radioactive) is unfit. Humans would be far from the first species to go extinct from altering it's own enviorment.

fitness in human beings is not just a biological one, it is social and technological one as well.
A human's capacity for society/technology is a product of his biology. The society/technology he is surrouned by is his enviornment.

the fitness function is at best chaotic and at worst a social/technological form of Heisenbergs uncertainty principle
Even without technology the specific challenges an organism must overcome to reproduce are often Heisenberg - recursive, complex, and even contradictory. Mental instability may result in more offspring (someone I've met comes to mind, heh).

In the end, individuals with decendants are evolutionarily fit. Those without decendants are not.

Human society and technology makes for a very complex enviornment. The rules of evolution apply until we start choosing our own DNA.

Re:if only it were that simple

[Alsee]

If you had code that could determine how correct your data is that's all the fitness function you need.

Did you miss my context? I was talking about feeding data to an evolving fitness function. You can create correct data(simulated output), slightly bad data, very bad data, and totally random data. Good fitness functions would returning higher values for the better data. The idea was to evolve a fitness function and use that to evolve a solution.

Re:if only it were that simple

[Cassandra]

The fitness function for humans is how many decendants they have.

That's not the fitness function, at least not in GP. The fitness function determines the number of decendants.

Re:if only it were that simple

[manyoso]

Yes, having offspring might change the parent's probability for survival such as when the offspring kills the parents. However, this is of course not guaranteed. What I was arguing was that the ability to have many children does not define how fit a person is. In fact, in the vast majority of cases it would have no impact whatsoever. Having children does not (in general) make people survive longer, just that people who have many children most likely are good at surviving.

Re:if only it were that simple

[manyoso]

"In the context of evolution, number of decendants is the definition of fitness."

Just what do you mean "context of evolution". Excuse me but the ability to survive is the "definition of fitness". Those that survive are fit, those that do not, die! That is the basic tautology of "survival of the fittest".

Re:if only it were that simple

[Alsee]

That's not the fitness function, at least not in GP. The fitness function determines the number of decendants.

Hehe, ok. Then the fitness function of every human is unique. It consists of the state of the universe in a sphere around that person with a radius in light years equal to the remaining lifespan of the person, and returning the number of children that person is capable of producing.

The function is the unique environment. It is irreducable. I think the only way to simplify it is conceptually as I did in "The fitness function for humans is how many decendants they have". It is equivalant and easier to mentally process.

Re:if only it were that simple

[Alsee]

Just what do you mean "context of evolution"

Maybe I missunderstood you. You had said "but having many kids does not make a person _fit_!" and the only way I could make sense of it was to assume you were using "fit" in a generic language sense. Example I know a mentally unstable person with children. This person is not "fit" in a conversational sense, bit is fit (or sucessful) in an evolutionary sense.

Re:if only it were that simple

[Lozzer]

Its funny how that is accepted by everyone, yet we also hear the quote "More people are living now than have died throughout history"

Re:if only it were that simple

[xmedar]

Evolution doesn't give a damn about human ideas of good or bad. If you have 100 trillion people, and food for 10 billion, then 999.99 trillion would die. By definition the living ones are fit and the dead ones are not.

So if say BillG cornered the worlds market in food and so only his offspring and employees survived they would "by definition" be fit even though their survival had nothing to do with any intrinic abilities they possessed but rather a random factor of birth/employment?

A human's capacity for society/technology is a product of his biology. The society/technology he is surrouned by is his enviornment.

This is a Nature 1 : Nurture 0 argument, i.e. biological predestination, my biology is very similar to all other humun beings, yet some work in supermarket check outs or fly airplanes and I chose to be a techie, my consciousness is only partly determined by my genetics, I would venture that mostly it's a product of my choices, driven by what I feel is interesting, as someone who is part of creating my environment I know that it is a two way relationship, which is what I was getting at.

Even without technology the specific challenges an organism must overcome to reproduce are often Heisenberg - recursive, complex, and even contradictory. Mental instability may result in more offspring

So you are agreeing with me that it is not possible to form a fitness function as negative and positive traits cannot be descerned.

In the end, individuals with decendants are evolutionarily fit. Those without decendants are not.

So test tube babies created from donor sperm/eggs make the individual fit then?

Human society and technology makes for a very complex enviornment. The rules of evolution apply until we start choosing our own DNA.

The rules of evolution always apply, the difference is what is fit in one social / technological environment is not fit in another, and as we humans shape our societies and technologies, we are already changing the selection criteria.

Re:if only it were that simple

[shibboleth]

Aside from pattern recognition tasks, can you give me an example of where one knows how a fitness function should be scoring given input at the same time that the fitness function itself is unknown?

From what i've read and thought, the problem in using GAs is in det'ing how to break down a complex task into "tasklets" (my term) amenable to GA. Deciding where to apply a fitness function and for what it should be testing is the issue that really needs to be solved in the general case for GAs to become a widespread, practical technology.

While some objectives are ill-defined (eg, art and obscenity are typically defined as "i know it when i see it" :-]), det'ing how a fitness function should be scoring given input and det'ing a usable fitness function are usually going to be ths same job.

Re:if only it were that simple

[Alsee]

So you are agreeing with me that it is not possible to form a fitness function as negative and positive traits cannot be descerned.
Some significant traits can be descerned, but ultimately the fitness function is the universe around that person. Each individual experiences a unique fitness function. A more specific description of the function may be useful, but is necessarily incomplete(except in the past tense). ('function necessarily incomplete' is probably agreement with 'not possible to form a fitness function')
Genes even affect which tests we are exposed to. An individual afraid of snakes is less likely to be exposed to the test of surviving rattler venom. If snakes were a common threat, fear of snakes would be a + to fitness.

So if say BillG cornered...food ..."by definition" be fit even though their survival had nothing to do with any intrinic abilities
There is certainly a random factor. Fitness is the ability to survive the random set of challenges you face(your unique fitness function). Even in this example traits are being selected for. Those that died could have stored food, or been able to digest wood, or had a resistance to starvation. They failed that test. Those that survived had associated with a powerful person, a survival trait.

The sun going nova would be a pretty intense selection pressure, hehe. In the year 2XXX humans will be fit. Interstellar travel could be a pretty handy survival trait :)

&GT A human's capacity for society/technology is a product of his biology.
&GT The society/technology he is surrouned by is his enviornment.
This is a Nature 1 : Nurture 0 argument, i.e. biological predestination
?Misunderstanding? I didn't intend anything like that.
Nature is potential and inclination.
Nurture is possibility and influence.
If you have steady hands you have the potential to be a surgeon.
If your parents can afford medical school you have the possibility to be a surgeon.
If you have an 'adrenaline junkie' gene you may be inclined to become a cop.
If your adoptive parents are cops you might be influenced to become a cop.

So test tube babies created from donor sperm/eggs make the individual fit then?
Society is part of the environment. The environment changed. Some forms of infertility are no longer selected against. So yep, they are fit in their environment.

&GT choosing our own DNA
The rules of evolution always apply
If we have designer babies (or redesign ourselves) the rules go out the window. The multiplication of genes is no longer linked to survival / sucessful reproduction. The elimination of genes is no longer linked to failure.

Re:if only it were that simple

[Alsee]

My idea was to pretend to use the fitness function normally, but really feed it simulated cases with known the order of accuracy...

can you give me an example of where one knows how a fitness function should be scoring given input at the same time that the fitness function itself is unknown?

It's been a while since I've experimented with GA's. A hard part was dreaming up tasks complex enough to be interesting, but simple enough to be attackable. I can't think of anything good offhand, so I'll use the a semi-lame :) example of sorting numbers.

If you can create correct answers then you can create varying levels of erroneous answers. Make a list of "errors" you can apply - swapped numbers, a missing number, a doubled number. Apply N errors to a correct list. Feed the evolving fitness function a correct list, some lists with different numbers of errors, and a totally random list. An evolving fitness function would score high if it rated them in close to the right order.

Did that help?
It's just something I dreamed up in the middle of posting here. No clue if it's useful or is just a dumb idea. If you can think of good target problems let me know :)

Re:if only it were that simple

[Alsee]

What I was arguing was that the ability to have many children does not define how fit a person is ... Having children does not make people survive longer

I'm not sure if I understand - are you equating an individual's lifespan with fitness?

Unless an individual has additional offspring, longevity is (mostly) irrelevant to evolutionary success(fitness).

Re:if only it were that simple

[Kalani]

Yes and we also hear, "there are no habitable planets or life-sustaining resources within our reach, except for our own Earth."

Re:if only it were that simple

[xmedar]

Some significant traits can be descerned, but ultimately the fitness function is the universe around that person. Each individual experiences a unique fitness function.

And would you agree that an individual human beings effect on their environment is much larger than zero, and orders of magnitude greater than the other lifeforms on the planet, e.g. my "fitness" may be bad in a poor country as my technology skills are not required therefore I will not eat and therefore die, but if I get on a plane and fly to a country where my skills are in high demand I can live a very nice life and have many offspring. In that case I can choose my environment and therefore choose my fitness, therefore my fitness and my choices are inseperable.

There is certainly a random factor. Fitness is the ability to survive the random set of challenges you face(your unique fitness function). Even in this example traits are being selected for. Those that died could have stored food, or been able to digest wood, or had a resistance to starvation. They failed that test. Those that survived had associated with a powerful person, a survival trait.

My point is that conscious choice means that there is massive non-linear and random feedback which makes the fitness function impossible to devine therefore you cannot model the system. As for surviving by being associated with a powerful person, that assumes a continuation of power, in the above example you might survive a while, before BillG comes crashing down under the weight of Open Source and therefore has no more power therefore you die and the trait dies with you (sorry this is /. remember).

The sun going nova would be a pretty intense selection pressure, hehe. In the year 2XXX humans will be fit. Interstellar travel could be a pretty handy survival trait :)

I think the estimate is about 4 billion years before the Sun becomes a red giant and engulfs this planet, which illustrates my point again. Humans would take plants / animals with them and therefore the fitness function for planet/animals would also become entwined with humans and therefore their fitness function would not be calculable, imagine a fitness function that incorporates terms describing how liked they are by humans as pet/food/inspirational/spiritual, do you think you could do that?

Nature is potential and inclination.
Nurture is possibility and influence

Agreed, and...
Imagination is possibility.
Conscious choice is actualisation.

Society is part of the environment. The environment changed. Some forms of infertility are no longer selected against. So yep, they are fit in their environment.

Who is they? Do you mean the genetic donor? The Sperm/eggs? Or in infertile parents?

If we have designer babies (or redesign ourselves) the rules go out the window. The multiplication of genes is no longer linked to survival / sucessful reproduction. The elimination of genes is no longer linked to failure.

The rules are already out of the window. Survival / reproduction is no longer something that is guided only by genes, nurture does play a part, and conscious choice now plays an even larger part. Take people who have a particular musical bent (like perfect-pitch), some might choose to be part of a classical orchestra, and some may choose to be a rockstar, the rockstar has more chance of reproduction than the classical musician, yet they both share a genetic predisposition in the same direction, so genetics becomes much less important than conscious choice, therefore the human is the more influential part of the fitness function and cannot be discounted, therefore there is no possibility of creating a fitness function for the human. QED

Re:if only it were that simple

[manyoso]

Yes, I regard an individual's lifespan aka likelyhood to survive as a statement of the organism's fitness. Any self-reproducing organism by definition has the ability to pass on it's genes, but only those that survive long enough because they are fit are actually able to. I think you are confusing things when you say an organism's fitness _is defined by_ the amount of offspring they have, rather an organism's fitness _defines_ how many offspring they _may_ have.

Re:if only it were that simple

[manyoso]

I think I understand where we disagree. You are basically saying that in an "evolutionary context" fitness is _defined by_ how many offspring a given organism has. I disagree. I am saying that in every context including evolution the amount of offspring an organism has is _defined by_ how fit that organism is. I think you are taking the cart before the horse.

Re:if only it were that simple

[The Milky Bar Kid]

Thanks for this, rossjudson. I'm 6/7 months into a phD which is currently heading towards swarm robotics as a subject. I'd heard of the ant trail stuff, but I hadn't seen the particle swarm idea before now. Looks really cool. Thanks.

Re:if only it were that simple

[Alsee]

Just because something benefits an individual does not imply it improves fitness.

Yes, I regard an individual's lifespan aka likelyhood to survive as a statement of the organism's fitness.

Let me split that into two pieces...

[] likelyhood to survive as a statement of the organism's fitness.
This is true in that an organism must survive long enough to mature and reproduce.

I regard an individual's lifespan [] as a statement of the organism's fitness.
I am not claiming longer lifespan is never a benefit, but in many cases it is false. Lifespan in itself is not an evolutionary advantage. Many species breed once and die. The males of some species gain an advantage by being eaten by their mates. There are even cases where long lifespan would be a disadvantage, and would be selected against (competing with their own offspring for food etc).

Longer lifespan is selected for in two cases.
(A) The individual continues to produce offspring, and the offspring are net gain (law of diminishing returns due to sibling competition).
(B) The individual benefits their decendants (rare, but may apply to post-menopausal women).

Re:if only it were that simple

[mrogers]

'Fitness' is easy to determine in simple optimization problems such as the travelling salesman problem, and this is the area where genetic programming has enjoyed some success. But it's difficult to imagine applying genetic programming techniques to the development of what most people think of as software: operating systems, word processors, web browsers and the like. The 'fitness' of large, complex programs can be as difficult to determine, and as subjective, as the 'fitness' of biological organisms. For example, even if you could measure abstract properties of a program such as usability, robustness and performance, what relative weights would you assign to those abstract properties in your overall fitness function? It is absurd to think that a property such as 'usability' could be measured in an automatic way (that is, without large amounts of user testing and statistical analysis of the results), and if a property cannot be measured it cannot be used in a fitness function.

Genetic programming suffers from the same scalability problems as manual programming: it is easy to write an isolated algorithm or procedure, but the difficult part of design is not algorithms but architecture: to design the whole requires an understanding of the parts and vice versa. (Which is not to say that picking the right algorithm isn't important, but it shouldn't be difficult.) Designing the fitness function for a complex program requires as much architectural insight as designing the program itself.

So where will genetic programming come into its own? Consider natural selection. An organism does not live or die based on an abstract fitness function, it lives or dies based on the particular circumstances in which it finds itself. The fitness function is different for each individual in each situation: in fact the fitness function is no less complex than the world itself. The fitness function includes every predator, every drop of rain, every photon escaping from the organism's surface. The enormous complexity of the environment drives the evolution of ever more complex organisms. As more complex organisms evolve, they make the world more complex for their neighbours, so species must continue to evolve just in order to survive: like the Red Queen, they must run to stand still.

Where can we find this kind of complexity in computer science (outside of the POSIX standards documents)? In applications that are connected to the hugely complex social world of human beings: applications like email and chat. There are already programs living 'in the wild' in this complex environment, programs that are able to reproduce in the digital world by exploiting niches in the social world: email viruses.

Evolution will occur in any system that meets three basic requirements:

• Competition between individuals for limited resources
• Variation among individuals, affecting their chance of reproducing ('fitness')
• Inheritance (offspring are more similar to their parent(s) than to a random member of the population)

Wherever evolution occurs, the complexity of the evolving system will increase to match the complexity of its environment. Viruses will eventually exceed the complexity of any hand-written software, because they will evolve to meet the complexity of their environment, the human social environment, which is far more complex than any artifact designed by a single human being.

Re:if only it were that simple

[Alsee]

I think we pretty much agree on many points, but we are phrasing it differently :) I am going to *try* to reduce this effect.

I think pretty much agree on the following?
note: "organism" = "humans, just like everything else".
There is a feedback loop between an organism and it's environment. The society that an organism is born into is part of it's enviornment. It's potential to relate to that society(and the rest of it's enviornment) and it's inclinations in doing so are determined by it's genes. The enviornment has a huge impact(possibilities and influences) on how it develops. Fitness is how well it interacts with it's enviornment to reproduce.

Earlier in the thread I said "ultimately the fitness function is the universe around that person[I should have used organism rather than person]...a more specific description...is necessarily incomplete" so I think we agree it is hopeless to try to create an actual function, human or otherise (except perhaps with huge simplifying assumptions).

It looks like many parts of your post is centered around a relationship between human intellegence and fitness function. I *think* the dissagreement is that I don't see humans as beyond the rules.

Last post you said The rules are already out of the window, but your post before said The rules of evolution always apply? My position is/was "The rules of evolution apply until we start choosing our own DNA."

rockstar/classical conscious choice
Human thought is more sophisticated, but I don't see it as fundamentaly changing anything. Different enviornments(experiences) lead to different behavior(decisions).

human is the more influential part of the fitness function and cannot be discounted
I agree that no organism can be discounted from it's fitness function - the interaction is fundamental. It changes it's enviornment by mere presenece. I dissagree about humans having some unique effect.
I can choose my environment and therefore choose my fitness, therefore my fitness and my choices are inseperable.
Animals choose their enviornment when they migrate. Beavers radically alter/create their enviornment by building dams. Humans may have (figuratively and literally) raised it to a science, but it is not a new effect.
conscious choice means that there is massive non-linear and random (?) feedback
I think massive non-linear feedback is a given in any biological system, even bacteria. As far as conscious choice - I think if you can "solve the problem" for apes then you have either solved it for humans, or are a relatively small step away.

no possibility of creating a fitness function for the human. QED
iff (ape QED) iff (frog QED) iff (fly QED) iff (yeast QED).

Sun/red giant/function entwined with humans/[can I calculate the function]
Many species already rely on other species for survival. If you can give me all the current species functions without humans, I'll give you the you the the entwined function. :) I claim the difference is relatively trivial.

-miscellaneous below here
surviving by being associated with a powerful person, that assumes a continuation of power...BillG comes crashing down...trait dies with you
The trait of associating with power would imply an inclination to jump ship and find a new association.

Imagination is possibility. Conscious choice is actualisation.
Error processing input. (A)bort, (R)etry, or (I)gnore?
Please (R)etry.

&GT &GT So test tube babies created from donor sperm/eggs make the individual fit then
&GT they are fit in their environment
Who is they?
The sperm/egg donors. Coocoo bird fitness is based on laying eggs in other's nests.
The confusion is probably because I merged the donor 'they' and receiver 'they'. My mental image was of a couple using their own sperm/eggs to overcome a defect.

Re:if only it were that simple

[Alsee]

I think you are taking the cart before the horse.

In a sense, yes. And in a sense no :)
I'm saying impossible to see the actual cart except from the horse. (Umm, or is it the other way around? hehe)

The only way to measure fitness is in relation to a specific enviornment and to analyze/predict it's interaction with that enviornment. In the case of a biological organism on earth the enviornment is a sphere of the universe with radius in lightyears equal to it's lifespan. A comet heading towards the earth can have a huge effect on it's fitness - positive or negative.

The problem is irreducable unless you change the ground rules (example: yeast in an ideal infinite vat of nutrients).

For an irreducable problem the only answer is historical.

Other measures of fitness are possible and useful, but they are necessarily incomplete.

Re:if only it were that simple

[xmedar]

note: "organism" = "humans, just like everything else".

Yes humans are organisms like every other the only difference is the magnitude of change in terms of survival that each individual can make not only to him/herself but also to the rest of the population, if you want to take recent events then look to see if there are any other animals that can slaughter 5,000-6,000 of its bretheren in the space of a couple of hours, I am certainly not aware of any other organism that can do such a thing. Compare say with an ant colony, say an ant wanders off on its own and does not return, that ants contribution to the whole is lost, but it does not make a difference of anything like the same magnitude as one human being can make. What Iam arguing is that humans, due to intelligence / technology / choice have a much higher tipping point as far as the survival of others is concerned. Maybe if Hilter had not been born there would have been no WWII and millions of lives would not have been lost. Comparing other organisms to humans makes sense if we were still cave dwellers scavenging for food, today we have the ability as individuals to affect the lives of millions or even billions of our species, no other organism can do that.

There is a feedback loop between an organism and it's environment. The society that an organism is born into is part of it's enviornment. It's potential to relate to that society(and the rest of it's enviornment) and it's inclinations in doing so are determined by it's genes. The enviornment has a huge impact(possibilities and influences) on how it develops. Fitness is how well it interacts with it's enviornment to reproduce.

As above I am saying that the feedback is orders of magnitude more than other organisms and therefore is approximate to a discontinuity.

Earlier in the thread I said "ultimately the fitness function is the universe around that person[I should have used organism rather than person]...a more specific description...is necessarily incomplete" so I think we agree it is hopeless to try to create an actual function, human or otherise (except perhaps with huge simplifying assumptions).

BINGO! The simplifying assumptions can approximate simple lifeforms which can then be modelled, like I said my point is that you cannot make assumptions about humans as you have to factor in the choice-technology part of the equation (e.g. you can only choose to nuke the planet if you have invented nukes) which can have more of an impact on survival than being a good hunter-gatherer.

It looks like many parts of your post is centered around a relationship between human intellegence and fitness function. I *think* the dissagreement is that I don't see humans as beyond the rules.

Do you mean that the intelligence-choice-technology aspect is so small as can be discounted as a simplifying assumption then? If so could you explain to my why as I see no way to discount them given the sort of examples I have given above and in this thread.

Last post you said The rules are already out of the window, but your post before said The rules of evolution always apply? My position is/was "The rules of evolution apply until we start choosing our own DNA."

The rules of evolution always apply because they would not be the rules of evolution if they did not. As far as the rules being out of the window, I should clarify I mean our conception of the rules is out of the window, i.e. survival of the fitest is always true by its own definition, it is just we cannot determine what constitutes "fit" due to addition of the highly disruptive intelligence-choice-technology component of the equation.

Human thought is more sophisticated, but I don't see it as fundamentaly changing anything. Different enviornments(experiences) lead to different behavior(decisions).

Expereince is not genetically coded and therefore is outside of the evolutionary sphere (unless you are arguing for Lamarkian evolution where expereince IS coded in genes). Environments(experiences) and behavior(decisions) are connected via the human brain which itself an evolving entity, i.e. you have evolution in the mind within the lifetime of the individual which is a majot part of determining whether the individual reproduces.

As far as conscious choice - I think if you can "solve the problem" for apes then you have either solved it for humans, or are a relatively small step away.

Thats fine, except for the fact it ignores technology which allows us more choices, an ape may choose to wipe out every other ape on the planet, but it doesnt have the means, we do, and thats why there is such a huge difference in the individuals contribution to not only its own survival but all the others survival. If you happen to have some AI that will even approximate an ape I would be very interesting in knowing about it, and if you can simulate the interaction of 6 billion apes with that AI to see how the AI changes the survival characteristics of an individual I would be more than happy to see it in action (read I can be anywhere in the world to see it in ~12hours with suitcases of money to fund you)

iff (ape QED) iff (frog QED) iff (fly QED) iff (yeast QED).

Thats a nice reductionist line, however complexity (which is what this is really all about) cannot be reduced in such a fashion, if it could be then the AI problem would be simple and we'd have cracked it by now. As far as say simulating a micro-organism is concerned it is possible to simulate by either completely discounting interactions with the environment or modelling them simply (no yeast is going to be elected president of the USA and cause global-thermonuclear war).

Many species already rely on other species for survival. If you can give me all the current species functions without humans, I'll give you the you the the entwined function. :) I claim the difference is relatively trivial.

Co-evolution does happen and that evolution does take place at the genetic level, there is no higher function like consciousness that gets in the way. Of course around 99% of the earths biomass is single celled organisms, if you can tell me how they are all affected by human intervention I'd be interested to know, as there are so many types you could start with the micro-organisms that live by deep underwater vents in the oceans and move through to those that live in rocks kilometres (or miles) down in the earths crust for billions of years before humans even walked on the earth :)

Re:if only it were that simple

[Alsee]

Akk You sent 4.5 screenfulls even at 1024x768. I was attempting shorten the posts :)

My reducio-ad-absurdum of comparing yeast and humans - my point was that modeling yeast by "completely discounting interactions with the environment" is about as valid of a measure of yeast in the wild as modeling a human by "completely discounting interactions with the environment".

slaughter 5,000-6,000...I am certainly not aware of any other organism that can
In most species of primates an individual is easily capable of killing one millionth of it's population in an hour. If you want raw numbers of dead, an ant colony can do it. (Before you complain a colony isn't an individual, a human can only do it based on the efforts of others as well. You can't build a nuke alone.) Even if I were to grant the human effect is larger, it's not a new effect.

I'm saying *IF* you can deal with an effect present in non-humans, then you can deal with it in humans.

I think our dissagreement is that you think I'm trivializing the effect of human intellegence and interaction, where as I think you are trivializing the effect of non-human intellegence and interaction.

I see parallels for all of your human arguments in non-humans. Humans are a large part of my enviornment, but social interaction is a primary factor in survival/reproduction in many species. This is extremely hard to model. My claim isn't that humans are easy to model, but that *if* you can model primates minds then you can model human minds. "higher function like consciousness that gets in the way" If you learn american sign language I'll dig up a gorilla to debate the point with you :)

I'm lumping technology into enviornment. Farming/housing/clothing/cars/electricity/nuclear warheads were all present before I was born. Even new inventions are part of my enviornment. Anything other than me and my actions is my enviornment.

I am saying that the feedback is orders of magnitude more
I am saying the feedback is everything, and therefore equal.
approximate to a discontinuity
I see no break. Organisms that interact well with their enviornment leave more copies of their genes in later generations. The details of that interaction may vary in nature and complexity.

I am puzzled by your request for me to show you Ape AI. My position was that human AI would be a relatively small small problem if we had it.

I am puzzled by your request for me to tell you how humans affect earths biomass. My position was that it was a relativly small problem if we had the function for earth without humans.

&GT &GT rockstar/classical conscious choice
&GT Human thought is more sophisticated, but I don't see it as fundamentaly changing anything. Different enviornments lead to different behavior.
Your response to this seemed completely offpoint to me. Maybe I didn't quote enough of your text.
(compressed quote) conscious choice plays an even larger part. Take people who have a musical bent, some might choose classical orchestra, some may choose rockstar. rockstar has more chance of reproduction so genetics becomes much less important than conscious choice. I was trying to refute that by pointing out that any organism in a different enviornment will behave differently, human or not.

P.S. Saying a individuals mind evolves is poor choice of words in an evolution discussion. An individual cannot evolve, it develops.

Any insufficently advanced man is distingiushable from God.

Re:if only it were that simple

[xmedar]

Sorry for the long posts, I am just trying to make the points as well as I can.

My reducio-ad-absurdum of comparing yeast and humans - my point was that modeling yeast by "completely discounting interactions with the environment" is about as valid of a measure of yeast in the wild as modeling a human by "completely discounting interactions with the environment".

You seem to be saying that yeast has the same potential as humans to affect its environment and therefore the rest of its species accordingly and that the biological and chemical interactions of yeast are no different in scale or scope to what humans achieve with technology. This is where I would have to disagree with you, from my perspective human potential is exponentially increased with the ability to a) have conscious choice and b) create technology.

In most species of primates an individual is easily capable of killing one millionth of it's population in an hour. If you want raw numbers of dead, an ant colony can do it. (Before you complain a colony isn't an individual, a human can only do it based on the efforts of others as well. You can't build a nuke alone.) Even if I were to grant the human effect is larger, it's not a new effect

If there were 6 billion apes would one individual be able to kill one millionth of that number? No, I think not, infact our ability to change out environment and thus the survival chances of one another are determined by technology and by our conscious choices, no other organism on the planet can do that. As for the ant colony, the colony is working for a common goal, the difference with humans is that an individual can subvert the work of all others to bring about an outcome that completely different to what the rest of the species was working towards, that is done through leveraging technology,something the ants cannot do.

I'm saying *IF* you can deal with an effect present in non-humans, then you can deal with it in humans.

Again you seem to be discounting the emergent phenomena that come from human cosnsciousness and technology. If you want to take the line down from yeast we could go down to a virus, or a protein, or an atom, or an electrons quantum waveform. This is again the same reductionist line that has failed time and time again do deal with emergent phenomena.

I think our dissagreement is that you think I'm trivializing the effect of human intellegence and interaction, where as I think you are trivializing the effect of non-human intellegence and interaction.

I'm not trivialising, I am saying that there is a large difference in what is possible due to human intelligence and interaction, one that is so large that it becomes the driving factor in determining survival vs. genetic traits. If you look at the number of geneticdefects that would be fatalin the wild and are not now due to human intervention you can see this, or look at the effect of estrogenic compounds in water that is now contributing to infertility.

If you learn american sign language I'll dig up a gorilla to debate the point with you :)

Please and while you're at it if you could get Noam Chimpsky to explain the themes of The Matrix with regard to late 20th century Western society :)

I am saying the feedback is everything, and therefore equal.

Therefore yeast can have an equal effect to humans in terms the effect on the planet earth?

Organisms that interact well with their enviornment leave more copies of their genes in later generations. The details of that interaction may vary in nature and complexity.

And how do we define "well"? If we have 6 billion humans on the planet that would assume we are interacting well and therefore "fit", unfortuantely if we degrade the environment through pollution / thermonuclear war etc and thus kill ourselves off in the end, we are then not fit, without knowing the future course of humanity it is not possible to determine whether we are fit as we don't know the outcome.

I am puzzled by your request for me to show you Ape AI. My position was that human AI would be a relatively small small problem if we had it.

Would it? Perhaps you'd like to take the current work on nematode brains and scale up (a small problem) to an ape brain and the on to a human and we can see if the jump is really that small.

I am puzzled by your request for me to tell you how humans affect earths biomass. My position was that it was a relativly small problem if we had the function for earth without humans.

No, I maade the point that most of life is single celled, and you said you'd show how human interaction affects any lifeform I asked, so I asked if you could provide the entwining function with regard to a) single celledorganisms living in superheated deep ocean vents and b) those living kilometres down in the earths crust, if you still want toanswer I'd be interested to hear some answers.

I was trying to refute that by pointing out that any organism in a different enviornment will behave differently, human or not.

My point is that I can choose my environment, asopposed to having to put up with whatever environment I am presented with, and yes animals and birds migrate, and that is not conscious choice of environment.

P.S. Saying a individuals mind evolves is poor choice of words in an evolution discussion. An individual cannot evolve, it develops.

That would depend is you define evolution as only genetic evolution, from Merriam Webster -
Main Entry: evolution
Pronunciation: "e-v&-'lü-sh&n, "E-v&-
Function: noun
Etymology: Latin evolution-, evolutio unrolling, from evolvere
Date: 1622
1 : one of a set of prescribed movements
2 a : a process of change in a certain direction : UNFOLDING b : the action or an instance of forming and giving something off : EMISSION c (1) : a process of continuous change from a lower, simpler, or worse to a higher, more complex, or better state : GROWTH (2) : a process of gradual and relatively peaceful social, political, and economic advance d : something evolved
3 : the process of working out or developing
4 a : the historical development of a biological group (as a race or species) : PHYLOGENY b : a theory that the various types of animals and plants have their origin in other preexisting types and that the distinguishable differences are due to modifications in successive generations
5 : the extraction of a mathematical root
6 : a process in which the whole universe is a progression of interrelated phenomena

Re:if only it were that simple

[Alsee]

you said you'd show how human interaction affects any lifeform I asked
You must have missread my post. I went back and got it exactly:
&GT If you can give me all the current species functions without humans, I'll give you the you the the entwined function. :) I claim the difference is relatively trivial. (Emphasis added) My point was that the first problem is infinitely large(as specified in last paragraph below), and would imply the ability to solve the second problem.

&gt I'll dig up a gorilla to debate the point with you :)
Please
Okey, here. I dug up the gorilla, but it's up to you to learn sign language and arrange an interview :)

That would depend is you define evolution as only genetic evolution
I think we are discussing 4b:
a theory that the various types of animals and plants have their origin in other preexisting types and that the distinguishable differences are due to modifications in successive generations
Other meanings are valid, but I think mixing them will only will increase confusion.

On that note, we might make progress if we try to define what we are talking about. I think (feel free to dissagree) it started with my statement "The rules of evolution apply until we start choosing our own DNA." But what rules are we talking about? I'll take a stab at it and you point out where you dissagree or what rule doesn't apply to humans? It should clarify my position and assumptions.

1) Individual starts with fertilization (or division) and consists of that cell and anything it consumes and integrates.
2) Enviornment is everything outside the individual.
3) Genes/nature determines potential and inclinations, and is present in the individual from the start.
4) Experience/nurture is any interaction between individual and envionment beyond the control of the individual. It determines possibilities and influences.
5) Behavior is any interaction between individual and envionment controled/initiated by the individual.
6) Behavior is determined by Nature+Nurture a.k.a. Genes+Experience.
7) Behavior and experience are a tightly bound feedback loop.
8) The sole criteria in evolution is weather or not the indiviual's genes perpetuate into the future.
9) Fitness is equated (cause/effect ambigous) with interactions resulting in the individual's genes sucessfully propagating into the future.

As far as a "fitness function", it would necessarily be composed of 2 parts - the individual and the enviornment. By definitions above the second part is larger and makes it pretty much insoluable in nature, except in the past tense.

sure you can improve it....

[Zurk]

if you know what the final correct output should be. what about systems where there are multiple correct and almost-correct values ? i.e. the real world. The real problem is solving problems which dont have one true solution. i.e. recognising an object in a random, slightly blurred photograph from a moving vehicle.

Re:sure you can improve it....

[SEWilco]

The real problem is solving problems which don't have one true solution, i.e. recognising an object in a random, slightly blurred photograph from a moving vehicle.

In this case, those are two problems: creating the routine which judges the correctness, and making the mutation routine create mutations so that both routines can handle multiple answers. Processing images has an increase in the complexity of the processing, but with the proper image-processing routines the mutable code won't necessarily be all that complex. But if you want to use mutation to create the image-processing routines, go ahead...but start by having code which first tries to identify the difference between a fly and a butterfly and becomes more complex after that, don't plan on feeding it CNN right away.

In the example given, when I think I recognize an object in that situation I remember the appearance of the object and when I later see a similar object I judge how well I identified it the first time. The delay might range from fractions of a second (that looked like a street sign -- wriggle my head and look through a different part of the wet windshield) to days (when I'm not moving on a sunny day and see another copy of the blurry billboard seen earlier).

It's the fitness function, stupid...

[Anonymous Coward]

The biggest problem with any genetic system is testing fitness. It has always been that way, and always will. The genetic system can only be as good (regardless of computing power) as the fitness function. Find a way to improve THAT automatically, then you will have true machine intelligence with infinite potential.

Re:It's the fitness function, stupid...

[Boronx]

What would a fitness function for a fitness function look like?

Re:It's the fitness function, stupid...

[greenrd]

This is a problem with rational choice as well (although it's much less severe). Your business needs 10,000 FooBarWidgets. Mission-critical purchase. You could buy some from Wilkos, but how do you know they are good enough for what you need them for? They're popular, right? Well that's no guarantee, lots of people eat at McDonalds. You could employ someone to do some research, but how do you know that they will do their job properly? Ask for two references and ask them. But how do you know they're telling the truth? Or give your potential employees aptitude tests. But how do you know that the aptitude tests are not just a load of bunk? Etc. etc.

Of course some of these problems are largely theoretical, but some of them are very real.

Infinite regression of information gathering. How do you know your information gatherers are doing their job correctly, and how do you know how important the information you're going to gather is going to be before you've gathered it? Not always easy to answer.

Re:It's the fitness function, stupid...

[vulg4r_m0nk]

Find a way to improve [the fitness function] automatically, then you will have true machine intelligence with infinite potential.

Why should we expect "true" intelligence to manifest in a form of evolution that differs fundamentally from the evolutionary processes that produced the human brain? We did not evolve according to an improving fitness function, but rather through a messy series of brutal conflicts with other organisms and the forces of nature, those organisms most able to contribute genetic material to future generations being the most fit. Fitness does not exist in a vacuum (as the genetic programming task seems to imply), but as a relation between an organism and its environment. In fact, if genetic programming is to bear any resemblance to biological evolution, we shouldn't expect an orgaism that is "best" according to some absolute measure ultimately to appear, but rather a program that produces the most viable offspring within that environment.

The fact that humans are so frequently irrational is explained well by a theory of evolution that operates according to a contextualized measure of fitness rather than a constantly improving fitness function independent of a changing environment. Perhaps such a function would yield extremely powerful AI, but I think it would be a much different form of intelligence from that of human beings.

Re:It's the fitness function, stupid...

[manyoso]

"We did not evolve according to an improving fitness function, but rather through a messy series of brutal conflicts with other organisms and the forces of nature, those organisms most able to contribute genetic material to future generations being the most fit."

Excuse me, and how do you know this? And how does having offspring make an individual organism fit? This is a common tautology with naive ideas of evolution. An organism that has many offspring might very well be fit, but having offspring does not _make_ an organism fit. The problem with fitness functions is a mathematical one and appealing to naive philosophical views of our common evolution does not render it any less of a problem.

Re:It's the fitness function, stupid...

[NoOneInParticular]

The fitness function is important, but not sufficient. What Roland is trying to do
is evolve the representation/variation component of the GA. This is probably even more important than 'merely' the fitness function.

An example: suppose you are optimizing a shower to output 1 cubic meter of water per appropriate time unit. You also want the water to be 37 degrees Celsius. Now make two representations to optimize this problem. The first is the usual with a hot and a cold water tap. More hot water gives you more water and a higher temperature. The other is a temperature tap and a capacity tap. With trivial mutation operators, with which of the two representations is a GA more likely to get the result quickest?

This is where the evolving variation operators comes in: they try to change the variation in such a way that it aligns with the fitness function. Whether this is possible or not is another issue.

With an inappropriate representation/variation combination, you can twiddle the fitness function as much as you like, but you will not get better results than random search. See also the comment on Core Wars above.

Re:It's the fitness function, stupid...

[Cassandra]

The natural universe is, in its very nature, a fitness function. For living creatures, survival is determined by the fitness function of the universe.

Ehm, you could specify an abstract fitness function in this way, but try implementing it :-) There are other living creatures also existing in the world, so your fitness function would have to have all aspects of the world (i.e. locations and mental states of all creatures, and even the location of each grain of sand) as input. This is not a reasonable approach, which I believe is what vulg4r_m0nk meant when saying that fitness functions don't apply.

Re:It's the fitness function, stupid...

[maxpublic]

In biological evolution the only actual measure of fitness is whether or not you manage to pass your genes on to the next generation. Fail to do so and by definition you aren't fit - your genes are lost and out of the evolutionary race. The actual subjective quality of the organism (by whatever mechanism you use to measure such a nebulous thing) is irrelevant.

Obviously this isn't what you want in a computer program. But a computer program has purpose as defined by its maker (even through something like a fitness function) whereas evolutionary biology has no purpose at all. It simply happens; there is no guiding hand or principle.

Survival of the offspring is the only measure of 'success' in real-world evolution. Fitness functions in computer programming have nothing to do with biological evolution at all; there is no counterpart you can point to.

Max

Re:It's the fitness function, stupid...

[__soup_dragon__]

yeah, i agree: this ga stuff is really cool but when you want to solve high level problems it gets really complicated (fitness function wise). so i dont expect to see a computer generated kernel anytime soon. but there are two problems where it looks like they could help: process schedulers and packet routing. those are NP complete problems,
arent they? and wouldn't it be cool to dynamically generate the schedulling algorithms in the kernel? you could let the user define a criteria and then let the computer evolve the algorithms. same would apply to routing. i havent STW on it, is this feasible? is anyone working on this?

Similar to

[SevenTowers]

a project that took place back in 1996 I think. Programmers wrote a physical environment in which a set of parameters were included (gravity, friction, etc) along with a basic mechanical crawling robot composed of several joints and "muscles". It was left to "evolve" on a machine and actually improved itself to the point of being able to move at something like 5-6mm per second.

Re:Similar to

[BLAMM!]

It's similar only in the respect of using a GA. They difference here and the point is supposed to make *this* GA unique is that it isn't making fitness checks on an external object. It's checking itself for fitness, supposedly to increase its own abilities. The apparent goal being to end up with a "super" GA.

Re:Similar to

[Dyolf Knip]

I've always been impressed by things like Tierra. You write an environment where self-replicating programs have to compete with each other for space and runtime. Factor in the occasional mutation and the ancestral program (70 or 80 commands) evolves, after several million generations, into a whole panolpy of organisms. There were simple ones that could replicate using only 30 commands, then there were parasites on those that could do it in 20, ones that could only replicate in the presence of a similar program, parasites on the parasites, all sorts of things.

Great..

[VFVTHUNTER]

Someone took a GP algorithm and superimposed it on the architecture of an RS Flip-Flop. On the plus side, with all of /.'s traffic, they probably won't have a hard time finding someone to fill that open position at the bottom of the page.

A framework for self-improving systems

[Black Acid]

ResearchIndex lists Theo: A framework for self-improving systems. Although The NECI Scientific Literature Digital Library: ResearchIndex itself does not carry the document, it lists several related ones. Heavy stuff. An excerpt from ResearchIndex summarizes Theo quite well:

For instance, the THEO system (Mitchell et al. 1989) uses a single knowledge base and a single set of axioms.

I'd suggest anyone seriously interested in self-improving systems check out Mitchell, T. M., J. Allen, P. Chalasani, J. Cheng, O. Etzioni, M. Ringuette, and J. C. Schlimmer's 1989 book, Theo: A Framework for Self-Improving Systems: National Science Foundation, published by DEC.

Genetic Programming

[nyjx]

... has been around since the mid 80's and although it works for toy problems it's very hard to get systems of a significant scale out of it. You're basically swapping sub branches of your program around to see what works - tranversing the space of all possible programs - it takes *a lot* of random attempts to do better than a human doing it analytically. Most AI researchers believe that you need at least a little bit of knowledge to guide your program's adaptation rather than blind mutation.

The Father of GP (John Koza) may disagree with me - he runs genetic-programming.org and more or less invented the field. He's also known for his vigorous defences of GP: anybody know of real applications?

A somewhat more complete description of GP can be found at Genetic-programming.com.

Re:Genetic Programming

[VB]

"...it takes *a lot* of random attempts to do better than a human doing it analytically."

Which is why efforts at AI programming will continue to require human interaction for the foreseeable future. MIT has been at it over 40 years. Experience indicates that our programming interfaces haven't nearly evolved to the state of efficiency that we can interact with the machines in a natural enough way to make any significant progress. Many good programmers can't type. Some interface producers are giving us pseudo-intellegent controls that "learn" our preferences and traits (ex.: things that don't show up on menus if you haven't used them in 4 weeks, unless you expressly expand the list). The interfaces appear to be dummying down the human intelligence, which strikes me as antithetical to the task. Machine code is time-consuming. C/C++ also, but less so.

The interface needed has to be more LISP in nature, and a Voice interface is probably going to be needed before enough programming effort can be applied.

I'd certainly love to see the voice interaction tools start to evolve to a point of usefulness.

Re:Genetic Programming

[awaterl]

What does the word 'convexity' mean when applied to a search space?

Re:Genetic Programming

[Some Dumbass...]

Which is why efforts at AI programming will continue to require human interaction for the foreseeable future.

No kidding. And in related news, educating humans will require human intervention in the forseeable future.

Obvious, eh? Almost as obvious as the idea that the random mutations used in genetic programming are about as efficient as real random mutations. They get the job done eventually, but require a lot of screw-ups to make one improvement.

Re:Genetic Programming

[call -151]

There are some "real applications" where genetic algorithms are used to solve some difficult questions in abstract mathematics.

There are a number of difficult questions in the field of research in combinatorial group theory for which no reasonable-time (non-exponential or worse) algorithms are known. Genetic algorithms have proven to be surprisingly effective for some questions in this area; I am part of an open-source project (the Magnus project, an endeavor of the New York Group Theory Cooperative) which has implemented a number of genetic algorithms in our software for computations in combinatorial group theory. See this page for a descripition of some of the genetic algorithms implemented in our software. In particular, some difficult theoretical questions that had been studied for more than 20 years turned out to be answered quickly (less than 30 seconds on a 300 Mhz PII) via a genetic algorithm approach. (The most remarkable of them was the dismissal of a potential counterexample to the Andrews-Curtis conjecture which had been very resistant to theoretical and traditional computational approaches.)

I know of other successes of genetic algorithms in research mathematics in areas like control theory and modelling, but I am most familiar with algebraic applications. In the situations described above, there are good measures of `fitness' and a good notion of two reasonably-fit individuals combining and possibly mutating to make even-more-fit offspring. It is much more difficult to apply the techniques where there is not a good measure of fitness or of combination.

Re:Genetic Programming

[call -151]

`Convexity' of a search space which can be described in terms of a vector of real numbers means that given any valid search parameters A and B, all possible convex combinations (combinations which are of the form tA + (1-t)B for some real number t between 0 and 1) are valid search parameters as well. If the search space lies in some Euclidean n-dimensional space, "convex" means the same thing as the usual convexity of a subset of n-dimensional space. (That is, a subset X of R^n is convex if given any two points A and B in X, every point on the segment joining A to B also lies in X.)

When you are searching a convex search space, it makes sense to try things "in between" A and B- if your space is not convex, it is more difficult to come up with new valid guesses which are somehow related to A and B.

Re:Genetic Programming

[ZaneMcAuley]

And whats that in English? :)

Re:Genetic Programming

[Cassandra]

You're basically swapping sub branches of your program around to see what works - tranversing the space of all possible programs - it takes *a lot* of random attempts

This is quite a good summary of GP, and it also describes why IMHO GP should be the last thing to try. i.e. use it when everything else has failed...

I think reinforcement learning (RL) methods are much more promising in general, and should be tried before GP whenever they are applicable.

In GP you set up a fitness function that evaluates the performance of the entire program, while in RL the reward function rewards individual actions i.e. small parts of the program. The big problem in both cases is the design of the fitness/reward function. In GP you want it to increase fitness as your agents grow better and better (yes this is difficult, I tried it once in the RoboCup simulation league). In RL you can give rewards very easily by basically saying good/bad to the program after it has performed an action. The problem in RL is that the program has to find out which of the recent actions caused the reward. There is a large number of algorithms for distributing rewards among recent actions. However, they all do better than GP, since GP is equivalent to the extreme case of just one reward after the program has finished running.

Re:Genetic Programming

[CyberDruid]

A lot of people seems to be overlooking that this is not "just" GP. It is GP with a feedback loop unto itself. Now, the difficult thing with this is: How do you make a fitness-function that measures how good your program is at improving itself? This is a damn hard problem, which the page does not even try to explain. But since the notion of "Seed-AI", as Eliezer would call it, is so tantalizing, there are more and more people trying to accomplish it.

I have done some work on how to solve it, on the swedish University of Chalmers. An overview of how we think it can be solved, using some concepts from information theory (together with a small introduction to strong AI in general), can be found here.

Please mail me if you have any thoughts/comments regarding the text in the previous link.

Re:Genetic Programming

[Foresto]

If I remember correctly, PostgreSQL has a genetic query optimizer that kicks in when you run queries that are sufficiently complex. Does that count as a real application?

Re:Genetic Programming

[awaterl]

Thank you for the explanation.

How do you define improvement?

[Fuzion]

The problem with self-improving programs using Genetic Programming, is that the problem inherent in the process of evolution are present in the programs. When species evolve, it's not always for the better, there have been cases where evolution has made things worser than before.

This might not be noticable for relatively simply programs, but on a very complex program, how do you tell if a certain modification introduced by the system, is actually an improvement? What if the modifications makes the program slightly faster, but introduces long-term problems?

I think this is one of the biggest problems (other than the programs becoming sentient, and taking over the world ;-)) with self-improving programs.

Re:How do you define improvement?

[marauder]

how do you tell if a certain modification introduced by the system, is actually an improvement?

GAs are graded using a fitness function, which represents your concept of how well an instance meets whatever purpose you had in mind. Defining the fitness function is hard work for complex problems, but once you have it you can tell straight off which modifications are improvements and which are not.

The problem is not being unable to test fitness during self-improvement, but being unable to define the test before you start. To take the extreme case, how do you determine a particular human's fitness? What is the end-goal of human evolution anyway?

What if the modifications makes the program slightly faster

Using program execution speed as a fitness function doesn't seem to represent any particular problem you'd like to solve. In general I can't imagine it being used as one.

Re:How do you define improvement?

[Alsee]

Using program execution speed as a fitness function doesn't seem to represent any particular problem you'd like to solve. In general I can't imagine it being used as one.

Almost any sufficently rich evolving program is going to have the potential to run for hours, or fail to terminate at all. At a minimum you need to kill any individual that doesn't terminate within a certain time frame. In addition programs that run faster can be evolved faster. For many problems speed and size are pretty much irrelevant, but going for efficency is always a nice plus as long as you do get a result.

Hmm, now that I think about it, optimizing for speed could be a primary goal if you're looking for faster code for an inner loop for a graphics engine or something.

Re:How do you define improvement?

[maxpublic]

Not being a conscious or directed process, evolution has no end goal. That's a fallacy in the thinking of those who don't actually understand biological evolution.

Max

Re:How do you define improvement?

[marauder]

Not being a conscious or directed process

What makes you say this? You're inside the system; you can't possibly tell what's going on outside it. In any case, until you define your terms better I'd say that "unconscious" and "undirected" apply to the operation of a GA.

Re:How do you define improvement?

[maxpublic]

I can say that because it's part and parcel of the definition of evolution. You should've learned this in Bio 101. It matters not a whit where I am in the system because human beings defined the process; it wasn't defined for us by some cosmic power.

Evolution is simply the observed phenomena of organisms changing over time due to mutation and inbreeding, usually adapting to environmental conditions (because those mutations that don't adapt die out, not because there's any 'invisible hand' at work directing the adaption).

There's no argument to be had here. This is simply the definiton of evolution. Anything else isn't evolution as any biologist or geneticist would understand it. If you're having trouble with the concept or never covered evolution in a biology class there are plenty of good, scientific books which can explain it to you in detail.

Max

Fitness Functions

[Niban]

I'm rather fond of how the 'fitness function' is a simple labelled box. Truth of the matter is, this is where all the important (read HARD) stuff happens, and its waved off in the 'a miracle occurs' manner. Cute.

The fitness function amounts to taking your new baby Genertic Algorithm and throwing it into the wildernes filled with GA-eating beasties. Those that manage to survive for more than X amount of time are now determined to be 'fit'.

The catch of course, is that 'fit' for you, and 'fit' for the GA, don't always equate nicely. If a GA decides that it can surive best by eating the rest of your test subjects, well....

If you go look at the page and even begin to think that its a marvelously kean concept, note that people have been failing to get this to work on a large scale for thee past 20 years. Go google on 'genetic algorithms','autonomous agents','self-evolving networks', or just look up exactly how sucessful people are at winning the Loebner prize.

Hmmm, I Wonder...

[Myriad]

... if the author, or some of the people who have posted so far, have any first hand experience of "Automatic Design of Algorithms Through Evolution" (ADATE)?

If not, might I suggest getting out more?? :)

Re:Hmmm, I Wonder...

[NoOneInParticular]

Uhm, have I been trolled, but the author *is* the one from adate? Check the same site as the note

So I guess the answer is yes.

Re:Hmmm, I Wonder...

[Brummund]

Heh, I had Roland as a lecturer, and he's a great guy.

(I remember he came into class one day and uttered "Yesterday, I made an OS that..." :)

Flaw in Logic

[gururise]

Basically looks as if they are using a Genetic Algorithm to evolve better crossover and mutation algorithims based upon fitness of the individuals produced by the first Genetic Algorithm.

A Simple Genetic Algorithm:
1) Randomly create population of individuals and their genome.
2) Calculate fitness of each individual
3) Probabilistically select individuals for mating, based upon their fitness scores.
4) During Mating, use crossover (usually 70% chance) and mutation (usually .1 - .01% chance) on the chromosome(genome) to create a new offspring population.
5) If done, then finish, otherwise goto step 2 with the new population.

Using the Genetic Algorithm to evolve new crossover operators seems feasible; however, evolving the mutation operator to produce individuals of higher fitness is flawed logic. Mutation's purpose is to prevent genetic code from becoming "lost" (ie sometimes when you lose genetic information from crossover, you can never get it back w/o random mutations). By evolving the mutation operator to produce individuals of higher fitness, I suspect you will run into the Local Optima problem, where you've reached a local optimum fitness, but you are nowhere the global optimum fitness for the population.

Mutation is very important in preventing the local optimum problem, changing the way mutation works will probably have a detrimental effect on the performance.

Gururuse
ERA Champion Realty, Inc.

Re:Already been done!

[VB]

That's just too strange to be an American joke...

Still pretty damn, funny tho'.

Real world examples of application of GP

[ZaneMcAuley]

Does anybody have references to Real World examples of GP being applied and the results, also in real world languages rather than academic languages, ie., C#, C++, Java as opposed to SML, Lisp, Prolog etc?

Re:Real world examples of application of GP

[ZaneMcAuley]

As a software engineer, where could I apply these concepts within the real world of software design and testing of our own code?

Test harness scenario: Using self improving algorithms to get code coverage for hitting all possible error paths and positive code paths?

It is nice having all this in theory, but where can I use them today?

Re:Real world examples of application of GP

[NoOneInParticular]

Pfa, genetically programmed C++ code is for women. Real men use machine code GP.

In any case, GP works with parse trees, outputting the results in any language is then trivial.

Re:Real world examples of application of GP

[ZaneMcAuley]

Maybe so but I want to code at the high level (concentrating on the algorithms) and not have to worry about memory management etc which is where most of the source for bugs in software are.

Re:Real world examples of application of GP

[NoOneInParticular]

Well, the entire idea of GP is that you even stop focussing on the algorithms: the focus is on what has to be done.

One of Koza's favourite quotes is from Samuel (the one from the early checkers program 1956 or 65, I forgot):

Automatic programming: programming a computer by telling it what to do, not how to do it.

Re:Real world examples of application of GP

[ZaneMcAuley]

Yeah telling it what to do and now how to do it. Sure, but in machine code? Surely its easier to tell it what to do in a higher level language.

This is news??

[po8]

As a practicing AI researcher, I'm as puzzled as some of the other posters about what the news is here. Any decent introductory textbook on AI written in the last few years (I'm currently teaching from the new Nilsson text) has a chapter on GAs and GP. They have much promise, but other standard AI techniques work much better on almost all practical problems.

Let's try to keep the "news", and not just the "for nerds," folks...

GP is useful - in a limited way

[ehack]

GP is useful, as all of Artificial Evolution methods, in the context of optimisatiion, eg, scheduling, place and route, filter design, neural net training.

Unfortunately, GP and GA do not scale up too well, modularity is not being achieved. There is no easy way to define fitness for subroutines (ADFs in KozaSpeak). I believe this is the main reason why the field is stagnating.

Distributed Processing for GA's?

[Hercynium]

I've experimented with some of this myself during my free time. It was nothing incredibly complex, however I used the basic concepts of protein synthesis and enzyme function to operate on a 'DNA' code base that was dynamically mutated and generated.

While the 'enzymes' and 'proteins' were fixed during my experiments, they certainly could be mutated and evolved in more advanced versions of my programs.

An interesting side effect was that as a strain of 'DNA' evolved it became longer and longer. Upon tracing advanced mutations I found large sections of the genes to go completely unused.

Anyhow, what I menat to get to was that a model like this could certainly be distributed much like Bovine or SETI. A central server distributes 'DNA' to the client machines as well as a series of environmental test suites to measure their development. The client machines would iterate the DNA code through the test environment and mutate (or even breed) successors to the original DNA so as to discover a more efficient GA. The result set as well as the DNA fragments would then be transmitted back to the Server for analysis, processing and ultimately re-distribution.

An additional benefit of this approach would be that if a single genome is sucessful on a large number of systems it would be relatively easy to identify.

While my inital experiments were written in C, I eventually migrated to C++ (which actually made it much more complex.) However for a distributed client, the use of java would likely be the most efficient, espesially for the distribution of the testing environments.

Re:Distributed Processing for GA's?

[Alsee]

java would likely be the most efficient

OUCH. Java has it's good points, but the most efficient language it is not. :)

Aside from that, yes. GA is an ideal candidate for parallel or distributed processing. I'm not familiar with any SETI style projects, but it has been run on a Connection Machine with 65,536 processors (drool).

Re:Distributed Processing for GA's?

[peul]

I just finished writing a system for distributing the fitness evaluation of a genetic programming system using the idle time (PM-DGP). The biggest bottleneck is the bandwidth required to send the programs to the clients, for the engineering problems we use it for, this is not a problem. They all have a sufficiently high evaluation time/program size ratio.

Distributing the breeding process (using the deme or island approach) requires computers of comparable and constand speed. It is difficult (I didn't succeed) to find a way to effectively use idle time while evolving and evaluating local populations occasionally exchanging genetic material. When slower machines fall behind they are no longer able to effectively contibute to the effort.

Reflection

[ZaneMcAuley]

Is it possible to code self modifying code in C# using Reflection?

C# is at a very high level and thus can focus more on algorithms rather than the nitty gritty of memory management (like Java).

Re:Reflection

[ZaneMcAuley]

erm wots funny? Reflection is a class discovery mechanism. This way you could create a class at runtime then invoke the methods by using reflection and thus have self modifying code.

Re:Reflection

[julesh]

Well, firstly I have to say the idea of self improving code using a standard applications programming language is well off in the future: current methods tend to function around arrangement of structures to pass signals between them (sort of like automatically designing a signal processing chip) and these structures are usually hand coded.

Secondly, what weird ideas have you got about java programs getting involved in memory management? As far as I can tell C# and Java are pretty much identical in this (and most other) respects. They both take care of everything for you.

Re:What's an RS Flip-Flop

[VFVTHUNTER]

EE may not be your cake, but at least you knew it was EE. Broadly speaking, there are two kinds of digital logic: combinatorial and sequential. Sequential digital logic is basically combinatorial digital logic with some feedback wires. An RS flip-flop is a couple of digital logic gates with the outputs fed back as inputs. This means that the output of the RSFF depends not only on its current inputs, but its current outputs (i.e., its current state) as well. So, in its most basic sense, an RS flipflop is (maybe) the simplest implementation of a finite state machine. The GP page this post links to uses feedback in much the same manner - the synthesized mutation code and crossover code are fed back into the GP systems. Given that many systems considered for analysis are inherently non-linear, this is probably a good idea - are brains would not be the wonders that they are without feedback.

The old "a miracle appears here" function!

[Spinality]

So many of these formalisms seem to rely on pushing all the hard stuff into a magic black box: "A miracle appears here." Of course, one shouldn't trivialize the state of research; we usually only make progress in little steps. Then later on, we look back and say "Oh! This little step was actually a big one."

GA Archive

[metlin]

Check out the GA Archive. Great collection of the more famous GA's and proceedings.

For those wishing to get an intro to GA, try The Hitchhiker's Guide to Evolutionary Computation.

Re:GA Archive

[ZaneMcAuley]

Strange URL, ftp://ftp.cerias.purdue.edu/pub/doc/EC/Welcome.htm l

Browsing over FTP?

Re:GA Archive

[metlin]

That's a pretty famous archive, the Hitchhikers guide to GA's. There were other mirrors too, but I just have this one that works :^)

Re:GA Archive

[ZaneMcAuley]

Yeah, i got it to work but felt strange browsing over FTP ;D

GP

[otherwhere]

Maybe Steven Spielberg's AI film is closer to reality than the general public knows *smile*?"

The General public didn't see AI; they heard it sucked. They heard it from me.

Re:Already been done!

[ZaneMcAuley]

Warning: PostgresSQL query failed: ERROR: id_in: 3ba7 eadc-03cdf340 not in id format in /home/segfault/htdocs/story.phtml on line 30
Story Error
The selected story does not appear to exist.

Oops

My own experiments with evolved code

[melquiades]

In college, I did a project in which I attempted to evolve programs for Core Wars, in which two programs running in a virtual machine language basically attempt to overwrite each other's memory space.

My algorithm started with random programs and pitted them against each other in the Core Wars arena. The fitness function was simple: programs that beat other programs got higher ratings. Top-rated programs would "breed", and all programs would mutate. The hope was that after time, successful warriors would evolve.

And, lo and behold, they did! My algorithm "evolved" some simple bombers -- not nearly as good as what a human would write, but amazing considering I put no knowledge about strategy into the algorithm, and started with random core wars code.

Ah, but (there's always a but) I found that there was no significant correlation between how successful a warrior was and how many generations of crossover went into it. In other words, the genetic algorithm did no better than an algorithm which simply selected lots of random programs and kept the ones that work. So actually, my result was not very impressive at all -- I was basically doing a brute force random search for programs, and happened to find a few.

Others might get much better results with different languages, because Core Wars machine code does not lend itself to crossover (i.e. it's had to merge two Core Wars programs into a better program). Functional languages do a bit better with this. But I really doubt that Genetic Algorithms will prove useful in the near future for generating any sort of code that wouldn't be trivially easy for a human to write.

Re:My own experiments with evolved code

[Animats]

In other words, the genetic algorithm did no better than an algorithm which simply selected lots of random programs and kept the ones that work.

That's not unusual. Any broad-front search (which includes genetic algorithms, simulated annealing, and neural nets) should be tested in this way. Both ends of the search spectrum - pure hill-climbing using a greedy algorithm, and random search, should be tried. Unless a more elaborate algorithm beats both of them, it's not accomplishing anything.

This is an embarassing truth which GA researchers hate to hear. But GA people need to do this validation or they waste time on problems for which GAs are unsuitable.

Re:My own experiments with evolved code

[kubalaa]

Didn't you basically prove that your crossover implementation didn't preserve any high-level characteristics of the parent programs? And doesn't this illustrate a flaw in your implementation, saying nothing about GA in general? You kind of hinted at this, but I thought it should be stated outright.

I wonder what kind of success one would have placing the breeding algorithm into the organism itself and allowing that to evolve as well...

Re:My own experiments with evolved code

[Rogerborg]

• This is an embarassing truth which GA researchers hate to hear. But GA people need to do this validation or they waste time on problems for which GAs are unsuitable

Amen to that. Back when I was in research, I had endless hours of fun baiting GA reasearchers on just this issue. For all the applications that I tried GA's for (most notably scheduling issues), using a good fitness evaluation function plus a random generator produced usable (but not optimal) results in much shorter times than a breeding program.

I agree that to arrive at a optimal or unique solution in a large search space, GA's have a use, but for most human purposes, just roll the dice and see what you get.

Notice the silence

[ZaneMcAuley]

I cant but help notice the lack of trolls, flames etc in this topic as I guess most idiots are out on this Saturday night getting piss blind drunk :)
And as for the rest of us nerds, we are sitting in here reading slashdot (news for nerds) :D

Re:Notice the silence

[phoey]

true dat

Re:Already been done!

[Marx_Mrvelous]

http://www.segfault.org/story.phtml?id=3ba7eadc-03 cdf340 Hmmm, take out the spoace and it works fine! Pretty funny article... No surprise that Perl was involved!

Why genetic algorithms are powerful

[Alsee]

A common misconception is that genetic algorithms are based on mutations. For example someone here said:
random mutations used in genetic programming are about as efficient as real random mutations. They get the job done eventually, but require a lot of screw-ups to make one improvement.

Mutations are a red herring. Genetic algorithms produce results faster without mutations. The benefit of mutations is that they allow the search to go farther - potentially indefinitely - and produce better results.

The power of genetic algorithms comes from impicit parallelism. This can increase the search rate by a factor of over a billion. There is a complicated mathematical anaylsis, but here is a description:

one of a genetic algorithm's most important qualities is its ability to evaluate many possible solutions simultaneously. This ability, called implicit parallelism, is the cornerstone of the genetic algorithm's power. Implicit parallelism results from simultaneous evaluation of the numerous building blocks that comprise the string. Each string may contain millions of these building blocks, and the genetic algorithm assesses them all simultaneously each time it calculates the string's fitness. In effect, the algorithm selects for patterns inside the string that exhibit high worth and passes these building blocks on to the next generation.

Re:Why genetic algorithms are powerful

[Alsee]

Most sorts based on divide-and-conquer are O (n log n), while most based on nested loops are O (n^2)). This isn't a matter of replacing a building block, but rather the whole algorithm!

This issue is well known and studied in the field. A genetic algorithm randomly searches for a solution. If it happens to focus on a nested loop method it will probably converge to an extremely efficent form of O(n^2). This is known as a local optimum. Depending upon how the genetic algorithm is set up it may or may not be able to discover an O(n log n) solution given time. For one thing, a larger population size helps.

The most common solution is to run the genetic algorithm from scratch a few times so that different random strategies get tested. Another technique is to co-evolve "parasites". First the sort programs converge on a solution and they all start to look alike. Then the parasites home in on the sorting programs. The sort programs start to diversify to escape the parasites. The "fleeing" sort programs explore for different algorithms to use.

Voice Control

[motu_]

Regardless of the intelligence of any computer in the future, I wouldn't consider voice interaction a useful feature. As for me, I can type much faster than I speak, and talking eight hours straight to my computer would not decrease my work-load in any way.
I think this voice control thingy stems from this old, rather male, dream in which one commands his secretary to do all kind of nasty things. I mean, who really needs two free hands? :)

Re:Voice Control

[VB]

"...I think this voice control thingy stems from this old, rather male, dream..."

Perhaps voice control does derive from that. As I mentioned in my post, not everyone can type more quickly (and, accurately) than they can speak. Some people speak very quickly. Very few people quickly key in accurate data. Surely, isn't new to you.

Typing is not a problem for me. But, when you find yourself yanking the keyboard from people so you can type in the commands you're trying to get them to type for you, you'll start looking more closely at the interfaces that don't appear to be working for the masses...

Interesting response, but I have to disagree with you that voice interaction shouldn't be considered a useful feature.

Two free hands are awesome when you're an artist. I'd rather my hands be at the ivories, all day, but our interfaces haven't evolved to that extent, yet.

Simulated annealing... I have AI if you want it

[CrazyJim0]

check out my page:
www.contrib.andrew.cmu.edu/~sager

Back in 1992, I predicted MMORPG from muds(tried to make one too www.ebayrp.bizland.com), 1 auction site, and instant messaging(who didn't though)....

I can see it being done in 10 if some corporation attempts it. But I know it will happen within 20, or the whole of humanity is just plain stupid.

I am not so sure we'll be seeing androids because of construction difficulties, but who knows.

That's called bloat

[carlossch]

An interesting side effect was that as a strain of 'DNA' evolved it became longer and longer. Upon tracing advanced mutations I found large sections of the genes to go completely unused.

The growth of the proportion of introns (genetic code which does not directly influence the fitness function) to exons ("relevant" genetic information) as the fitness of the individual grows is a reasonably well-documented phenomenon in GP communities, and is commonly called bloat. "Relevant" because, despite conclusive evidence, most researchers believe that the introns are also relevant to the individual, even if not directly.

For example, mutations can occur on introns without any direct change to the individual. As introns are comprised essentially of copies or parts of original genetic code, they probably provide a place where mutations to possibly beneficial (albeit inactive) genes can occur safely.

Besides that, as bloat increases, the active genetic code decreases in proportion, and as a result you get a kind of 'clustering' of active genes, which is a good thing, because the chances of a disrupting crossing-over go down.

A great book on the subject is Genetic Algorithms + Data Structures = Evolution Programs, by Zbigniew Michalewicz (but I'm not sure if he covers bloat in the text). I remember reading a paper on bloat in one of the Springer-Verlag Lecture Notes on Computer Science about Genetic Programming.

Now, to see some really wacky and interesting things, the book to read is Evolutionary Design by Computers, edited by Peter Bentley, with lots of nice papers to read (and a kickass foreword from THE MAN Richard Dawkins)

Links for the paranoid:
http://www1.fatbrain.com/asp/bookinfo/bookinfo.asp ?theisbn=3540606769&vm=
http://www1.fatbrain.com/asp/bookinfo/bookinfo.asp ?theisbn=155860605X&vm=

Carlos

I was recently contemplating the same thing

[I Am The Owl]

I was talking to a friend of mine the other day about how he had taken one of those programs in which you "make" your own battle robot out of assembly code, and had written a program that wrote a bunch of them and then matched them up, combining the instructions of the winning bots to form the next generation.

This got me intrigued, so I hopped on to Google, and, lo and behold, this is what I found. Probably one of the more interesting works that I have read online in quite some time, although there were parts that I didn't understand since I haven't yet taken enough coursees in high math to properly comprehend them.

Not that simple

[samael]

Number of descendants that are _fit_ is the definition of fitness. :->

Having 20 children that all die before having children of their own doesn't make you fit.

Re:Not that simple

[gorilla]

Many people studying evolutionary biology use the number of grandchildren as the measurement. If you have grandchildren it's clear that your children survived to reproduce, and therefore your behaviour was good.

Spielberg's AI ?!?

[chemguru]

Maybe Steven Spielberg's AI film is closer to reality than the general public knows *smile*?"

It was more of a Kubrick film than Spielberg's. I mean seriously... Give the man some friggin credit!

Re:Spielberg's AI ?!?

[tolaj]

Researchers are also dreamers and philosophers. They are actually trying to do something with their dreams (with great public success or risking a catastrophic failure). The critics and obstacles provided will never stop those dreaming adventurers. Why creating more and more complex CPUs, when we normaly should consentrate on creating intelligent and *userfriendly* systems?
E.g. our body is "userfriendly" it repairs itself when getting injured! Computer systems should do the same.

A.I. has been there all the time - and getting more and more approved, but we are using it already without knowing it. Isn't it userfriendly or what? ;)

Sincerely Roland's student

Tough for human-level intelligence

[rusti999]

As other readers have pointed out, this is nothing new. John Holland originated the genetic algorithm idea in around 1970's (his book, "Adaptation in Natural and Artificial Systems", was first published in 1975). Then John Koza extends this idea to genetic programming (the first volume of his "Genetic Programming" series came out in 1992). It's still under a lot of research. But there are quite a number of people, most notably Marvin Minsky, that argue that this approach won't be the cure-all and solve-all for the problem of achieving artificial human-level intelligence within a reasonable timeframe (around 50 years from now), which the movie AI exhibits. The argument draws from the evolution of life itself. How long did it take from the first lifeforms to the first human species? In the order of million, if not billion, of years certainly. The point is, it's going to take a heck lot of time for this kind of programs to truly achieve our (human's) level of intelligence, if it's possible at all. Not to say that the technique is not useful--it has been applied in a number of applications. But if we're looking for human-level intelligence, it alone would barely solve the problem.

Sorry, nothing further to add.

[shibboleth]

Sorry, nothing further to add.

Except that if that doesn't pan out and you are still looking for an interesting project, you may want to check out Bluebox. (Something about a universal internet language.)

GP and intellectual property

[strombrg]

Folks, GP is a really promising area, but please don't forget, it's a patented algorithm, and probably will be for some time.

I wrote to the patent holder to see if I could use GP in a GPL'd project (offered him a big chunk of my prize money if my project panned out), and after suggesting I publish my results if I get anywhere instead, he totally blew me off. The project in question was a "go/igo/weichi/baduk AI", a really challenging artificial intelligence problem that has eluded many. I'm actually more interested in giving away my code than the prize money though.

So you can probably assume that where OSS and FS are concerned, this guy isn't interested, although maybe if you're project doesn't have prize money involved, he might react differently; I don't know. I'm beginning to think lawyers tell their clients not to tip their hand either way where patents are concerned, because it seems there's a big vacuum surrounding FS/OSS and patents. :(

I believe the patent in question is 4,935,877.

evolutionary algorithms and mutation

[mcoletti]

Genetic algorithms produce results faster without mutations.

That is untrue. Solution space exploration would be critically curtailed with no mutation. In fact, plain vanilla evolutionary strategies employ only mutation for solving problems.

Also, mutation can be a more potent exploratory force than cross-over.

The moral of this story is that you should prefer canonical sources for knowledge than quips made on /.

Re:evolutionary algorithms and mutation

[Alsee]

Firstly, my post was intened to clear up a common misconception (and someone's specific statement).
random mutations used in genetic programming are about as efficient as real random mutations. They get the job done eventually, but require a lot of screw-ups to make one improvement.

GA is NOT a pathetic mutation by mutation crawl towards a solution. I think you'll agree with me there :)

&GT Genetic algorithms produce results faster without mutations.
That is untrue.
I stand by what I said. Mutations slow the process of getting results. It disrupts the weighting of tested schema, and reduces fitness more often than it increases fitness.

We agree on the value of mutations. We both said they increase the search range and give better results in the end.

exploration would be critically curtailed
It depends on how fast you lose diversity. If you have a pop of 100 and kill 75% per generation, and have no diversity pressure, then yes, you're screwed.
If you have a pop of 2000 and kill 25% per generation, and have a diversity pressure (in my other post to you I mention I've used a virtual parasite cost based on similarity) then you can maintain high diversity and do an excellent job on search space even without mutation.

In fact, plain vanilla evolutionary strategies employ only mutation for solving problems
I know. They have their uses, but they lack the incredible power of massive implicit parallelism. I didn't mention them because implicit parallelism was my point.

mutation can be a more potent exploratory force than cross-over
Double Akk. It's a postcript file gzipped. I *think* I have gzip somewhere, but not a postscript reader. Nutz. I'm curious to read it. It must be talking about some sort of special case because in a diverse population crossover is generally thousands or millions of times more powerful.

The moral of this story is that you should prefer canonical sources for knowledge than quips made on /.
I agree with your moral, but I think you underestimated my knowledge on the subject.

Question: Have YOU programmed any genetic algorithms?

Ill informed about co-evoluionary methodologies

[mcoletti]

Another technique is to co-evolve "parasites". First the sort programs converge on a solution and they all start to look alike. Then the parasites home in on the sorting programs. The sort programs start to diversify to escape the parasites. The "fleeing" sort programs explore for different algorithms to use.

You seem to be confusing evolutionary game theory with evolutionary algorithms.

Co-evolutionary algorithms can be cooperative or competitive (or maybe even some combination of the two). Danny Hillis, of Thinking Machines fame, developed a competitive co-evolutionary system that plied a system evolving sorting networks against systems that evolved difficult datasets. This system produced significantly better sorting networks than an evolutionary algorithm that just evolved sorting networks. Mitch Potter's doctoral thesis is on co-operative evolution, and makes for possibly good introductory reading.

The notion of "fleeing parasitic programs" is, as far as I know, a fantasy.

Not Quite True

[uberdave]

...whereas evolutionary biology has no purpose at all. It simply happens; there is no guiding hand or principle.

Not quite. Mankind has directed the evolution of many species for a long time: cross pollenating to produce hardier plants, selectively breeding animals for strength, speed, shape, etc. We have husbandry records dating back farther than most people can trace their own ancestry.

Re:Not Quite True

[maxpublic]

This isn't evolution; it's breeding. The two concepts have nothing to do with one another. Evolution is *random*, completely and utterly; breeding is directed and non-random.

Once again, breeding and evolution have nothing whatsoever to do with one another. And again, if anyone has a problem with the concept of evolution there are a great many basic bio texts which go into the idea in detail.

Max

Re:Not Quite True

[uberdave]

breeding and evolution have nothing whatsoever to do with one another

POPPYCOCK

Evolution is the change in the genetic makeup of a species as a result of selective breeding. Whether that selection is natural, or artificial is irrelevant. The mechanism is the same. Individuals with adventageous genetic traits are available to breed, so those genetic traits are favoured. Individuals with unfavourable traits are unavailable, so those traits are not passed on.

The only difference is that man is determining the fitness to survive, rather than nature.

Re:Not Quite True

[maxpublic]

Jesus H. Christ, do a little reading. There's no 'selective' about it in evolution; everything that can breeds does, and the better-adapted offspring tend to win out over generations. This is utterly different than what you assert.

Furthermore, nature doesn't determine fitness to survive because NATURE DOESN'T DETERMINE A GODDAMNED THING. Nature is not sentient - it's not even real, just a concept that human beings made up. You keep ascribing directed characteristics to something that doesn't exist and even in its least abstract form is unable to 'choose' anything at all since it lacks any form of consciousness or motivation.

Finall, there is no 'fitness to survive' anywhere in the theory of evolution - you'd know that if you weren't pulling your assumptions out of your ass.

Evolution is random. The better mutations tend (and I say *tend*) to result in a greater number of offspring over time than the less beneficial ones. Results may vary. That is IT in a nutshell.

Max

Re:Not Quite True

[uberdave]

OK, I've taken your advice and done a bit of reading:

1. "Evolution is a change in the gene pool of a population over time."
   "The mechanisms of evolution are mutation, natural selection, genetic drift, recombination and gene flow."

Well, OK, selection is not the only factor in evolution. However, it is probably the most important, and it is definitely the most widely recognized.

Furthermore, nature doesn't determine fitness to survive because NATURE DOESN'T DETERMINE A GODDAMNED THING. Nature is not sentient - it's not even real, just a concept that human beings made up. You keep ascribing directed characteristics to something that doesn't exist and even in its least abstract form is unable to 'choose' anything at all since it lacks any form of consciousness or motivation

I did not in any way mean to imply that nature was sentient, what I meant was what is typically meant by natural selection:

1. "As each organism is tested by its environment, the number of its offspring depends on the fitness to survive conferred by those characteristics."
   "In the long run, only those species that have qualities better adjusted to the natural environment can live longer. These organisms will usually have better ability to find or store food, or are more able to escape their predators. Thus, these organisms have more chance to mate and give birth to more and healthier off-spring."

Again, nothing out of the ordinary or contradictory here. Perhaps what is throwing you is the "reverse" logic I was using. If only the "fittest" survive, then the only organisms that an individual can breed with are "the fittest".

There's no 'selective' about it in evolution; everything that can breeds does, and the better-adapted offspring tend to win out over generations.

Finally, there is no 'fitness to survive' anywhere in the theory of evolution

I'm not sure I understand your point here. Even the most cursory reading on the subject of evolution is littered with references to selection and fitness. Even in your own words you use the terms "better-adapted", "win out", and "greater number of offspring". Well...

1. "Fitness. The probability that an organism with a particular set of traits will survive to reproduce more offspring than others that do not possess these traits."
   "Fitness, in an evolutionary sense, is the average reproductive output of a class of genetic variants in a gene pool."
   "Natural selection ... is defined as differential reproductive success of pre- existing classes of genetic variants in the gene pool."
   "Natural selection is not random: it is the determinate result of sorting processes according to relative fitness"

I'm going to leave all that aside. Your original assertion was that "evolutionary biology has no purpose at all. It simply happens; there is no guiding hand or principle.". Well, for the most part I understand and agree with what you're saying. However...

1. "Strict natural selection is not the only type of selection that takes place in nature or that has an effect on evolution. Other types of selection, all corollaries or variations of natural selection, are also present in the rich tapestry of evolution. The major variant types of selection are artificial selection, sexual selection, and kin selection."
   "Artificial selection is the process by which a non-natural selection pressure on a population of organisms is set up by human activities, especially domestication of animals and plants. Humans breed from domestic organisms possessing the most desirable qualities in a process known as selective breeding, which then sets up a survival and reproductive advantage for those organisms that possess the desirable qualities. The result is an increase in the number of organisms possessing such qualities until these alleles come to dominate the gene pool of the population."
   "Artificial selection is the process of changing the characteristics of animals by artificial means. For example, animal breeders, are often able to change the characteristics of domestic animals by selecting for reproduction those individuals with the most desirable qualities such as speed in racehorses, milk production in cows, trail scenting in dogs."

So, the point of my previous posts, is this: Your original assertion that "evolutionary biology has no purpose at all. It simply happens; there is no guiding hand or principle." is not quite true. Some of it is directed by mankind.

Re:correction

[Alsee]

a competitive co-evolutionary system that plied a system evolving sorting networks against systems that evolved difficult datasets.

Yes, that's probably where I first heard the term parasites in relation to GA. You are correct the technique doesn't quite match the decription I gave.

One of the issues in GA is maintaining diversity.
In reading about biology there is strong evidence that parasites have been one of the major driving forces in creating diversity, and the reason for sexual reproduction itself (as opposed to asexual, which would ordinarily be more efficient). I made the obvious connection, and I assumed this technique was part of the literature. I just did a moderate search and it doesn't seem to be there.

While I haven't actually co-evolved parasites, I have added a 'virtual' parasite cost based on similarity. It was extremely effective.

Maybe I should write a paper on it :)

The notion of "fleeing parasitic programs" is, as far as I know, a fantasy.
You're right in that I don't see it in the literature, but the result is obvious if you understand GA. The main population would converge and the parasites would be drawn there. The parasites would turn the local optimum into a local minimum and the main population would "flee" the minimum.

Tom Ray did this a long time ago--Tierra

[BobTheWonderMonkey]

Check out http://www.isd.atr.co.jp/~ray/tierra/ to read about Tierra, the first time evolution was used to grow programs.

Ultimately, Ray used this to try to evolve complex parallel processing programs.

The evolutionary process will be introduced into the context of the global computer network, internet. The objective is to evolve complex MIMD distributed processes.

Neat stuff. Check it out.