University Course Timetabling Problem

  • H1: Only one event is assigned to each room at any timeslot.
  • H2: The room is big enough for hosting all attending students and satisfies all the features required by the event.
  • H3: No student attends more than one event at the same time.

In addition, a candidate timetable receives a penalty cost for violating any of the following three soft constraints:

  • S1: A student should not have a class in the last slot of a day.
  • S2: A student should not have more than two classes in a row.
  • S3: A student should not have a single class on a day.

A Hybrid Algorithm for UCTP

hybrid algorithm mainly based on construction heuristics and meta-heuristics

The algorithm deals separately with hard and soft constraints.

  • The hard constraints:
    • Local search and tabu search procedures
  • The soft constraints:
    • Variable neighborhood descent and simulated annealing

In particular, simulated annealing plays a significant role.

The algorithm was developed, configured and tuned through the race-based experimental methodology.

heuristic algorithm

The use of experience and practical efforts to find answers to questions or to improve performance

维基百科词条heuristic，将其定义为基于经验的技巧（technique），用于解决问题、学习和探索。并对该词进行了更详尽的解释并罗列了多个相关领域：

A heuristic method is used to rapidly come to a solution that is hoped to be close to the best possible answer, or ‘optimal solution’. A heuristic is a “rule of thumb“, an educated guess, an intuitive judgment or simply common sense.

A heuristic is a general way of solving a problem. Heuristics as a noun is another name for heuristic methods.

Heuristic可以等同于：实际经验估计（rule of thumb）、有依据的猜测（educated guess, a guess beased on a certain amount of information, and therefore likely to be right）和常识（由经验得来的判断力）。

驾驶汽车到达某人的家，写成算法是这样的：沿167 号高速公路往南行至Puyallup；从South Hill Mall 出口出来后往山上开 4.5 英里； 在一个杂物店旁边的红绿灯路口右转，接着在第一个路口左转；从左边褐色大房子的车道进去，就是North Cedar 路714 号。

用启发式方法来描述则可能是这样：找出上一次我们寄给你的信，照着信上面的寄出地址开车到这个镇；到了之后你问一下我们的房子在哪里。 这里每个人都认识我们——肯定有人会很愿意帮助你的；如果你找不到人，那就找个公共电话亭给我们打电话，我们会出来接你。

启发式策略（heuristic）是一类在求解某个具体问题时，在可以接受的时间和空间内能给出其可行解，但又不保证求得最优解（以及可行解与最优解的偏离）的策略的总称。许多启发式算法是相当特殊的，依赖于某个特定问题。启发式策略在一个寻求最优解的过程中能够根据个体或者全局的经验来改变其搜索路径，当寻求问题的最优解变得不可能或者很难完成时（e.g. NP-Complete 问题），启发式策略就是一个高效的获得可行解的办法。

元启发式策略（metaheuristic）则不同，元启发式策略通常是一个通用的启发式策略，他们通常不借助于某种问题的特有条件，从而能够运用于更广泛的方面。元启发式策略通常会对搜索过程提出一些要求，然后按照这些要求实现的启发式算法便被称为元启发式算法。许多元启发式算法都从自然界的一些随机现象取得灵感（e.g. 模拟退火、遗传算法）。现在元启发式算法的重要研究方向在于防止搜索过早得陷入局部最优，已经有很多人做了相应的工作，例如禁忌搜索（tabu）和非改进转移（模拟退火）。

作者：王斌 链接：https://www.zhihu.com/question/36635796/answer/70528089

来源：知乎著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

模拟退火

http://www.cnblogs.com/heaad/archive/2010/12/20/1911614.html

爬山算法

只能接受下一个解比当前解好的情况

模拟退火

以一定概率接受比当前解差的解，此概率随时间经过逐渐变小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/*
* J(y)：在状态y时的评价函数值
* Y(i)：表示当前状态
* Y(i+1)：表示新的状态
* r： 用于控制降温的快慢
* T： 系统的温度，系统初始应该要处于一个高温的状态
* T_min ：温度的下限，若温度T达到T_min，则停止搜索
*/
while( T > T_min )
{
　　dE = J( Y(i+1) ) - J( Y(i) ) ; 

　　if ( dE >=0 ) //表达移动后得到更优解，则总是接受移动
	Y(i+1) = Y(i) ; //接受从Y(i)到Y(i+1)的移动
　　else
　　{
      // 函数exp( dE/T )的取值范围是(0,2/w/611) ，dE/T越大，则exp( dE/T )也
      if ( exp( dE/T ) > random( 0 , 1 ) )
      Y(i+1) = Y(i) ; //接受从Y(i)到Y(i+1)的移动
　　}
　　T = r * T ; //降温退火 ，0<r<1 。r越大，降温越慢；r越小，降温越快
　　/*
　　* 若r过大，则搜索到全局最优解的可能会较高，但搜索的过程也就较长。若r过小，则搜索的过程会很快，但最终可能会达到一个局部最优值
　　*/
　　i ++ ;
}

禁忌搜索

http://www.wangxianfeng.name/2012/08/intelligent-optimization-algorithms-tabu-search/

