A 'hands on' strategy for teaching genetic algorithms to undergraduates

Genetic algorithms (GAs) are a problem solving stra tegy that uses stochastic search. Since their introduction (Holland, 1975), GAs have proven to be particularly useful for solving problems that are ‘intractable’ using classical methods. The la nguage of genetic algorithms (GAs) is heavily laced with biological metaphors from evolutionary literature, such as population, chromosome, crossover, cloning, mutation, genes and generati ons. For beginners studying genetic algorithms, there is quite an overhead in gaining comfort w ith these terms and an understanding of their par- allel meanings in the unfamiliar computing milieu of an evolutionary algorithm. This paper describes a ‘hands on’ strategy to introduce and teach gene tic algorithms to under- graduate computing students. By borrowing an analogical model from senior biology classes, poppet beads are used to represent individuals in a population (Harrison, 2001). Described are several introductory exercises that transport stude nts from an illustration of natural selection in Biston betula moths, onto the representation and solution of differing mathematical and comput- ing problems. Through student manipulation and interactions with poppet beads, the exercises cover terms such as population, generation, chro mosome, gene, mutation and crossover in both their biological and computing contexts. Importantly, the tasks underline the two key design is- sues of genetic algorithms: the choice of an appr opriate chromosome representation, and a suit- able fitness function for each specific instance. Finally, students are introduced to the notion of schema upon which genetic algorithms operate. The constructivist model of learning advocates the us e of such contextual problems to create an environment where students become active partic ipants in their own learning (Ben-Ari, 1998; Greening, 2000; Kolb, 1984). In itial student feedback about these “hands on” exercises has been enthusiastic. As well, several st udents have made reference to the lessons learnt as the basis for GA coding in subsequent open-e nded assignments. It seems that once the hurdle of becoming familiar with GA terminology has been surmounted , students find genetic algorithms to be par- ticularly intriguing for their uncanny ability to solve incredibly complex problems quickly and proficiently (Moore, 2001)