## Thursday, January 29, 2009

### Modern Genetic (And Other) Algorithms Explained: Part 6 - Tabu Search

(This is part 6 in the Modern Genetic Algorithms Explained series, click here to go to the first post, or browse through all the parts with the Table Of Contents at the end of this post.)

Tabu search is not really "modern" anymore, but still widely used nonetheless.

The pseudocode looks like this:

```Construct an initial solution Until timelimit hit or satisfiable solution found do:     Find all neighbours which are not in the tabu list, and calculate their score     Pick the best neighbour, add the previous solution to the tabu list```

Notice that the "best neighbour" must not be better than the current solution, or than the ever best found solution.

Maintaining a tabu list can be time and memory consuming, alternatively we could construct a list like this: add the difference between two following solutions to the list (so that they cannot be undone), and keep it in the list for n iterations. N, or the length of the list is important: make it too long and the algorithm might get stuck, make it too short and the algorithm will tend towards local maxima.

This time, I've coded the example in PHP, I hope nobody minds:

```\$target = 300; //construct an initial solution \$tabulist = array('ttl' => array(), 'change' => array()); \$solution = array(); \$min = 0; \$max = 100; for (\$i=0;\$i<6;\$i++)     \$solution[] = rand(\$min,\$max);    //until solution found while (true){     \$best_neighbour_solution = false;     \$best_neighbour_score = 1000;     \$best_neighbour_tabu = false;     for (\$position=0;\$position<6;\$position++){         if (!in_array("\$position+",\$tabulist['change'])                 and \$solution[\$position] < \$max){             \$temp_solution = \$solution;             \$temp_solution[\$position]++;             \$score = fitness(\$temp_solution,\$target);             if (\$score < \$best_neighbour_score){                 \$best_neighbour_score = \$score;                 \$best_neighbour_solution = \$temp_solution;                 //make sure this step doesn't get undone                 \$best_neighbour_tabu = "\$position-";             }         }         if(!in_array("\$position-",\$tabulist['change'])                 and \$solution[\$position] > \$min){             \$temp_solution = \$solution;             \$temp_solution[\$position]--;             \$score = fitness(\$temp_solution,\$target);             if (\$score < \$best_neighbour_score){                 \$best_neighbour_score = \$score;                 \$best_neighbour_solution = \$temp_solution;                 //make sure this step doesn't get undone                 \$best_neighbour_tabu = "\$position+";             }         }     }     //pick the best neighbour     \$solution = \$best_neighbour_solution;     \$fitness = fitness(\$solution,\$target);     echo "Iteration \$iterations: fitness = \$fitness\n";     if (\$fitness == 0){         echo "Perfect solution found:\n";         print_r(\$solution);         die;     }     //add change to tabu list     \$tabulist['ttl'][\$iterations] = 5; //remember for 5 iteration     \$tabulist['change'][\$iterations] = \$best_neighbour_tabu;     //update the tabulist     foreach (\$tabulist['ttl'] as \$key => &\$val){         \$val--;         if (\$val <= 0){             unset(\$tabulist['ttl'][\$key]);             unset(\$tabulist['change'][\$key]);         }     }     echo "Iteration \$iterations: tabulist now contains "         .count(\$tabulist['ttl'])." items \n";     \$iterations++; } function fitness(\$array, \$target){     return abs(array_sum(\$array)-\$target); } ```

The neighbour calculation could be done a little better (there's a bit of ugly duplicate code), but the following output is given:

```Iteration : fitness = 57 Iteration : tabulist now contains 1 items Iteration 1: fitness = 56 Iteration 1: tabulist now contains 2 items Iteration 2: fitness = 55 Iteration 2: tabulist now contains 3 items Iteration 3: fitness = 54 Iteration 3: tabulist now contains 4 items Iteration 4: fitness = 53 Iteration 4: tabulist now contains 4 items Iteration 5: fitness = 52 Iteration 5: tabulist now contains 4 items ... Iteration 55: tabulist now contains 4 items Iteration 56: fitness = 1 Iteration 56: tabulist now contains 4 items Iteration 57: fitness = 0 Perfect solution found: Array (      => 66      => 14      => 20      => 99      => 14      => 87 ) ```

With this sample problem, such an output was, of course, expected. Notice that I've used the second method of keeping a tabulist.

This post concludes this series, we only have one post to go, with a general conclusion.

-----