A Problem to Solve

Evolution is often presented as problem-solving. Genetic algorithms are often offered as proofs of evolution’s ability to solve problems. Genetic algorithms are as search algorithms.

As one book says:

Fundamentally, all evolutionary algorithms can be viewed as search algorithms which search through a set of possible solutions looking for the best – or “fittest” – solution.

Tom has asked me to specify a problem independently from the evolutionary process. Now I have to admit that I don’t really understand what that means. But I like Tom and I have a lot of respect for him, so I want to give it my best shot and see where it takes us. I’m also hoping this will shed some light on claims about how problem-solving genetic algorithms are designed to solve a particular problem.

Tom:

Do you at least agree that if the modeler is solving a problem, then you ought to be able to write out a nontrivial problem? (Saying that the problem is to output a particular sentence won’t hack it. That would amount to saying that Dawkins wrote a “Hello, world!” program.)

Well, I do believe that Dawkins wrote a program to output a particular sentence and that what he did is in effect a hello world program! So where does that get us, lol?

Tom:

There is no independently specified problem that the monkey/Shakespeare model solves. The event of interest to the modeler is the event most likely to occur in the process over the long term.

I disagree. But the language is vague so that’s what we’re here to tease apart.

Tom:

I keep asking you to write a specification of the problem that the modeler wrote the simulation model to solve. The reason you cannot do it is that you can only concoct a “problem” by specifying what tends to occur in the simulated process. This is much the same as making the “problem” solved by evolution in nature what tends to occur in evolutionary processes.

I’ve tried to make this clear. I’m not in an argument with you. Please try to switch gears, and explain to me what you make of what I’ve said. Do you at least agree that if the modeler is solving a problem, then you ought to be able to write out a nontrivial problem?

It seems to me that specifying a problem independently of the evolutionary process is exactly what takes place with genetic algorithms. One book even delineates classes of problems that might be approached using evolutionary algorithms.

– If the problem is sufficiently hard to write code to solve
– When a human isn’t sure how to solve the problem
– If a problem is constantly changing
– When it’s not feasible to search through each possible solution
– When a “good-enough” solution is acceptable

So I’ll take that as my lead. Now surely I can refer to any number of problem-solving evolutionary algorithms, so whether it can be done or not ought not be in dispute. But I always appreciate a concrete example, so here it goes.

Problem: Find a string which is comprised entirely of ones. So for a string with a length of 5 the best solution would be “11111”.

I find it hard to believe that this is what Tom had in mind, but nothing ventured nothing gained. Is this problem too trivial? Or have I missed out totally on what Tom is asking for?

