Tournament Selection

I was writing some code this week and used a technique called tournament selection. Tournament selection is useful when you have a collection of objects and you want to select one relatively good (but not necessarily best) object from the collection. Tournament selection is often used in Genetic Algorithms to select two good individuals from a population in order to use them to produce two new child objects. Suppose you have 8 student objects and their goodness is based on a GPA field:

ID = 001, GPA = 2.5
ID = 002, GPA = 3.3
ID = 003, GPA = 2.8
ID = 004, GPA = 3.7
ID = 005, GPA = 2.0
ID = 006, GPA = 1.9
ID = 007, GPA = 4.0
ID = 008, GPA = 3.6

The basic idea of tournament selection is to first choose a random subset of the entire set, then pick the best object from the subset. The first question is how big the subset should be. This is often controlled by a variable called tau. Suppose tau is 0.4 — this means the subset is 0.4 of the size of the original set. So in this example, 0.4 * 8 = 3.2 -> 3. Now we select three random students, suppose they are 003, 005, and 008. The best of these three is 008 with a GPA of 3.6. Notice that 008 is a good student but not the best. The larger tau is, the larger the subset, and the more likely you are to get the absolute best object. Coding up tournament selection is surprisingly tricky.

This entry was posted in Machine Learning, Software Test Automation. Bookmark the permalink.