Genetic programming/algorithms

Ask questions about projects relating to: computer science or pure mathematics (such as probability, statistics, geometry, etc...).

Moderators: MelissaB, kgudger, Ray Trent, Moderators

Genetic programming/algorithms

Postby epwaotl » Sun Aug 15, 2010 3:33 pm

I have heard about the use of genetic programming and algorithms (I will use the abbreviation gp for genetic program) in relation to physics computer simulations. As I understand it you put down your guidelines/requirements (the characteristics that you want the final generation to have). The gp in conjunction with simulation software will create a the first generation of a population. Each individual is a mutation of others so each is different. Then using the simulation each individual is tested and assigned fitness (how closely it comes to your original guidelines/requirements). A second generation is created by combining individuals of the previous generation that had high fitness and creating new mutations. This process is then repeated multiple times until an individual in the final generation reaches or surpasses the original guidelines/requirements.
This seems like a powerful tool for optimizing designs, yet I have only heard of 5 cases where this was used. i would have thought that this would be very popular. I can only think of a few reasons why this is not the case. 1 it might be difficult to write gp. 2 requires simulation software that is not readily available. 3 require powerful computers not readily available.

Can anyone give me more information about genetic programming? If my basic understanding of how genetic programming works please correct me. If the few reasons that I put forth for the apparent unpopularity of gp are incorrect again please correct me.

I am interested in using gp to optimize some of my designs for a science fair project and what to know if it would be feasible. If so any suggestions on how to pull it off would be most appreciated.

Thank you for your help.
epwaotl
 
Posts: 30
Joined: Sun Sep 14, 2008 8:54 am
Occupation: student
Project Question: n/a
Project Due Date: n/a
Project Status: Not applicable

Re: Genetic programming/algorithms

Postby epwaotl » Sat Aug 21, 2010 6:18 pm

Does no one know anything else about genetic programing? Does anyone know of any other place/person I could ask who knows about genetic programming?

Thanks
epwaotl
 
Posts: 30
Joined: Sun Sep 14, 2008 8:54 am
Occupation: student
Project Question: n/a
Project Due Date: n/a
Project Status: Not applicable

Re: Genetic programming/algorithms

Postby mpphlipot » Mon Aug 23, 2010 6:05 pm

Hi epwaotl,
Sorry that no one has gotten back to you. I guess that may be some indicator that no one here knows much about GP. Me included. I only have peripheral knowledge on the subject from judging a few projects at science fairs. But, given that, I can tell you that there are at least a few people out there using it. If nothing else, then for research projects.

I did some internet searching to educate myself a little more before replying to you. I found a site that appears to have a really good tutorial for GP. See http://www.geneticprogramming.com/Tutorial/index.html. In particular, note the flowchart they have for genetic programs. Not terribly complicated as you look at it but when you start reading the details it gets pretty hairy.

Also note that it makes a distinction between genetic programming and genetic algorithms. Genetic algorithms try to find an optimum data set. Genetic programming is a specific niche of GA where the data set is made up of programs. That is, GP attempts to find an optimum program from a population of random programs that mutate over time. You keep evolving the program until you find the best program that works. Looking at the description you gave, you appear to be describing GA rather than GP.

Carnegie Mellon has an FAQ on GA at http://www.cs.cmu.edu/Groups/AI/html/fa ... c/top.html. In particular, look at the answer to What’s a Genetic Algorithm at http://www.cs.cmu.edu/Groups/AI/html/fa ... doc-2.html.

Depending on how complicated your problem is, I don’t think it would be too difficult to write your own GA, which means you wouldn’t have to depend on other simulation software. I also think run-of-the-mill computers of today would be able to handle a simple-to-medium level GA. It all comes down to what is the problem you’re trying to solve.

Take a look at these links and click around those sites for additional info. If you have more questions after that, post them back here and we’ll try to help out.

Mike
mpphlipot
Former Expert
 
Posts: 79
Joined: Thu Nov 06, 2008 5:31 pm
Occupation: Operations Manager
Project Question: n/a
Project Due Date: n/a
Project Status: Not applicable

Re: Genetic programming/algorithms

Postby mpphlipot » Mon Aug 23, 2010 6:10 pm

Here are what look like a couple other good URLs on GP, too:

http://www.genetic-programming.org/
http://www.well.com/~xanthian/link_page ... mming.html
mpphlipot
Former Expert
 
Posts: 79
Joined: Thu Nov 06, 2008 5:31 pm
Occupation: Operations Manager
Project Question: n/a
Project Due Date: n/a
Project Status: Not applicable

Re: Genetic programming/algorithms

Postby chpolack » Thu Sep 02, 2010 3:04 pm

epwaotl,

I have some experience with Genetic Algorithms and Genetic Programming from my previous science fair projects.

If what you are looking for is information/research, I would look for information written by John Koza, a computer scientist who expanded greatly on the idea of genetic programming. A good book about Genetic Programming is called "Genetic Programming" written by John R. Koza. This book goes it to much detail about Genetic Programming in many applications.

Genetic Programming is a specialization, or type, of evolutionary algorithm (mathematical pattern). In an evolutionary algorithm, the solutions to the given problem are evolved. When the program starts, random solutions to the problem are created.The algorithm then analyzes those solutions to see which solves the problem the best, and assigns it a value known as a fitness score. The best solution to the problem is carried over into the next "generation", while all of the other solutions are discarded. The best solution from the previous generation is now multiplied and mutated, to form many more different versions of the original. Once again the best solution out of these new solutions is used in the next generation. This process repeats many times, and in Genetic Programming with the processing power of computers this happens about 200 times every minute. With an evolutionary algorithm, the answer always gets more precise, because only solutions that were better than the previous best are kept.

To see how Genetic Programming works first hand, visit this website below. This Genetic Programming applet uses a genetic programming algorithm to create a linear equation to solve the problem. In this case, the problem is a line consisting of 10 x and y values plotted on a graph. The Genetic Programming applet tries to make an equation to match this line as closely as possible, using hundreds of generations of solutions.

http://alphard.ethz.ch/gerber/approx/default.html

If you have any more questions, feel free to ask me.

Hope this Helps!

-Chris
chpolack
Former Expert
 
Posts: 2
Joined: Fri Aug 20, 2010 10:20 am
Occupation: Volunteer/Expert
Project Question: n/a
Project Due Date: n/a
Project Status: Not applicable

Re: Genetic programming/algorithms

Postby epwaotl » Tue Sep 28, 2010 12:28 am

Thanks for all the help so far.
It seems to me that in addition to the fitness testing and reproduction part of the program a simulation program is required as well. Does one have to write the simulation program as well or can one use a preexisting simulation program and add on the genetic program part?
Thanks
epwaotl
 
Posts: 30
Joined: Sun Sep 14, 2008 8:54 am
Occupation: student
Project Question: n/a
Project Due Date: n/a
Project Status: Not applicable

Re: Genetic programming/algorithms

Postby hhemken » Tue Sep 28, 2010 10:22 am

epawotl,

What do you mean by simulation program, the part that does all of the GP stuff (mutating "genomes" and creating new instances), the one that tests each instance for fitness, or some overall program to make it all work? What do you have so far? Are you willing or able to do any light programming on your own?
Heinz Hemken
Mentor
Science Buddies Expert Forum
hhemken
Expert
 
Posts: 264
Joined: Mon Oct 03, 2005 3:16 pm

Re: Genetic programming/algorithms

Postby epwaotl » Wed Apr 06, 2011 5:01 pm

I meant the program that would test the fitness of an instance. In my case it would most likely be some sort of CFD.
As for programming I am able to program but a CFD is beyond my abilities.
epwaotl
 
Posts: 30
Joined: Sun Sep 14, 2008 8:54 am
Occupation: student
Project Question: n/a
Project Due Date: n/a
Project Status: Not applicable

Re: Genetic programming/algorithms

Postby hhemken » Wed Apr 06, 2011 5:47 pm

CFD is Computational Fluid Dynamics, or what?
Heinz Hemken
Mentor
Science Buddies Expert Forum
hhemken
Expert
 
Posts: 264
Joined: Mon Oct 03, 2005 3:16 pm


Return to Grades 9-12: Math and Computer Science

Who is online

Users browsing this forum: No registered users and 1 guest