19 Replies to “A Problem to Solve”

  1. Mung Mung
    Ignored
    says:

    Hah. I should have called it Searching for a Problem to Solve. That sounds more like Evolution.

    ok Tom. Like I said, I wasn’t ignoring your questions. I wanted to do them justice. Let’s see if we can work through this.

    Sorry to hear about your father, by the way. Sincerely.

  2. OMagain
    Ignored
    says:

    Tom said:

    Saying that the problem is to output a particular sentence won’t hack it. That would amount to saying that Dawkins wrote a “Hello, world!” program.

    You said:

    Well, I do believe that Dawkins wrote a program to output a particular sentence and that what he did is in effect a hello world program! So where does that get us, lol?

    I guess you’ve never wondered why Dawkins just did not write a print statement instead of the code he did write.

  3. Allan Miller
    Ignored
    says:

    Problem: Find a string which is comprised entirely of ones. So for a string with a length of 5 the best solution would be “11111”.

    It’s up to you, but you’d probably be better going for something where you don’t already know the answer.

    You need a fitness function that just evaluates strings in any current population, as the program runs. Some are more, some less, some equally likely to get passed on to the next generation. Comparison to a ‘target’ is one implementation, but misleading in this instance. You don’t need to code the destination or the route map.

  4. OMagain
    Ignored
    says:

    Allan Miller: It’s up to you, but you’d probably be better going for something where you don’t already know the answer.

    What about “how to stay alive in the polar region”?

  5. Mung Mung
    Ignored
    says:

    Allan Miller: It’s up to you, but you’d probably be better going for something where you don’t already know the answer.

    So something like the Traveling Salesman Problem? I considered starting off with that but wanted to make sure I was on the right track first. Are there TSP solvers out there that don’t use EA’s at all?

  6. Mung Mung
    Ignored
    says:

    OMagain: I guess you’ve never wondered why Dawkins just did not write a print statement instead of the code he did write.

    Not really. I also considered using Dawkins’ Weasel for my example, writing out a problem statement for it. But hasn’t it been done to death already? And what makes it fundamentally different from the all ones problem, really?

  7. Tom English Tom English
    Ignored
    says:

    I believe that this is the fourth time (I know that it’s at least the third) that I’ve asked Mung, If the model is searching for a solution to a problem, then what’s the problem? I was trying to put things somewhat differently this time, not to replace everything that I’d written previously. But I do give him credit for linking to my latest posing of the question. Knowing from statistics at my (neglected) blog Bounded Science that relatively few people click on links, even when I indicate that the background is important, I’m copying the full comment here.

    ___________________

    Mung:

    The second factor that could affect whether populations evolve in parallel concerns whether there are multiple ways to solve a problem posed by the environment.

    – Improbable Destinies p. 241

    Evolution as problem solving. Let’s hope this is just a single isolated case.

    You’ve got your eye on the ball [meaning: this is relevant to Tom’s OP, Evo-Info 3: Evolution Is Not Search“], but you need to work on your follow-through.

    The author is referring to a “problem” identified after the fact of its being “solved” by an evolutionary process. The analysis of Marks, Dembski, and Ewert does not apply. I showed (with animation) in “The Law of Conservation of Information Is Defunct” that when the most probable outcome of a “search” is designated the “target,” active information is not conserved.

    Part of my difficulty in explaining the book [Introduction to Evolutionary Informatics] is that Marks et al. have abandoned the claim that “Darwinian evolution is inherently teleological,” and have replaced it with a claim that the models are teleological. Now their line is something like “If the modelers can’t get evolution to work without designing their models to search for prespecified targets, then what of nature?” A modeler is not saying, as indicated by the math of Marks et al., that an evolutionary process magically sprang into existence to solve a problem s/he was given. The modeler is saying, “Here are circumstances in which the event tends to occur in an evolutionary process.” The modeler jointly selects the process and the event. Marks et al. are terribly sloppy when they say that the problem is “specified in advance” (I think I quoted that at the end of the OP). They are mistaking specified before the simulation of the process runs for specified in advance of the definition of the evolutionary process. The process and the event of interest are tailored to each other. The modeler is saying that the event occurs only under certain circumstances, not that the circumstances occur because the event was specified as the solution set of a problem.

    What I’ve just said applies even to Dawkins’s monkey/Shakespeare model of cumulative selection. Dawkins is not saying that the (simulated) experimental setup, in which the monkey is supplied with a copy of “METHINKS IT IS LIKE A WEASEL,” sprang magically into existence after he (Dawkins) was given a problem to which the answer was “METHINKS IT IS LIKE A WEASEL.”

    There is no independently specified problem that the monkey/Shakespeare model solves. The event of interest to the modeler is the event most likely to occur in the process over the long term.

    I keep asking you to write a specification of the problem that the modeler wrote the simulation model to solve. The reason you cannot do it is that you can only concoct a “problem” by specifying what tends to occur in the simulated process. This is much the same as making the “problem” solved by evolution in nature what tends to occur in evolutionary processes.

    I’ve tried to make this clear. I’m not in an argument with you. Please try to switch gears, and explain to me what you make of what I’ve said. Do you at least agree that if the modeler is solving a problem, then you ought to be able to write out a nontrivial problem? (Saying that the problem is to output a particular sentence won’t hack it. That would amount to saying that Dawkins wrote a “Hello, world!” program.)

  8. Mung Mung
    Ignored
    says:

    Tom, simply repeating yourself doesn’t help me. You brought up models and Weasel. Are you saying that you’re not talking about models and Weasels? Was your question about actual biological evolution itself and not computer models?

    If the model is searching for a solution to a problem, then what’s the problem?

    In the case of Dawkins’ Weasel, finding the target phrase in fewer attempts than it would take by random sampling of the space of all possible strings of the same length composed of combinations of the letters of the alphabet including the space character and ignoring case.

  9. Tom English Tom English
    Ignored
    says:

    You’ve written a post to say that you don’t understand what I was asking for, when you were supposed to write a post providing what I’d asked for. I need to give other stuff priority at the moment.

    I opened my laptop computer today, and found that I’d started to give you some advice on the other thread, several days ago. It went something like this: Start by defining a conventional problem, and showing how to solve it using an evolutionary process to sample the space of solutions. I know that you develop software (at least sometimes), and that you read books on evolutionary computation, so I have no doubt that you can do what I’ve just suggested. The challenge is to write out a comparable problem that a modeler might have been given, and to show how the modeler developed an evolutionary model in order to solve the problem. (What we ordinarily mean by problem solving is that we are given a problem, and then select a method for solving the problem. The choice of method depends on what problem is given, but the given problem does not depend on the method that we choose.)

  10. Tom English Tom English
    Ignored
    says:

    Mung:

    There is a difficulty I should mention. For computer scientists, a problem usually comprises a set of instances. And we usually characterize performance on the problem in terms of the worst-case or average performance over the instances.

    For Marks, Dembski, and Ewert, a problem specifies a sample space (the space of all possible solutions to the problem), along with a particular subset of the sample space (the set of actual solutions to the problem, which MDE call the target). A problem like this is silly if the specification of the target simply lists the elements. A problem that spells out the solutions is already solved. What makes sense is for a property of elements of the target to be specified, e.g., the target

        \[T = \{\omega \in \Omega \mid f(\omega) \geq \theta\}\]

    where the function f: \Omega \rightarrow [0, 1] is defined… and the threshold \theta = 0.9.

  11. Mung Mung
    Ignored
    says:

    OMagain, where are you?

    I also considered using Dawkins’ Weasel for my example, writing out a problem statement for it. But hasn’t it been done to death already? And what makes it fundamentally different from the all ones problem, really?

  12. OMagain
    Ignored
    says:

    aww, Mung, do you need an argument with me to distract from Tom seeing through you like a windowpane? Not going to happen I’m afraid. I saw your comment before I was logged in this once. If you want to say something to me you can PM me or ask someone to quote it so I can see it.

    Now, get back to Tom’s lesson why don’t you.

  13. Mung Mung
    Ignored
    says:

    OMagain: aww, Mung, do you need an argument with me to distract from Tom seeing through you like a windowpane?

    Just testing to see if you were interested in actual discussion. I have my answer.

  14. Corneel Corneel
    Ignored
    says:

    Mung: I also considered using Dawkins’ Weasel for my example, writing out a problem statement for it. But hasn’t it been done to death already? And what makes it fundamentally different from the all ones problem, really?

    It isn’t. Your example is a Weasel with a different target string. If I understand Tom correctly, this is not a proper problem, since the target element (i.e. the solution) is known beforehand.

  15. Mung Mung
    Ignored
    says:

    At the end of the day, we know evolution is not random or haphazard. Natural selection restricts the way that species can evolve, often constraining them to adapt in the same way when facing similar environmental circumstances. In some cases, there are single best biological solutions to problems posed by the environment, and in many cases, species repeatedly obtain these optima. …convergent evolution usually results from the conjunction of a limited number of optimal solutions and shared similarities in genetics, development, and ecology funneling adaptation in the same direction.

    – Improbably Destinies

    This is what biologists teach. Evolution as problem solving. Finding optimal solutions to problems posed to the organism. Thanks to natural selection.

  16. keiths keiths
    Ignored
    says:

    Mung,

    Instead of just barking like a trained seal at the sight of certain words, are you ever going to show us how the use of those words supports the claims of ID?

  17. Mung Mung
    Ignored
    says:

    keiths: Instead of just barking like a trained seal at the sight of certain words, are you ever going to show us how the use of those words supports the claims of ID?

    What does it have to do with ID?

    Evolutionists sell evolution to the public as a process of constant adaptation and improvement finding optimal solutions to problems. Is it any wonder the models they present to the public as shining examples of what evolution can do are search algorithms?

    Not to me it isn’t.

  18. keiths keiths
    Ignored
    says:

    Mung:

    What does it have to do with ID?

    That’s what I want to know. If the answer is “nothing”, then why all the barking?

  19. Mung Mung
    Ignored
    says:

    It is a fallacy to imagine that natural selection works by trying out, at random, all possible phenotypes until, by chance, it hits on the best one. Instead, natural selection is a process analogous to hill-climbing, in which the best phenotype is reached by a series of steps, each step leading to a type that is fitter than the previous one.

    – Evolutionary Genetics. John Maynard Smith. p. 7

    Unless it isn’t.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.