Print

Print


It looks like I'll be exercising those GE changes Sean made.

I'm doing a timetabling problem as part of a 4th year directed study at our 
university using GP. My solution will likely be based on this paper,

 http://cswww.essex.ac.uk/staff/rpoli/papers/BaderElDenPoliFatimaMemeticCom
p2009.pdf
  
I'm kind of divided on going this route. I need to keep my solution simple
enough that I don't lose my audience in the presentation (mostly 1st, 2nd year 
comp sci students and sciences profs) on the one hand and yet provide a 
solution which serves as a basis for further studies into genetic computing 
and also provides a solution to the school's timetabling tasks. 

My prof has been the chair of sciences for quite a while now and he has 
developed a set of personal heuristics which have helped him to manage this
task pretty well. After examining his methods I concluded most of the work
could be defined in the terminals as hard constraints (since they don't change)
and the rest was mostly an optimisation problem with soft constraints on the
selection process. So the genomes would have time slots randomly allotted to 
them from a table for each individual in a generation and then assessed for 
fitness.

One idea I had in mind, for the sake of teaching what GP does and to optimise
the next run, was to evolve individuals from the hard constraints in a run and 
then use them as terminals. So, in a sense creating an ADF statically. 

Another idea was to do multiple runs with varying soft constraints. One run 
would, for example, preferentially reward fewer early morning classes and 
another would reward fewer back-to-back classes for a prof, etc. Then the 
elites would form the basis of a final run which optimised for a range of 
selective criteria. For example, if the timetables didn't make some profs happy 
(a social selection criteria) the final stage could be run again with different 
weightings. This way interactive solutions could converge quickly. The elites 
would have enough diversity to cover most of the social selection criteria 
encountered, but if not just breed a new group of elites and try again.

Now, on the other hand, using the GPHH method from the article also provides 
teaching points since it incorporates a wider range of materials we've studied
in previous years. The final stage method for social selection by diverse 
elites could still be used with GPHH, so nothing lost there. However, I'm one 
of three students in our final presentation and my time will be limited. So, 
I don't know how much teaching I can actually get done. Still, this work could 
possibly be used as an illustrative example for other classes in later years. 
My prof is retiring at the end of this year and he's hoping a leave a 
timetabling tool behind, most likely to cut down on support calls from the 
succeeding science chair (or pleadings from profs to lend a hand :)

So, after all that... any ideas or suggestions that will help to minimise any
potential blind alleys I might take? I'm reading Sean's book (thanks Sean!) 
and also the manual. I have Koza's first book at hand. I'll be going over the
examples to get a better idea of what ECJ is doing and I need to get 
programming to have something to show -- soon. Of course I need to do this 
work myself, but collaboration is fair game if I can point to published papers or 
even correspondence on this list.

Of course I'll report any problems which look like they may be related to
Sean's recent changes. 

-- ray
(sorry for the wordiness -- I kill trees)