4

I am developing a timetabling application. What are the relative advantages of genetic algorithms vs simulated annealing?

I have these points specific to my situation:

  1. At a single time, we are allocating a maximum of (3 teachers X 6 hours)X(3 classes X 35 hour workweek) at a single go, we are iteratively building the timetable.

  2. There will be impossible states and any impossible timetables must be notified without the application getting stuck- we expect this application to be pushed to it's limits.

  3. It must return results in a constant time or report that it failed.

Jesvin Jose
  • 22,498
  • 32
  • 109
  • 202
  • Did you look at [existing software](http://www.dmoz.org/Computers/Software/Educational/Administration_and_School_Management/Scheduling_Utilities/)? – Andreas Dec 30 '11 at 11:12

1 Answers1

6

First, I have to say that it seems like a pretty small solution space: are you confident that brute-force isn't your easiest way forward?

Second, do you mean to say that you need a "pretty good" result in some constant time or that you need the algorithm to be O(1)? I won't say that's impossible, but... well, I'm pretty sure it's impossible.

On the specific point, the major difference between GAs and SA is that SA is essentially a hill-climbing algorithm that searches "outward" from the last point in the solution space, while GAs are probabilistic and search hyperplanes within the solution space.

You say two things that make me think SA is a better fit for your problem: "iteratively building" and "impossible states." Since GAs recombine "pretty good" solutions across hyperplanes in the solution space, they tend to "re-discover" dead zones in the solution space. If you're convinced that a better solution can be iteratively built from a pretty good solution, you're in hill-climbing territory and SA could fit better.

To be very general, the relative advantage of GAs is that they quickly process very large volumes of the solution space, but they rely on there being briefly-encoded "good ideas" within that solution space. The relative advantage of SA is that it searches the local solution space "around" its initial solution, which tends to find local improvements efficiently. The disadvantage is that SA is seeded randomly and so is not efficient in exploring large solution spaces.

Larry OBrien
  • 8,484
  • 1
  • 41
  • 75
  • Can I use brute force as a 'doing combinations' will have to explore 10^16 states optimistically (and a million times that sometimes)? I mean not an O(1), but predictable number of iterations (say 10 million). – Jesvin Jose Dec 30 '11 at 06:39
  • I suggested brute force or hill-climbing based on the 3*6*18*35 numbers you posted. If you can build a good solution from such discrete chunks, brute force or hill-climbing might be your solution. A 10^16 solution space is very large for SA, unless it's very smooth, which timetabling usually isn't. – Larry OBrien Dec 30 '11 at 16:57