Improving performance of evolutionary algorithms with an ancestral cache

Today our department hosted a lunch for the graduate students to meet with the scientist who will be presenting during this afternoon’s department seminar, and I’m glad I went (not just for the pizza). This semester’s first speaker is actually a computer scientist–I’m pleasantly surprised since I’m in a genetics department. Anyway, it was a great chalk talk and I look forward to the formal presentation.

During lunch we chatted with the speaker about evolutionary algorithms. I first learned about evolutionary algorithms as an undergrad. Despite the term’s connotation, evolutionary algorithms have a lot more to do with computer science and problem solving in general than biology. The algorithms borrow ideas from evolutionary theory (such as mutation, fitness, and selection) to try to guess better solutions to a problem. If you have a population of potential answers to a solution, you can mutate that population, select potential solutions with desirable traits, and repeat the process. Over time, these algorithms have the capability to generate nearly-optimal solutions to problems that are otherwise very difficult to solve.

The main gist of the chalk talk is that you can improve the performance of an evolutionary algorithm by drawing from an ancestral cache. Essentially, the idea is that every once in a while, you mutate a solution by reaching back several generations and copying characteristics of an ancestral solution. When he first tried this approach, he got better results when pulling from grandparent- and greatgrandparent-solutions than from parent solutions. However, when he tried reaching back even further (hundreds or even thousands of generations back), the performance improvement was even more pronounced. We discussed possible analogs to evolutionary theory as it applies to living organisms (as opposed to problems formed in mathematical terms), one of which is a putative repair mechanism for Arabidopsis. Overall, it was a very interesting and fun discussion.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s