Wednesday, February 16, 2011

Algorithms in Action: Genetic Algorithm

  Artificial intelligence uses a great number of algorithms to perform various functions required by the AI. An algorithm is a structured set of logical instructions to reach some solution to a problem. One such algorithm is a genetic algorithm, a search heuristic that mimics heredity to explore various solutions based on the fitness, or correctness, of each element in a generation. Heuristics are experience based approaches that utilize previous knowledge for problem solving or learning, such as a rule of thumb or trail and error. BoxCar2D has been created to give a very good visual on how the genetic process works.
  Genetic algorithms follow a flow not unlike biological genetics to simulate evolution of a system. An initial population is created, generally randomly, and each element of that population is set through a fitness test. After these tests are run, a percentage of the population that is deemed most fit is selected and allowed to "breed." This select division of the population mix portions of their code together to generate a new population of children that will hopefully improve overall fitness of the new population. Along with the mixing of the genetic code the algorithm can introduce mutations to a percentage of the next generation, randomizing different segments of the code to introduce new traits and to prevent an evolutionary dead end.
BoxCar2D in action
  In the BoxCar2D simulation, the user can specify a few traits of the car and watch it evolve. The fitness testing of the car is based on how far the car can go and how fast. The best few are selected and pass on their traits to the next generation and the pattern continues. The user can affect the selected traits by up or down voting cars and changing the mutation rate, which can affect body shape, wheel size, or wheel placement. The graph that populates gives the user a look at how the generations do on average compared to the fitness threshold for it. Take it for a drive and see how it works.

7 comments:

  1. That was fun, a great analogy for biological evolution. Looking at the best car list, different environments, or tracks, foster different characteristics for the optimal car design. What is very cool is that the top three scores for a certain track have very similar characteristics, even though they may have evolved from completely different ancestors.

    ReplyDelete
  2. My friend showed this algorithm to me last weekend. I let in run on my computer for two days, and at the end of the two days, the cars were getting really good. It is really cool that we can use computers to simulate evolution and natural selection. What will they think of next?

    ReplyDelete
  3. This is really neat. One major component that the car model lacks in the correlation to biological evolution is whether the traits are heritable or able to be passed down to the next generation. Obviously that doesn't apply to a car made with vectors and circles but that seems to me to be a logical next step in making it like the biological process. I really like this idea though, very interesting

    ReplyDelete
  4. So, you got great comments on this post, which is excellent!

    Of course, a layperson could ask, what's an algorithm? What's a heuristic?

    In other words, there's still a lot of jargon here that some of your classmates get but that may need more explanation for the rest of us. Thanks!

    ReplyDelete
  5. Jen,

    I edited the post to include information about what algorithms and heuristics are. Hopefully, they can clear up any confusion someone might run into for the post.

    ReplyDelete
  6. I found this a little while ago and have since spent many many hours watching this website. I find it interesting how "recent" developments in AI have moved towards simulating biological systems instead of reinventing the wheel. Very fascinating!

    ReplyDelete