Tabu search
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)
How the Tabu search is different from particle swarm optimization?
Both Tabu search and PSO are meta-heuristic approaches for global optimization. In Tabu search, the algorithm will try to quarantine some search space which been already visited to help exploration. While PSO will try to follow a leader with some degree of surrounding exploration for the agents.