CS 540, Spring 2015: Assignment 3
Evolutionary Algorithms and Timetabling

Part A: Test cases Due Monday 3/2/2015 at noon
Questions and Code Due Tuesday 3/10/13 at noon

For this assignment, you are required to implement an evolutionary algorithm to solve the same problem as in assignment 2: Timetabling.

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.

Otherwise, 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.

Questions [30 points]

Point value for each question is listed with it.
  1. 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 it.
  2. 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.
  3. 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.
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.

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.

Your program will be submitted through Checkin. This time the tar file should be named PA3.tar.


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.
  1. 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.
  2. 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
  3. 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
  4. A problem set from ftp://ftp.mie.utoronto.ca/pub/carter/newprob/UofLimerick/Set_1/ That 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
  5. 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
  6. 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
  7. Another random generator built by the student (student file, course file)Note: format good, solution feasible, but verifier says obj fn 2 is incorrect.
  8. I generated this sample problem with a program that I wrote. (student file, course file)
  9. The dataset I am submitting was one made by a random dataset generator I put together. (student file, course file)
  10. 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
  11. 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)
  12. 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)
  13. The problem instance was generated using a problem instance generator code that I wrote in python. (student file, course file)
  14. 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)
  15. The testcase was generated using a random number generator. (student file, course file) Note: input format is correct, but submitted solution was not feasible.
  16. 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
  17. I wrote a program to generate the instance. (student file, course file) Note: input format is correct, but submitted solution was not feasible.
  18. This test case was generated by my own program. (student file, course file)
  19. 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)
  20. 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.
  21. 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)
  22. part of the Carter benchmarks, York Mills Collegiate Institute 1983 finals, density conflict of 0.29 (student file, course file)
  23. 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
  24. 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)
  25. 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