Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

Perl, Genetic Algorithms and Encoding...

by parcelforce (Novice)
on Nov 15, 2003 at 16:45 UTC ( #307326=perlquestion: print w/replies, xml ) Need Help??

parcelforce has asked for the wisdom of the Perl Monks concerning the following question:

hello all, I'm currently *trying* to build a simple GA, using Perl to do some timetabling. There seems to be loads about this on the net, quite a few Perl modules but everything is a little too mathematical for me, or it's too generalised, I'm not that great at applying this abstract knowledge and could do with a little help. I suppose this isn't a Perl question specifically, but I know (from copious amounts of lurking) that there's a lot of knowledge around here. I can't seem to visualise the encoding of the data (rooms, teachers, students) onto a chromosome. Being that data::dumper helped me finally understand perl structures, I would really appreciate it if someone could give me an idea as to what the timetable chromosome data structure may look like, or how I might go about constructing it.

But, many apologies if this is too far left of field, just ignore me in that case :)

hopefully,
dave

  • Comment on Perl, Genetic Algorithms and Encoding...

Replies are listed 'Best First'.
Re: Perl, Genetic Algorithms and Encoding...
by eduardo (Curate) on Nov 15, 2003 at 17:03 UTC

    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!!

Re: Perl, Genetic Algorithms and Encoding...
by blokhead (Monsignor) on Nov 15, 2003 at 18:25 UTC
    I'd have to question why you think you need a GA for this problem. There are a lot of timetabling algorithms out there, as most scheduling problems can be modelled as graph matching/coloring problems. Maybe you just want to learn about GAs, which I think is a great reason! Even though this problem doesn't seem well-suited to a GA, you'll learn a lot along the way.

    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.

    blokhead

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://307326]
Approved by Corion
Front-paged by bart
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (4)
As of 2020-07-11 13:13 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?