faq.html

用遗传算法写的软件,非常有用! 值得大家一看!

<P>-------------------------------------------------------------------------------</P>
<P><BR><BR>
</P>
<P>Q: What advantages has FET over other applications?</P>
<P>A: - It is free software</P>
<P>- Supports weekly and biweekly activities (my university of
Craiova, Romania, needed that);</P>
<P>- Independent subgroups, overlapping or independent groups,
overlapping or independent years (flexible enough to permit any kind
of students structure). FET can even be used to manage every
individual student, if you really need that;</P>
<P>- Possibility of optional activities;</P>
<P>- Many kinds of constraints, possibility to add many more (please
suggest!).</P>
<P><BR><BR>
</P>
<P>-------------------------------------------------------------------------------</P>
<P><BR><BR>
</P>
<P>Q: What are the disadvantages of FET, compared to other
applications?</P>
<P>A: - Very unfriendly (no help, primitive graphical user
interface);</P>
<P>- Potentially buggy. I do not have enough sample files for testing
FET (and I hate testing :-)</P>
<P>-------------------------------------------------------------------------------</P>
<P><BR><BR>
</P>
<P>Q: Does FET compile on other operating systems than GNU/Linux?</P>
<P>A: FET can be compiled easily in operating systems which are
similar to GNU/Linux. I will provide help to compile this program on
any operating system. In particular, FET can be compiled on Microsoft
Windows, if you install Qt from trolltech.com.</P>
<P><BR><BR>
</P>
<P>-------------------------------------------------------------------------------</P>
<P><BR><BR>
</P>
<P>Q: Does FET claim to be the best timetabling software in the
world, like all the other timetabling applications?</P>
<P>A: I cannot pretend that, because I could not compare FET with
other applications (if you could help me, that would be great). All I
can say right now is that I did not see any application with as many
kinds of constraints and such flexibility as FET, and besides being
free software.</P>
<P><BR><BR>
</P>
<P>Is FET the first free timetabling software (GNU/GPL)? Hmmm... the
first one was Tablix, as I found out after finishing FET. You can see
links to this software if you look in the LINKS file or if you search
it on the internet.</P>
<P><BR><BR>
</P>
<P>-------------------------------------------------------------------------------</P>
<P><BR><BR>
</P>
<P>Q: What is the difference between unallocated and random
initialization? Which one is better?</P>
<P>A: This means the method of initializing the population of
solution candidates. It seems (practical results) that unallocated
initialization is better. I have not read about unallocated
initialization anywhere, but it seems to me more natural and I have
an empirical explanation somewhere on my thesis.</P>
<P><BR><BR>
</P>
<P>-------------------------------------------------------------------------------</P>
<P><BR><BR>
</P>
<P>Q: Help on ConstraintMinNDaysBetweenActivities.</P>
<P>A: It refers to a set of activities and involves a constant, N.
For every pair of activities in the set, it does not allow the
distance(in days) between them to be less than N. If you specify N=1,
then this constraint means that no two activities can be scheduled in
the same day. N=2 means that each two subactivities must be separated
by at least one day</P>
<P>Example: 3 activities and N=2. Then, one can place them on Monday,
Wednesday and Friday (5 days week).</P>
<P>Example2: 2 activities, N=3. Then, one can place them on Monday
and Thursday, on Monday and Friday, then on Tuesday andFriday (5 days
week).</P>
<P><BR><BR>
</P>
<P>-------------------------------------------------------------------------------</P>
<P><BR><BR>
</P>
<P>Q: Is it easy to add new constraints to FET?</P>
<P>A: It is very easy. I can say that I am able to implement a new
constraint in a matter of hours. You can find a description of this
procedure in file /.../fet-x.x.x/doc/how-to-implement-new-constraints</P>
<P><BR><BR>
</P>
<P>-------------------------------------------------------------------------------</P>
<P><BR><BR>
</P>
<P>Q: Help on ConstraintStudentsEarly.</P>
<P>A: It is a constraint that imposes the condition that all the
students must begin their courses as early as possible. You have to
be careful with this constraint: if any set of students begins the
classes later than the first hour in a certain day, you</P>
<P>will get a conflict.</P>
<P><BR><BR>
</P>
<P>-------------------------------------------------------------------------------</P>
<P><BR><BR>
</P>
<P>Q: FET fails to solve my timetable.</P>
<P>A: Please try to use a greater population size. Then, try more
simulations. If that does not solve your problem, please try to relax
the conditions on the timetable. You can accomplish that by deleting
compulsory constraints or by making them non-compulsory</P>
<P><BR><BR>
</P>
<P>-------------------------------------------------------------------------------</P>
<P><BR><BR>
</P>
<P>Q: Do the weights have any importance? What is the best way to
choose them?</P>
<P>---The comment below was written when FET used only mutation which
randomized an activity's starting time.</P>
<P>A: Yes, the weights are important, but unfortunately I cannot
answer to the second question.</P>
<P>I can justify the first affirmation by an example: the considered
file is named (for the moment) sample4. As it is right now, it is a
good example of a very constraint timetable, difficult to schedule by
FET. The weights are chosen such that the basic constraints have a
smaller weight than the constraint avoiding the gaps for the
students. I think that after about 4 tries, FET manages to find a
clash-free timetable (I am only referring to compulsory constraints).
There was no trial in which FET failed with more than 3 compulsory
constraints conflicts (usually 1).</P>
<P>I wanted to impose the more important basic constraints, so I
raised their importance (weight) and lowered the weight of the gaps
constraints. The results came as a very unpleasant surprise for me: I
never obtained less than 3 conflicts, with an average of 6. What
conclusions can be derived: I am currently thinking and analysing
this issue. Until someone will come up with a plausible explanation,
I think that: the weights of the constraints are influencing the
conflicts function. The function can have more or less local minima
(which are a headache for genetic algorithms designers). You are
encouraged to play with different weights.</P>
<P><BR><BR>
</P>
<P>New comment: FET-s algorithm favorises the one-mutation
transitions, that is, from a candidate solution you obtain a new
candidate solution with a single activity rescheduled. The old
candidate solution and the new one must have a good fitness, to be
preferred in the evolutionary process. Basic constraints are more
likely to be respected by this mutation, whereas gaps constraints
require more mutations and the intermediary candidate solutions are
not so fit and therefore the chances are lower of finding the good
solution.</P>
<P><BR><BR>
</P>
<P>---The comment below was written after I chosed to introduce also
the second kind of mutation, a swapping of two random activities.
This swapping was very benefical, and now the results are the same,
regardless of the weights (I am only referring to the above example).
The reason is that this random swap helps FET transform a candidate
solution which does break gaps constraints into a candidate solution
which does not.</P>
<P><BR><BR>
</P>
<P>-------------------------------------------------------------------------------</P>
<P><BR><BR>
</P>
<P>Q: Can I use FET to do interactive timetabling?</P>
<P>A: Yes, but this is not easy. All the part regarding data
representation and gradually construction of the solution is working,
only the interface has to be updated.</P>
<P>Anyway, when you add a compulsory ConstraintActivityPreferredTime,
it means that you fixed that activity. You can use this feature for a
semi-automatic or even manual timetabling, but it is not so
convenient.</P>
<P><BR><BR>
</P>
<P>-------------------------------------------------------------------------------</P>
<P><BR><BR>
</P>
<P>Q: Help on ConstraintActivityPreferredTimes.</P>
<P>A: You can specify a set of time slots when this activity can be
scheduled (a kind of OR of more ConstraintActivityPreferredTime).</P>
<P><BR><BR>
</P>
<P>Important: For only one non-compulsory preferred time,
ConstraintActivityPreferredTimes might behave better than
ConstraintActivityPreferredTime, depending on whether you are
interested in minimizing the distance to this preferred time or only
in reaching the exact preferred time. Please see the detailed
observation in the explanation of ConstraintActivityPreferredTime</P>
<P><BR><BR>
</P>
<P>-------------------------------------------------------------------------------</P>
<P><BR><BR>
</P>
<P>Q: Help on ConstraintStudentsSetIntervalMaxDaysPerWeek.</P>
<P>A: Quite a difficult and long name. A user needed a constraint to
disallow more than 2 afternoons per week for a students set. This
constraint is more general. You can specify an interval (by the start
and end hour), a students set and the maximum number of days in a
week when it is permitted to have activities in this time interval.</P>
<P><BR><BR>
</P>
<P>-------------------------------------------------------------------------------</P>
<P><BR><BR>
</P>
<P>Q: Help on Constraint2ActivitiesConsecutive.</P>
<P>A: A user needed a timetable to respect the requirement that 2
activities follow one after the other (order is important). For
compulsory and non-compulsory, normal error reporting is done. The
conflicts are a difference in days + a difference in hours. The
number of conflicts is multiplied with 2 if the first activity is
weekly (not bi-weekly) and again multiplied with 2 if the second
activity is weekly.</P>
<P>-&gt;added - 15 May 2004.</P>
<P>-&gt;modified - 20 February 2005.</P>
<P><BR><BR>
</P>
<P>-------------------------------------------------------------------------------</P>
<P><BR><BR>
</P>
<P>Q: Help on Constraint2ActivitiesGrouped.</P>
<P>A: A user needed a timetable to respect the requirement that 2
activities follow one after the other (order is not important).For
compulsory and non-compulsory, normal error reporting is done. The
conflicts reported are: the difference in days+: - the difference in
hours if the activities are too far from each other</P>
<P>- a constant number if the activities overlap</P>
<P>- 0 if the hours are OK.</P>
<P>The number of conflicts is multiplied with 2 if the first activity
is weekly (not bi-weekly) and again multiplied with 2 if the second
activity is weekly.</P>
<P><BR><BR>
</P>
<P>-&gt;added - 15 May 2004.</P>
<P><BR><BR>
</P>
<P>-------------------------------------------------------------------------------</P>
<P><BR><BR>
</P>
<P>Q: Help on ConstraintActivitiesPreferredTimes.</P>
<P>A: A user suggested that ConstraintActivityPreferredTimes should
be more general. Now, you can specify a teacher, the students and a
subject as a filter to a set of activities that must be scheduled in
certain intervals.</P>
<P><BR><BR>
</P>
<P>-&gt;added - 15 May 2004.</P>
<P><BR><BR>
</P>
<P>-------------------------------------------------------------------------------</P>
<P><BR><BR>
</P>
<P>Q: After finding the timetable of our school, suppose that a
single teacher needs to modify his timetable and the rest would like
to keep their timetable unchanged. Thus, it is needed to fix all the
activities of the rest of the teachers and re-allocate the hours. Can
FET deal with such a situation?</P>
<P>A: Yes, FET can deal with that. Just add many compulsory
ConstraintActivityPreferredTime-s, one for each activity that you
would like to be fixed (the preferred time will be the one from the
previous allocation). This will not slow down the allocation, because
compulsory constraints of this type are dealt with in a special way
(repairing of the chromosomes, to be more specific).</P>
<P><BR><BR>
</P>
<P>-&gt;added - 17 November 2004.</P>
<P><BR><BR>
</P>
<P>-------------------------------------------------------------------------------</P>
<P><BR><BR>
</P>
<P>Q: What about introducing duplicate constraints in the timetable
data?</P>
<P>A: It will slow down the automatic allocation, so please don't.</P>
<P><BR><BR>
</P>
<P>-&gt; added - 12 February 2005.</P>
<P><BR><BR>
</P>
<P>-------------------------------------------------------------------------------</P>
<P><BR><BR>
</P>
<P>Q: What about the one phase and 2 phases automatic allocation?</P>
<P>A: If FET fails to solve your timetable in 2 phases (it has many
broken space constraints), try a single phase allocation</P>
<P>-&gt; added - 14 February 2005.</P>
<P><BR><BR>
</P>
<P ALIGN=RIGHT>this documentation by Liviu Lalescu</P>
</BODY>
</HTML>