Possible application of Genetic Algorithms

[andrewkg]

Ok so I have a view ideas in mind for a project I was planning on doing involving genetic algorithms for my high school science fair class. I do have 3 mentors one a mathematician, a computer scientist who focuses on GAs, and a physicist who focuses on nano structures. here where I live, but before I go and talk to the GA mentor about my project in genetic algorithms I want to check on here and see if it would be even possible. So as to not make a fool of myself. So I have all of the background covered mostly I am just not quite well versed enough in GAs to decide how feasible this project is.

Well my ideas may not be very good but if you steal them I will find you! No that's more of a joke, but if by some chance they happen to be good please don't.

Project 1) Ok so I can across a problem that scientists currently facing with the formation of multi-layered graphene structures. And I though hmm I could use a GA the find possible solutions to this. By creating a population of methods for its formation and optimize or find a new solution. This is were I am unsure. Can you use this as the population? How will I apply mutations? How will I set the parameters for selection? In what ways it could go wrong? If you need more details about the project just ask.

Or would you guys suggest I do some non-linear programming to set up an equation. Then write a program to brute force a feasible approximation and work from there.

Oh yes I should add that I do have a way to test my possible solutions. I am working on constructing my own Scanning Probe Microscope.

Thank YOU!

 

[chiro]

Hey andrewkg.

You might want to get an idea about the computational complexity of genetic algorithms before you actually start a project on them.

If they are large enough, then it might not be feasible or practical enough to actually use. This is of course, one of the downsides of these algorithms.

 

[DrClaude]

Project 1) Ok so I can across a problem that scientists currently facing with the formation of multi-layered graphene structures. And I though hmm I could use a GA the find possible solutions to this.

That seems difficult, not to say impossible. One of the first things you need to do in any optimization is set up a cost functional, something that will give you a number that you want to minimize. In your problem, can you come up with an equation where given two sets of parameters, you get an output that will tell you which set of parameters gives a better result?

Even in the case where you find a way to construct a cost functional, you must also compute that functional. For example, if you need to calculate the interactions between the different layers of graphene, that part of the problem may be orders of magnitude more complex than the GA itself.

By creating a population of methods for its formation and optimize or find a new solution. This is were I am unsure. Can you use this as the population? How will I apply mutations? How will I set the parameters for selection? In what ways it could go wrong? If you need more details about the project just ask.

In a general way, as I hinted above, what you need is to define a set of parameters that affet the problem at hand and have a cost functional, whose value depends on these parmeters, that you want to minimize. Once that is done, the rest is pretty much a technical application of GAs, which you can program yourself if you want to keep it simple, or use a pre-written toolbox. Determining things like mutation rates, how to produce offsprings, population size, and so on, will require tweaking depending on the problem.

Oh yes I should add that I do have a way to test my possible solutions. I am working on constructing my own Scanning Probe Microscope.

How much time to you have for this project? If you connect the GA to an experiment, consider that the number of cost functional evaluations you need to do can easily number in the thousands. If the number of experiments you can carry out is small, GAs are definitely not the way to go. I guess this is what chiro was hinting at.

 

[andrewkg]

Well I have about 16 months. During the school year I can put in 5 hours & on weekend more.

If they are large enough, then it might not be feasible or practical enough to actually use. This is of course, one of the downsides of these algorithms.

When you say these algorithms is there another type that you know of that could be more effective for this project?

So do you think there is no way they could be effectively used. I have a whole book about how they are used to atomic structure prediction of nano structures. And it would seem that is equally complex of a task.

Thanks for the response!

 

[chiro]

I don't know anything about your project or the areas you have mentioned in enough detail so I can't really comment on that.

One thing I would however recommend you do, is to get a book on computational complexity that specifies a list of various algorithms and data structures and see what the complexity is for various parameters.

By doing this you will become familiar with the various modes of computation and you'll be able to get an idea of when a particular form of computation becomes intractable or computationally un-feasible.