Become a fan of Slashdot on Facebook

 


Forgot your password?
Close
typodupeerror
×
Programming IT Technology

Self-Improving Systems 174

Posted by Hemos from the bigger-better-faster dept.
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*?"
This discussion has been archived. No new comments can be posted.

Self-Improving Systems More

Self-Improving Systems

Comments Filter:

  • if only it were that simple (Score:3, Insightful)

    by rossjudson ( 97786 ) on Saturday October 27, 2001 @02:09PM (#2487730) Homepage
    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.
    • 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.
      • 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.
        • 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.
          • 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_!
            • 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)
              • 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.

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

            • 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.
              • "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".
                • 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.
              • 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.
                • 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.
          • 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.
            • 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.
              • 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.
                • 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.
                  • 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
                    • 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 :)
                    • 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

          • 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.

            • 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.
        • 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.
          • 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.
            • 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.
              • 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 :)
      • '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.

  • 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.
    • 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... (Score:2, Insightful)

    by 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.
    • What would a fitness function for a fitness function look like?
    • 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.

    • 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.

      • "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.
        • 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
    • 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.
    • 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?
  • 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.

    • 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.
    • 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.. (Score:3, Informative)

    by VFVTHUNTER ( 66253 ) on Saturday October 27, 2001 @02:13PM (#2487750) Homepage
    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 (Score:4, Informative)

    by Black Acid ( 219707 ) on Saturday October 27, 2001 @02:17PM (#2487761)
    ResearchIndex lists Theo: A framework for self-improving systems [nec.com]. Although The NECI Scientific Literature Digital Library: ResearchIndex [nec.com] 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 (Score:4, Informative)

    by nyjx ( 523123 ) on Saturday October 27, 2001 @02:18PM (#2487765) Homepage
    ... 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 [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)

      by VB ( 82433 )

      "...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.

      • 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.
      • 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? :)

        • "...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)

      by call -151 ( 230520 ) on Saturday October 27, 2001 @05:06PM (#2488130) Homepage
      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 [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.

    • 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.

  • 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.
    • 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.

      • 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.
      • 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
  • 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.

  • ... 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?? :)

  • 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. [erachampion.com]

  • 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?

  • 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, 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.
  • 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.

    • That's called bloat (Score:2, Informative)

      by carlossch ( 459196 )
      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 [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:
      http://www1.fatbrain.com/asp/bookinfo/bookinfo.asp ?theisbn=3540606769&vm=
      http://www1.fatbrain.com/asp/bookinfo/bookinfo.asp ?theisbn=155860605X&vm=

      Carlos

    • 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).
    • I just finished writing a system for distributing the fitness evaluation of a genetic programming system using the idle time (PM-DGP [sourceforge.net]). 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.
  • 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).

  • GA Archive (Score:3, Informative)

    by metlin ( 258108 ) on Saturday October 27, 2001 @04:28PM (#2488051) Journal
    Check out the GA Archive [navy.mil]. 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 [purdue.edu].
  • 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.

  • My own experiments with evolved code (Score:4, Insightful)

    by melquiades ( 314628 ) on Saturday October 27, 2001 @05:33PM (#2488182) Homepage
    In college, I did a project in which I attempted to evolve programs for Core Wars [sourceforge.net], 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.
    • 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.

        • 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.

    • 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...

  • 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

  • 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)

    by I Am The Owl ( 531076 ) on Saturday October 27, 2001 @10:59PM (#2488794) Homepage Journal
    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 [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.


  • 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!

  • 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 [mit.edu], 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.

Slashdot Top Deals

There is no opinion so absurd that some philosopher will not express it. -- Marcus Tullius Cicero, "Ad familiares"

Close