Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot
 
PerlMonks  

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??
Yeah I did my dissertation on this subject - using Perl. Without getting into all the intricate details, a really nice representation is to use a 3D array. $array[ROOM_NUMBER][WEEKDAY][TIMESLOT] = CLASS You are susceptable to the label replacement problem (i.e. classes can be booked more than once, or not at all), but that can be easily fixed by a genetic repair operator which just books them again in the next available slot. To give you an example - take the room capacity violation, it's a hard contraint, the pseudo code may look something like this:
Procedure room_capacity_violation For R in 0 .. totalRooms For D in 0 .. totalDays For H in 0 .. totalHours If (chromosome[R][D][H] != 0) If (chromosome[R][D][H]->CLASS_SIZE > room[R]->CLASSROOM_SIZE) + count := count + 1 End If End If End For End For End For Return(count) End room_capacity_violation
So you return the count which represents how many times that hard constraint has been violated. This allows you to perform selection based on the best individuals (those who violate the contraints least) - or whatever selection method you use, because sometimes it's good to keep some traits in your population for the sakes of genetic diversity. One benefit that comes from this encoding method is that one contraint is alreadt assured; it is impossible to double book a room. I hope that is of some help (direct or otherwise).

In reply to Re: Looking for help with AI::Genetic and classroom scheduling by salonmonk
in thread Looking for help with AI::Genetic and classroom scheduling by merlyn

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (3)
As of 2022-10-02 18:19 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    My preferred way to holiday/vacation is:











    Results (12 votes). Check out past polls.

    Notices?