A 'Hands On' Strategy for Teaching Genetic Algorithms to Undergraduates

Article excerpt

Introduction

The study of data structures and their algorithms is fundamental in most undergraduate information technology and computer science programs and this can be simply evidenced by nearly 42,000 Google hits on the term "data structures course". Renown for his seminal works in the field, Donald Knuth (Softpanorama, 2006) is credited with saying "Languages come and go, but algorithms stand the test of time". Others, like Alan Kay (2006), argue that many of the ideas that are presented in computing have become dated and that "almost nothing exciting about computing today has to do with data structures and algorithms". We suggest that by introducing genetic algorithms (GAs) in our undergraduate computing programs, it is possible to still pay reverence to classical problems and their traditional algorithmic solutions whilst capturing the imagination of our students.

Genetic algorithms are a problem solving strategy that uses stochastic search. Since their introduction in 1975 (Holland, 1975), GAs have proven to be particularly useful for solving problems that are "intractable" using classical methods. In such situations, the problem is viewed as a landscape upon which possible solutions may be found. As seen in Figure 1, an individual solution is located and represented by its coordinates. For optimisation problems, where one is looking for the highest hill or the lowest valley, it can be seen that some individual solutions are better located than others. Borrowing heavily from the language of biological evolution, these solutions/ individuals are said to be the fittest in a population of competing solutions. Then over successive iterations, the GA evolves the population of competing solutions until it becomes a population of consistently very fit individuals, as seen in Figure 2.

[FIGURE 1 OMITTED]

[FIGURE 2 OMITTED]

To better describe the process that is a genetic algorithm, one relies even more heavily upon the biological metaphor. In a GA, each possible solution is coded using a data structure known as a chromosome. A chromosome is composed of a string of genes, each gene representing a specific input variable. Collectively the genes are used to evaluate the fitness of an individual solution. Then, proportional to their specific fitness value, chromosomes are allowed to reproduce using the genetic operators of crossover and mutation. So the fittest chromosomes are more likely to reproduce and contribute to the next generation of chromosomes whereas less fit individuals eventually become lost to future generations. Over successive iterations, the average fitness of the whole population improves and the genetic algorithm can be expected to breed an optimal solution to the problem (Negnevitsky, 2005).

For beginners with little or no exposure to the language of evolutionary literature, there is a considerable overhead of understanding genetic terminology and the underlying biological concepts as applied in a GA. However, if the hurdle of becoming familiar with the language can be surmounted, students find genetic algorithms to be particularly intriguing for their uncanny ability to solve incredibly complex problems quickly and proficiently (Moore, 2001). This paper outlines a strategy to quickly overcome student unfamiliarity with the biological concepts and language used in genetic algorithms. Perhaps not surprisingly, the approach has been borrowed from introductory genetics courses and it has undergone modification as to situate it more naturally for computing students.

The "Hands On" Strategy

[FIGURE 3 OMITTED]

To introduce genetic algorithms to computing students, an analogical model is used. As described by Harrison (2001), an analogical model is one that helps "people visualise the objects and processes which they are trying to understand" and these models typically use "a familiar object or experience to inform the learner about new and poorly understood objects, processes or concepts. …