# Multipath Adaptive Tabu Search for a Vehicle Control Problem

Authors: Jukkrit Kluabwang; Deacha Puangdownreong; Sarawut Sujitjorn
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

Tabu search has become acceptable worldwide as one of the most efficient intelligent searches applied to various real-world problems. There have been different modifications made to the generic tabu search in recent years to achieve better performances. Among those reviewed in the introduction of this paper, the adaptive tabu search (ATS) has incorporated the backtracking and the adaptive search radius mechanisms that help accelerate the search and release it from a local solution lock. The paper explains an enhancement made to the ATS to accomplish multipath ATS (MATS) algorithms. Performances of the ATS and the MATS are evaluated using surface optimization problems, and results are presented in the paper. Finally, the MATS is applied to solve a real-world vehicle control problem.


---

## Body

## 1. Introduction

The tabu search (TS) [1], one of the most widely used local search techniques, was proposed to solve the combinatorial optimization problems. The TS is based on the neighbourhood search approach and adaptive memory. With the common deterministic scheme, the search process of the TS is commonly based on the recency and the frequency approaches [2, 3]. The high-quality solution found by each search round is stored in the tabu list (TL). In case of entrapment (deadlock) problems caused by some local minima, the elite solutions stored in the TL are retrieved according to the aspiration criteria (AC) for starting a new search such that the search could be released from the deadlock. By literatures, the TS has been successfully applied to solve optimization problems in various fields, for examples, power systems [4, 5], transportation [6], flow shop [7], food processing [8], and so forth. However, the conventionally simple TS cannot completely handle the deadlock problems. With this challenging task, some researchers have proposed modified versions of the original TS to find alternative, more potential versions to overcome such problems. Distinctively modified version of the TS include the reactive tabu search (RTS) [9, 10], the parallel tabu search (PTS) [11–13], the modified tabu search (MoTS) [14–16], the probabilistic tabu search (PrTS) [17–19], and the hybrid tabu search (HTS) [20–29].Recently, the adaptive tabu search (ATS) has been launched [30] as a modified versions of the original TS. The ATS consists of the backtracking (BT) and the adaptive search radius (AR) mechanisms. As firstly introduced in 1996 [7], the BT regarded as a diversification strategy is used for the search to escape from the deadlocks caused by local minima. The AR concept introduced in 1989 [31] and regarded as an intensification strategy is applied to speed up the search process. The convergence analysis and the performance evaluation of the ATS were reported [30]. In addition, the ATS has been successfully applied to various engineering problems, for examples, electrical system protection [32], dynamical system identification [33], control synthesis [34], and acoustic signal processing [35].This article proposes the multipath adaptive tabu search (MATS) and begins with the review of the ATS algorithms in Section2. Section 3 explains the MATS in details and presents some algorithm analyses. Performance evaluations of the MATS compared with the ATS via surface optimization problems can be found in Section 4. An application of the proposed MATS to the control synthesis problem of a scaled vehicle (the Illinois Roadway Simulator system (IRS) [36]) is illustrated in Section 5. The application is considered as a special case (n=2) of the n-dimensional continuous optimization problems. Conclusion follows in Section 6.


## 2. Review of the Adaptive Tabu Search

In this section, reviews of the adaptive tabu search (ATS) are provided. The section is divided into two parts, that is, the ATS algorithms review and its performance evaluation via some benchmark surface optimization problems.


### 2.1. Adaptive Tabu Search Algorithms

Regarding the original TS as the predecessor, the adaptive tabu search (ATS) consists of two additional mechanisms, that is, the backtracking (BT) regarded as a diversification strategy and the adaptive search radius (AR) regarded as an intensification strategy. The ATS begins the search with some random initial solutions belonging to an entire search space. In practice, the users may implement heuristically seeded initial solutions instead. All solutions in a neighbourhood search space within a certain search radius are evaluated via the objective function. The solution giving the minimum objective value (cost value) is set as a new starting point for the next search round and memorized in the tabu list (TL). According to the original TS algorithm and the TL property, the visited search spaces (or visited solutions) are prohibited for consecutively generated solutions. These search spaces are remarked as tabu. However, once the search is held by a local minimum (deadlock problem), the BT is activated. The BT looks up the TL and selects one of the memorized solutions as a new starting point. A new search could begin in a new direction. Hence, the search can possibly be released from the deadlock, and the search proceeds towards a better local minimum. Once the search approaches an elite local solution, the AR is invoked to speed up the search process. The search radius is subsequently decreased in accordance with the cost value of the current solution to provide finer and finer solutions within a short duration. The less the cost value, the smaller the search radius becomes. With these two mechanisms, a sequence of solutions obtained by the ATS is efficiently and rapidly converged towards the global minimum. Figure1 expresses the generic algorithms of the original TS and the ATS with the BT and the AR mechanisms, respectively, while Figure 2 depicts the diagram representing some movements of the ATS. Both figures give a clear view for the reader to follow.Generic algorithms of the TS and the ATS: (a) generic TS algorithms, (b) generic ATS algorithms, (c) the BT mechanism of the ATS, and (d) the AR mechanism of the ATS.
(a)(b)(c)(d)Figure 2
Movements of the ATS.


