14,426,608 members

# Tabu Search: Finding the Minimal Value of Peaks Function

Rate this:
7 Jul 2011CPOL
Tabu search algorithm used for finding the minimal value of the function

## Introduction

This is the implementation of tabu search in order to find the global minimum of the objective function which is given in the picture above. It is developed in C# as a console application.

## Tabu Search

Taboo – strong social prohibition (ban) relating to any kind of human activity or social custom that is sacred and forbidden based on moral judgement and even sometimes religious beliefs (Wikipedia).

Tabu Search (TS) is a metaheuristic algorithm which represents a modification of basic local search.

• Tabu list is implemented using short-term memory.
• Tabu list stores tabs.
• The simplest implementation stores whole forbidden solutions.
• This approach is not used very often, due to huge requirements regarding memory and processing time.
• Most often, tabu list stores several last transformations or key features of the solutions visited.
• Any transformation opposite to the one used to reach the current point is forbidden.
• The change of a feature back to the previous one is forbidden.
• Neighborhood consists of all vectors which differ in one bit position.
• Tabu list: `T=[t1,t2,...,tn]`.
• Each element of tabu list represents the number of iterations during which it is not allowed to change the bit value for each position of the current solution.
• The tabu list is updated after each iteration:
---------------------------------------
Example:
Iteration `k`:
Current solution: `x=[1, 0, 1, 1, 0, 0, 1, 0]`
Tabu list: `T=[0, 2, 0, 3, 0, 0, 1, 4]`
Iteration `k+1`:
New current solution: `x=[1, 0, 1, 1, 1, 0, 1, 0]`
New tabu list: `T=[0, 1, 0, 2, 5, 0, 0, 3]`
--------------------------------------
• Duration of tabu (parameter) is `M=5`, which means that the 5th position of bit string can't be changed during the next 5 iterations.

Algorithm of Tabu list is explained in the picture:

Example of the search process in Tabu search along with the tabu list (`size = 5`) on the right side:

## Using the Code

The peaks function should be inserted in method `vrijednostFunkcije`. It takes 2 parameters `x1 `& `x2 `and calculates the value of the objective function defined in this method. The code looks like this:

```static double vrijednostFunkcije(double x1, double x2)
{
// Calculating the value of the function
double y = 1.8 * Math.Pow(x1, 2) + 0.04 * Math.Pow(x1, 4) -
0.55 * Math.Pow(x1, 3) + 2 * Math.Pow(x2, 2) + 5;
return Math.Round(y, 2);
}```

Coordinates are stored in a multidimensional array:

```Tacka[,] myTacka = new Tacka[15,14]; // Multidimensional array of
//object Tacka(Point): (15-1) rows and (14-1) columns
double[] arrX1 = { -3.0, -2.0, -1.0, 0,
1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 	// Data for Columns(x1): 14
double[] arrX2 = {- 3.50, -3, -2.50, -2, -1.50, -1, -0.50, 0, 0.5,
1.0, 1.5, 2, 2.5, 3, 3.50 }; 	// Data for rows(x2): 15
for (int i = 0; i < 15; i++) 		// Row
{
for (int j = 0; j < 14; j++) 	// Column
{
myTacka[i, j] = new Tacka(arrX1[j], arrX2[i],
vrijednostFunkcije(arrX1[j], arrX2[i])); 	// Column, Row, Value
}
}```

For storing the visited tabs, tabu list is created by defining the generic collection of type `Queue`.

## History

• 5th July, 2011: Initial version

## Share

 Software Developer Unis Energetika Bosnia and Herzegovina
More on www.faruk.ba

 First Prev Next
 Someone can provide me the Pseudo-code from this sample code ? OrozcoHsu20-Dec-11 23:47 OrozcoHsu 20-Dec-11 23:47
 My vote of 5 OrozcoHsu20-Dec-11 23:45 OrozcoHsu 20-Dec-11 23:45
 My vote of 5 sam.hill7-Jul-11 5:54 sam.hill 7-Jul-11 5:54
 Last Visit: 23-Jan-20 21:33     Last Update: 23-Jan-20 21:33 Refresh 1