Tabu Search Algorithm: Optimizing the Search Runtime
Abdul Nayeem Khalid, Naga Malleswara Rao Baki, Tarun Sai Phani Varma, Adnan Khan, Nilu Singh · 2024
In the realm of combinatorial optimization, the Tabu Search algorithm has proven to be a powerful tool for solving complex problems. However, its practical implementation often encounters computational challenges, particularly in managing the frequently accessed” tabu list.” In this paper, authors introduced the Drop-set data structure, a novel approach designed to streamline the management of the tabu list within the Tabu Search algorithm. The Drop-set data structure enables the efficient addition and removal of elements from the tabu list in constant time, alleviating the computational burden associated with traditional data structures. Through experimental evaluation conducted on the well-known knapsack problem, authors demonstrated the performance enhancements achieved by integrating the Drop-set data structure into the Tabu Search algorithm. Results indicate promising reductions in computational time, thereby propelling the algorithm's convergence speed and improving solution quality. This research not only presents a practical solution to enhance Tabu Search but also establishes a foundation for the development of future optimization algorithms that can benefit from the integration of the Drop-set data structure.