fairfolio
Saved Projects

Evolving Near Optimal Solutions to Computationally Hard Problems Using Natural Selection

CSEF · 2017 Mathematical Sciences Second Award

Hunter D. Ruebsamen · Marine View Middle School, Huntington Beach, Orange County

Overview

Objectives/Goals Determine if processes of natural selection can be applied to non-biological or simulated entities to produce nearly optimal solutions to a variety of computationally hard problems in a reasonable amount of time. Methods/Materials Desktop computer with Processing Compiler/IDE, Processing.js extension and Chrome browser. I developed my own algorithms using research on the internet, for my 3rd problem of evolving locomotion in virtual agents, I borrowed from some open-source code published by Cary Huang and extensively modified it. Results Three different problems were easily solved using the algorithm I devised. Results show nearly optimal solution to Linear Regression Problem in as little as 5 generations and Traveling Salesman Problem of 350 cities produced near optimal results after 200 generations and evolving locomotion in virtual creatures produced good results within 300 generations of evolution. Conclusions/Discussion I developed an algorithm based on natural selection that can be used to find near optimal solutions to a variety of complex problems in a reasonable amount of time. I show that it is not only possible for simulated evolution to work with non-biological entities, but also demonstrate that evolution can produce solutions to computationally complex problems that are difficult or impossible to solve using traditional methods or exhaustive search.

Summary statement

Using simulated evolution to generate near optimal solutions for computationally complex problems

Help received

I learned about Linear Regression in my Algebra class. I researched the Traveling Salesman Problem online and the code for my locomotion of virtual creatures was based on open source code by Cary Huang and modified by myself. The simulated evolution algorithm was programmed by myself after research on

Awards (1)

Competition history

  • CSEF 2017 Mathematical Sciences · Entry J1507

Resources

Related projects

Closest projects by meaning, across every fair and year in the corpus.

Browse more like this

Source: California Science & Engineering Fair public projects

Save projects to your library

Sign in with Google to keep track of projects you find interesting, organized into folders. An account also raises your daily allowance for “Has this been done?”, and lets you create a key for the MCP server with a much higher limit than anonymous use. Browsing stays public.

Continue with Google