时间表优化问题作为调度领域的研究热点问题,涉及范围大到军事国防,小到医院学校的时间安排,在现实世界中的应用领域十分广泛。开展时间表优化问题的高效进化算法研究对国家、社会和个人都具有重大的意义。本论文以考试时间表问题作为研究背景,分析现有解决该问题的进化算法所面临的主要问题,比如：传统的直接编码方式不利于算法的搜索；同样的进化操作算子及适应度函数不利于同时优化硬约束条件和软约束条件；传统单目标建模方式的运算效率较低等。通过对超启发技术、协同进化理论、多目标优化理论的深入研究,本论文提出了多种解决该问题的启发式进化算法,主要成果包括以下五部分内容：第一,借鉴超启发技术和进化的思想,提出一种基于超启发的Memetic算法(Memetic Algorithm based on Hyper-Heuristics, MAHH)用于求解单目标考试时间表优化问题。MAHH是一种结合了超启发技术和进化策略的混合算法。超启发技术的引入改变了传统进化算法直接对个体进行搜索的模式,采用一种间接的搜索模式,即通过传统进化策略搜索启发式链表的方式寻找潜在个体。这种搜索方式可有效避免在处理考试时间表优化问题时直接编码方式对算法搜索性能的影响。除此之外,一种特殊的邻域变异方式被用于有效的指导MAHH算法进行局部搜索。算法的仿真实验表明：MAHH的实验结果在11个测试问题中的整体表现较为出色,且3个测试问题的结果比其他7种传统的超启发解决方法更加优秀。第二,提出一种基于双进化策略的Memetic算法用于求解单目标考试时间表问题(Memetic Algorithm based on Double Evolutionary Strategies, MADES)。考试时间表中存在两类需要优化的子问题,即硬约束条件优化和软约束条件优化,两类子问题并不适用于相同的进化算子和适应度函数进行处理。MADES采用直接编码方式,在两个进化空间中分别采用两种不同的进化算子和适应度函数。此外,克隆算子的应用能有效改善考试时间表问题中可行个体不足的情况。MADES的仿真试验表明：MADES中的各算子都对算法的搜索产生积极的影响；算法的运行结果与其它多种经典的考试时间表问题优化算法相比具有一定的竞争性。第三,借鉴第一章超启发与进化混合的思想,以及第二章提出的双进化策略,提出一种求解单目标考试时间表问题的自适应协同进化Memetic算法(Adaptive Co-evolutionary Memetic Algorithm, ACMA)。ACMA采用启发式搜索空间和解空间两个进化空间,利用基于超启发的进化策略和传统的进化策略分别进行硬约束条件优化和软约束条件优化。此外,为了更合理的分配算法的计算资源,设计了一种自适应协同进化算子。该算子可根据种群中个体的实际情况,动态控制算法的搜索空间。同时,两空间的个体能够通过协同进化策略进行协作。随后的仿真实验表明：超启发进化策略的引入有利于算法更好的处理硬约束条件优化,而传统的进化策略则能够较好的保持种群的多样性；自适应参数能够指导算法在更加合适的空间进行搜索；协同进化算子则进一步减少了因搜索方式的固定搜索易于陷入局部最优的可能。与接近20种解决该问题的常见算法相比,ACN MA的结果仅次于当前效果最好的四种算法,明显优于其他方法。第四,为了给多目标考试时间表问题提供高效的进化算法,本工作进行多目标优化算法的理论研究,并提出一种新的多目标免疫算法(Enhanced Multi-Objective Immune Algorithm, EMIA)。EMIA算法借鉴了经典多目标优化算法NNIA的算法思路,构建了一种资源分配模型,并在此模型的基础上,结合NNIA的克隆策略,设计了一种可动态调节不同个体克隆比例的的新型克隆算子。此外一种新的拥挤距离度量方法的设计可有效改善原有方法在处理二目标以上问题上的不足,同时辅以拥挤距离动态更新策略,可使个体分布密度的估计更为准确。针对10个测试问题,EMIA与三种经典的多目标进化算法NNIA、NSGA-Ⅱ, MOEA/D进行比较,其结果表明EMIA在绝大多数问题中其收敛性和多样性均好于NNIA、 NSGA-II,在某些问题上EMIA的收敛性比MOEA/D更佳。第五,本工作首先构建了一种新的多目标考试时间表模型。随后根据此模型的特点,同时参考之前提出的EMIA算法,设计了一种解决该问题的EMIA改进算法。多目标考试时间表模型是在原有单目标时间表模型的基础上,增加一个时间表长度最小化的目标函数。EMIA的改进算法采用一种混合初始化方法,并且舍弃了EMIA中原有的拥挤距离度量方法,采用一种简单的新方法保证种群的多样性；同时采用一种特殊的局部搜索方法进一步优化个体。最终的仿真结果表明：EMIA的改进算法在处理多目标考试时间表问题时能够得到多样性和收敛性较好的非支配解集,并且在大部分问题上,与其它传统单目标优化算法的结果相差不大。