2024年6月19日上午，西班牙奥维耶多大学Ramiro Varela教授应吉林大学计算机科学与技术学院邀请，在王湘浩楼A521教室为我院师生作了题为“Evolving Scheduling Heuristics by Means of Hyper-heuristics”的学术报告。
在此次报告中，Ramiro教授主要介绍了iScOp 团队开发的一种遗传编程方法，该方法以优先级规则的形式发展调度启发式方法，允许贪婪算法适应具有相似特征的问题实例系列。
首先，报告介绍了调度问题及其启发式方法，介绍了调度问题的定义和重要性，以及如何使用启发式方法来解决这些问题，重点讨论了单机调度问题和旅行商问题（TSP）。随后，详细描述了单机容量有限调度问题 (1,Cap(t)||ΣTi) 的背景和定义，以及它的来源、形式化定义，通过实例说明了计算机器容量的方法。
接着，报告讲解了遗传编程（GP）作为超启发式方法来进化调度启发式算法的步骤。超启发式是一种在给定问题的启发式算法空间中搜索的方法，而GP作为一种超启发式，通过定义问题属性的字母表、操作符、文法规则来生成和评估候选的启发式算法。报告详细介绍了GP的工作原理，包括初始化、评估、选择、重组、替换等步骤，并展示了如何通过GP来进化出适应特定实例集的启发式算法。
报告还介绍了旅行商问题（TSP）的背景，并讨论了构建旅行路线的启发式算法，如最近邻（NN）算法。此外，报告展示了如何使用GP来进化TSP的启发式算法，包括定义问题属性、生成文法和评估规则。
报告展示了在单机容量有限调度问题和TSP问题上的实验结果，比较了GP生成的规则与传统启发式方法的性能。实验结果表明，GP能够显著提高启发式算法的性能，尤其是在适应特定实例集方面。
最后，报告总结了GP方法在提升调度启发式算法效果上的优势，并指出了GP在实际应用中的一些挑战，如计算成本高和搜索空间巨大的问题。报告提出了减少执行时间和提高调度启发式性能的策略，包括识别相关属性、使用语法和语义方法减少候选表达树的数量，以及使用规则集成来提高性能。此外，报告还提出了未来的研究方向，包括利用其他学习范式和探索调度启发式的替代表示方法。报告以感谢致辞结束，并为未来的研究工作提供了开放的研究方向。
讲座结束后，Ramiro教授热情地与同学们展开互动，并根据同学和老师们的问题提供了详尽的解答，本次报告受到了广大师生的热烈响应。
Ramiro Varela 是奥维耶多大学计算机系人工智能和计算机科学教授。他是智能调度和优化团队 (iScOp) 的成员，目前的研究兴趣包括启发式搜索、元启发式和超启发式，应用于调度和其他组合优化问题。他指导了多篇博士论文，并以研究员或负责人的身份参与了西班牙的各种国家项目，并发表了许多关于这些主题的期刊和会议论文。他目前是奥维耶多大学计算机博士课程的协调员和《Applied Soft Computing》杂志的副主编。他是西班牙人工智能协会 (AEPIA) 和西班牙计算机科学学会 (SCIE) 的成员。
