Nand Ravneil, Sharma Bibhya, Chaudhary Kaylash
The University of the South Pacific, Suva, Fiji.
PeerJ Comput Sci. 2022 Sep 2;8:e1068. doi: 10.7717/peerj-cs.1068. eCollection 2022.
In recent times, there has been a growing attention to intelligent optimization algorithms centred on swarm principles such as the firefly algorithm (FA). It was proposed for the continuous domain that mimics the attraction of fireflies to flashing light and has been used in discrete domains modification. A discrete domain that is a major challenge in most higher education institutes (HEI) is examination timetabling. This article presents a new methodology based on FA for uncapacitated examination timetabling problems (UETP) where the proposed method is an extension of earlier work by the authors on the continuous domain. UETP is considered in this article as it is a university examination timetabling problem, which is still an active research area and has not been solved by FA algorithm as per authors knowledge. The proposed method concentrates on solving the initial solution using discrete FA where it consolidates the reordering of examinations and slots through a heuristic ordering known as neighborhood search. Three neighborhoods are employed in this research, where one is used during the initialization phase while two are utilized during solution improvement phase. Later, through preference parameters, a novel stepping ahead mechanism is used, which employs neighborhood searches built on previous searches. The proposed method is tested with 12 UETP problems where the preference based stepping ahead FA creates comparative results to the best ones available in the literature for the Toronto exam timetabling dataset. The results obtained are proof of concept at the preliminary stage and require further experiments on other educational datasets such as the second international timetable competition benchmark sets. The newly introduced preference based stepping ahead mechanism takes advantage of the current best solution space where it exploits the solution space for better solutions. This paves the way for researchers to utilize the mechanism in other domains such as robotics, .
近年来，以萤火虫算法（FA）等群体原理为核心的智能优化算法受到了越来越多的关注。它是为连续域提出的，模仿萤火虫对闪光的吸引力，并且已用于离散域的修改。在大多数高等教育机构（HEI）中，离散域是考试时间表安排这一主要挑战。本文提出了一种基于萤火虫算法的新方法，用于解决无容量限制的考试时间表安排问题（UETP），该方法是作者早期在连续域工作的扩展。本文考虑UETP是因为它是大学考试时间表安排问题，这仍然是一个活跃的研究领域，据作者所知，尚未被萤火虫算法解决。所提出的方法专注于使用离散萤火虫算法求解初始解，通过一种称为邻域搜索的启发式排序来整合考试和时间段的重新排序。本研究采用了三个邻域，其中一个在初始化阶段使用，另外两个在解改进阶段使用。后来，通过偏好参数，使用了一种新颖的向前步进机制，该机制采用基于先前搜索构建的邻域搜索。所提出的方法在12个UETP问题上进行了测试，其中基于偏好的向前步进萤火虫算法与多伦多考试时间表数据集文献中可用的最佳结果产生了可比结果。获得的结果是初步阶段的概念验证，需要在其他教育数据集（如第二届国际时间表竞赛基准集）上进行进一步实验。新引入的基于偏好的向前步进机制利用了当前的最佳解空间，在其中探索更好解的解空间。这为研究人员在机器人技术等其他领域利用该机制铺平了道路。
