Genetic Algorithm enrichment lesson

Question

As a special lesson, I would like to show students the very basic idea of genetic\evolutionary algorithms. I let them play a bit in a genetic algorithm online game, to get the idea.

Then I teach them the main concepts (Population, individual with genes, mutation, crossover, fitness etc.) and I introduce the Traveling Salesman Problem. Then I go through solving TSP with genetic algorithm with them, so they see it in action and in practice. However I'm out of practice exercises.

So, I am looking for problems that have a solution which can vary in its "goodness", and its goodness can be judged by some requirements. To explain this, take the example of a timetable for tests over a month. a solution is a random time table. a good solution is one where tests are suffeciently spaced so that students have time to revise. in the game, a solution is just any vehicle, but a good solution, is one that gets far.

Note: I am not necessarily looking for an answer that shows any previous knowledge about genetic algorithms (though it is appreciated ;)), just any problem as described above.

What kinds of exercises\problems such as those are used?

The students are high-school students learning in java, and they are familiar with OOP.

Answer 1

Classification problems are reasonable candidates. For instance, I wrote a GA that looked at the mushroom dataset taken from the UCI Machine Learning Repository with the goal of classifying an unknown mushroom as safe or poisonous based on its traits. Each candidate solution encoded a series of rules (Red cap means poisonous, blue spores are safe). During the learning phase I used a portion of the dataset, but to perform the final evaluation I used the full set.

That particular dataset might not be well suited to the high-school level, as it has missing values on some entries, but there are a lot of other datasets. Also, numerical data is generally easier to encode than categorical data. That being said, it was a fun dataset to use - "Hey look, after fixing that bug my GA poisons us 15% less often!"

Beyond that, it might be worth deliberately looking at a variety of problems including some that are poor candidates for GAs in order to demonstrate their relative strengths & limitations.

Answer 2

I'm adding an answer to show what sort of things I'm looking for.

An example of such a problem could be fitting coefficients for a polynomial​ function. We have a dataset of (X,Y), and the highest power of the polynomial. Then a solution is a set of numbers (number of parameters is the highest power).

The fitness of a solution could be

fitness := 1.0/(sum(dataset's Y - polynomial's Y, for each X in dataset))

This is an introductory genetic algorithm to give the idea, before going into more complex exercises.