Re: [Watchmaker Framework] Class Scheduling problem
Daniel Dyer
<rishi...@yahoo.com> wrote:
> Hi
> I am a high school student trying to learn how GA works. I am trying
> to develop a way to solve class scheduling problem and thought that
> the Sudoku example would be a good way to start. I modified the
> Sudoku example evaluation function such that the problem is only
> looking to see whether a set of pre-specified numbers are present in
> each of the rows. I am starting with a blank 9X9 matrix (using the
> custom option).
That's an interesting approach. There are a few Sudoku-specific
heuristics in the fitness function and evolutionary operators that make a
big difference to how quickly the algorithm converges on a solution (the
more naive solution was so slow as to be unusable). I'm not sure how
these heuristics would work for your problem, it depends how you have
modified these classes.
> It works great when I limit the number choices that the factory uses
> to generate random numbers to 1-9 and use the same numbers in the
> preferred solution. When I increase the number choices for the
> factory from 1 - 9 to 1-20 with 9 blanks to fill in, the problem does
> not converge and seems to get stuck.
If you still have a 9x9 grid, but with 20 different possible values, what
are you trying to optimise? It sounds like a different problem to Sudoku.
It may just be that you need a bigger population size and/or more
generations because you have made the search space bigger.
> Can you please let me know if I am approaching this problem
> correctly? Is there a better way to approach the class scheduling
> problem? What could I do to make the problem converge?
I think quite a few people have used GAs for scheduling problems (school
timetables, sports fixtures, etc.) with varying degrees of success. I
haven't tried it myself. Maybe somebody else here can suggest some good
papers?
Dan.
--
Daniel Dyer
Paul
value you somehow know to be suboptimal?
GAs can lose diversity prematurely, which effectively means that they
"converge" to a suboptimal solution. If that's happening, you might
consider either increasing the mutation rate or introducing
immigration (meaning that some portion of each generation is filled by
randomly generated solutions).
/Paul