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