helpfaqform_template.ui

基于遗传算法的排课软件源码 根据需要安排合理的课程时间等

<!DOCTYPE UI><UI version="3.3" stdsetdef="1">
<class>HelpFaqForm_template</class>
<widget class="QDialog">
    <property name="name">
        <cstring>HelpFaqForm_template</cstring>
    </property>
    <property name="geometry">
        <rect>
            <x>0</x>
            <y>0</y>
            <width>540</width>
            <height>553</height>
        </rect>
    </property>
    <property name="caption">
        <string>FET - Frequently asked questions</string>
    </property>
    <grid>
        <property name="name">
            <cstring>unnamed</cstring>
        </property>
        <property name="margin">
            <number>11</number>
        </property>
        <property name="spacing">
            <number>6</number>
        </property>
        <widget class="QPushButton" row="1" column="0">
            <property name="name">
                <cstring>closePushButton</cstring>
            </property>
            <property name="text">
                <string>Close</string>
            </property>
        </widget>
        <widget class="QTextBrowser" row="0" column="0">
            <property name="name">
                <cstring>textBrowser3_2</cstring>
            </property>
            <property name="text">
                <string>FET FAQ:
--------

Q: What is the organization of FET input data?
A: 	- Students - organized into sets (years, containing groups, containing subgroups).
	- Teachers.
	- Subjects (the names of the possible courses, eg. Maths, Physics, etc.).
	- Rooms (classrooms).
	- Activities: a coupling of one or more teachers, a subject and one or more students set. This is usually named a course, a lecture, a laboratory and so on.
	- Constraints. They can be: time constraints (referring to the allocated day and hour) or space constraints (referring to rooms allocation). They can also be compulsory or non-compulsory. ConstraintBasicCompulsoryTime and ConstraintBasicCompulsorySpace are two implicit constraints of any timetable. They are added automatically. Also automatically added are ConstraintActivityPreferredTime, added by FET when a new activity is inserted. Each constraint has a weight. The implicit constraints have the weight 1.0. You can choose the weight of the other constraints and you are encouraged to play with that. How to calculate the conflict factor of a constraint? Basically, the number of conflicts, multiplied with 1 for biweekly activities and with 2 for weekly activities, and then multiplied with the weight. 

PS: Please try to work with integer weights, for now (between 1 and 100).

New adding: the FET data set also may contain a list of equipments and a list of subject tags.

-------------------------------------------------------------------------------

Q: How does FET work?
A: A really simple genetic algorithm. You can read my papers (available on my web site - http://lalescu.ro/liviu/fet/) about it.
The essence (hour allocation only): each possible timetable is represented by an array, say times[i], where i goes from 0 to the number of activities - 1. The location times[i] represents the allocated time for activity i. This is the representation.
Now, it applies a genetic algorithm (using notions like selection, crossover, mutation, etc.) to obtain a close to optimal solution (hopefully).

-------------------------------------------------------------------------------

Q: How can I obtain a good timetable and why do I get different results each time?
A: The generation of the timetable is a random process; please restart and try again if you are dissatisfied with the results. Also, you can increase the population number. For the moment, the population 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 of memory). This variable is stored in the file src/engine/genetictimetable_defs.h and is named MAX_POPULATION_NUMBER.

NEW ADDING - 18 Oct. 2004: you can decrease the variable MAX_ACTIVITIES to the number of activities you have in your school, then increase MAX_POPULATION_NUMBER. I have achieved results with MAX_ACTIVITIES set to 400 and MAX_POPULATION_NUMBER set to 65536. These variables can be found in the file src/engine/genetictimetable_defs.h. Please run a "make clean" before running "make" (there is a bug in gcc, I think).

NEW ADDING - 14 Feb. 2005: The variable MAX_ACTIVITIES is now set by default to 1250, and MAX_POPULATION_NUMBER to 8192.

-------------------------------------------------------------------------------

Q: What is the structure of the students FET can handle?
A: FET was designed to allow any school structure:
	- independent subgroups (non-overlapping);
	- overlapping groups (several subgroups) and years (several groups).
	
-------------------------------------------------------------------------------
	
Q: How can one work with overlapping structures of students?
A: If you have overlapping groups, then you must define the smallest independent subgroup, which does not overlap with any other subgroup. Example: you have 1 group, subject sport (which must be taught to boys and girls separately) and subject physics, which is an optional subject and only some students would like to have this course (yes, FET can manage optional subjects). Then, you must define the subgroups: boys who want physics, boys who do not want physics, girls who want physics, girls who do not want physics. Now, it is very easy. Just define 
group girls=subgroup girls who want physics + girls who do not want physics, 
group boys=subgroup boys who want physics + boys who do not physics
group physics=boys who want physics + girls who want physics. 
Then, you can add as many activities as you want to the corresponding groups:
Activity1: teacher A, group girls, subject sport;
Activity2: teacher B, group boys, subject sport;
Activity3: teacher C, group physics, subject optional physics.

