Content area
Kurzfassung
The seriation problem is an important problem in combinatorial optimization. The goal of seriation is to find a linear order for data objects in order to reveal structural information given a loss or a merit function as an objective function. For the seriation problem, finding an optimal solution using exact algorithms (e.g., branch-and-bound) to find the optimal solution is currently not practical for problems with more than 35 objects. Therefore, local search approaches, such as hill climbing and metaheuristics, are alternative approaches capable of solving the seriation problem to near optimal solutions within acceptable computation times. In this praxis, five different local search algorithms are investigated to maximize the gradient measure objective function: hill-climbing algorithms, basic tabu search, intensification and diversification tabu search, iterated local search, and memetic algorithms. Moreover, parameter tuning via the design of experiments approach is employed to find the best parameter setting for each algorithm in terms of effectiveness, efficiency, and robustness. We also propose two new computation-time-reduction techniques for insertion: forward/backward adjacent swap and search space reduction. The results indicate that the most effective, efficient, and robust algorithm is the hill-climbing algorithm using a stochastic approach as the hill-climbing method and insertion as the neighborhood structure.
