際際滷

際際滷Share a Scribd company logo

Hill-climbing #2

Download as PPTX, PDF
Mohamed Gad
Mohamed Gad

Hill climbing is an optimization technique that iteratively improves the current state by evaluating possible successor states. It works by considering states laid out on a landscape, where the height corresponds to the evaluation function - it can only move to higher points. A problem is that it can get stuck at local maxima. Variants like simulated annealing allow worse states to be taken temporarily to avoid dead ends. Hill climbing has been applied to problems like the travelling salesman problem and in areas like robotics coordination and machine learning.

1 of 13
Downloaded 249 times
HILL CLIMBING Search algorithm
AGENDA 1. Optimization technique 2. Iterative Improvement 3. Algorithm in Pseudocode 4. Applications
OPTIMIZATIONTECHNIQUE Hill climbing is an optimization technique for solving computationally hard problems. It is best used in problems with the property that the state description itself contains all the information needed for a solution (Russell & Norvig, 2003).[1] The algorithm is memory efficient since it does not maintain a search tree: It looks only at the current state and immediate future states.
OPTIMIZATIONTECHNIQUE Hill climbing attempts to iteratively improve the current state by means of an evaluation function. Consider all the [possible] states laid out on the surface of a landscape.The height of any point on the landscape corresponds to the evaluation function of the state at that point (Russell & Norvig, 2003).[1]
OPTIMIZATIONTECHNIQUE In contrast with other iterative improvement algorithms, hill-climbing always attempts to make changes that improve the current state. In other words, hill-climbing can only advance if there is a higher point in the adjacent landscape.
ITERATIVE IMPROVEMENT The main problem that hill climbing can encounter is that of local maxima. This occurs when the algorithm stops making progress towards an optimal solution; mainly due to the lack of immediate improvement in adjacent states.
ITERATIVE IMPROVEMENT Local maxima can be avoided by a variety of methods: Simulated annealing tackles this issue by allowing some steps to be taken which decrease the immediate optimality of the current state. Algorithms such as simulated annealing can sometimes make changes that make things worse, at least temporarily (Russell & Norvig, 2003).[1] This allows for the avoidance of dead ends in the search path.
ALGORITHM IN PSEUDOCODE
function HILL-CLIMBING(problem) returns a solution state inputs: problem, a problem static: current, a node next, a node current < MAKE-NODE(lNlTIAL-STATE[problem]) loop do next a highest-valued successor of current ifVALUE[next] <VALUE[current] then return current current *next end
APPLICATIONS Hill climbing can be applied to any problem where the current state allows for an accurate evaluation function. For example, the travelling salesman problem, the eight-queens problem, circuit design, and a variety of other real-world problems. Hill Climbing has been used in inductive learning models. One such example is PALO, a probabilistic hill climbing system which models inductive and speed-up learning. Some applications of this system have been fit into explanation-based learning systems, and utility analysis models. (Cohen, Greiner, & Schuurmans, 1994)
APPLICATIONS Hill Climbing has also been used in robotics to manage multiple-robot teams. One such example is the Parish algorithm, which allows for scalable and efficient coordination in multi-robot systems.The group of researchers designed a team of robots [that] must coordinate their actions so as to guarantee location of a skilled evader. (Gerkey,Thrun, & Gordon, 2005).[3]
APPLICATIONS Their algorithm allows robots to choose whether to work alone or in teams by using hill-climbing. Robots executing Parish are therefore collectively hill-climbing according to local progress gradients, but stochastically make lateral or downward moves to help the system escape from local maxima. (Gerkey,Thrun, & Gordon, 2005)
THANKYOU

More Related Content

Hill-climbing #2

  • 2. AGENDA 1. Optimization technique 2. Iterative Improvement 3. Algorithm in Pseudocode 4. Applications
  • 3. OPTIMIZATIONTECHNIQUE Hill climbing is an optimization technique for solving computationally hard problems. It is best used in problems with the property that the state description itself contains all the information needed for a solution (Russell & Norvig, 2003).[1] The algorithm is memory efficient since it does not maintain a search tree: It looks only at the current state and immediate future states.
  • 4. OPTIMIZATIONTECHNIQUE Hill climbing attempts to iteratively improve the current state by means of an evaluation function. Consider all the [possible] states laid out on the surface of a landscape.The height of any point on the landscape corresponds to the evaluation function of the state at that point (Russell & Norvig, 2003).[1]
  • 5. OPTIMIZATIONTECHNIQUE In contrast with other iterative improvement algorithms, hill-climbing always attempts to make changes that improve the current state. In other words, hill-climbing can only advance if there is a higher point in the adjacent landscape.
  • 6. ITERATIVE IMPROVEMENT The main problem that hill climbing can encounter is that of local maxima. This occurs when the algorithm stops making progress towards an optimal solution; mainly due to the lack of immediate improvement in adjacent states.
  • 7. ITERATIVE IMPROVEMENT Local maxima can be avoided by a variety of methods: Simulated annealing tackles this issue by allowing some steps to be taken which decrease the immediate optimality of the current state. Algorithms such as simulated annealing can sometimes make changes that make things worse, at least temporarily (Russell & Norvig, 2003).[1] This allows for the avoidance of dead ends in the search path.
  • 9. function HILL-CLIMBING(problem) returns a solution state inputs: problem, a problem static: current, a node next, a node current < MAKE-NODE(lNlTIAL-STATE[problem]) loop do next a highest-valued successor of current ifVALUE[next] <VALUE[current] then return current current *next end
  • 10. APPLICATIONS Hill climbing can be applied to any problem where the current state allows for an accurate evaluation function. For example, the travelling salesman problem, the eight-queens problem, circuit design, and a variety of other real-world problems. Hill Climbing has been used in inductive learning models. One such example is PALO, a probabilistic hill climbing system which models inductive and speed-up learning. Some applications of this system have been fit into explanation-based learning systems, and utility analysis models. (Cohen, Greiner, & Schuurmans, 1994)
  • 11. APPLICATIONS Hill Climbing has also been used in robotics to manage multiple-robot teams. One such example is the Parish algorithm, which allows for scalable and efficient coordination in multi-robot systems.The group of researchers designed a team of robots [that] must coordinate their actions so as to guarantee location of a skilled evader. (Gerkey,Thrun, & Gordon, 2005).[3]
  • 12. APPLICATIONS Their algorithm allows robots to choose whether to work alone or in teams by using hill-climbing. Robots executing Parish are therefore collectively hill-climbing according to local progress gradients, but stochastically make lateral or downward moves to help the system escape from local maxima. (Gerkey,Thrun, & Gordon, 2005)