Local search algorithms for combinatorial problems. Analysis, improvements, and new applications (Thesis TU Darmstadt 1998) (Q2726296)

The book under review is the author's Ph.D. Thesis written in the area of Artificial Intelligence. The following aims are pursued in it: 1) to present the author's improvements to existing metaheuristics (i.e. general schemes or skeletons) applied in local search algorithms; 2) to provide a methodology for analysis of run-time behavior of the suggested metaheuristics; 3) to present some new applications of the developed algorithms. The book consists of 7 Chapters and is organized in the following way. NEWLINENEWLINENEWLINEChapter 1 is a short introduction consisting of motivation of researches and a brief synopsis of the author's contribution. NEWLINENEWLINENEWLINEChapters 2 and 3 present the backgrounds for Chapters 4-6. Chapter 2 is devoted to theoretic backgrounds. It contains examples of combinatorial optimization problems, brief summary of the results of the NP-completeness theory, general issues of local search and its computational complexity, the review of metaheuristics for local search (ant colony optimization, iterated local search, tabu search, simulated annealing, genetic algorithms, greedy randomized adaptive search procedures), the synopsis of characteristics of considered metaheuristics and the principles of a search space analysis. Chapter 3 is devoted to a novel type of empirical evaluation methodology based on measuring and characterizing run-time and solution quality distributions arising from applications of local search algorithms to optimization and decision problems. Basic principles of improving algorithms by exploiting run-time behavior are presented. NEWLINENEWLINENEWLINEIn Chapters 4-6 metaheuristics for local search developed by the author are examined in details. Chapter 4 presents MAX-MIN ant system (AS). It differs from AS in following three aspects: 1) to exploit the best solutions found during an iteration or during the run of the algorithm, after each iteration only one single ant (iteration-best or global-best) is used for pheromone update; 2) to limit the stagnation of the search, a more direct influence on the pheromone trail limits is exerted by limiting the allowed range of possible pheromone trails to an interval determined by \([ {\tau}_{min}, {\tau}_{max} ]\), where \({\tau}_{min}\) and \({\tau}_{max}\) are, correspondingly, the minimal and the maximal pheromone trail on any arc; 3) to get higher exploration of tours at the start of the algorithm pheromone trails are initialized to \({\tau}_{max}\). Applications of MAX-MIN AS for solving of the Traveling Salesman Problem (TSP), the Quadratic Assignment Problem (QAP) and the Flow Shop Problem (FSP) are considered. Parallelization strategies for MAX-MIN AS optimization are examined. In Chapter 5 applications of iterated local search for solving of TSP, QAP and FSP are considered. Its comparision with MAX-MIN AS is examined. In Chapter 6 applications of tabu search to improve the min-conflicts heuristic for constraint satisfaction problems are presented. NEWLINENEWLINENEWLINEChapter 7 is a short conclusion. Contributions of the author are listed and areas for future researches are outlined. NEWLINENEWLINENEWLINEThe book is of exceptional interest for students, post-graduates, lecturers, specialists and researchers dealing with applications of local search for solving of combinatorial problems in both, fundamental and applied aspects.