Tabu Search (TS)

A module for the tabu search with long-term memory for discrete/combinatorial optimization.

Original papers:

  • Glover, F. (1989). Tabu search—part I. ORSA Journal on computing, 1(3), 190-206.

  • Glover, F. (1990). Tabu search—part II. ORSA Journal on computing, 2(1), 4-32.

What can you use?

  • Multi processing: ❌

  • Discrete spaces: ✔️

  • Continuous spaces: ✔️

  • Mixed Discrete/Continuous spaces: ✔️

Parameters

class neorl.evolu.ts.TS(mode, bounds, fit, tabu_tenure=6, penalization_weight=0.8, swap_mode='perturb', ncores=1, seed=None)[source]

Tabu Search Algorithm

Parameters

  • mode – (str) problem type, either min for minimization problem or max for maximization

  • bounds – (dict) input parameter type and lower/upper bounds in dictionary form. Example: bounds={'x1': ['int', 1, 4], 'x2': ['int', -10, 10], 'x3': ['int', -100, 100]}

  • fit – (function) the fitness function

  • tabu_tenure – (int): Timestep under which a certain list of solution cannot be accessed (for diversification). Default value is 6.

  • penalization_weight – (float): a scalar value for the coefficient that controls exploration/exploitation, i.e. importance of the frequency of a certain action performed in the search. The higher the value, the least likely is an action to be performed again after multiple attempts.

  • swap_mode – (str): either “swap” for swapping two elements of the input or “perturb” to perturb each input within certain bounds (see Notes below)

  • ncores – (int) number of parallel processors (only ncores=1 is supported now)

  • seed – (int) random seed for sampling

evolute(ngen, x0=None, verbose=False)[source]

This function evolutes the TS algorithm for number of generations

Parameters

  • ngen – (int) number of generations to evolute

  • x0 – (list) initial position of the tabu (vector size must be of same size as len(bounds))

  • verbose – (bool) print statistics to screen

Returns

(tuple) (best individual, best fitness, and dictionary containing major search results)

Example

from neorl import TS

#Define the fitness function
def Sphere(individual):
    """Sphere test objective function.
                    F(x) = sum_{i=1}^d xi^2
                    d=1,2,3,...
                    Range: [-100,100]
                    Minima: 0
    """
    y=sum(x**2 for x in individual)
    return y


#Setup the parameter space (d=5)
nx=5
BOUNDS={}
for i in range(nx):
    BOUNDS['x'+str(i)]=['int', -100, 100]

#setup and evolute TS
x0=[-25,50,100,-75,-100]  #initial guess
ts=TS(mode = "min", bounds = BOUNDS, fit = Sphere, tabu_tenure=60, 
      penalization_weight = 0.8, swap_mode = "perturb", ncores=1, seed=1)
x_best, y_best, ts_hist=ts.evolute(ngen = 700, x0=x0, verbose=1)

Notes

  • Tabu search (TS) is a metaheuristic algorithm that can be used for solving combinatorial optimization problems (problems where an optimal ordering and selection of options is desired). Also, we adapted TS to solve bounded discrete problems for which the candidate solution needs to be perturbed and bounded.

  • For swap_mode, choose perturb for problems that have lower/upper bounds at which the individual is perturbed between them to find optimal solution (e.g. Sphere function). Choose swap for combinatorial problems where the elements of the individual are swapped (not perturbed) to find the optimal solution (e.g. Travel Salesman, Job Scheduling).

  • tabu_tenure refers to the number of timesteps to perform to enable any particular update to happen again (i.e. swapping of two entries \(x_i, x_j\) or perturbation of an entry \(x_i\)). For example, if tabu_tenure=6 and \(x_i\) of a candidate solution is perturbed, within 6 additional timesteps, \(x_i\) can be perturbed if and only if the resulting perturbation yields to a solution better than the current best one.

  • penalization_weight represents the importance/frequency of a certain action performed in the search. Large values of penalization_weight reduces the frequency of using the same action again in the search.