Tabu search
Implementation of Tabu Search, a meta-heuristic optimization algorithm for combinatorial problems. Includes benchmark comparisons against simulated annealing and greedy approaches.
The code was inspired by the medium post.
What is Tabu Search?
Tabu Search is a commonly used meta-heuristic used for optimizing model parameters. A meta-heuristic is a general strategy that is used to guide and control actual heuristics. Tabu Search is often regarded as integrating memory structures into local search strategies.
Tabu List
a list of previously visited nodes, that should not be visited for a certain number of times in future to avoid being in local minimum.
Tabu Tenure
The life cycle of a solution in tabu list. It can be used to avoid exploding tabu list.
Tabu size
The maximum length for Tabu list, which is used to avoid tabu list exploding. Each time, the oldest solution is deleted from the the list, when the size overpass the accepted limit.
Aspiration Criteria
Criteria for accepting/rejecting the solutions that are even if they are in the Tabu list. Some example can be:
- if the new solution is better than the current best solution, then the new solution is used even if it’s on the Tabu List
- setting the Tabu Tenure to be a smaller value
Neighbourhood solution:
The neighbourhood of a solution is defined as the set of solutions that are generated by flipping only one element of the solution
fun
Objective function to evaluate solutions. It receives a solution as an input
In this code, we try to solve the unconstrained binary minimization problem. The problem is NP-hard. The set of solutions are binary values (xi) given the cost function ΣiΣj (qij xi xj)
I write about this kind of work — reliability, uncertainty, building things that work in production. One email per month.