Understanding through Discussion


Welcome! You are not logged in. [ Login ]
EvC Forum active members: 78 (8896 total)
Current session began: 
Page Loaded: 03-23-2019 3:17 PM
37 online now:
AZPaul3, DrJones*, PaulK, Tanypteryx (4 members, 33 visitors)
Chatting now:  Chat room empty
Newest Member: WookieeB
Post Volume:
Total: 848,593 Year: 3,630/19,786 Month: 625/1,087 Week: 215/212 Day: 30/27 Hour: 0/1


Thread  Details

Email This Thread
Newer Topic | Older Topic
  
Prev12
3
45Next
Author Topic:   Evolution as an Algorithm
PurpleYouko
Member
Posts: 713
From: Columbia Missouri
Joined: 11-11-2004


Message 31 of 74 (345392)
08-31-2006 10:13 AM
Reply to: Message 21 by Woodsy
08-31-2006 7:05 AM


Re: Not an algorithm
Hi Woodsy.

If you are interested in what actually goes on in such a computer simulation, I recommend that you give DarwinBots a try.
It is an open source program built around hundreds (or thousands) of little "bots" that interact with each other to feed, fight reproduce and generally try to survive.
Each one has a "DNA" which is able to mutate due to various conditions during reproduction. The aim of the simulations is to see what happens when we change the physical conditions in the DarwinBots universe.


This message is a reply to:
 Message 21 by Woodsy, posted 08-31-2006 7:05 AM Woodsy has not yet responded

Replies to this message:
 Message 44 by kuresu, posted 08-31-2006 1:40 PM PurpleYouko has responded

  
JavaMan
Member (Idle past 397 days)
Posts: 475
From: York, England
Joined: 08-05-2005


Message 32 of 74 (345404)
08-31-2006 11:05 AM
Reply to: Message 29 by nwr
08-31-2006 9:33 AM


Re: Not an algorithm
Does the term "genetic algorithm" apply to the individual steps taken, which are algorithmic and deterministic? Or does it apply to the overall process which uses random input, and is thus neither algorithmic nor deterministic (unless a deterministic pseudo-random number generator is used)?

I don't know why you're insisting that an algorithm must be deterministic. Despite the standard definition of an algorithm being something that always generates the same outcome given a fixed set of inputs, in reality an algorithm is just a set of instructions. If one of those instructions says, 'generate me a set of solutions with a certain amount of random input', then what you've got is a non-deterministic algorithm.

See Wikipedia entry on Nondeterministic Algorithms

Edited by JavaMan, : No reason given.


'I can't even fit all my wife's clothes into a suitcase for travelling. So you want me to believe we're going to put all of the planets and stars and everything into a sandwich bag?' - q3psycho on the Big Bang
This message is a reply to:
 Message 29 by nwr, posted 08-31-2006 9:33 AM nwr has responded

Replies to this message:
 Message 33 by nwr, posted 08-31-2006 11:34 AM JavaMan has responded

  
nwr
Member
Posts: 5585
From: Geneva, Illinois
Joined: 08-08-2005


Message 33 of 74 (345412)
08-31-2006 11:34 AM
Reply to: Message 32 by JavaMan
08-31-2006 11:05 AM


Re: Not an algorithm
I don't know why you're insisting that an algorithm must be deterministic. Despite the standard definition of an algorithm being something that always generates the same outcome given a fixed set of inputs, in reality an algorithm is just a set of instructions. If one of those instructions says, 'generate me a set of solutions with a certain amount of random input', then what you've got is a non-deterministic algorithm.

I teach that class.

The term "non-deterministic algorithm" is a term of art. One must avoid confusing the expression "non-deterministic" as used here, with the philosophic notion of indeterminism.

As I am careful to point out to my students, a non-deterministic algorithm is perfectly deterministic.

In theoretical use, a non-deterministic algorithm is sometimes described in terms of periodically consulting an oracle for advice on the next move. The advice from the oracle is part of the input to the algorithm. The output of the algorithm is a deterministic function of its input.