禁忌搜索算法的基本思想：一群兔子如何寻找世界最高峰

一群兔子要寻找世界最高山峰，兔子们找到了泰山，它们之中的一只就会留守在这里，其他的再去别的地方寻找。就这样，一大圈后，把找到的几个山峰一一比较，珠穆朗玛峰脱颖而出。

  • 当兔子们再寻找的时候，一般地会有意识地避开泰山，因为他们知道，这里已经找过，并且有一只兔子在那里看着了，这就是禁忌搜索中的“禁忌表（Tabu List）”；

  • 那只留在泰山的兔子一般不会就安家在那里了，它会在一定时间后重新回到找最高峰的大军，因为这个时候已经有了许多新的消息，泰山毕竟也有一个不错的高度，需要重新考虑，这个归队时间，就是禁忌搜索中的“禁忌长度（Tabu Length）”

  • 如果在搜索的过程中，留守泰山的兔子还没有归队，但是找到的地方全是华北平原等比较低的地方，兔子们就不得不再次考虑选中泰山，也就是说，当一个有兔子留守的地方优越性太突出，超过了“best so far”的状态，就可以不顾及有没有兔子留守，都把这个地方考虑进来，这就是禁忌搜索中的“特赦准则（aspiration criterion）”。

禁忌搜索算法的基本流程

给定一个初始解和一种邻域，然后在当前解的邻域中确定若干候选解；若最佳候选解对应的目标值优于“best so far”状态，则忽视其禁忌特性，用其替代当前解和“best so far”状态，并将相应的对象加入禁忌表，同时修改禁忌表中各对象的任期；若不存在上述候选解，则选择在候选解中选择非禁忌的最佳状态为新的当前解，而无视它与当前解的优劣，同时将相应的对象加入禁忌表，并修改禁忌表中各对象的任期；如此重复上述迭代搜索过程，直至满足停止准则。条理化些，则简单禁忌搜索的算法步骤可描述如下：

1. 按照随机方法产生一个初始解作为当前解X，置空禁忌表。
2. 判断算法是否满足终止准则？若是，则停止算法并输出优化结果；否则，继续以下步骤。
3. 利用邻域函数在当前解X的邻域N(X)中选出满足禁忌要求的候选解集C-N(X);
4. 在候选解集C-N(X)中选一个评价值最好的解作为当前解Y=C-N(X)-best。
5. 对候选解判断藐视准则是否满足？若成立，则用满足藐视准则的最佳状态Y替代x成为新的当前解，即X=Y，并用与Y对应的禁忌对象替换最早进入禁忌表的禁忌对象，同时用Y替换“best so far”状态，然后转步骤7；否则，继续以下步骤。
6. 判断候选解对应的各对象的禁忌属性，选择候选解集中非禁忌对象对应的最佳状态为新的当前解，同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象元素。
7. 转到步骤2。

可以明显地看到，邻域函数、禁忌对象、禁忌表和藐视准则，构成了禁忌搜索算法的关键。其中，邻域函数沿用局部邻域搜索的思想，用于实现邻域搜索；禁忌表和禁忌对象的设置，体现了算法避免迂回搜索的特点；藐视准则，则是对优良状态的奖励，它是对禁忌策略的一种放松。

禁忌搜索的关键参数

  • 禁忌表：是用来存放禁忌对象的一个容器，放入禁忌表中的禁忌对象在解禁之前不能被再次搜索。禁忌表模拟了人的记忆机制，主要目的是阻止搜索过程中出现循环和避免陷入局部最优，进而探索更多搜索空间；
  • 禁忌长度：可以为常数，也可以根据问题的规模确定；
  • 评价函数：可以为直接评价函数，通过目标函数的运算得到评价函数；也可以是间接评价函数，构造其他评价函数替代目标函数（应反映目标函数的特性）减少计算复杂性.
  • 藐视准则：它保证搜索过程在全部候选解被禁或者是有优于当前最优解的候选解被禁时，能够释放特定的解，从而实现全局优化搜索。当一个禁忌移动在随后T次的迭代内再度出现时，如果它能把搜索带到一个从未搜索过的区域，则应该接受该移动即破禁，不受禁忌表的限制。
  • 终止规则：保证算法具有优良的优化性能和时间性能，可以
    • (1) 确定步数终止，无法保证解的效果，应记录当前最优解；
    • (2) 频率控制原则，当某一个解、目标值或元素序列的频率超过一个给定值时，终止计算；
    • (3) 目标控制原则，如果在一个给定步数内，当前最优值没有变化，可终止计算。

Neighborhood Structure

  1. $N_1(a)$ move a single event to a different room and time slot. (an event involved in at least one hard constraint violated)
  2. $N_2(a)$ swap timeslots and rooms of two events.(at least one causes a hard constraint violated.)

Do not introduce violations of new the hard constraints.

$N_1’ \subseteq N_1$ , $N_2’ \subseteq N_2$

  1. $N_3(a)$ swap all events assigned to two timeslots
  2. $N_4(a)$ (Kempe chain ?…待续)

side walk move: move that doesn’t change the evaluation function value.