Flowchart Tabu Search [PDF]

Zitiervorschau

Tabu Search do and force any move to a neighbor with the least cost deterioration (Pirim, Bayraktar & Eksioglu, 2008). It leads to a conclusion that Tabu Search uses their memory (long term and short term) to keep track of their previous solutions to the problem, so they prevent to revisit the existing solution. This method experienced some iterations while it searching for its local optimum.

Figure 1. Tabu Search Algorithm Flowchart (Hao, Wang, Wu, Boriboonsomsin & Barth, 2017)

As could be seen in Figure 1. above, it can be concluded that the steps of Tabu Search Algorithm as follow. 1. Start 2. Generate an initial solution / current solution for the problem. In this step Tabu Search will Store the initial/current solution as the current seed and the best solution. 3. Create the candidate list of Neighbor to Current Solution. In this step, the Tabu list also being cleared.

4. Find the best solution (S’) from the candidate list. 5. Look up whether the S’ exist in the Tabu list. If yes, go to step 6. If no, go to step 7. 6. Delete the S’ from the candidate list then go back to step 4. 7. Let solution S = S’ and update the Tabu list. 8. Look up whether the stopping criterion is satisfied. If yes, then go to Step 9. If no, back to step 3. 9. Finish Hao, P., Wang, Z., Wu, G., Boriboonsomsin, K., & Barth, M. (2017). Intra-platoon vehicle sequence optimization for eco-cooperative adaptive cruise control. 2017 IEEE 20Th International Conference On Intelligent Transportation Systems (ITSC). doi: 10.1109/itsc.2017.8317879 Tabu Search Parameter (nadhilah) Based on the steps in the flowchart that be given in previous chapter, we need to initialize current solution before conduct the Tabu Search. The Extended Tabu Search method by Sexton et al. (1998) is mainly based on a random sampling around the best solution found. Taha (2017) elaborate an example with the initial value could be get by selection the member of neighborhood randomly or based on the least cost criterion. Tabu search will apply its local search procedure to look up for one potential solution to another improved solution (Hao, Wang, Wu, Boriboonsomsin & Barth, 2017). As in theory, the search procedure could go on forever, unless the optimal solution at hand is known beforehand. In the practical, the search has to be stopped at some point. The most common used stopping criteria in Tabu Search as below: 1. After a fixed number of iterations (or a fixed amount of CPU time); 2. After some number of iterations without an improvement in the objective function value (the criterion used in most implementations); 3. When the objective reaches a pre-specified threshold value. In complex tabu schemes, the search is usually stopped after completing a sequence of phases, the duration of each phase being determined by one of the above criteria.