[kde-edu]: Fwd: Timetable program

[Imre, Nagy Jr.]

> Maybe I can say something about this, since it's my field of research. The
> program uses a Genetic Algorithm, which is inspired by natural evolution.
> Solutions to a problem (which is a certain timetable here) are coded like
> genes and genetic operators like mutation and crossover are used to produce
> new solutions. The selection of those solutions who become parents depends
> on the fitness that the candidate parent solution has.
>
> Genetic algothims have been used before in this field. The quality of the
> output depends on
>  - the quality of the representation of solutions
>  - if the fitness function really includes all aspects the user wants to
> see in the best solution
>  - configuration of the algorithm (like which type of selection, rates of
> mutation and crossover, etc.)

I had a project with the same approach. Time-scheduling works fine as long as 
the fitness-calculation function's resource cost is low. The problem is that 
adding more and more requirements (balanced lessons, less emplty lessons)
complicates the fittness calculation -> slows down the cylce dramatically. On 
the other hand, as I experienced (and I think this is normal) the number of 
cycles to solve the problem increases dramatically when on uses more data 
(pust more teacher, students).

Other possible problem is the mutation and selection. Because a normal 
timetable is a 4 or 5 dimension array in which there can be logical links 
enywhere between any dimensions. Like modification or movement of 
A[x1,y1,z1,q1,w1] elemets has an impact on A[x2,y2,z2,q2,w2] ... 
A[xn,yn,zn,qn,wn] which also have effect on .... So it is a deadly important 
thing to find a quick and efficient method for mutation and selection. 
(Mutation and selection should compare less array-items and should not harm 
logical integrity of timetable)

Also experiences, that genetic algorhytm works great for a 10x10 environment, 
like 10 teachers, 10 classes. But for a current environment (I have some 
relations with a local high-school) what has 107 teachers, 46 classes and 
group-splittings (10 people from the class have language1 class, 10 people 
from the class have typing lessons while 10 people from the same class have 
music) is just not suitable for GA since it calculates a lot (most likely 
6-10 hours on a AMD 2000+)

So, before starting I think it would be nice to define what a school needs, 
what kind of requirement there are in different countries for a high-school 
timetable, and think about if it is really should be done only with GA?

For myself I would be more than happy to contribute to this project.
 
-- 
Have fun,
Mulder

===============	The Bug Is Out There ================================

Imre, Nagy Jr.			Email: mulder at intrepid.rulez.org
leading programmer,		Web: http://intrepid.rulez.org/mulder
network manager			while !(sleep) sheep++;