### 2.2. Performance Evaluation of the ATS

Although the performance evaluation of the ATS has appeared [30], the work reported here is an extension via six well-known surface optimization problems, that is, Bohachevsky function (BF), Rastrigin function (RF), Shekel’s foxholes function (SF), Shubert function (ShF), large area Schwefel function (type-1 or ScF#1), and small area Schwefel function (type-2 or ScF#2), respectively. Details of these tested functions are summarized in Table 1. Among these, the ShF contains 18 global solutions while each of the rest has only one.Table 1
Summary of the surface optimization problems.
Surface namesSurface functionsSearch spacesSketchesBohachevskyF(x,y)=x2+2y2-0.3cos(3πx)-0.4cos(4πy)+0.7, fmin(0,0)=0[-2,2]RastriginF(x,y)=x2+y2-10cos(2πx)-10cos(3πy)+20,
fmin(0,0)=0[-2,2]Shekel’s foxholesf(x1,x2)=[1/500+∑j=125(1/(j+∑i=12(xi-aij)6))]-1[-40,40]Whereaij=(-32-1601632-32⋯01632-32-32-32-32-32-16⋯323232)fmin(-32,-32)=1Shubertf(x,y)=(∑i=15icos((i+1)x1+i))(∑i=15icos((i+1)y+i))[-10,10]fmin(xj,yj)=-186.7309,j∈{1,2,…,17,18}Schwefel If(x1,x2)=418.9829×2-∑i=12(xisin|xi|), fmin(421,421)=0[-500,500]Schwefel II[400,500]The ATS algorithms were coded by MATLAB, and run on the Intel Celeron(R), 2.6 GHz, 238 Mbytes SD-RAM, 30 Gbytes HDD. Referring to the Table1, the global solutions of the tested functions are as follows: BF and RF-{x=y=0 with the cost value f(0,0)=0}; SF-{x=y=-32 with f(-32,-32)=0.998}; ShF-{xj,yj with f(xj,yj)=-186.7309, where j=1,2,…,18}, and ScF#1 and #2-{x=y=421 with f(421,421)=0}. The variables’ boundaries of all tested functions are set to form the corresponding search spaces as declared in the Table 1.Following the recommendations [30], the parameter settings of the ATS for each tested function are declared in the Table 2, where Remax is the maximum allowance of the solution cycling before invoking the BT, kth is the backward-selected solution by the BT, countmax is maximum search round, R is search radius, J is the cost value, and Jmin is minimum cost value used as the termination criteria (TC) for all tests in order to assure the global minimum found. The performance tests were conducted 50 trials against each tested function to obtain the average search round and time consumed. Each trial starts with a random initial solution generated by MATLAB using a seed number. The initial solution forms the center of a uniformly distributed hypersphere of a given radius, from which a neighbourhood is generated. The ATS stops when J<Jmin or count≥countmax.Table 2
Setting of the ATS search parameters.
Test functionATS parametersSearch radiusno. of neighboursBTARTCRemaxkthStage IStage IIStage IIICountmaxJminBF0.2 (5%)3055J<0.1, R=0.002J<0.001, R=0.002—10,0001e-9RF0.2 (5%)3055J<0.1, R=0.002J<0.001, R=0.002—10,0001e-8SF0.8 (1%)3055J<5, R=0.2J<2, R=0.1—10,0000.999ShF1.0 (5%)3055J<-100, R=0.1J<-150, R=0.015—10,000−186.7ScF#1100 (10%)2055J<100, R=50J<10, R=0.01J<1, R=0.00110,0001e-4ScF#21.0 (1%)2055J<10, R=0.01J<1, R=0.001—10,0001e-4The results obtained are summarized in Table3, where the first row stands for the average time consumed, the second row is the average search round, and the third row expresses the average time consumed per one search round. It is found that the ATS yields very satisfactory search performance in terms of solution convergence and the search time consumed for all surface optimization problems.Table 3
Results of the ATS’s performance evaluation.
Search resultsTest functionsBFRFSFShFScF#1ScF#2(1) Search time (sec)5.39408.20672.28373.397838.10370.2522(2) Search rounds556.06759.80108.22342.54336.2431.24(1)/(2) (sec/round)0.00970.01080.02110.00990.11330.0081


## 2.1. Adaptive Tabu Search Algorithms

Regarding the original TS as the predecessor, the adaptive tabu search (ATS) consists of two additional mechanisms, that is, the backtracking (BT) regarded as a diversification strategy and the adaptive search radius (AR) regarded as an intensification strategy. The ATS begins the search with some random initial solutions belonging to an entire search space. In practice, the users may implement heuristically seeded initial solutions instead. All solutions in a neighbourhood search space within a certain search radius are evaluated via the objective function. The solution giving the minimum objective value (cost value) is set as a new starting point for the next search round and memorized in the tabu list (TL). According to the original TS algorithm and the TL property, the visited search spaces (or visited solutions) are prohibited for consecutively generated solutions. These search spaces are remarked as tabu. However, once the search is held by a local minimum (deadlock problem), the BT is activated. The BT looks up the TL and selects one of the memorized solutions as a new starting point. A new search could begin in a new direction. Hence, the search can possibly be released from the deadlock, and the search proceeds towards a better local minimum. Once the search approaches an elite local solution, the AR is invoked to speed up the search process. The search radius is subsequently decreased in accordance with the cost value of the current solution to provide finer and finer solutions within a short duration. The less the cost value, the smaller the search radius becomes. With these two mechanisms, a sequence of solutions obtained by the ATS is efficiently and rapidly converged towards the global minimum. Figure1 expresses the generic algorithms of the original TS and the ATS with the BT and the AR mechanisms, respectively, while Figure 2 depicts the diagram representing some movements of the ATS. Both figures give a clear view for the reader to follow.Generic algorithms of the TS and the ATS: (a) generic TS algorithms, (b) generic ATS algorithms, (c) the BT mechanism of the ATS, and (d) the AR mechanism of the ATS.
(a)(b)(c)(d)Figure 2
Movements of the ATS.


## 2.2. Performance Evaluation of the ATS

Although the performance evaluation of the ATS has appeared [30], the work reported here is an extension via six well-known surface optimization problems, that is, Bohachevsky function (BF), Rastrigin function (RF), Shekel’s foxholes function (SF), Shubert function (ShF), large area Schwefel function (type-1 or ScF#1), and small area Schwefel function (type-2 or ScF#2), respectively. Details of these tested functions are summarized in Table 1. Among these, the ShF contains 18 global solutions while each of the rest has only one.Table 1
Summary of the surface optimization problems.
Surface namesSurface functionsSearch spacesSketchesBohachevskyF(x,y)=x2+2y2-0.3cos(3πx)-0.4cos(4πy)+0.7, fmin(0,0)=0[-2,2]RastriginF(x,y)=x2+y2-10cos(2πx)-10cos(3πy)+20,
fmin(0,0)=0[-2,2]Shekel’s foxholesf(x1,x2)=[1/500+∑j=125(1/(j+∑i=12(xi-aij)6))]-1[-40,40]Whereaij=(-32-1601632-32⋯01632-32-32-32-32-32-16⋯323232)fmin(-32,-32)=1Shubertf(x,y)=(∑i=15icos((i+1)x1+i))(∑i=15icos((i+1)y+i))[-10,10]fmin(xj,yj)=-186.7309,j∈{1,2,…,17,18}Schwefel If(x1,x2)=418.9829×2-∑i=12(xisin|xi|), fmin(421,421)=0[-500,500]Schwefel II[400,500]The ATS algorithms were coded by MATLAB, and run on the Intel Celeron(R), 2.6 GHz, 238 Mbytes SD-RAM, 30 Gbytes HDD. Referring to the Table1, the global solutions of the tested functions are as follows: BF and RF-{x=y=0 with the cost value f(0,0)=0}; SF-{x=y=-32 with f(-32,-32)=0.998}; ShF-{xj,yj with f(xj,yj)=-186.7309, where j=1,2,…,18}, and ScF#1 and #2-{x=y=421 with f(421,421)=0}. The variables’ boundaries of all tested functions are set to form the corresponding search spaces as declared in the Table 1.Following the recommendations [30], the parameter settings of the ATS for each tested function are declared in the Table 2, where Remax is the maximum allowance of the solution cycling before invoking the BT, kth is the backward-selected solution by the BT, countmax is maximum search round, R is search radius, J is the cost value, and Jmin is minimum cost value used as the termination criteria (TC) for all tests in order to assure the global minimum found. The performance tests were conducted 50 trials against each tested function to obtain the average search round and time consumed. Each trial starts with a random initial solution generated by MATLAB using a seed number. The initial solution forms the center of a uniformly distributed hypersphere of a given radius, from which a neighbourhood is generated. The ATS stops when J<Jmin or count≥countmax.Table 2
Setting of the ATS search parameters.
Test functionATS parametersSearch radiusno. of neighboursBTARTCRemaxkthStage IStage IIStage IIICountmaxJminBF0.2 (5%)3055J<0.1, R=0.002J<0.001, R=0.002—10,0001e-9RF0.2 (5%)3055J<0.1, R=0.002J<0.001, R=0.002—10,0001e-8SF0.8 (1%)3055J<5, R=0.2J<2, R=0.1—10,0000.999ShF1.0 (5%)3055J<-100, R=0.1J<-150, R=0.015—10,000−186.7ScF#1100 (10%)2055J<100, R=50J<10, R=0.01J<1, R=0.00110,0001e-4ScF#21.0 (1%)2055J<10, R=0.01J<1, R=0.001—10,0001e-4The results obtained are summarized in Table3, where the first row stands for the average time consumed, the second row is the average search round, and the third row expresses the average time consumed per one search round. It is found that the ATS yields very satisfactory search performance in terms of solution convergence and the search time consumed for all surface optimization problems.Table 3
Results of the ATS’s performance evaluation.
Search resultsTest functionsBFRFSFShFScF#1ScF#2(1) Search time (sec)5.39408.20672.28373.397838.10370.2522(2) Search rounds556.06759.80108.22342.54336.2431.24(1)/(2) (sec/round)0.00970.01080.02110.00990.11330.0081


## 3. Multipath Adaptive Tabu Search (MATS)

In order to improve the search performance of the ATS, one may utilize an exploration strategy proposed by this paper. The implementation is suitable for use on a single CPU platform. The proposed MATS consists of partitioning, sequencing, and discarding mechanisms (PM, SM, and DM), respectively. Each mechanism is described next.Partitioning Mechanism (PM)
This mechanism operates only once at the beginning of the search. The PM starts with decomposing the entire search space into a number of sub-search-spaces defined by the user. The PM also defines explicit boundaries for the sub-search-spaces, each of which is given an individual initial solution and an independent ATS path. Since all ATS paths as the search cores of the MATS use the same set of search parameters, this approach is referred to as the multiple points single strategy (MPSS). Just before launching the search paths, the PM removes the predefined boundaries such that all ATS paths could search freely on the originally entire search space. This technique helps to reduce any conflicts that may arise during the search along the border lines. Figure3 summarizes the PM procedures.Figure 3
The PM procedures.As an example, the surface of the Shekel’s foxholes function (SF) partitioned into 4 sub-search-spaces is shown in Figure4. The boundaries of the sub-search-spaces are defined in the form of ((upper limit of the 1st variable) (upper limit of the 2nd variable); (lower limit of the 1st variable) (lower limit of the 2nd variable)).Figure 4
Partitioned surface of the SF: (a) 2D contour, (b) 3D surface.Regarding this notion, the entire search space can be defined as[4040;-40-40], and the sub-search-spaces #1, 2, 3, and 4 are confined within [4040;00],[040;-400],[00;-40-40] and [400;0-40], respectively. In practice, any geometrical forms and coordinates are possible for the partitioning process to suit the applications. The number of sub-search-spaces must be finite and not too great, and the problem dimensions are not limited. Subsequently, an ATS path is assigned to each sub-search-space, and the boundaries are then removed.Sequencing Mechanism (SM)
As mentioned earlier, the proposed MATS is intended for the use on a single CPU platform. Since the MATS possesses a few to many search paths, it needs some organizing mechanisms for its correct sequential operations. The SM is implemented to accomplish this, and can be represented by the simple diagram in Figure5. Assuming that there are n search paths organized by the SM, the first ATS path (#1ATS) begins its first trial. Afterward, it goes to the wait state. Once the CPU finishes its service to the #1ATS, it provides the service to the second path. Once the #2ATS finishes its first search trial, it has to wait. The operation goes on in this manner until the #nATS finishes its first search trial. The CPU then returns to service the #1ATS for its second search trial, then the #2, #3, … and #nATS, in sequential manner. The operation is repeated until one of the ATS paths hits the solution, and requests for exiting the search according to the satisfied termination criterion. Either an equal or an unequal number of search rounds constitutes one search trial. The works by this paper utilize an equal number of search rounds for all ATS paths to work on one search trial. Readers may notice that organizing the search this way, more search paths would result in more wait states making the search process very time consuming. Hence, the number of search paths employed must be limited. Moreover, another mechanism, namely, the discarding mechanism (DM) is introduced and explained in the next section. With the DM, as time goes by, more and more search paths will be cut off from the search process until only one path is left to continue searching for most cases. However, an individual ATS can request for a complete termination once the global solution is found at any time. The SM needs to communicate with the DM to learn about the existing and the forcedly terminated (or discarded) ATS paths. Thus, the SM can be summarized by the procedures shown in Figure 6.Figure 5
Diagram representingn paths of the ATS.Figure 6
The SM procedures.Discarding Mechanism (DM)
The DM is designed to reduce the overall search time of the MATS based on the idea of forcing some low-quality search paths to stop as soon as possible. Various possible approaches can be used to implement this idea including evaluation of the search-path quality based on the cost values of the current best-solutions or a set of previous elite solutions of the specific search path, the probability or the possibility of the search path to hit some higher quality solutions, and so forth. A simple implementation of the recency strategy via the evaluation of the cost values of the current best-solutions of the search paths is demonstrated. Each time the DM operates, the number of search paths is reduced by half. However, the number of search paths to be reduced can be arbitrarily adjusted to suit an application. After this forced termination made to the low-quality paths, the DM transfers the information concerning the being-terminated and the existing paths to the SM. Figure7 summarizes the DM procedures.Figure 7
The DM procedures.According to the previous explanation, the MATS algorithms can be described by the list in Figure8 due to the fact that the ATS is used as the core search algorithms.Figure 8
The MATS algorithms.


## 4. Performance Evaluation

Evaluation of the performance of any search algorithms can be done in several ways, for example, using data mining, logistic, surface optimization problems, and so forth. The works reported here have applied the six surface optimization problems described in Section2 for the purposes. These test functions are referred to shortly as the BF, RF, SF, ShF, ScF#1, and ScF#2, respectively, and summarized by the Table 1. Performance comparisons are made among the ATS, the MATS with 2, 4, 8, 16, 32, and 64 paths denoted as MATS#2, MATS#4, MATS#8, MATS#16, MATS#32 and MATS#64, respectively.The PM and the DM settings are rather complicated for the performance investigations. The SM simple settings can be either fixed or adjustable search rounds for each ATS path. The fixed numbers of search rounds as well as the same ATS search parameters have been used throughout the studies. As mentioned earlier, the proposed MATS employs the multiple points single strategy (MPSS) method.The PM settings are now explained by referring to Table4, which declares the boundaries of the sub-search-spaces for 2,4,…,64 paths. As an example, consider the ShF having its entire space defined by [10 10; −10 −10]. For MATS#32, the ShF is decomposed into #1[10 10; 7.5 5] for the 1st region, #2[7.5 10; 5 5] for the 2nd, #3[5 10; 2.5 5] for the 3rd, and so on. The similar approach for space partitioning can be applied to the other surface functions. In addition, other geometric partitioning techniques and coordinates could be employed to suit particular applications.Table 4
Sub-search-spaces partitioned by PM.
Test functionsSub-search-spaces defined by PMMATS#2MATS#4MATS#8MATS#16MATS#32MATS#64BF and RF[0 2;  −2 −2]#1[2 2; 0 −2]#1[2 2; 0 0]#1[2 2; 1 0]#1[2 2; 1 1]#1[2 2; 1.5 1]#1[2 2; 1.5 1.5]#2[0 2;−2 −2]#2[0 2;−2 0]#2[1 2; 0 0]#2[1 2; 0 1]#2[1.5 2; 1 1]#2[1.5 2; 1 1.5]#3[0 0;−2 −2]#3[0 2;−1 0]#3[0 2;−1 1]#3[1 2; 0.5 1]#3[1 2; 0.5 1.5]#4[2 0; 0 −2]#4[−1 2;−2 2]#4[−1 2;−2 1]#4[0.5 2; 0 1]#4[0.5 2; 0 1.5]#5[−1 0;−2 −2]#5[−1 1;−2 0]#5[0 2;−0.5 1]#5[0 2;−0.5 1.5]⋮⋮⋮⋮SF[40 40; −40 −40]#1[40 40; 0 −40]#1[40 40; 0 0]#1[40 40; 20 0]#1[40 40; 20 20]#1[40 40; 30 20]#1[40 40; 30 30]#2[0 40;−40 −40]#2[0 40;−40 0]#2[20 40; 0 0]#2[20 40; 0 20]#2[30 40; 20 20]#2[30 40; 20 30]#3[40 0; 0 −40]#3[0 40;−20 0]#3[0 40;−20 20]#3[20 40; 10 20]#3[20 40; 10 30]#4[0 0;−40 −40]#4[−20 40;−40 0]#4[−20 40;−40 20]#4[10 40; 0 20]#4[10 40; 0 30]#5[40 0; 20 −40]#5[−20 20;−40 0]#5[0 40;−10 20]#5[0 40;−10 30]⋮⋮⋮⋮ShF[10 10; −10 −10]#1[10 10; 0 −10]#1[10 10; 0 0]#1[10 10; 5 0]#1[10 10; 5 5]#1[10 10; 7.5 5]#1[10 10; 7.5 7.5]#2[0 10;−10 −10]#2[0 10;−10 0]#2[5 10; 0 0]#2[5 10; 0 5]#2[7.5 10; 5 5]#2[7.5 10; 5 7.5]#3[0 0;−10 −10]#3[0 10;−5 0]#3[0 10;−5 5]#3[5 10; 2.5 5]#3[5 10; 2.5 7.5]#4[10 0; 0 −10]#4[−5 10;−10 0]#4[−5 10;−10 5]#4[2.5 10; 0 5]#4[2.5 10; 0 7.5]#5[−5 0;−10 −10]#5[−5 5;−10 0]#5[0 10;−2.5 5]#5[0 10;−2.5 7.5]⋮⋮⋮⋮ScF#1[500 500; −500 −500]#1[500 500; 0 −500]#1[500 500; 0 0]#1[500 500; 250 0]#1[500 500; 250 250]#1[500 500; 375 250]#1[500 500; 375 375]#2[0 500;−500 −500]#2[0 500;−500 0]#2[250 500; 0 0]#2[250 500; 0 250]#2[375 500; 250 250]#2[375 500; 250 375]#3[500 0; 0 −500]#3[0 500;−250 0]#3[0 500;−250 250]#3[250 500; 125 250]#3[250 500; 125 375]#4[0 0;−500 −500]#4[−250 500;−500 0]#4[−250 500;−500 250]#4[125 500; 0 250]#4[125 500; 0 375]#5[500 0; 250 −500]#5[−250 250;−500 0]#5[0 500;−125 250]#5[0 500;−125 375]⋮⋮⋮⋮ScF#2[500 500; 400 400]#1[500 500; 450 400]#1[500 500; 450 450]#1[500 500; 475 450]#1[500 500; 475 475]#1[500 500; 487.5 475]#1[500 500; 487.5 487.5]#2[450 500; 400 400]#2[450 500; 400 450]#2[475 500; 450 450]#2[475 500; 450 475]#2[487.5 500; 475 475]#2[487.5 500; 475 487.5]#3[500 450; 450 400]#3[450 500; 425 450]#3[450 500; 425 475]#3[475 500; 450 475]#3[475 500; 462.5 487.5]#4[450 450; 400 400]#4[425 500; 400 450]#4[425 500; 400 475]#4[462.5 500; 450 475]#4[487.5 500; 450 487.5]#5[500 450; 475 400]#5[425 475; 400 450]#5[450 500; 437.5 450]#5[450 500; 437.5 487.5]⋮⋮⋮⋮The DM employs the recency strategy by comparing the cost values of the current best-solutions of the ATS paths. Only the paths with the cost values lower than a preset limit are kept, otherwise they are discarded. The number of the paths being discarded can be set in the manner of either a gradual cut or a sudden cut. For the MATS with many search paths, the sudden cut is preferable such that the wait-state time be minimum. For a moderate to a few numbers of search paths inside the MATS, the gradual cut is more suitable. Table5 reveals the DM settings in details. Let us consider the SF case of 8, 32, and 64 paths as examples. For the case of SF with MATS#8, the DM becomes active firstly at the 2nd iteration, and 4 search paths are discarded. The DM becomes active again at the 4th and 6th iterations; 2 and 1 paths are forced to stop, respectively. Eventually, there is 1 path left to continue searching. This is one example of using the gradual cut technique. Different approaches, that is, the sudden cuts, are found for the cases of MATS#32 and #64. At the 1st iteration of both cases, 31 and 63 search paths are discarded correspondingly. This means that only one path is left after the 1st iteration to track down the solution as for the cases of MATS#32 and #64. It is found in some cases, that is, the ShF problem, that good performances are obtained via having more than one path left for searching and competing for solutions. Note that, for an effective operation, the qth iteration at which the DM is invoked should be less than half of the average search rounds consumed by the single path ATS (SR¯ATS). The SR¯ATSdata are presented in row 2, Table 3. Due to the fact that the MATS utilizes more than 1 search path, the inequality ∑i=1k(dmi×ni)<SR¯ATS must hold. Consider the case of BF with MATS#4, ∑i=1k(dmi×ni)=(5×4)+(10×2)<556, for instance.Table 5
The DM settings.
qth iteration at which the DM is invoked and the number of discarded path(s)Test functionsMATS#2#4#8#16#32#641st1st2nd1st2nd3rd1st2nd3rd4th1st2nd3rd4th5th1st2nd3rdBFqth itr.5510510155101520510152025135no.dis.pth.1214218421168421321615RFqth itr.550—24624682468101——no.dis.pth.13—421842116842163——SFqth itr.52424624681————1——no.dis.pth.121421842131————63——ShFqth itr.11—13—35——1————1——no.dis.pth.13—22—84——28————60——ScF#1qth itr.513135135—1————1——no.dis.pth.121421843—31————63——ScF#2qth itr.11—1——1———1————1——no.dis.pth.13—7——7———31————63——The investigations of the search performance of the proposed MATS were conducted against the six surface optimization problems on the Intel Celeron(R), 2.6 GHz, 250 MB-RAM and 30 GB-HDD platform. Each figure of the results reported herein is an average of 50 trials. Tables6–9 reveal the detailed results. The averages of search rounds are summarized in Table 6. However, the figures do not disclose the actual activities performed by the ATS used as the search core of the MATS. These figures are therefore converted into the equivalent averages with-respect-to the ATS as shown in the Table 7. Noticeably, all cases, but the ScF#2, the MATS search rounds are actually less than those performed by the single path ATS.Table 6
Average values of search rounds.
Average search rounds obtained from 50 trialsTest functionsATSMATS1-path#2#4#8#16#32#64BF556.06530.20507.94186.82142.70202.34173.76RF759.80685.40603.78713.26327.32313.48200.32SF108.2279.8472.9664.6230.6254.0436.16ShF342.54291.56282.1675.6873.0261.6870.12ScF#1336.24304.88294.44241.56268.22263.18131.10ScF#231.2430.0229.2026.4824.2621.5819.96Table 7
Equivalent average search rounds with respect to the ATS.
Average search rounds equivalent to those of the ATSTest functionsATSMATS1-path#2#4#8#16#32#64BF556.06535.20527.94241.82272.70487.34328.76RF759.80690.40753.78735.26379.32427.48263.32SF108.2284.8480.9686.6282.6285.0499.16ShF342.54292.56285.16310.72336.08274.72340.48ScF#1336.24309.88299.44256.56303.22295.18194.10ScF#231.2430.0232.2033.4839.2652.5882.96Table 8
Average values of search time in seconds.
Test functionsAverage search time in seconds obtained from 50 trialsATSMATS1-path#2#4#8#16#32#64BF5.39405.05164.89012.34352.33094.13093.3029RF8.20676.58636.99257.21754.53165.00787.3221SF2.28371.88181.76971.81341.39181.79441.8431ShF3.39782.98193.13692.40382.60992.26402.9433ScF#138.103730.347534.620028.197533.710034.843129.2327ScF#20.25220.24190.26090.30090.32130.43501.5179Table 9
Percent reduction of search time.
Test functionsPercent reduction of searchATSMATS1-path#2#4#8#16#32#64BF0.00006.359.3456.5556.7923.4238.77RF0.000019.7414.8012.0544.7838.9810.78SF0.000017.6022.5120.5939.0621.4319.29ShF0.000012.247.6829.2523.1933.3713.38ScF#10.000020.369.1426.0011.538.5623.28ScF#20.00004.08−3.45−19.31−27.40−72.48−501.86The average values of search time tabulated in Table8 also confirm this. The figures indicating search time (in seconds) in Table 8 are converted into percent reduction of search time using the following relation for comparison purposes:(4.1)Percentreductionofsearchtime=(averagesearchtimeofATS-averagesearchtimeofMATS)averagesearchtimeofATS×100The percent reduction figures summarized in Table9 reflect the merits of the MATS. The proposed MATS can effectively reduce the search time in the range of 4.08–56.79%, except that it is not efficient for the ScF#2 problem. Among the six test functions, only the ScF#2 is actually smooth over the entire search space whereas the MATS is not aimed for. The conventional optimization methods should be favourable to this kind of problems. The contemporary search methods, for example, the MATS and those of the local search algorithms, and so forth, are more suitable to the problems having Pareto front, nonsmooth surfaces, and multiple global solutions in nature. The numeric figures in Table 9 are displayed as bar graphs in Figure 9 to give a clear view of the merits of the MATS whereas the negative values indicate the nonproductive domain of the MATS.Bar graphs of the reduction of search time in percentages.
(a)(b)(c)(d)(e)(f)To complement the revealed results, the cost values are also monitored and plotted as the convergence curves illustrated in Figure10, for instance. Referring to Figure 10, the accepted solutions must have the costs of less than 1e-9; the ATS hits the solution within 5.7650 s.; path#1 of the MATS#2 succeeds within 5.3440 s.; path#3 of the MATS#4 succeeds within 4.7500 s., and so forth. At present, it can be said that the proposed MATS performs faster than the single-path ATS; its speed for the best case (on a single CPU platform) is twice as much of the ATS speed; for the worst case its performance is about the same as the ATS, and the MATS can effectively reduce the search time by 30% as an average figure.Figure 10
Convergence curves (BF problem).


## 5. An Application: Car Control System in Roadway Simulator

This section presents the application of the proposed MATS algorithms for solving a real-world control problem of a car model.The Illinois Roadway Simulator (IRS) has been proposed [36] to study the effects of road surface on car dynamics. The IRS is a reduced scale car model for a laboratory use. It possesses the dynamics very similar to those of an actual car. In this, the yaw rate control is the issue of interest. The transfer function models of the IRS have been developed by applying the Buckingham-Pi theorem as well as system identification. The obtained transfer functions consist of the plant dynamic (G) and the disturbance dynamic (Gd) constituting the vehicle dynamics. The block diagram shown in Figure 11 indicating the 3-DOF control structure represents the original system.Figure 11
Block diagram representing the original yaw-rate control problem.The three controllers, namely,Gdc, Gff, and Gfb are designed via the model reference control (MRC) method. The vehicle models and the controllers are listed as follows:(5.1)G=2.802e4s+2.306e51.5s4+94.43s3+7.308e4s2+1.183e5s+5.361e5,Gd=8.024e4s+6.710e51.3s4+53.250s3+1.943e3s2+2.693e4s+1.162e5,Gdc=-1.2036e5s5-8.584e6s4-6.497e8s3-1.44e10s2-1.224e11s-3.598e113.6426e4s5+1.792e6s4+6.671e7s3+1.202e9s2+9.464e9s+2.679e10,Gff=103s2+1.8542e4s+8.34385e5s3+155.3s2+3.727e3s+2.0714e4,Gfb=-5.181s3+49.98s2+5.294e3s+4.8142e4s3+155.3s2+3.727e3s+2.0714e4.Note that the controllersGffand Gfb have the same poles. Referring to Figure 11, the system transfer function, Girs can be expressed as
(5.2)Girs(s)=Y(s)R(s)=Gd+G⋅Gdc+G⋅Gff1+G⋅Gfb,
and hence
(5.3)Girs=b23s23+b22s22+⋯+b1s+b0a27s27+a26s26+⋯+a1s+a0,
where the coefficients ai,i=0,1,2,…,27 and bi,i=0,1,2,…,23 are summarized in Table 10.Table 10
The coefficients of the transfer function in (5.3).
The coefficientsaibia0=4.115e41a10=3.346e35a20=4.678e20b0=3.565e42b8=9.645e37b16=4.055e26a1=6.265e41a11=2.225e34a21=6.423e18b1=4.813e42b9=7.143e36b17=6.618e24a2=4.480e41a12=1.251e33a22=7.331e16b2=3.016e42b10=4.307e35b18=8.798e22a3=2.001e41a13=5.979e31a23=6.805e14b3=1.165e42b11=2.136e34b19=9.327e20a4=6.265e40a14=2.445e30a24=4.957e12b4=3.107e41b12=8.779e32b20=7.624e18a5=1.462e40a15=8.580e28a25=2.671e10b5=6.075e40b13=3.006e31b21=4.525e16a6=2.643e39a16=2.590e27a26=9.423e7b6=9.037e39b14=8.590e29b22=1.7521e14a7=3.797e38a17=6.729e25a27=1.598e5b7=1.048e39b15=2.048e28b23=3.075e11a8=4.417e37a18=1.503e24a9=4.219e36a19=2.873e22The unit step response of the original control system is depicted in Figure12. The response possesses 40 ms delay time, and smoothly rises to the final value in 0.552 s.Figure 12
Original system response.To compensate for the delay time, an additional PD-controller is proposed in cascade connection to theGff. The theoretical PD-controller of the form GPD=KDs+KP is considered. Thus, the Gff block is modified to be GPD·Gff. The design of the PD-controller is not straight-forward because of the complexity of the existing control system structure. So, the search method has been applied to find an optimum PD-controller such that the following objectives are satisfied: P.O.<0.1% (no overshoot preferred), rise-time (tr)<0.231 s., and settling-time (ts)<5tr s. The control design problem becomes a multiobjective optimization problem in which the surrogate objective function, J, is formed such that
(5.4)J=α1tsj+α2trj+α3P.O.,
where trj=% rise-time (normalized), tsj=% settling-time (normalized), P.O.=% overshoot, and α1,α2, and α3 = weighting factors.In this application, the factorsα1=α2=α3=1, and the penalty concept is applied to trj,tsj,P.O. and J, respectively. Figure 13 provides the list of the objective function procedures.Figure 13
The objective function procedures for the control problem.The max-min ranges of bothKP and KD for the search are (2, 0). The MATS with two ATS-paths is used with the following settings: [2 2; 1 0] and [1 2; 0 0] for the PM, and the qth iteration = 50 for the DM. The initial solutions for the ATS#1 and #2 are (KP=1.824,  KD=0.153) and (KP=0.329, KD=0.776), respectively. The search parameters of the ATS are as follows: initial R=0.2,N=5,Nre_max=5, kth backward for the BT=5,(J<90)→(R=0.1) and (J<70)→(R=0.05)for the AR, and countmax=10,000 or J<65 for the TC.As a result shown in Figure14, path#1 of the MATS#2 spent 217.1648 s to track down the solutions KP=1.0 and KD=0.07 at the 326th iteration with the cost J=61.7234. Figure 15 illustrates the step responses of the original and the enhanced systems for comparison purposes. It can be observed that the delay time is reduced by 97%, and the rise-time and settling-time are reduced by 30%, approximately.Figure 14
Convergence curves of the PD-controller design problem.Figure 15
Comparison of the step responses.


## 6. Conclusion

The development of the multipath adaptive tabu search (MATS) has been reported by this paper. The algorithms incorporates the partitioning, sequencing, and discarding mechanisms, respectively, to the ATS, and can be run efficiently on a single CPU platform as being confirmed by the detailed performance assessment results using the well-known surface optimization problems. According to the assessment results, the MATS is about two-times faster than the ATS as the best case. Moderately, the MATS renders 30% reduction in the search time compared to the ATS. However, the MATS is not suitable for some smooth problems as it consumes more search time than the single ATS does. The paper has been closed by an illustrative example of using the MATS to solve the multiparameter control problem of a reduced scale vehicle in which the enhanced system becomes 4-DOF. The very satisfactory results obtained confirm the effectiveness and the usefulness of the proposed algorithms. The proposed algorithmic mechanisms described herein are open enough for applications to other search algorithms.



---

*Source: 731623-2012-02-23.xml*