tailieunhanh - Chapter 5: Local Search

Local search is a family of general-purpose techniques for search and optimization problems. Chapter 5: Local Search provides about Local search basics; General local search algorithm; Hill-climbing; Tabu search; Simulated Annealing; WSAT; Conclusions | Chapter 5 Local Search Outline Local search basics General local search algorithm Hill-climbing Tabu search Simulated Annealing WSAT Conclusions What is local search? Local search is a family of general-purpose techniques for search and optimization problems. The application of Local search algorithms to optimization problems start early 1960s. Since then the interests in this subject has grown in the fields of Operations Research, CS and AI. Local Search algorithms are non-exhaustive in the sense that they do not guarantee to find an optimal solution, but they search non-systematicaly until a specific stop criterion is satisfied. These techniques are very appealing because of their effectiveness and their widespread applicability LOCAL SEARCH BASICS Definition (Combinatorical Optimization Problems) We define an instance of a combina-torial optimization problem as a triple , where S is a finite set of solutions, F S is a set of feasible solutions and f: S | Chapter 5 Local Search Outline Local search basics General local search algorithm Hill-climbing Tabu search Simulated Annealing WSAT Conclusions What is local search? Local search is a family of general-purpose techniques for search and optimization problems. The application of Local search algorithms to optimization problems start early 1960s. Since then the interests in this subject has grown in the fields of Operations Research, CS and AI. Local Search algorithms are non-exhaustive in the sense that they do not guarantee to find an optimal solution, but they search non-systematicaly until a specific stop criterion is satisfied. These techniques are very appealing because of their effectiveness and their widespread applicability LOCAL SEARCH BASICS Definition (Combinatorical Optimization Problems) We define an instance of a combina-torial optimization problem as a triple , where S is a finite set of solutions, F S is a set of feasible solutions and f: S denotes an objective function that assesses the quality of each solution in S. The issue is to find a global optimum ,., an element x* F such that f(x*) f(x) for all x F. In these settings, the set F is called feasible set and its elements feasible solutions. The relation x F is called constraint. Example: the min-Graph-Coloring problem Definition (Search Problems) Given a pair where S is the set of solutions and F S is the set of feasible solutions, a search problem consists of finding a feasible solution, . an element x F. There are three main entities in Local Search algorithms: (1) the search space, (2) the neighborhood relation and (3) the cost function. Example: the k-Graph-Coloring problem Definition (Search space) Given a combinatorial optimization problem , we associate to each instance of it a search space S , with the following properties: 1) Each element s S represent an element x S. 2) At least one optimal element of F is .