Ass*_*ksi 11 python algorithm scheduling
我目前正在建立一个网站,允许我大学的学生根据他们想要的课程自动生成有效的时间表.
在开展网站工作之前,我决定解决如何有效安排课程的问题.
一些澄清:
我们大学的每门课程(我假设在其他所有大学)都包含一个或多个部分.因此,例如,微积分I目前有4个部分可用.这意味着,根据部分的数量,以及课程是否有实验室,这会极大地影响调度过程.
我们大学的课程使用主题缩写和课程代码的组合来表示.在微积分I的情况下:MATH 1110.
CRN是一个部分唯一的代码.
我所在的大学并不喜欢,这意味着男性和女性在(几乎)不同的校园里学习.我的意思几乎就是校园分为两部分.
datetime和timeranges dicts旨在减少对datetime.datetime.strptime()的调用,这是一个真正的瓶颈.
我的第一次尝试包括连续循环算法直到找到30个时间表.通过从一个输入的课程中随机选择一个部分,然后尝试从剩余的课程中放置部分来尝试构建有效的时间表来创建时间表.如果并非所有课程都符合时间表,即存在冲突,则会取消时间表并继续循环.
显然,上述解决方案存在缺陷.该算法运行时间太长,并且过于依赖随机性.
第二种算法与旧算法完全相反.首先,它使用itertools.product()生成所有可能的计划组合的集合.然后,它会遍历计划,将任何无效的计划交叉.为了确保各个部分,在验证之前调度计划组合(random.shuffle()).同样,涉及到一些随机性.
经过一些优化后,我能够让调度程序在1秒内运行,平均时间表包含5个课程.这很好,但一旦你开始添加更多课程,问题就开始了.
为了给你一个想法,当我提供一组输入时,可能的组合数量太大,以至于itertools.product()不会在合理的时间内终止,并且在此过程中会占用1GB的RAM.
显然,如果我要将其作为服务,我将需要更快,更有效的算法.在线和IRC中出现了两个:动态编程和遗传算法.
动态编程不能应用于这个问题,因为如果我正确地理解了这个概念,它会将问题分解成更小的部分,单独解决这些部分,然后将这些部分的解决方案结合在一起形成一个完整的解决方案.据我所知,这不适用于此.
至于遗传算法,我对它们了解不多,甚至无法理解如何在这种情况下应用它.我也理解GA对于一个非常大的问题空间会更有效,而且这并不是那么大.
我有什么替代品？我可以采取一种相对可以理解的方法来解决这个问题吗？或者我应该坚持我所拥有的并希望下个学期没有多少人决定参加8门课程？
我不是一个伟大的作家,所以我很抱歉这个问题含糊不清.请随时要求澄清,我会尽力帮助.
这是完整的代码.
http://bpaste.net/show/ZY36uvAgcb1ujjUGKA1d/
注意:很抱歉使用误导性标记(计划).
Aus*_*ley 15
调度是一个非常着名的约束满足问题,通常是NP-Complete.即使在与您相同的背景下,也已就该主题做了大量工作:使用高级ILP技术解决大学课程调度问题.甚至还有关于这个主题的教科书.
人们采取了很多方法,包括:
您需要减少问题空间和复杂性.做出尽可能多的假设(最大类数,基于块的时序等).这个问题没有灵丹妙药,但应该可以找到一个接近最优的解决方案.
一些半新出版物:
您读过有关基因编程的书吗？其背后的想法是，你让你想要解决的“事情”自行发展，直到它发展成为可能的最佳解决方案。
您生成了一千个时间表，其中通常零个处于有效的正确方向的任何地方。接下来，您随机更改“一些”课程。您可以根据您根据日程表的“优点”给出的评级，从这些新日程表中选择一些最好的日程表。接下来，您可以通过结合两个时间表上的一些课程来让他们重现。你最终会得到一千个新的时间表，但它们都比你原来的好一点点。让它重复直到您满意为止，然后从您生成的最后一千个中选择评分最高的时间表。
我承认，这涉及到随机性，但无论你让算法运行多久，时间表都会变得更好。就像现实生活和有机体一样，适者生存，并且可以查看同一类型时间表的不同一般“线程”，这与生成的另一个线程一样好。两种截然不同的时间表最终可以通过杂交育种来“战斗”。
涉及学校时间表和遗传编程的项目： http://www.codeproject.com/Articles/23111/Making-a-Class-Schedule-Using-a-Genetic-Algorithm
我认为他们很好地解释了你的需要。
我的最后一点是：我认为这是一个非常有趣的项目。制作起来相当困难，但一旦完成，很高兴看到您的解决方案不断发展，就像现实生活一样。祝你好运！