Loading ...
Sorry, an error occurred while loading the content.

Using GP to find efficient algorithms.

Expand Messages
  • Conan K Woods
    Hi, I m wondering if there has been any work on using GP s to discover efficient algorithms. For example, has there been any/many attempts to evolve a sorting
    Message 1 of 3 , Nov 24, 2005
    • 0 Attachment
      Hi, I'm wondering if there has been any work on using GP's to discover
      efficient algorithms. For example, has there been any/many attempts to
      evolve a sorting algorithm(Could a computer discover quicksort or better on its
      own)? Have any of these attempts been successful?

      Conan K Woods
    • Lee Spector
      The GP bibliography (http://liinwww.ira.uka.de/bibliography/Ai/ genetic.programming.html) returns 21 hits for sorting , many of which touch on the issues you
      Message 2 of 3 , Nov 29, 2005
      • 0 Attachment
        The GP bibliography (http://liinwww.ira.uka.de/bibliography/Ai/
        genetic.programming.html) returns 21 hits for "sorting", many of
        which touch on the issues you asked about (some on sorting networks,
        but also some on the evolution of more traditional sorting
        algorithms). There's a lot of other work using efficiency components
        in fitness functions, often without making a big deal of it in the
        publications -- this goes back at least to Koza's 1992 book, where he
        uses an efficiency fitness component in a block-stacking problem (and
        maybe others). As to whether any of this is "successful" -- some of
        it clearly is, but there's definitely more to be done.

        On a probably-wacky tangent, work on evolution of quantum algorithms
        has been almost entirely about evolving (quantum) efficiency... but I
        don't think this is what you were looking for.

        I hope this helps.

        -Lee


        On Nov 24, 2005, at 5:35 PM, Conan K Woods wrote:

        > Hi, I'm wondering if there has been any work on using GP's to discover
        > efficient algorithms. For example, has there been any/many
        > attempts to
        > evolve a sorting algorithm(Could a computer discover quicksort or
        > better on its
        > own)? Have any of these attempts been successful?
        >
        > Conan K Woods
        >
        >
        >
        >
        >
        > SPONSORED LINKS
        > Computer science distance education Computer science course
        > Computer science school
        > Computer science degree Computer science and education Computer
        > science education
        >
        > YAHOO! GROUPS LINKS
        >
        > Visit your group "genetic_programming" on the web.
        >
        > To unsubscribe from this group, send an email to:
        > genetic_programming-unsubscribe@yahoogroups.com
        >
        > Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service.
        >
        >

        --
        Lee Spector, Professor of Computer Science
        School of Cognitive Science, Hampshire College
        893 West Street, Amherst, MA 01002-3359
        lspector@..., http://hampshire.edu/lspector/
        Phone: 413-559-5352, Fax: 413-559-5438
      • Pradeep
        Hi, There has been work in trying to evolve sorting algorithms through the use of GP. But the focus was generally on evolving algorithms that worked, for all
        Message 3 of 3 , Nov 29, 2005
        • 0 Attachment
          Hi,

          There has been work in trying to evolve sorting algorithms through the use of GP. But the focus was generally on evolving algorithms that worked, for all input cases, rather than trying to evolve some thing that was better than existing algorithms.

          see http://citeseer.ist.psu.edu/kinnear93evolving.html

          Trying to evolve efficient algorithms would prove really computationally intensive, compared to evolving solutions that just worked. Mostly because, comparison of efficiency would usually mean lots of empirical testing.

          Pradeep

          Conan K Woods <woodsc@...> wrote: Hi, I'm wondering if there has been any work on using GP's to discover
          efficient algorithms. For example, has there been any/many attempts to
          evolve a sorting algorithm(Could a computer discover quicksort or better on its
          own)? Have any of these attempts been successful?

          Conan K Woods





          SPONSORED LINKS
          Computer science distance education Computer science course Computer science school Computer science degree Computer science and education Computer science education

          ---------------------------------
          YAHOO! GROUPS LINKS


          Visit your group "genetic_programming" on the web.

          To unsubscribe from this group, send an email to:
          genetic_programming-unsubscribe@yahoogroups.com

          Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service.


          ---------------------------------






          ---------------------------------
          Yahoo! Music Unlimited - Access over 1 million songs. Try it free.

          [Non-text portions of this message have been removed]
        Your message has been successfully submitted and would be delivered to recipients shortly.