Self-Improving Systems 174
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*?"
if only it were that simple (Score:3, Insightful)
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 (Score:1)
Re:if only it were that simple (Score:3, Insightful)
Re:if only it were that simple (Score:2, Interesting)
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 (Score:1)
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 (Score:1)
Re:if only it were that simple (Score:2)
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 (Score:1)
Re:if only it were that simple (Score:2)
Most people seem to agree that the ultimate survial probability for humans is 0% ;-)
Re:if only it were that simple (Score:1)
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 (Score:2, Informative)
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 (Score:1)
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 (Score:1)
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.
Not that simple (Score:2)
Having 20 children that all die before having children of their own doesn't make you fit.
Re:Not that simple (Score:2)
Re:if only it were that simple (Score:2)
Re:if only it were that simple (Score:1)
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 (Score:2)
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 (Score:1)
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
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
> 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
?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.
> 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 (Score:2)
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
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 (Score:2)
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.
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 (Score:2)
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 (Score:1)
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 (Score:1)
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 (Score:2, Insightful)
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 (Score:1)
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 (Score:1)
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"
Re:if only it were that simple (Score:1)
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
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 (Score:2)
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:
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.
sure you can improve it.... (Score:1)
Re:sure you can improve it.... (Score:1)
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... (Score:2, Insightful)
Re:It's the fitness function, stupid... (Score:1, Interesting)
Re:It's the fitness function, stupid... (Score:1)
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... (Score:1)
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... (Score:1)
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... (Score:1)
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... (Score:1)
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... (Score:1)
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... (Score:1)
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 (Score:1)
Re:Similar to (Score:1)
Re:Similar to (Score:2)
Great.. (Score:3, Informative)
Re:What's an RS Flip-Flop (Score:2)
A framework for self-improving systems (Score:4, Informative)
Genetic Programming (Score:4, Informative)
The Father of GP (John Koza) may disagree with me - he runs genetic-programming.org [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 [genetic-programming.com].
Re:Genetic Programming (Score:2, Interesting)
"...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 [mit.edu] 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 (Score:3, Insightful)
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.
Voice Control (Score:1)
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 (Score:1)
"...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.
Re:Genetic Programming (Score:4, Interesting)
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 [grouptheory.org] 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 [cuny.edu] 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 (Score:1)
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 [robocup.org] 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 (Score:1)
Re:Genetic Programming (Score:2)
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 (Score:1)
How do you define improvement? (Score:2, Insightful)
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
Re:How do you define improvement? (Score:1)
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? (Score:1)
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? (Score:1)
Max
Fitness Functions (Score:1)
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... (Score:2)
If not, might I suggest getting out more?? :)
Re:Hmmm, I Wonder... (Score:1)
So I guess the answer is yes.
Re:Hmmm, I Wonder... (Score:1)
(I remember he came into class one day and uttered "Yesterday, I made an OS that..."
Flaw in Logic (Score:1)
A Simple Genetic Algorithm: .1 - .01% chance) on the chromosome(genome) to create a new offspring population.
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
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. [erachampion.com]
Real world examples of application of GP (Score:1)
Re:Real world examples of application of GP (Score:1)
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 (Score:1)
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 (Score:1)
Re:Real world examples of application of GP (Score:1)
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 (Score:1)
This is news?? (Score:1)
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 [mkp.com] 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 (Score:1)
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? (Score:2, Interesting)
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.
That's called bloat (Score:2, Informative)
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 [fatbrain.com], 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 [fatbrain.com], edited by Peter Bentley, with lots of nice papers to read (and a kickass foreword from THE MAN Richard Dawkins)
Links for the paranoid:p ?theisbn=3540606769&vm=p ?theisbn=155860605X&vm=
http://www1.fatbrain.com/asp/bookinfo/bookinfo.as
http://www1.fatbrain.com/asp/bookinfo/bookinfo.as
Carlos
Re:Distributed Processing for GA's? (Score:1)
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? (Score:1)
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 (Score:1)
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 (Score:1)
GA Archive (Score:3, Informative)
For those wishing to get an intro to GA, try The Hitchhiker's Guide to Evolutionary Computation [purdue.edu].
Re:GA Archive (Score:1)
Browsing over FTP?
Re:GA Archive (Score:1)
Re:GA Archive (Score:1)
GP (Score:1)
The General public didn't see AI; they heard it sucked. They heard it from me.
My own experiments with evolved code (Score:4, Insightful)
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 (Score:3, Insightful)
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 (Score:2)
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.
Re:My own experiments with evolved code (Score:1)
I wonder what kind of success one would have placing the breeding algorithm into the organism itself and allowing that to evolve as well...
Notice the silence (Score:1)
And as for the rest of us nerds, we are sitting in here reading slashdot (news for nerds)
Re:Notice the silence (Score:1)
Why genetic algorithms are powerful (Score:2, Informative)
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. [slashdot.org]
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. [estec.esa.nl]
Re:Why genetic algorithms are powerful (Score:2, Insightful)
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.
Simulated annealing... I have AI if you want it (Score:1)
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.
I was recently contemplating the same thing (Score:3, Interesting)
This got me intrigued, so I hopped on to Google, and, lo and behold, this is what I found [cmu.edu]. 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.
Spielberg's AI ?!? (Score:1)
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!
Tough for human-level intelligence (Score:1)
Re:Already been done! (Score:1)
That's just too strange to be an American joke...
Still pretty damn, funny tho'.
Re:Already been done! (Score:1)
Story Error
The selected story does not appear to exist.
Oops
Re:Already been done! (Score:1)
The old "a miracle appears here" function! (Score:1)