-------------------------------------------------------------------------------
	
Q: Can you add more students sets or teachers to a single activity?
A: Yes, you can add several students sets (subgroups, groups or years) and several teachers per activity.

NEW ADDING - 18 Oct. 2004: The interface permits only 3 teachers and 4 students sets per activity. But you can edit by hand the input file and add there as more as 6 teachers per activity. Nobody asked me for more than 6 teachers and 4 students sets.

-------------------------------------------------------------------------------

Q: What represents the weight of the constraints?
A: The importance of the respective constraint, relative to other constraints. For the moment, please try to use integer weights (between 1 and 100). I never had to use different values than 1, but you might need that.

-------------------------------------------------------------------------------

Q: How can I increase the power of search?
A: You will have to increase the population number.

-------------------------------------------------------------------------------

Q: What means bi-weekly activity?
A: An activity which takes place once at two weeks (maybe this concept is not usual, but I considered it from the beginning because my faculty needed that).

-------------------------------------------------------------------------------

Q: Why are all the conflicts reported with double importance?
A: Because they are conflicts referring to weekly activities. For biweekly ones, they will appear with single importance.

-------------------------------------------------------------------------------

Q: How can I contribute to/support FET?
A: Please see the TODO file. Also, you can send any comment/suggestion to the author.
FET is free software and any donation would be great. Please contact the author for that.

-------------------------------------------------------------------------------

Q: What is the algorithm behind FET?
A: A simple genetic algorithm applied on a simple data representation.
	In the future, I hope I will put here some real description of the algorithm. Until then,here are different tricks needed to understand the program:
- The genetic algorithm and representation behind the program looks very simple to me now and I think it can be explained in at most 2 hours. The engine is also not so hard to understand. The nightmare is the graphical user interface, data representation and loading/saving part.
- Time (hours) and space (rooms) allocations are 2 similar phases. You must read my paper to see the reasons why you can firstly allocate the hours and then the rooms.
- I use for the teachers, subjects, students (years, groups, subgroups), activities and constraints a QPtrList. Before starting the simulation, all this information is copied into some arrays, to speed up the computation. Now, the simulation works by considering each teacher, subject and activity an index in these new arrays (the timetables are represented as matrices, indexed by the the teacher (students, rooms), day and hour, and have integer values, which represent activity indices (indices in this second copied arrays).
- I used int16 sometimes just because of the memory consumption
- With 8192 maximum population and 2500 maximum activities, class GeneticTimetable has the size of about 160 megabytes (I hope I remember well). In fact, it contains an array of 2500*8192*2*2 of 16 bit integers, which is ~160Mb of memory.

Modification (21 Feb. 2005) - with 8192 population size and 1250 activities the class Rules has size of ~160Mb.

-------------------------------------------------------------------------------

Q: Could you please detail the use of weights in constraints?
A: The weight of any constraint can be a real number (double). BUT: I preferred that any return value of a constraint to be an integer, which is this real value rounded up to the nearest integer (reasons of speed). For the moment, please try to work with integer weights (between 1 and 100).
	
-------------------------------------------------------------------------------

Q: Could you please explain why FET works in two phases, first the time, then the space?
A: For reasons of speed. But in the two phase allocation the first phase might find solutions that are not compatible with the second phase (for example, working with the sample number 12, from Marek Jaszuk, will not yield perfect solutions for the second phase, although there exists a perfect solution, found manually.

There are two solutions: 1) FET to work in a single phase (but the time will be a bit longer) or 2) add some time constraints so as the solution to the first phase will always respect all the space constraints (very complicated: all the constraints might be compulsory or non-compulsory and the execution time is very long).

This is a research problem.
	
-------------------------------------------------------------------------------
	
Q: How does ConstraintActivitiesSameStartingTime work?
A: 	- for compulsory constraints, the solution candidate is repaired before evaluation (so all solutions will respect these constraints and there will be no conflicts reported). This is faster, as an input file from user Ian Fantom proved.
	- for non-compulsory constraints, the method is conflict reporting (slower, worse than the above method).

-------------------------------------------------------------------------------
	
Q: How does ConstraintActivityPreferredTime work?
A: 	- for compulsory constraints, the solution candidate is repaired before evaluation (so all solutions will respect these constraints and there will be no conflicts reported). This is faster (proved practically, not theoretically).
	- for non-compulsory constraints, the method is conflict reporting. The procedure reports a conflicts factor that is increasing with the distance to the desired period. This might generate worse solutions, if you are only interested in the exact placement. In this case, please use ConstraintActivityPreferredTimes with only one preferred time.
		Example: 5 days per week
				5 activities daily exclusive
				activity 1 - preferred on monday
				activity 2 - preferred on monday