In practical use, we sometimes replace the oracle with a random number generator, but the algorithm still produces results that are a deterministic function of its inputs. Here the random numbers are part of the inputs. In another form of practical use. we apply a back-tracking or similar method, so that we can systematically try all possibilities. The resulting procedure is completely deterministic.

See Wikipedia entry on Nondeterministic Algorithms

That wiki article even indicates how one would turn the "non-deterministic algorithm" into a deterministic one in order to actually implement it.
This message is a reply to:
 Message 32 by JavaMan, posted 08-31-2006 11:05 AM JavaMan has responded

Replies to this message:
 Message 34 by PurpleYouko, posted 08-31-2006 11:54 AM nwr has responded
 Message 37 by JavaMan, posted 08-31-2006 12:04 PM nwr has acknowledged this reply
 Message 58 by JavaMan, posted 09-01-2006 4:25 AM nwr has responded

  
PurpleYouko
Member
Posts: 713
From: Columbia Missouri
Joined: 11-11-2004


Message 34 of 74 (345421)
08-31-2006 11:54 AM
Reply to: Message 33 by nwr
08-31-2006 11:34 AM


Re: Not an algorithm
That wiki article even indicates how one would turn the "non-deterministic algorithm" into a deterministic one in order to actually implement it.

Please correct me if I have this wrong.
The wiki article appears to be saying that a random number generator inside an algorith (probabilistic deterministic algorith) is going to send the output in one of a finite number of possible directions such that for any one set of input criteria, N possible outcomes are possible because that is the total number of random possibilities that exist within the randomiser.
This is then deterministic because you can run the algorith N number of times, you will get every possible outcome.
Does that sound about right or am I way off base?
This message is a reply to:
 Message 33 by nwr, posted 08-31-2006 11:34 AM nwr has responded

Replies to this message:
 Message 39 by nwr, posted 08-31-2006 12:08 PM PurpleYouko has responded

  
Hyroglyphx
Member
Posts: 5622
From: Austin, TX
Joined: 05-03-2006


Message 35 of 74 (345423)
08-31-2006 11:56 AM
Reply to: Message 16 by Parasomnium
08-30-2006 7:01 PM


Re: I am convinced
And it's funny you should say that, because a catastrophy is what I had to introduce to overcome the problem of so-called 'local minima'. This is a technical term which means that sometimes an evolutionary path leads to a solution that cannot be improved upon other than by an enormous change at once. But evolution only proceeds by small changes. Since any small change to a local minimum will most likely diminish its fitness, it is therefore less likely to be selected for. Only a catastrophy once in a while will make sure that the gene pool is "cleaned up" as it were, wiping out successful and less successfull solutions alike. So, in short, your doubt is unfounded.

I'm glad you added that element, because history is full of catastrophe's that surely would effect numerous populations and how and when they would evolve, supposing that would at all.

But you're forgetting that it's the genome that determines the organism, not vice versa. Yes, for a given organism, it's obviously true that its genome cannot be endlessly varied upon, or it would cease to be that given organism.

Well, this a chicken-egg argument I suppose. But you make the distinction for me that if organisms were so prone to variabilty, we would not have the populations that we do. In fact, if evolution were true why wouldn't we see so much more variabilty than we do?

