1. Introduction
One of the many problems that are considered to be NP-Hard is the Multiple Sequence Alignment one that initially requires, as for any other of its siblings, a specific encoding schema and design of the main functionalities of the heuristics algorithm being implemented and executed. This design was supported by references [1] [2] [3] [4].
The main issue with that problem, as discussed in our ICeND2013 conference [1], was to come up with an encoding that would be suitable for the different Heuristics algorithms inspired by papers [5] [6] [7] [8]. Once the encoding is agreed on, the remaining part of designing and building the algorithm that will get a solution as close to the optimum as possible would be nonetheless as important. We have decided in our research to focus on the Tabu Search heuristic. However, we discovered that to be able to adjust some of the flaws of the standard algorithm, we improved it by adding functionalities like tracing the executions, so that later analysis could help tune the initial parameters better.
In this paper, we’ll be discussing the implementation of an advanced version of the Tabu Search algorithm, adding to the standard version some modifications such as the tracing functionalities, mainly through the use of different kinds of memories, short-term (STM) and long-term (LTM) instead of one, for solutions checked as Tabu or as good fit, along with some useful parameters.
The problem in the standard algorithm would be that, despite “unfit” solutions would be moved/marked as Tabu, so they won’t be handled in further iteration, there is no guarantee that the algorithm would get out of a local optimum which could eventually be far from the effective best solution.
2. Initial Algorithm
Standard Algorithm
Tabu Search (TS) is a heuristic procedure proposed by Fred Glover to solve discrete combinatorial optimization problems. The basic idea is to avoid that the search for best solutions stops when a local optimum is found, by maintaining a list of non-acceptable or forbidden (taboo) solutions/costs, called Tabu list or Short-Term Memory (STM). We have found many papers discussing different implementations of TS, amongst them references [9] [10] [11] [12] [13]. Other papers in literature suggest some hybrid or generic implementation of the initial heuristic procedure, as in reference [14] - [19], while keeping focus on the problem being tackled.
Advanced TS algorithms suggest that some of the best solutions found so far be saved for search diversification in a list called Long-Term Memory (LTM).
The use of these memory lists bring to light the fact that the updating process of the current and best solution does ignore those that were marked in the lists, which grow and shrink per iteration. Occasionally, moving the current solution to a “forbidden” one is allowed given a certain “aspiration” criteria, usually involving an improvement in cost from the current one.
As opposed to other algorithms, the current solution of the inner loop next iteration is selected from a set of N neighbor solutions, deduced from the actual current one by perturbing it N times. This solution will be overwritten if, at the beginning of the next iteration, a better solution was previously acknowledged in memory.
![]()
Figure 1. Standard Tabu search general flow diagram.
As shown in Figure 1, the standard algorithm starts from an initial solution and set of parameters then repeatedly, until a certain stopping condition is satisfied, creates a candidate list of solutions called neighbors, evaluates and chooses the best admissible one among them, updates the STM and acquisition components with the selection, then replace the current solution with the one newly selected.
3. Proposed Algorithm
The main idea behind Tabu Search algorithm was to simulate placing solution as Tabu, when their evaluation will be more costly to the algorithm in further iterations, thus avoiding using them as potential neighbor. However, most literature about the standard algorithm don’t mention any approach to avoid getting stuck in a local optimum area, since that best solution is not going to be moved to Tabu. Because of this gap in literature, we decided in our algorithm to give the opportunity to remember a previously best fit solution as a potential optimum instead of the best one, into a long-term memory. Adding more memories into the algorithm came supported by the procedure that the human brain follows to shift selected information from its STM (also known as daily memory) into its LTM (mostly storing/recalling experiences from the past).
The steps of our proposed algorithm are almost very similar to those of the basic standard algorithm, with the difference that some of them, highlighted in blue, offer the possibility to later on trace back each execution and allow better analysis, thus resulting in eventual update of initial parameters. The words/fragments highlighted in green are more of structure and/or behavior enhancements that try to bridge the gap between the initial annealing process and our simulated annealing algorithm.
3.1. Main Procedure
Inputs: Initial Solution S0, Number of Iterations numIterations,
Number of Neighbors numNeighbors,
Precondition:
Outputs: Optimal Solution BestS,
Algorithm:
Assign to “CurS” the value of the initial solution “S0”
Compute estimate of “CurS” into “CurEstimate”
Assign “CurS” and estimate to {“BestS”, “BestEstimate”}
Create a dynamic list “LTM” of solutions and estimates
Initialize index “i” to 1
While True do
If
or
then
Exit While
Update LTM with current and/or best solutions
Reset the STM memory
{{Current Solution and Estimate are selected}}
{{ from LTM first if possible}}
Select best fit between LTM and STM into “CurS”
Compute estimate of “CurS” into (
)
Save in history “CurrS” {{history
memory}}
Add to STM values of “CurS” and “CurEstimate”
Generate a list of “Neighbors” from “
”
For “j” from
to “numNeighbors” do
Assign to “Sol” neighbor solution at “j”
Compute estimate of “Sol” into “SolEstimate”
{{If neighbor is not tabu or tabu}}
{{ but aspires to be better than CurS}}
{{Otherwise, consider the neighbor as Tabu}}
If
Or
Then
Assign “Sol” and “SolEstimate” to current
{{Update best solution so far}}
{{ if neighbor aspires to be the best}}
If
Then
Assign “Sol” and “SolEstimate” to best
Else-If
And
Then
Add to STM value of “
”
Save in history {“BestS”, “BestEtimate”, “CurS”, “CurEstimate”
“Neighbors”, “LTM”, “STM”}
Increment the index “i” by 1
The proposed algorithm, discussed in the main steps mentioned above and in Figure 2, differs from the standard one mainly by the introduction two update steps before and after checking the stopping/iterating condition: first applies on the two running (current and best) solutions, while the other one modifying the different memory components is applied initially and after the condition check. Note that after updating those components, the algorithm will be able to switch
![]()
Figure 2. Advanced Tabu search general flow diagram.
the current solution with a best fit previously evaluated and selected as a potential optimal solution.
3.2. Object-Oriented Design
In order to implement the algorithm steps in Figure 2, we designed our object-oriented components in a simple way as shown below in Figure 3 with suggested classes representing some problems in Figure 4, since the flexibility we are offering is much more in the steps themselves. In order to simplify the suggested algorithm, we considered the memory components as lists of solutions, and the selection and/or memorization of solutions as procedures to be handled directly by the algorithm’s main steps.
The main component “TSProblem”, on the upper-right, is intended to hold properties managing the different parameters, components and methods the algorithm will need while executing its steps, whether generic and/or purpose-specific, as for ex: the ability to create a new solution or get a new neighbor.
The class “TSSolution”, just at its left, is intended to hold properties managing the different values encapsulated in each solution handled during execution, mainly those related to the evaluation process.
Last but not least, the “TabuSearch” base algorithm with its two base/super classes, show the main components being handled and functionalities being executed per iteration. The reason behind splitting them into three classes was to set the ground for potential use of some methodologies with other algorithms that might find some common grounds, and benefit from Object-Oriented development as much as possible.
In order to prove that our implementation is generic enough, we designed some basic problems, where we can have results to compare with those of the algorithm, in a simple way. For simplicity and efficiency, we chose to work with simple math formula “Formula” fed with values of radix {2, 8, 10 or 16}. We also have implemented each radix-related problem as both minimization and maximization.
![]()
Figure 3. Suggested TS components class diagram.
In this implementation, only the estimates are moved to the STM list, instead of the whole solution’s properties. Therefore, evaluating if a solution is tabu becomes as simple as evaluating its penalty. The aspiration method implemented relies on finding the minimal or maximal solution estimate.
If the Tabu Search algorithm deals with minimization, the estimate of a solution should be the result of the evaluation function, mentioned in a previous chapter, and multiplied by –1 otherwise. For both approaches, the result of the neighbor function for a given solution is, in other words, a set of results of the perturbation of this solution.
The fact that TS may deal, with either minimization or maximization, yields the obligation to implement, consequently, a method used during the aspiration, and that returns the best solution between 2 solutions fed as parameters.
In order to illustrate the generic implementations applied on these problems, we have developed a quick straight forward windows application, in which we dynamically modified the parameters a default algorithm based on the suggested generic implementation, instead of writing many versions inheriting for our main implementation.
![]()
Figure 4. Some supporting problem implementations.
Figure 5 shows the first step in running the algorithm, which is the problem selection. In our windows application, we populated this drop-down dynamically from a folder containing problems included in our package.
Next step, shown in Figure 6 and Figure 7, is about parametrization of the algorithm run, whether concerning properties of the problem (environment) itself or the execution’s methods. Even though default values were given to those parameters, we advise to modify them to be able to view effective results, and/or test different cooling schedules.
The third and final step, as shown in Figure 8, is to simply run the algorithm. In the above screenshot, we are showing the generated result of an execution on problem Pb001, along with the actual value corresponding to the last current solution compared to the cost evaluated during the last iteration of the algorithm.
![]()
Figure 5. Win App, TS execution—problem selection.
![]()
Figure 6. Win App, TS exec.—problem parameterization.
![]()
Figure 7. Win App, TS exec.—algorithm parameterization.
![]()
Figure 8. Win App, TS execution—sample run.
![]()
Figure 9. TS Tracing functionality—initial iteration.
The next section of the screen shows the optimal solution it was able to detect with a cost of 0, which is mathematically the actual best cost. For more complex problems, running the algorithm for more time will most probably change the best cost value converging towards a more suitable optimum.
Tracing back the execution of the execution mentioned we can see in Figure 9 that the algorithm reached 80377 as the best solution at the end of the initial step.
4. Conclusion
This research can be developed by trying to design and implement solutions to the below issues raised during our research:
➢ Fixed Input Parameters:
○ “Tabu Search” explores the search space for a given number of iterations, and a number of neighbors per iteration.
➢ Applying benchmarks for more accurate analysis and validation of the alternatives
○ Use benchmarks for different problem encodings have to be applied.
➢ Randomness doesn’t handle potentially repetitions:
○ In Neighbor method
➢ Initial solution may be far from the optimal one, thus the algorithm will take more time.
➢ Moving a solution to and from Tabu lists is not dynamically efficient, as it doesn’t really account or take into consideration the potential effect of the values of some fields or variables induced by previous moves.
➢ Inspired by references [10] [11] [14] and [16] amongst others, more efforts can be put into making more use of the LTM and possible introduction of other types of memory.
➢ Another future work idea would be work on the memory components by making them more self-manageable through encapsulating the updating and selection procedure, then enriching the system with other types of memory components that would allow potential intensification and diversification during the algorithm run. This idea is further supported by references [20] to [28].
➢ A second future work could be to allow the main procedure of generating neighbors and selecting from memories “smart” enough to gain time and search further more.