Comment (Useful?) Resources (Score 2, Informative) 60
Most people who have spoken up so far seem right:
GAs can be used to find sub-optimal or optimal (given enough time) solutions for NP-complete problems, Timetable (TT) being one of them.
However, I think the core benefits of using such a heuristic, in this case, might be:
1. At any point in time, you can tell the GA to stop, and you can get a feasible (but probably sub-optimal) soltuion from it,
2. GAs are, in some small ways, parallelizable.
Of couse, you're probably not looking for a whiz-bang super-duper fast utility, so (2) probably isn't useful.
Perhaps you can find some use of these:
- A presentation I did on why TT is NP-Complete,
- I spoke about a GA approach for solving the TT.
Note that the time spent by a GA in finding an optimal solution is not guaranteed to be any better than the speed of an approximation algorithm, nor even the speed of the naive approach, when solving TT (or any other NP-complete problem).
The GA approach mentioned above had been used successfully in practice, though.
GAs can be used to find sub-optimal or optimal (given enough time) solutions for NP-complete problems, Timetable (TT) being one of them.
However, I think the core benefits of using such a heuristic, in this case, might be:
1. At any point in time, you can tell the GA to stop, and you can get a feasible (but probably sub-optimal) soltuion from it,
2. GAs are, in some small ways, parallelizable.
Of couse, you're probably not looking for a whiz-bang super-duper fast utility, so (2) probably isn't useful.
Perhaps you can find some use of these:
- A presentation I did on why TT is NP-Complete,
- I spoke about a GA approach for solving the TT.
Note that the time spent by a GA in finding an optimal solution is not guaranteed to be any better than the speed of an approximation algorithm, nor even the speed of the naive approach, when solving TT (or any other NP-complete problem).
The GA approach mentioned above had been used successfully in practice, though.
