Greetings!

Ok, so before we get started, let me preach for a few minutes. A genetic algorithm is an incredibly expensive "directed stochastic" search of a very large problem domain in which an elegant algorithmic method for finding solutions (or approximations to solutions) does not exist. Due to that fact, once you've resigned to using a genetic algorithm to attempt to approximate a solution to your problem domain, you are making the statement: "I can't write an algorithm other than an exhaustive search of some sort to find this answer in a reasonable amount of time, so I am going to use a heuristic to attempt to approximate it in the time I have alotted." You'll notice I used the word "time" twice. Perl (although it's my favoritest language ever to program in) really is a slow language for a great many tasks. And programming a genetic algorithm in perl (other than for purposes of prototyping a GA) is usually not a "good idea" due to the fact that you're sacrificing orders of magnitude of performance over the exact same algorithm implemented in C or C++.

But I don't *know* C or C++, I hear you say. Well, guess what... the subset of C or C++ you neeed to learn in order to effectively use any of the *fine* genetic algorithm libraries out there is minimal at best. If I could, let me direct you to GAlib: Matthew's Genetic Algorithm Library. Written for use in C++, it already provides an entire framework for programming genetic algorithms with very little effort, and it also provides buckets of sample programs to show you how to use it. You can most likely modify one of the sample problems slightly, and get what you want. Even better there is a thesis available for you to read about using GAlib for jobshop scheduling available here! Things just don't get any nicer than that.

Now, as to how you would actually encode such a thing, the problem that you have is that you not only have to worry about encoding of the problem domain into a genome... but due to the nature of your data, your crossover and mutation operators are going to have to be intelligent enough to not render a genome invalid (making up a class number that doesn't exist, for example) or your selection criteria is going to have to check each genome for "validity."

Good luck, but just remember, there is *volumes* of literature regarding constraint based scheduling using genetic algorithms. With a bit of googleing you should find a thesis, dissertation, or sample implementations to get you on your way.

Wow! Thanks eduardo, I'm going to take a look at all of that stuff, many thanks for responding so quickly. Yep, as you say it's probably only worthwhile prototyping in Perl which is what I am aiming it. After I know how to actually program it, I was going to rewrite it in plain old C. I'm really slow at programming C, and Perl gives me all those syntactic niceties :)

thanks once again!!

I disagree with eduardo's suggestion to not use Perl for this. Sure, EA/GAs do a lot of number-crunching, but I doubt you're dealing with gigs and gigs of data either. In my experience, Perl's many strengths have almost always made up for its raw computational speed. But I also have not used GAlib. If it really does make things that easy for you, and if you're as comfortable with C as with Perl, go for it. But I wouldn't put off Perl just because it's "slower." Besides, if you were out to make the fastest algorithm for this problem, you wouldn't be using a genetic algorithm anyway.

I'm obliged to plug my A Beginning Guide To Evolutionary Algorithms node. It is fairly general, but maybe you may find it helpful. Give it a read if you're not sure about how to put together the parts of an EA/GA. I also have a bunch of (biased) evolutionary algorithm links at the bottom of my homenode.

You seem to be having trouble coming up with a data representation, and that is usually the hardest part. If your goal is to make a conflict-free schedule, perhaps your fitness function could be the number of schedule conflicts, and your evolution can try to minimize that number. In picking a data representation for the schedule chromosome, try to make it one that facilitates easily mixing two schedules to a new schedule, preserving many aspects of the original schedules. I suggest an array indexed by either classes, students or teachers. That way you can just crossover the two arrays and not get any new schedule conflicts for whatever your indexing is in. Without more information about your problem, I don't think I can be more specific.