Skip to content

4. Algorithm

Jump to bottom Edit New page
Georgi Krastev edited this page Jul 21, 2015 · 3 revisions

Tabu Search

Tabu search is a pluggable heuristic search algorithm that can be successfully applied as a basis for many domain-specific optimization problems [1]. [2], [3]. As a heuristic, it can't guarantee that a globally optimal solution will always be found, but it will always find at least a local optimum of the objective function.

The basic idea of the search routine is that it climbs towards a local maximum and keeps a limited number of traversed states as history, in order to reduce the memory requirements of the program. The history is then used in a domain-specific way to prohibit (make tabu) similar states to those already visited, in order to keep exploring the search space instead of revisiting old solutions. Also, aspiration criteria have to be defined for lifting this restriction whenever it would prevent the algorithm from finding a better solution. The last component of tabu search is to define transitions (moves) between different states in the domain and an objective function to evaluate those states, that will be maximized by the algorithm.

Tabu criteria

We considered two options for the tabu criteria. The first one is to keep timestamps for every student that track the latest movement. Then moving a student would be prohibited for the next n steps. This is the strategy used by R. Hübscher. However, this would almost certainly have a prohibitive effect on dropping and filling groups (see moves below), because these moves involve a whole set of students. The other option which we use in the final implementation, is to build a bounded tabu queue that contains the latest n moves and prohibits similar moves, e.g. swapping the same 2 students, switching the same student or dropping / filling the same group.

Aspiration criteria

The aspiration criteria define when the tabu criteria can be violated, in order to reach a better solution. In this case, we use the simplest strategy - the best ever aspiration criteria, which applies whenever the move in question would lead to the best solution found so far with respect to the objective function.

Objective Function

This section explains in more detail the composition of the objective function that the matching algorithm tries to maximize.

Definitions

First, some common definitions:

  • IG : Index of group IDs
  • IS : Index of student IDs
  • G = { Gi | i ∈ IG } : Set of groups
  • S = { Si | i ∈ IS } : Set of students
  • K* : Set of all skills
  • Kg ⊆ K* : Set of global skills (per course)
  • K = { Ki | i ∈ IG, Ki ⊆ K* } : Set of skills per group
  • M = { Msk | s ∈ IS, k ∈ K* } : Skill matrix (sparse)
  • P = { Psg | s ∈ IS, g ∈ IG } : Preference matrix (sparse)

Components

So far we have the following components to the objective function out of the box. More can be added later on. Every component is calculated separately over the current assignment, and then the values are combined into a total score, by multiplying them with the global weights provided in the algorithm configuration. A global weight of 0 will turn off the respective criterion altogether.

Note that some criteria are global (i.e. calculated over the whole assignment) whereas others are local (calculated per student and summed up). The objective function is well defined only when a single global criterion is used. On the other hand, local criteria allow for specifying fine grained per student weights to improve the performance of the solver.

  • Maximally Diverse (global)

    Optimizes for groups with maximal diversity with respect to available skills. The assumption here is that knowledge sharing between peers improves with increasing difference in experience and expertise across subjects. Note that this is a global criteria. Only one of those should be used at a time.

    maxDiverse = \sum_{i \in I_G} \sum_{s' \in G_i} \sum_{s'' \in G_i} \sum_{k \in K^g \cup K_i} | M_{s'}k - M{s''}_k |

  • Evenly Skilled (global)

    Optimizes for groups with evenly distributed skills. The assumption here is, that in order to maximize the learning objective, all relevant skills in the groups need to be well represented. In this way, students are likely to pick up the skills that the course was designed to convey. Note that this is a global criteria. Only one of those should be used at a time.

    C = \big{ \min_{i \in I_G} \max_{s \in G_i} M_s_k | k \in K^* \big}

    evenlySkilled = \big( \min_{k \in K^} C_k \big) \sum_{k \in K^} C_k

  • Friends and Foes (local)

    We also want to allow students to specify friends, with which they would like to be in the same group. For completeness, we show the formula that works for friends and foes, but the algorithm doesn't expose the foes functionality. This is a local criterion, so per student weights are supported.

    F_{s'}_{s''} = \begin{cases} -w' & \text{if s'' is a foe of s'} \ 0 & \text{if s' doesn't care about s''} \ +w' & \text{if s'' is a friend of s'} \end{cases}
    where w' is the local weight of student s' on this criterion.

    friendsFoes = \sum_{i \in I_G} \sum_{s' \in G_i} \sum_{s'' \in G_i} F_{s'}_{s''}

  • Group Preferences (local)

    One of the classic optimization criteria for solving the assignment problem is letting students express their preferences for a group. In this implementation, we also consider this factor, but it's not a strict requirement to have stable pairs. Also, we opted for a weighted map of preferences instead of an ordered list for more flexibility. In this setup, stable pairs don't make sense any more. Note that this is a local criterion, so per student weights are supported.

    groupPrefs = \sum_{i \in I_G} \sum_{s \in G_i} w P_s_i
    where w is the local weight of student s on this criterion.

Moves

In our implementation of the tabu search algorithm, we allow the following moves (transitions) between valid student-group assignments.

  • Swap: swap(s1: Student, s2: Student)

    Simply swap the (current) places of 2 students (in different groups). It's also a valid move to swap a student in a group with a student in the waiting list, although in this case the subject shouldn't be mandatory for the student going to the waiting list.

  • Switch: switch(s: Student, g: Group)

    Move a student from his current group to another one. After the move has been performed, the minimal and maximal group size requirements of both the old and the new group have to be fulfilled. It's also valid to switch a non-mandatory student to the waiting list and a student from the waiting list to a regular group.

  • Drop Group: dropGroup(g: Group)

    Drop a group from the course and move all students currently assigned to it to the waiting list. This move is only valid, if the group to be dropped is not mandatory for the subject.

  • Fill Group: fillGroup(g: Group, ss: Set[Student])

    Fill an empty group with students from the waiting list. The number of students should be equal or greater than the minimum size and equal or less than the maximum size of the group.

References

  1. R. Hübscher, Assigning Students to Groups Using General and Context-Specific Criteria.
  2. F. Glover and M. Laguna, Tabu Search, Kluwer Academic, 1997.
  3. F.W. Glover and G.A. Kochenberger, Handbook of Metaheuristics, eds. Springer, 2003.
Add a custom footer
Add a custom sidebar

Clone this wiki locally