java 在java中使用遗传算法生成时间表
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/10512381/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Time table Generation using Genetic Algorithms in java
提问by shridatt
I am trying to seek a solution for timetable generation using Genetic Algorithms(GA). In my scenario i view a timetable of 6 days. Monday to Saturday.
我正在尝试使用遗传算法（GA）寻找时间表生成的解决方案。在我的场景中，我查看了 6 天的时间表。周一到周六。
Each day is divided into number of lectures/Time slots.(maximum no. of lectures are 6 in a day/Each time slot if 1 hr so that means 6 hours for a day)
每天分为讲座次数/时段。（每天最多讲座6次/每个时段如果1小时，则意味着每天6小时）
I have tried to represent a Class consisting of Teacher,Student Group(set), and a lecture. I maintain a pool of possible teachers,possible subjects and possible student groups. And i randomly assign them to these Class.
我试图代表一个由教师、学生组（组）和讲座组成的班级。我保留了一个可能的教师、可能的科目和可能的学生团体。我将它们随机分配给这些班级。
so a Class is collection of all these references. so for each time slot we have the Class object representation in it. similarly a day is made up of number of lectures Class object representation. and so on with the week making up of 6 days.
所以一个类是所有这些引用的集合。所以对于每个时隙，我们都有 Class 对象表示。类似地，一天由讲座的数量组成 类对象表示。以此类推，一周由 6 天组成。
A set of possible constraints that i have is:
我拥有的一组可能的约束是：
1.A teacher can take only one lecture in one time slot
2.A teacher can take a set of subjects(finite)
3.A teacher can be unavailable on a certain day
4.A teacher can be unavailable on a certain timeslot
1.一个老师只能在一个时间段上一
节课 2.一个老师可以选一组科目（有限）
3.一个老师可以在某一天
不可用 4.一个老师可以在某个时间段不可用
And other constraints as it may be included lately.
以及最近可能包含的其他限制。
Can anyone give me a idea about how to represent these constraints or handle these constraints? and how to calculate the fitness scores depending on constraints?
谁能给我一个关于如何表示这些约束或处理这些约束的想法？以及如何根据约束计算适应度分数？
EDIT : The implementation is herehttps://github.com/shridattz/dynamicTimeTable
回答by shridatt
UPDATE:
更新：
The code can be found here
代码可以在这里找到
In my TimeTable Generation I have used A timetable object. This object consists of ClassRoom objects and the timetable schedule for each them also a fittness score for the timetable. Fittness score corresponds to the number of clashes the timetable has with respect to the other schedules for various classes.
在我的 TimeTable Generation 中，我使用了一个时间表对象。该对象由 ClassRoom 对象和每个对象的时间表以及时间表的适合度分数组成。适合度分数对应于时间表相对于不同课程的其他时间表的冲突次数。
ClassRoom object consists of week objects.Week objects consist of Days. and Days consists of Timeslots. TimeSlot has a lecture in which a subject,student group attending the lecture and professor teaching the subject is associated
ClassRoom 对象由周对象组成。周对象由天组成。和天由时间段组成。TimeSlot有一个讲座，其中一个主题，参加讲座的学生群体和教授该主题的教授相关联
This way I have represented the timetable as a chromosome.
通过这种方式，我将时间表表示为染色体。
And further on talking about the constraints, I have used composite design pattern, which make it well extendable to add or remove as many constraints.
进一步讨论约束时，我使用了复合设计模式，这使得添加或删除尽可能多的约束具有很好的可扩展性。
in each constraint class the condition as specified in my question is checked between two timetable objects. If condition is satisfied i.e there is a clash is present then the score is incremented by one.
在每个约束类中，在两个时间表对象之间检查我的问题中指定的条件。如果满足条件，即存在冲突，则分数加一。
This way the timetable with the least Score is the Best we can get.
这样分数最低的时间表是我们能得到的最好的。
回答by tgr
For this problem ther is no efficintsolution. I think you got that too because you use genetic algorithms. I wrote some month ago a framework for genetic algorithm myself.
I think you missed: every class has a list of lessons per week and only one lesson can happen at a time. Now you can combine randomly teachers and classes for the timeslots.
In the fitnes function I'd give a huge plus if a class has all lessons to do a week. A big minus would be if teachers haven't simmilar load (teacher a has two lessons a week and teacher b 12 for example). This you might relativate if a teacher has to work just 20 hours a week (use %).
All in all it is not that trivial and you might look for an experienced co-worker or mentor to help you with this topic.
If you want more specific advises, please specify your question.
对于这个问题，没有有效的解决方案。我想你也明白了，因为你使用了遗传算法。几个月前我自己写了一个遗传算法框架。
我想你错过了：每节课每周都有一个课程清单，一次只能上一节课。现在您可以为时间段随机组合教师和班级。
在健身功能中，如果一个班级有一周的所有课程，我会给予极大的加分。如果教师没有类似的负担（例如，教师 a 每周上两节课，而教师 b 每周有 12 节课），则将是一个很大的缺点。如果教师每周只需要工作 20 小时（使用 %），您可能会认为这是相对的。
总而言之，这并不是那么简单，您可能会寻找一位经验丰富的同事或导师来帮助您解决这个问题。
如果您需要更具体的建议，请说明您的问题。
