Click here to Skip to main content
14,426,608 members

Tabu Search: Finding the Minimal Value of Peaks Function

Rate this:
4.56 (6 votes)
Please Sign up or sign in to vote.
4.56 (6 votes)
7 Jul 2011CPOL
Tabu search algorithm used for finding the minimal value of the function
Image 1

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:

Image 2

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

Image 3

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

Image 4

History

  • 5th July, 2011: Initial version

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

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

Comments and Discussions

 
Questionthank you Pin
heba ahmad7-Mar-15 2:31
Memberheba ahmad7-Mar-15 2:31 
GeneralSomeone can provide me the Pseudo-code from this sample code ? Pin
OrozcoHsu20-Dec-11 23:47
MemberOrozcoHsu20-Dec-11 23:47 
GeneralMy vote of 5 Pin
OrozcoHsu20-Dec-11 23:45
MemberOrozcoHsu20-Dec-11 23:45 
GeneralMy vote of 5 Pin
sam.hill7-Jul-11 5:54
Membersam.hill7-Jul-11 5:54 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Article
Posted 7 Jul 2011

Tagged as

Stats

38.1K views
1.7K downloads
9 bookmarked