📄 faq.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"><HTML><HEAD> <META HTTP-EQUIV="CONTENT-TYPE" CONTENT="text/html; charset=iso-8859-1"> <TITLE></TITLE> <META NAME="GENERATOR" CONTENT="OpenOffice.org 1.1.3 (Linux)"> <META NAME="AUTHOR" CONTENT="Lalescu Liviu"> <META NAME="CREATED" CONTENT="20050228;17341200"> <META NAME="CHANGEDBY" CONTENT="Liviu Lalescu"> <META NAME="CHANGED" CONTENT="20050707;16583200"></HEAD><BODY LANG="en-US" DIR="LTR"><P>FET FAQ:</P><P>--------</P><P><BR><BR></P><P>Q: What is the organization of FET input data?</P><P>A: - Students - organized into sets (years, containing groups,containing subgroups).</P><P>- Teachers.</P><P>- Subjects (the names of the possible courses, eg. Maths, Physics,etc.).</P><P>- Rooms (classrooms).</P><P>- Activities: a coupling of one or more teachers, a subject andone or more students set. This is usually named a course, a lecture,a laboratory and so on.</P><P>- Constraints. They can be: time constraints (referring to theallocated day and hour) or space constraints (referring to roomsallocation). They can also be compulsory or non-compulsory.ConstraintBasicCompulsoryTime and ConstraintBasicCompulsorySpace aretwo implicit constraints of any timetable. They are addedautomatically. Also automatically added areConstraintActivityPreferredTime, added by FET when a new activity isinserted. Each constraint has a weight. The implicit constraints havethe weight 1.0. You can choose the weight of the other constraintsand you are encouraged to play with that. How to calculate theconflict factor of a constraint? Basically, the number of conflicts,multiplied with 1 for biweekly activities and with 2 for weeklyactivities, and then multiplied with the weight. </P><P><BR><BR></P><P>PS: Please try to work with integer weights, for now (between 1and 100).</P><P><BR><BR></P><P>New adding: the FET data set also may contain a list of equipmentsand a list of subject tags.</P><P><BR><BR></P><P>-------------------------------------------------------------------------------</P><P><BR><BR></P><P>Q: How does FET work?</P><P>A: A really simple genetic algorithm. You can read my papers(available on my web site - http://lalescu.ro/liviu/fet/) about it.</P><P>The essence (hour allocation only): each possible timetable isrepresented by an array, say times[i], where i goes from 0 to thenumber of activities - 1. The location times[i] represents theallocated time for activity i. This is the representation.</P><P>Now, it applies a genetic algorithm (using notions like selection,crossover, mutation, etc.) to obtain a close to optimal solution(hopefully).</P><P><BR><BR></P><P>-------------------------------------------------------------------------------</P><P><BR><BR></P><P>Q: How can I obtain a good timetable and why do I get differentresults each time?</P><P>A: The generation of the timetable is a random process; pleaserestart and try again if you are dissatisfied with the results. Also,you can increase the population number. For the moment, thepopulation number is limited to 8192 but, if you have plenty of RAM,you can make it as big as you want (8192 means about 160 megabytes ofmemory). This variable is stored in the filesrc/engine/genetictimetable_defs.h and is namedMAX_POPULATION_NUMBER.</P><P><BR><BR></P><P>NEW ADDING - 18 Oct. 2004: you can decrease the variableMAX_ACTIVITIES to the number of activities you have in your school,then increase MAX_POPULATION_NUMBER. I have achieved results withMAX_ACTIVITIES set to 400 and MAX_POPULATION_NUMBER set to 65536.These variables can be found in the filesrc/engine/genetictimetable_defs.h. Please run a "make clean"before running "make" (there is a bug in gcc, I think).</P><P><BR><BR></P><P>NEW ADDING - 14 Feb. 2005: The variable MAX_ACTIVITIES is now setby default to 1250, and MAX_POPULATION_NUMBER to 8192.</P><P><BR><BR></P><P>-------------------------------------------------------------------------------</P><P><BR><BR></P><P>Q: What is the structure of the students FET can handle?</P><P>A: FET was designed to allow any school structure:</P><P>- independent subgroups (non-overlapping);</P><P>- overlapping groups (several subgroups) and years (severalgroups).</P><P>-------------------------------------------------------------------------------</P><P>Q: How can one work with overlapping structures of students?</P><P>A: If you have overlapping groups, then you must define thesmallest independent subgroup, which does not overlap with any othersubgroup. Example: you have 1 group, subject sport (which must betaught to boys and girls separately) and subject physics, which is anoptional subject and only some students would like to have thiscourse (yes, FET can manage optional subjects). Then, you must definethe subgroups: boys who want physics, boys who do not want physics,girls who want physics, girls who do not want physics. Now, it isvery easy. Just define </P><P>group girls=subgroup girls who want physics + girls who do notwant physics, </P><P>group boys=subgroup boys who want physics + boys who do notphysics</P><P>group physics=boys who want physics + girls who want physics. </P><P>Then, you can add as many activities as you want to thecorresponding groups:</P><P>Activity1: teacher A, group girls, subject sport;</P><P>Activity2: teacher B, group boys, subject sport;</P><P>Activity3: teacher C, group physics, subject optional physics.</P><P><BR><BR></P><P>-------------------------------------------------------------------------------</P><P>Q: Can you add more students sets or teachers to a singleactivity?</P><P>A: Yes, you can add several students sets (subgroups, groups oryears) and several teachers per activity.</P><P><BR><BR></P><P>NEW ADDING - 18 Oct. 2004: The interface permits only 3 teachersand 4 students sets per activity. But you can edit by hand the inputfile and add there as more as 6 teachers per activity. Nobody askedme for more than 6 teachers and 4 students sets.</P><P><BR><BR></P><P>-------------------------------------------------------------------------------</P><P><BR><BR></P><P>Q: What represents the weight of the constraints?</P><P>A: The importance of the respective constraint, relative to otherconstraints. For the moment, please try to use integer weights(between 1 and 100). I never had to use different values than 1, butyou might need that.</P><P><BR><BR></P><P>-------------------------------------------------------------------------------</P><P><BR><BR></P><P>Q: How can I increase the power of search?</P><P>A: You will have to increase the population number.</P><P><BR><BR></P><P>-------------------------------------------------------------------------------</P><P><BR><BR></P><P>Q: What means bi-weekly activity?</P><P>A: An activity which takes place once at two weeks (maybe thisconcept is not usual, but I considered it from the beginning becausemy faculty needed that).</P><P><BR><BR></P><P>-------------------------------------------------------------------------------</P><P><BR><BR></P><P>Q: Why are all the conflicts reported with double importance?</P><P>A: Because they are conflicts referring to weekly activities. Forbiweekly ones, they will appear with single importance.</P><P><BR><BR></P><P>-------------------------------------------------------------------------------</P><P><BR><BR></P><P>Q: How can I contribute to/support FET?</P><P>A: Please see the TODO file. Also, you can send anycomment/suggestion to the author.</P><P>FET is free software and any donation would be great. Pleasecontact the author for that.</P><P><BR><BR></P><P>-------------------------------------------------------------------------------</P><P><BR><BR></P><P>Q: What is the algorithm behind FET?</P><P>A: A simple genetic algorithm applied on a simple datarepresentation.</P><P>In the future, I hope I will put here some real description of thealgorithm. Until then,here are different tricks needed to understandthe program:</P><P>- The genetic algorithm and representation behind the programlooks very simple to me now and I think it can be explained in atmost 2 hours. The engine is also not so hard to understand. Thenightmare is the graphical user interface, data representation andloading/saving part.</P><P>- Time (hours) and space (rooms) allocations are 2 similar phases.You must read my paper to see the reasons why you can firstlyallocate the hours and then the rooms.</P><P>- I use for the teachers, subjects, students (years, groups,subgroups), activities and constraints a QPtrList. Before startingthe simulation, all this information is copied into some arrays, tospeed up the computation. Now, the simulation works by consideringeach teacher, subject and activity an index in these new arrays (thetimetables are represented as matrices, indexed by the the teacher(students, rooms), day and hour, and have integer values, whichrepresent activity indices (indices in this second copied arrays).</P><P>- I used int16 sometimes just because of the memory consumption</P><P>- With 8192 maximum population and 2500 maximum activities, classGeneticTimetable has the size of about 160 megabytes (I hope Iremember well). In fact, it contains an array of 2500*8192*2*2 of 16bit integers, which is ~160Mb of memory.</P><P><BR><BR></P><P>Modification (21 Feb. 2005) - with 8192 population size and 1250activities the class Rules has size of ~160Mb.</P><P><BR><BR></P><P>-------------------------------------------------------------------------------</P><P><BR><BR></P><P>Q: Could you please detail the use of weights in constraints?</P><P>A: The weight of any constraint can be a real number (double).BUT: I preferred that any return value of a constraint to be aninteger, which is this real value rounded up to the nearest integer(reasons of speed). For the moment, please try to work with integerweights (between 1 and 100).</P><P>-------------------------------------------------------------------------------</P><P><BR><BR></P><P>Q: Could you please explain why FET works in two phases, first thetime, then the space?</P><P>A: For reasons of speed. But in the two phase allocation the firstphase might find solutions that are not compatible with the secondphase (for example, working with the sample number 12, from MarekJaszuk, will not yield perfect solutions for the second phase,although there exists a perfect solution, found manually.</P><P><BR><BR></P><P>There are two solutions: 1) FET to work in a single phase (but thetime will be a bit longer) or 2) add some time constraints so as thesolution to the first phase will always respect all the spaceconstraints (very complicated: all the constraints might becompulsory or non-compulsory and the execution time is very long).</P><P><BR><BR></P><P>This is a research problem.</P><P>-------------------------------------------------------------------------------</P><P>Q: How does ConstraintActivitiesSameStartingTime work?</P><P>A: - for compulsory constraints, the solution candidate isrepaired before evaluation (so all solutions will respect theseconstraints and there will be no conflicts reported). This is faster,as an input file from user Ian Fantom proved.</P><P>- for non-compulsory constraints, the method is conflict reporting(slower, worse than the above method).</P><P><BR><BR></P><P>-------------------------------------------------------------------------------</P><P>Q: How does ConstraintActivityPreferredTime work?</P><P>A: - for compulsory constraints, the solution candidate isrepaired before evaluation (so all solutions will respect theseconstraints and there will be no conflicts reported). This is faster(proved practically, not theoretically).</P><P>- for non-compulsory constraints, the method is conflictreporting. The procedure reports a conflicts factor that isincreasing with the distance to the desired period. This mightgenerate worse solutions, if you are only interested in the exactplacement. In this case, please use ConstraintActivityPreferredTimeswith only one preferred time.</P><P>Example: 5 days per week</P><P>5 activities daily exclusive</P><P>activity 1 - preferred on monday</P><P>activity 2 - preferred on monday</P><P>activity 3 - preferred on tuesday</P><P>activity 4 - preferred on thursday</P><P>activity 5 - anytime</P><P>The best solution will contain 2 conflicts, and a possiblesolution would be:</P><P>act 1 - mon</P><P>act 2 - tue</P><P>act 3 - wed</P><P>act 4 - thu</P><P>act 5 - fri</P><P>If you use ConstraintActivityPreferredTimes, you will get only oneconflict:</P><P>act 1 - mon</P><P>act 2 - wed</P><P>act 3 - tue</P><P>act 4 - thu</P><P>act 5 - fri</P>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -