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

By Venables, Anne; Tan, Grace | Journal of Information Technology Education, Annual 2007 | Go to article overview
Save to active project

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


Venables, Anne, Tan, Grace, Journal of Information Technology Education


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.

The rest of this article is only available to active members of Questia

Sign up now for a free, 1-day trial and receive full access to:

  • Questia's entire collection
  • Automatic bibliography creation
  • More helpful research tools like notes, citations, and highlights
  • Ad-free environment

Already a member? Log in now.

Notes for this article

Add a new note
If you are trying to select text to create highlights or citations, remember that you must now click or tap on the first word, and then click or tap on the last word.
Loading One moment ...
Project items
Notes
Cite this article

Cited article

Style
Citations are available only to our active members.
Sign up now to cite pages or passages in MLA, APA and Chicago citation styles.

Cited article

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

Settings

Typeface
Text size Smaller Larger
Search within

Search within this article

Look up

Look up a word

  • Dictionary
  • Thesaurus
Please submit a word or phrase above.
Print this page

Print this page

Why can't I print more than one page at a time?

While we understand printed pages are helpful to our users, this limitation is necessary to help protect our publishers' copyrighted material and prevent its unlawful distribution. We are sorry for any inconvenience.
Full screen

matching results for page

Cited passage

Style
Citations are available only to our active members.
Sign up now to cite pages or passages in MLA, APA and Chicago citation styles.

Cited passage

Welcome to the new Questia Reader

The Questia Reader has been updated to provide you with an even better online reading experience.  It is now 100% Responsive, which means you can read our books and articles on any sized device you wish.  All of your favorite tools like notes, highlights, and citations are still here, but the way you select text has been updated to be easier to use, especially on touchscreen devices.  Here's how:

1. Click or tap the first word you want to select.
2. Click or tap the last word you want to select.

OK, got it!

Thanks for trying Questia!

Please continue trying out our research tools, but please note, full functionality is available only to our active members.

Your work will be lost once you leave this Web page.

For full access in an ad-free environment, sign up now for a FREE, 1-day trial.

Already a member? Log in now.

Are you sure you want to delete this highlight?