There are some common objections to evolutionary simulators and their applicable feasibility. For instance, AiG feels that algorithms cannot mimic biological evolution for the following reasons:

  • A ‘trait’ can only be quantitative so that any move towards the objective can be selected for. Many biological traits are qualitative—it either works or it does not, so there is no step-wise means of getting from no function to the function.

  • A single trait is selected for, whereas any living thing is multidimensional. A "GA" (Genetic Algorithm) will not work with three or four different objectives, or I dare say even just two. A GA does not test for survival; it tests for only a single trait. Even with the simplest bacteria, which are not at all simple, hundreds of traits have to be present for it to be viable (survive); selection has to operate on all traits that affect survival.

  • Something always survives to carry on the process. There is no rule in evolution that says that some organism(s) in the evolving population will remain viable no matter what mutations occur. In fact, the GAs that I have looked at artificially preserve the best of the previous generation and protect it from mutations or recombination in case nothing better is produced in the next iteration. This has a ratchet effect that ensures that the GA will generate the desired outcome—any move in the right direction is protected.

    (And this objection could be applied to your introduction of the catastrophe. I agree that such variables should exist simply because they surely exist in actual nature, however, one cannot introduce a catastrophe simply because their algorithm is no longer producing viable organisms any longer).

  • Perfect selection (selection coefficient, s = 1.0) is often applied so that in each generation only the best survives to ‘reproduce’ to produce the next generation. In the real world, selection coefficients of 0.01 or less are considered realistic, in which case it would take many generations for an information-adding mutation to permeate through a population. Putting it another way, the cost of substitution is ignored.

    Those are just a few objections to the simulator/algorithm programs.


    “"All science, even the divine science, is a sublime detective story. Only it is not set to detect why a man is dead; but the darker secret of why he is alive." —G. K. Chesterton
    This message is a reply to:
     Message 16 by Parasomnium, posted 08-30-2006 7:01 PM Parasomnium has responded

    Replies to this message:
     Message 36 by PurpleYouko, posted 08-31-2006 12:02 PM Hyroglyphx has not yet responded
     Message 38 by Modulous, posted 08-31-2006 12:07 PM Hyroglyphx has responded
     Message 41 by Woodsy, posted 08-31-2006 12:52 PM Hyroglyphx has not yet responded
     Message 45 by Parasomnium, posted 08-31-2006 1:56 PM Hyroglyphx has not yet responded

        
  • PurpleYouko
    Member
    Posts: 713
    From: Columbia Missouri
    Joined: 11-11-2004


    Message 36 of 74 (345425)
    08-31-2006 12:02 PM
    Reply to: Message 35 by Hyroglyphx
    08-31-2006 11:56 AM


    Re: I am convinced
    A GA does not test for survival

    DarwinBots does. :)
    Nothing is selected for except for the organism's ability to stay alive and reproduce successfully. Any number of individual attribute may account for general survival rate.
    This message is a reply to:
     Message 35 by Hyroglyphx, posted 08-31-2006 11:56 AM Hyroglyphx has not yet responded

      
    JavaMan
    Member (Idle past 397 days)
    Posts: 475
    From: York, England
    Joined: 08-05-2005


    Message 37 of 74 (345427)
    08-31-2006 12:04 PM
    Reply to: Message 33 by nwr
    08-31-2006 11:34 AM


    Re: Not an algorithm
    I teach that class.

    The term "non-deterministic algorithm" is a term of art. One must avoid confusing the expression "non-deterministic" as used here, with the philosophic notion of indeterminism.

    As I am careful to point out to my students, a non-deterministic algorithm is perfectly deterministic.

    Lets say I have an algorithm that consists of the sequence of instructions A, B and C, and instruction B states, 'generate me a set of random numbers as input to C'.

    Now assume that I provide input to this algorithm at step A and receive output from step C. Is there any way in which I can say that the output from C is determined by the input at A? If not, then why can I not say that my algorithm A->C is non-deterministic?


    'I can't even fit all my wife's clothes into a suitcase for travelling. So you want me to believe we're going to put all of the planets and stars and everything into a sandwich bag?' - q3psycho on the Big Bang
    This message is a reply to:
     Message 33 by nwr, posted 08-31-2006 11:34 AM nwr has acknowledged this reply

    Replies to this message:
     Message 49 by Percy, posted 08-31-2006 3:06 PM JavaMan has responded

      
    Modulous
    Member (Idle past 182 days)
    Posts: 7789
    From: Manchester, UK
    Joined: 05-01-2005


    Message 38 of 74 (345428)
    08-31-2006 12:07 PM
    Reply to: Message 35 by Hyroglyphx
    08-31-2006 11:56 AM


    More falsifications...
    A ‘trait’ can only be quantitative so that any move towards the objective can be selected for. Many biological traits are qualitative—it either works or it does not, so there is no step-wise means of getting from no function to the function.

    A long time falsification for evolution, Darwin mentioned it in 'The Origin'. It's the Holy Grail of the ID Movement, but all they have is irreducible complexity which has so far been thwarted by redundant complexity. If any of these traits you mention were out there, then a thread could dedicated to exploring them. As it stands, nobody has come forward with hard evidence that there is no step-wise way to get to them.


    This message is a reply to:
     Message 35 by Hyroglyphx, posted 08-31-2006 11:56 AM Hyroglyphx has responded

    Replies to this message:
     Message 52 by Hyroglyphx, posted 08-31-2006 7:41 PM Modulous has responded

      
    nwr
    Member
    Posts: 5585
    From: Geneva, Illinois
    Joined: 08-08-2005


    Message 39 of 74 (345429)
    08-31-2006 12:08 PM
    Reply to: Message 34 by PurpleYouko
    08-31-2006 11:54 AM


    Re: Not an algorithm
    As written, the wiki article is a bit ambiguous.

    It could mean that the random number generator is to be considered as outside the algorithm, so what the algorithm does is deterministic. Or, as you suggest, it could mean that the random number generator is to be considered inside, but the effect is deterministic in a probablistic sense.

    I suspect the second meaning (i.e. the one you suggested), is what was intended.


    This message is a reply to:
     Message 34 by PurpleYouko, posted 08-31-2006 11:54 AM PurpleYouko has responded

    Replies to this message:
     Message 40 by PurpleYouko, posted 08-31-2006 12:35 PM nwr has responded

      
    PurpleYouko
    Member
    Posts: 713
    From: Columbia Missouri
    Joined: 11-11-2004


    Message 40 of 74 (345431)
    08-31-2006 12:35 PM
    Reply to: Message 39 by nwr
    08-31-2006 12:08 PM


    Re: Not an algorithm
    I suspect the second meaning (i.e. the one you suggested), is what was intended.

    I thought so too. glad you agree with me.

    This does pose some rather interesting questions about biological evolution though.

    At heart, DNA is made up of a limited number of combinations of base pairs. It would be easy to apply the same logic to the real system since the randomiser that is "mutation" can only work within tightly defined criteria (ie. a finite number of base pairs). For any mutation event during reproduction, there are only a finite number of possible outcomes so that would mean that real evolution would also fall into the same definition of the term "non-deterministic algorith".


    This message is a reply to:
     Message 39 by nwr, posted 08-31-2006 12:08 PM nwr has responded

    Replies to this message:
     Message 42 by nwr, posted 08-31-2006 1:28 PM PurpleYouko has responded

      
    Woodsy
    Member (Idle past 1452 days)
    Posts: 301
    From: Burlington, Canada
    Joined: 08-30-2006


    Message 41 of 74 (345436)
    08-31-2006 12:52 PM
    Reply to: Message 35 by Hyroglyphx
    08-31-2006 11:56 AM


    Re: I am convinced
    I see no reason why the items you quote from AiG could not be included in a program quite easily. The fact that some programs do not do so does not show that none ever could. I find that argument very fishy indeed.

    You seem to assume that some large fraction of variations must be viable. I do not see why this should be so. A line I like from Dennett's book goes: "Evolution depends on events that almost never happen.".

    I gather that you see some flaw in the overall evolutionary algorithm or process or whatever we might like to call it. Would you care to describe it?


    This message is a reply to:
     Message 35 by Hyroglyphx, posted 08-31-2006 11:56 AM Hyroglyphx has not yet responded

      
    nwr
    Member
    Posts: 5585
    From: Geneva, Illinois
    Joined: 08-08-2005


    Message 42 of 74 (345447)
    08-31-2006 1:28 PM
    Reply to: Message 40 by PurpleYouko
    08-31-2006 12:35 PM


    Re: Not an algorithm
    At heart, DNA is made up of a limited number of combinations of base pairs. It would be easy to apply the same logic to the real system since the randomiser that is "mutation" can only work within tightly defined criteria (ie. a finite number of base pairs). For any mutation event during reproduction,

    Let's keep in mind that there is more to biology than DNA. People sometimes talk as if the DNA is a specification or blueprint for an organism. But it isn't. Rather, it is specification for manufacturing a variety of proteins. A biological organism comes about when this manufacturing is done in a suitable development environment.

    We must also remember that our evolutionary history might have involved symbiotic unions. For example, Lynn Margulis has proposed that the eukaryote cell originated as a symbiotic union. If correct, then the structure of that symbiotic union is part of what is passed on to the next generation, and the way that structure is passed on is not as part of the DNA specification.


    This message is a reply to:
     Message 40 by PurpleYouko, posted 08-31-2006 12:35 PM PurpleYouko has responded

    Replies to this message:
     Message 43 by PurpleYouko, posted 08-31-2006 1:36 PM nwr has acknowledged this reply
     Message 51 by Wounded King, posted 08-31-2006 5:01 PM nwr has responded

      
    PurpleYouko
    Member
    Posts: 713
    From: Columbia Missouri
    Joined: 11-11-2004


    Message 43 of 74 (345450)
    08-31-2006 1:36 PM
    Reply to: Message 42 by nwr
    08-31-2006 1:28 PM


    Re: Not an algorithm
    Let's keep in mind that there is more to biology than DNA. People sometimes talk as if the DNA is a specification or blueprint for an organism. But it isn't. Rather, it is specification for manufacturing a variety of proteins. A biological organism comes about when this manufacturing is done in a suitable development environment.

    Yes it's a good idea to keep that stuff in mind for the broader picture but i'm just thinking about a single mutation event of a single organism and whether it can be considered to be an algorith or not.
    If it has a random element in the same way as the hypothetical "probabilistic deterministic algorithm" then how is the event any different to a computer modelled event.
    For the moment I am ignoring the fact that computers only generate pseudo random events since the wiki definition did not specify that a computer was the source of the randomness.
    This message is a reply to:
     Message 42 by nwr, posted 08-31-2006 1:28 PM nwr has acknowledged this reply

      
    kuresu
    Member (Idle past 591 days)
    Posts: 2544
    From: boulder, colorado
    Joined: 03-24-2006


    Message 44 of 74 (345453)
    08-31-2006 1:40 PM
    Reply to: Message 31 by PurpleYouko
    08-31-2006 10:13 AM


    Re: Not an algorithm
    yeah, about those darwin bots.

    I downloaded the newest patch, and apparently there's a critical file missing, which was stated to be an overlook.
    the FAQ gives me a link, but it's to a forum that I need membership in.

    the file i need is the sysvars2.21.txt.
    any help?


    All a man's knowledge comes from his experiences
    This message is a reply to:
     Message 31 by PurpleYouko, posted 08-31-2006 10:13 AM PurpleYouko has responded

    Replies to this message:
     Message 46 by PurpleYouko, posted 08-31-2006 1:56 PM kuresu has responded

        
    Parasomnium
    Member (Idle past 774 days)
    Posts: 2191
    Joined: 07-15-2003


    Message 45 of 74 (345458)
    08-31-2006 1:56 PM
    Reply to: Message 35 by Hyroglyphx
    08-31-2006 11:56 AM


    Re: I am convinced
    nemesis_juggernaut writes:

    I'm glad you added that element, because history is full of catastrophe's that surely would effect numerous populations and how and when they would evolve, supposing that would at all.

    I only included it to allow the whole evolutionary process to get out of local minima. Without the catastrophies evolution still took place.

    But you're forgetting that it's the genome that determines the organism, not vice versa. Yes, for a given organism, it's obviously true that its genome cannot be endlessly varied upon, or it would cease to be that given organism.

    Well, this a chicken-egg argument I suppose.

    I don't think so. The phenotype of an organism is for a large part the result of its genotype. The reverse isn't true.

    But you make the distinction for me that if organisms were so prone to variabilty, we would not have the populations that we do. In fact, if evolution were true why wouldn't we see so much more variabilty than we do?

    What do you mean? Isn't the variability in nature enough for you? There are about 3.500 different species of mosquitos alone. Based on that fact, can you imagine the total number of different species in the whole of nature? I know I can't.

    Besides, how do you propose to calculate how much variability evolution should yield?

  • A ‘trait’ can only be quantitative so that any move towards the objective can be selected for. Many biological traits are qualitative—it either works or it does not, so there is no step-wise means of getting from no function to the function.
  • To see why this is not true, please ask the nearest person with glasses whether they prefer their myopic eyes over no eyes at all.

  • A single trait is selected for, whereas any living thing is multidimensional. A "GA" (Genetic Algorithm) will not work with three or four different objectives, or I dare say even just two. A GA does not test for survival; it tests for only a single trait. Even with the simplest bacteria, which are not at all simple, hundreds of traits have to be present for it to be viable (survive); selection has to operate on all traits that affect survival.
  • Nothing stops a programmer from developing a more complex fitness function, or a set of them, all of which a candidate for survival has to pass.

  • Something always survives to carry on the process. There is no rule in evolution that says that some organism(s) in the evolving population will remain viable no matter what mutations occur. In fact, the GAs that I have looked at artificially preserve the best of the previous generation and protect it from mutations or recombination in case nothing better is produced in the next iteration. This has a ratchet effect that ensures that the GA will generate the desired outcome—any move in the right direction is protected.
  • This is a property of the evolutionary algorithms that you've looked at, but in no way a property that all of them must have of necessity.

    (And this objection could be applied to your introduction of the catastrophe. I agree that such variables should exist simply because they surely exist in actual nature, however, one cannot introduce a catastrophe simply because their algorithm is no longer producing viable organisms any longer).

    As I've stated above, I only included catastrophies to allow the evolutionary process to get out of local minima. I did not include them to in order to better model reality. Again, without them, evolution took place all the same.

    # Perfect selection (selection coefficient, s = 1.0) is often applied so that in each generation only the best survives to ‘reproduce’ to produce the next generation. In the real world, selection coefficients of 0.01 or less are considered realistic, in which case it would take many generations for an information-adding mutation to permeate through a population. Putting it another way, the cost of substitution is ignored.

    Again, evolutionary algorithms are a proof of concept, not an accurate model of the whole of nature. It is of no consequence that some aspects of evolution are a bit different in reality than they are in an evolutionary algorithm, or that they are absent in them altogether. What matters is that the principle still holds, you can see evolution happening, by just implementing the basics of it's mechanism.


    "Ignorance more frequently begets confidence than does knowledge: it is those who know little, not those who know much, who so positively assert that this or that problem will never be solved by science." - Charles Darwin.

    Did you know that most of the time your computer is doing nothing? What if you could make it do something really useful? Like helping scientists understand diseases? Your computer could even be instrumental in finding a cure for HIV/AIDS. Wouldn't that be something? If you agree, then join World Community Grid now and download a simple, free tool that lets you and your computer do your share in helping humanity. After all, you are part of it, so why not take part in it?

    This message is a reply to:
     Message 35 by Hyroglyphx, posted 08-31-2006 11:56 AM Hyroglyphx has not yet responded

      
    Prev12
    3
    45Next
    Newer Topic | Older Topic
    Jump to:


    Copyright 2001-2018 by EvC Forum, All Rights Reserved

    ™ Version 4.0 Beta
    Innovative software from Qwixotic © 2019