Computer Science 499 / 001

Metaheuristics

Meets

Tuesday, 4:30-7:10 PM, in Room 253 of Krug Hall.

Professor

Prerequisite

CS310.

What in the world is a Metaheuristic?

Let's say you have a problem and you don't know the answer: you don't even know how to go about finding the answer: but you do know a good answer when you see it. For example, imagine if you were trying to find a good simulated robot soccer player. You have a procedure for building arbitrary players; and you have a simulator in which to test them and give them a grade (maybe by playing them against each other). But you don't have any idea how to build good players. You can provide these tools to a metaheuristic algorithm to search for a solution automatically! For example, you could use a genetic algorithm to “breed” solutions inside the computer for you. Or have a particle swarm optimization algorithm deploy virtual swarms to hunt for the solution.

Experiments in metaheuristics can be expensive, especially if your test procedure (such as the robot simulator above) is slow. The department has a small supercomputer cluster (about 60 multi-core nodes), and the instructor expects that students will be given special access to this cluster to do experiments. Projects will be typically be in Java, and other languages if so negotiated.

Feel free to contact the instructor with any questions you have about this course.

About the Class

This course will cover techniques and algorithms in metaheuristics. Techniques may include, among others, evolutionary computation, particle swarm optimization, ant colony optimization, estimation of distribution algorithms, coevolution, simulated annealing, tabu search, and hill-climbing. Topics may include: multiagent metaheuristics, exploration and exploitation, bloat, quality assessment, stochastic optimization with constraints, distributed techniques (island models, distributed evaluation), and multiobjective optimization.

Course Web Page

http://cs.gmu.edu/~sean/cs499/

Texts

There are no textbooks. We'll be using various papers and lecture notes.

Grading

This course will consist largely of several large projects and two exams. The breakdown will be approximately: 1. Homework and (several) Projects: 50% with higher weight given to harder projects. 2.Exams (2 of them): 25% Each

Course Outcomes

1. An ability to employ a variety metaheuristic algorithms. 2. An ability to identify problems and determine what kinds of search and optimization techniques are appropriate for them (or if any are), and what issues are involved in the design and parameter-turning of such metaheuristics. 3. An ability to implement such algorithms to real problems on distributed computational environments.