CS 540, Spring 2015: Assignment 3
Evolutionary Algorithms and Timetabling
Part A: Test cases Due Monday 3/2/2015 at noon
For this assignment, you are required to implement an evolutionary
to solve the same problem as in assignment 2: Timetabling.
Questions and Code Due Tuesday 3/10/13 at noon
As before, you have some latitude in your
selection of language and algorithm.
For algorithm, the primary restriction is that you pick an algorithm
covered in class or described in the readings in the evolutionary
computation section of class.
Important: The solver must be from the material in this section of class. You cannot use your solver from assignment 2 to create a really good population and then run a GA or ES for a short period of time to look for minor improvements. Although I said you could use a hybrid, I am not recinding that because it would not honor the spirit of this assignment, will give an unfair advantage to those who did well on assignment 2 and will hinder assignment 4.
you have a fair amount of latitude in the design of your algorithm, e.g.,
initialization, recombination operators, selection... You must write
your own code for this; you are not allowed to download a GA,
ACO or EC
implementation and work with that. You can implement based on papers
from the literature. If you are in doubt about whether you
are straying too far from the content of lectures and readings, just
ask for a judgment on it. You are required to understand whatever code
you use. The instructor reserves the right to interview you about your
code if we suspect that you may have taken too much from other sources.
The input and output formats are identical to that in assignment 2, as
are the requirements for what to turn in.
A. More Problems [10 pts]
Test problems heavily influence the design and implementation of
search methods. For this assignment, we ask you to
help construct a test problem collection.
For grading of the programs, we will
pick test problems from among those submitted. We ask you
to find or create a new test problem (in the required format) and
submit it. Specifics:
We will set up an assignment 3A in Canvas for problem submissions. Only
one attempt will be allowed.
- If your source includes information on optimal or best known
solution, please include it!
- All viable problems (i.e., correct format, not duplicated)
will be shared with the rest of the class. In fact, as problems are
received and checked, they will be posted. Duplicate problems will not be accepted. So if someone else has found it
first and it has been posted, they get the credit and you
don't. (Incentive for getting problems in early!)
- Only one submission from each repository will be accepted.
- The problems must be non-trivial: more than 100 courses, more
than 200 students, each student must be in at least 2 courses.
- State from where you have obtained the problem. If elsewhere, indicate
the source (URL) in your submission. If self generated, indicate
roughly how you produced it.
- The problem should be solvable, i.e., at least one feasible solution exists for it. You will demonstrate this through submitting such a solution.
Questions [30 points]
Point value for each question is listed with it.
Each answer is expected be 1/2-1 page in length, single spaced, 12 pt font, 1 inch margins. Please do construct the answers as essays with paragraph breaks and some attention to organization.
- 10 points For the problem that you submitted, explain
where you got it or how you constructed it. Why do you think it is a
good test problem? Do you think it is/will be challenging? Why or
why not? Provide any background on the type of problem if you have
- 10 points Describe your algorithm and its implementation, explaining why
you designed it
as you did, citing any relevant literature or pilot experiments you
did to tune your implementation.
- 10 points Find and read a published research paper on
applying an evolutionary algorithm to timetabling. Provide the citation, summarize the paper and describe what you learned from it.
What to hand in
You can submit the test problem and the essays through Canvas. Your test problem should include three files: course file, student file and a sample solution file. Your solution should not violate the hard constraint (i.e., it should be feasible). Note: we will only post the two input files but will use the output file to check that there exists a feasible solution.
program will be submitted through Checkin. This time the tar file
should be named PA3.tar.
- Part A: 10 points if correct files in the correct format; 0 if not correct format. If late,
- Questions: 30 points [10 for Q1, 10 for Q2, 10 for Q3] points
awarded based on quality of the answer, appropriate level of detail,
level of understanding evidenced and quality of the writing.
- Code: 60 points
- Checkin success: 4 points
- Runs with valid solution: 26 points
- Followed algorithm guidelines: 10 points
- Thought behind solution: 10 points
- Relative Performance Rank: 10 points
Problems Submitted So Far
Check here for what others have already turned in... This list will include the instances exactly as they are turned in. Caveat Emptor: We will not be checking them for correctness prior to listing them.
- This problem (student file, course file) is "STA83" problem (version II) from the
University of Toronto Benchmark Data set: http://www.cs.nott.ac.uk/~rxq/files/II.zip
The known optimal solution for the problem is 35 time slots.
- A densely packed test problem, with 800 students spread over 108
classes. (student file, course file) The key feature of this test set is a high student-per-course ratio,
(around 25 per class) With the 100 level classes having exceptionally
high enrollment (around 105, with largest having 114 students).Note: Some students double enrolled. FIXED BY A STUDENT MARCH 8 @ 1PM
- Source of dataset is obtained from http://www.cs.nott.ac.uk/~rxq/data.htm
The files are generated from Random Exam Timetabling Problem Generator
(student file, course file) Note: input format is correct, but submitted solution was not feasible. NEW VERION OF CRS AS OF March 8 @ 3PM
- A problem set from
has been modified to ensure that every student is in at least two
classes. (student file, course file) Note: Some course counts are off. FIXED BY SUBMITTER MARCH 8 @ 1PM
- This problem was generated by a script that I wrote. The script takes one student at a time and randomly assigns them a number of exams 1 to n (n being max allowed exams, in this case 5). Initially it randomly assigns courses that have no students until every course has one student. After that, the courses assigned to the students are random, and if a course reaches the maximum room capacity then it is removed from the list. This problem consists of 200 courses, 400 students, 50 capacity, 200 time-slots, and 5 max courses per student. This problem was chosen out of 14 others created for its ease to find a valid timetable but difficulty to find a good timetable.(student file, course file) Note: input format is correct, but instance does not follow required guideline of each student being enrolled in at least 2 courses. FIXED BY SUBMITTER MARCH 8 @ 3PM
- Random generator built by the student (student file, course file)Note: input format is correct, but submitted solution was not feasible and some students double enrolled. FIXED BY A STUDENT MARCH 8 @ 1PM
- Another random generator built by the student (student file, course file)Note: format good, solution feasible, but verifier says obj fn 2 is incorrect.
- I generated this sample problem with a program that I wrote. (student file, course file)
- The dataset I am submitting was one made by a random dataset generator I put together. (student file, course file)
- This dataset was generated using a random dataset generator that I created. The variable initializers that I chose are of the same ratios as the original, trivial dataset, but of course with significantly larger values.
Number of courses: 250; Number of students: 250; Room capacity: 200; Max time slots: 250; Number of courses per student: 2 to 5. (student file, course file) NEW VERION OF CRS AS OF March 8 @ 3PM
- This test case was created by a generator I wrote. It has 150 courses, 500 students, 100 timeslots at most, and a room capacity of 150. The generator works by first assigning a random enrollment number for each course, from 1 to 1/4 of the total students. For each student, two random courses are assigned. Finally, the remaining courses are assigned to students at random. (student file, course file)
- These files were made using a problem generator I wrote. There are 30000 students, 2000 courses, a capacity of 1000, and 100 slots. Each student is enrolled in 2-4 courses. The students and courses were distributed into five "levels", freshman through grad, and enrolled accordingly, so seniors and sophomores aren't in the same classes, for example. Also, lower level courses have higher enrollment than upper level courses. (student file, course file)
- The problem instance was generated using a problem instance generator code that I wrote in python. (student file, course file)
- This test case was created by a generator I wrote. It has 1000 students in 200 courses with a room capacity of 1000 students and35 time slots. The generator will assign each student to 2-8 courses but the distribution of the number of courses per student is uneven. Students with 4 or 5 courses are the most common. (student file, course file)
- The testcase was generated using a random number generator. (student file, course file) Note: input format is correct, but submitted solution was not feasible.
- The data set provided is generated through random generator which I implemented. (student file, course file) Notes: Some students double enrolled. FIXED BY A STUDENT MARCH 8 @ 1PM
- I wrote a program to generate the instance. (student file, course file) Note: input format is correct, but submitted solution was not feasible.
- This test case was generated by my own program. (student file, course file)
- The way that I generated this file, was I started with 120 students and 250 courses. I then made sure that each courses had a random student in it.
At this point each course has at least one student, and each student is in 0 or more classes.
I then went through and added each student to between 2 and 4 more classes.
At this point, each student is in at least 2 classes, and each class has at least 1 student in it, which satisfies the requirements.
I decided on a max of 50 students per timeslot, and a max of 25 timeslots, because I thought that
these restraints were close to what it would be for a room during a finals week. (student file, course file)
- This instance was created from a generator I wrote. There 300 courses 3000 students, 8 possible timeslots and a room capacity of 50. Timeslots are incrementally assigned a random number of courses from 1 to 100 until the courses are all scheduled. For each course, a random number of students from 1/2*Room Capacity to room capacity is enrolled. The resulting enrollements were then checked to ensure that each student is enrolled in at least 2 courses. (student file, course file) Notes:Submitted solution is infeasible and problem is impossible to solve.
- This problem was "randomly" generated with 120 courses and 300 students. Each student is enrolled in 2-5 courses. The minimum course enrollment is 3. The room capacity is 50 and max timeslots are 100. This particular problem was chosen from 10 similar problems for it's large search space and difficulty relative to the others in the set. (student file, course file)
- part of the Carter benchmarks, York Mills Collegiate Institute 1983 finals,
density conflict of 0.29 (student file, course file)
- The data set provided is generated by a program, that I implemented.
(student file, course file) Note: input format is correct, but submitted solution was not feasible and some students are double enrolled. FIXED BY A STUDENT MARCH 8 @ 1PM
- The test case provided was generated by a random generator that I wrote. It has 200 courses, 500 students. I made sure that each course has atleast one student enrolled in it. And each student is enrolled in 2-10 courses. (student file, course file)
- Number of courses are chosen randomaly in between 100 to 120. Each course will have at least 2 students and at most 15 students. Room capacity is randomly selected between 20 to 30. Number of time slots are also selected between 80 to 100 randomly. Number of students are selected in between 200 to 220. Each student is assigned with at least 2 courses and at most 10 courses. (student file, course file) Note: input format is correct, but submitted solution was not feasible and some courses counts are off. FIXED BY SUBMITTER MARCH 8 @ 3PM