Tabu Search: Finding the Minimal Value of Peaks Function

• Download source - 24.73 KB

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 5^th 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.
Additional information regarding the code is explained throughout the code comments. However, for further questions, comments and updates please do not hesitate to ask, and visit my personal website.

Screenshot

History

• 5^th July, 2011: Initial version