Genetic Algorithm enrichment lesson
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 &amp; limitations.