UPI Study › Courses › Introduction to Artificial Intelligence › Free lessons › Lesson 4.6 Free with a free account
Climbing Toward Solutions: Local Search Methods
Introduction to Artificial Intelligence · Chapter 4: Search, Heuristics, and Game StrategySection 4.6 · lesson 28 of 6913 min · free with a free account
Free preview
Create a free account to keep watching
It takes a minute and costs nothing. Your free account unlocks all of Chapter 1 and 3 more lessons of Introduction to Artificial Intelligence.
Lesson complete
Earn the 3 college credits for Introduction to Artificial Intelligence
Enrolling adds a quiz after each lesson, the graded work and the official transcript. Recommended for credit by NCCRS.
Next lesson: Pruning Game Trees with Alpha-Beta Techniques →← Strategic Reasoning: Game Theory in Intelligent SystemsNext lesson: Pruning Game Trees with Alpha-Beta Techniques →
In this lesson
Hill climbing, simulated annealing, beam search, and genetic algorithms.
- Explain how local search uses a current state, neighbors, and an objective function
- Identify local maxima, plateaus, and ridges and the fixes for each
- Calculate random-restart run counts and simulated annealing acceptance probabilities
- Describe local beam search and genetic algorithms with selection, crossover, and mutation
Free study notes
Get this lesson's notes by email
The key points and 4 practice questions with answers, in your inbox. One email, free.
One email. Unsubscribe in one click.
Transcript
Everything said in the video, section by section (1,856 words). Read along, or search it.
Opening Analogy
A Hiker Lost in Fog
A hiker is lost in thick fog, and she wants to reach the highest peak in the area. She can't see the mountains. She can only feel the slope under her feet. So she follows one simple rule: always step uphill. Eventually she stops, because every direction goes down. But is she on the highest peak, or only on a small hill beside it? Local search methods face exactly that question. We use them when we want a good final answer, like a timetable, a circuit layout or a delivery plan, and don't care about the route taken to find it.
Core Idea
Current State, Neighbors, and Objective
A local search keeps just one complete candidate solution in mind, called the current state. Its neighbors are the states one small change away, and it moves to a better one. An objective function scores how good each state is. Take the eight-queens puzzle: put eight queens on a chessboard, so that no two attack each other. A state is a board with one queen in each column. A neighbor moves one queen up or down within its column, so every board has 56 neighbors. And the objective counts the pairs of queens that don't attack each other. Eight queens make 28 pairs, so 28 is perfect.
State Landscape
Global Maxima, Local Maxima, and Plateaus
Now picture every state laid out like a landscape, with its score as the height. Searching means climbing to the highest point. The global maximum is the best state of all: for eight queens, a board where no queens attack. A local maximum is better than all its neighbors, but not the best overall. Every single-queen move makes things worse, and yet the board isn't solved. And a plateau is flat ground, where no neighbor is any better.
Comparison
Local Search Versus Route-Finding Search
This is a different job from route-finding search. Those methods remember many partial routes, and their answer is the route itself. Local search remembers only the current state, or a few, so it needs very little memory. Its answer is the final state. The price is the guarantee. It may stop at a good answer that isn't the best, a local maximum. It suits huge problems where only the final arrangement matters.
Hill Climbing
Always Move to the Best Neighbor
Hill climbing is the simplest local search. Start from some state, often a random one, and score all its neighbors. If the best neighbor beats the current state, move to it, and repeat. If no neighbor is better, stop: the current state is the answer. It uses almost no memory, and it often reaches a good answer in a few steps.
Variants
Steepest-Ascent, First-Choice, Sideways, Random-Restart
Several variants change how the next move is chosen. Steepest-ascent examines every neighbor and takes the best one: the biggest gain, but slow when neighbors are many. First-choice takes the first better neighbor it finds. Stochastic hill climbing picks at random among the improving neighbors, favoring steeper ones. Sideways moves allow a step to an equally good neighbor, up to a fixed limit, so the search can walk across a flat shoulder. And random-restart runs hill climbing again and again, from random starting states, and keeps the best result.
Results
Hill Climbing on Eight Queens
How well do they work? Steepest-ascent was run on eight queens from 1,000 random boards, in a simulation. Plain hill climbing solved only about 14 percent. But it's fast: about four steps when it succeeds, and three when it gets stuck. Allowing up to 100 sideways moves lifted success to about 94 percent, at the cost of longer runs. That speed is what makes random restart attractive. If one run succeeds with probability p, you need about one over p runs on average. Here that's one over 0.14, about seven runs. Still very cheap, and success is almost certain.
Quick Check
Expected Runs at 25 Percent Success
Quick check. A hill climber for a scheduling problem succeeds on 25 percent of random starts, and each run takes under a second. With random restarts, about how many runs should you expect to need? Pause, and decide. About four. Each run succeeds a quarter of the time, so on average you need one over p: one over 0.25 is 4. Twenty-five reads the success rate as a count of runs. And seventy-five is the failure rate, not a number of runs.
Common Traps
Local Maxima, Plateaus, and Ridges
Three kinds of terrain stop hill climbing before the best answer. A local maximum is a peak higher than everything nearby, but lower than the best. Every neighbor is worse, so there's nowhere to climb. Random restarts, annealing, or keeping several candidates can get out. A plateau is flat: neighbors all score the same, so there's no sign of which way to go. Sideways moves with a limit, or restarts, can cross it. A ridge is a narrow crest that rises gently, with steep drops on either side. The allowed moves point down the sides.
Illustration
Why a Ridge Blocks the Climber
A ridge is hard to see, so let's draw one. Two settings can each change by one step at a time. The best direction runs diagonally, along the crest. But a single step to the right lands on the steep slope, and the score gets worse. A single step up does the same. The climber sees only downhill, even though a diagonal step would improve the score. All three traps share one cause: hill climbing looks only at its immediate neighbors, and never accepts a step backward. The next methods break that rule.
Simulated Annealing
Accepting Worse Moves While Cooling
Metalworkers anneal metal: they heat it until the atoms move freely, then cool it slowly, so they settle into a stable arrangement and the metal is less brittle. Simulated annealing copies that idea. Pick a random neighbor. If it's better, always move to it. If it's worse by an amount d, move to it anyway, with probability e to the minus d over T, where T is the temperature. Then lower T a little after every step. When T is high, bad moves are often accepted, so the search roams widely and explores. When T is low, they're almost never accepted, and it behaves like hill climbing.
Worked Numbers
Acceptance Odds at Different Temperatures
Here are the numbers. At a temperature of 10, a move worse by 1 point is accepted 90 percent of the time, and one worse by 5, 61 percent. At 2, those become 61 and 8 percent. At 1, 37 percent and under 1 percent. And at 0.2, a setback of 1 is accepted under 1 percent of the time, and one of 5, almost never. Small setbacks are accepted far more readily than big ones, and everything gets stricter as the temperature falls. On the landscape from earlier, in 500 simulated runs, hill climbing reached the global maximum about 51 percent of the time, and annealing about 88 percent.
Tuning
Starting Temperature and Cooling Speed
Tuning matters. Start too hot and it wastes time wandering, too cool and it's plain hill climbing. Cool too fast, and it freezes at a local maximum.
Quick Check
Worse by 2 at Temperature 4
Quick check. An annealing search is at temperature 4, and its random neighbor is worse by 2 points. About how likely is it to accept that move? Pause, and predict. About 61 percent. d over T is 2 over 4, a half, and e to the minus a half is about 0.61. It's the same ratio as worse by 1 at temperature 2. Fourteen percent forgets to divide by T, and almost zero multiplies instead.
Local Beam Search
Keeping the Best k States
Local beam search follows k states at once, where k is the beam width. Here k is 3, with illustrative scores. At every step it generates all the successors of all k states, pools them together, and keeps only the best k from the whole pool. Here, two of the three survivors came from state B, because its successors were the best. That's not the same as k separate hill climbs: effort shifts toward the promising region. The weakness is that the k states can crowd into one area and lose their variety. Stochastic beam search picks survivors at random, favoring better ones, to keep more variety.
Genetic Algorithms
Selection, Crossover, and Mutation
Genetic algorithms borrow from evolution. Instead of improving one state, they evolve a whole population of candidates over many generations. Each individual is a string of genes. For eight queens, 3 2 7 5 2 4 1 1 gives the row of the queen in each column. Every generation, measure each one's fitness, here the non-attacking pairs. Select parents, favoring the fitter ones. Cross them over, combining parts of two parents into a child. Mutate, with a small random change. And the children form the new generation.
Worked Example
A Child Better Than Both Parents
Here's one crossover. Parent 1 scores 23 non-attacking pairs, and parent 2 scores 24. The child takes its first six genes from parent 2, and its last two from parent 1. It scores 25, better than both parents. Then a mutation changes the last gene to a 6, and the score rises to 26. Crossover joins a good partial arrangement from one parent with a good one from another, something a single-state search can never do. Mutation adds variety that crossover can't, since crossover only recombines genes already in the population.
Population Variety
Why Diversity Matters as Much as Fitness
In one simulated run, the best board was perfect by generation 18, with the population's average fitness climbing steadily behind it. But not every run succeeds. Of 40 simulated runs, 24 found a perfect board within 100 generations. The other 16 stalled one point short, at 27. By then, only 30 to 56 of the 150 boards were different from one another, so crossover had little new to combine. Variety is as valuable as fitness. Too small a population, or too little mutation, loses it. Too much mutation turns the search random, and too strong a selection lets one lucky board take over early.
Real-World Uses
Timetables, Routes, Chips, and Designs
Local search runs real systems. School timetables use annealing, or hill climbing with restarts, to minimize clashes. Delivery routes are improved by small swaps in the order of stops. Chip layouts are placed by annealing, for the shortest wiring. Engineering designs and system settings are tuned with genetic algorithms. A sensible order: start with hill climbing plus random restarts. Reach for annealing when there are many local maxima, and for beam search or a genetic algorithm when candidates can share what they've learned. None of them guarantees the best answer, so judge the result on whether it's good enough.
Back to the Hiker
Restarts, Annealing, and Teams
Back to our hiker in the fog. Stepping only uphill, she can never know whether her peak is the highest one. But she could start again from many places, accept a few downhill steps early on, or bring a team that shares what it finds. Those are restarts, annealing, and beams or populations.
Key Takeaways
Local Search Methods Summed Up
To sum up. Local search keeps only the current state, or a few, and aims for a good final answer, not a route. Hill climbing is fast and simple, but stops at local maxima, plateaus and ridges. Restarts and sideways moves are cheap fixes. Simulated annealing accepts worse moves with a chance that falls as it cools. Beam search shares the best successors among k states. Genetic algorithms evolve a population by selection, crossover and mutation, and they need variety to keep improving.
Reflection
A 40-Stop Delivery Route
Here's something to think about. A company plans a 40-stop delivery route by hill climbing. It beats the old route, but still looks odd. Which trap might it be in, and what would you try next?
About Introduction to Artificial Intelligence at UPI Study
Introduction to Artificial Intelligence (Computer Science 373) is a self-paced online course of 69 video lessons in 9 chapters, from intelligent agents and search to game strategy, neural networks, logic and reasoning, machine learning, language, robotics and AI ethics. It carries a NCCRS credit recommendation for 3 semester credits.
Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →
Compare: AI vs Current Trends in CS and IT
Why take it here
Why students take Introduction to Artificial Intelligence with UPI Study
Where the credit goes
Universities that work with NCCRS
Introduction to Artificial Intelligence carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Thomas Edison State UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks with NCCRS
+many more cooperating universitiesFind my college →Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.
FAQ
Questions students ask us
About Climbing Toward Solutions: Local Search Methods
What is hill climbing in artificial intelligence?
How does random-restart hill climbing improve results?
How does simulated annealing decide whether to accept a worse move?
How does a genetic algorithm work?
About the Introduction to Artificial Intelligence course
How many college credits is Introduction to Artificial Intelligence?
How much does Introduction to Artificial Intelligence cost and what is included?
Which universities accept UPI Study credits?
How long does Introduction to Artificial Intelligence take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 3 credits in Introduction to Artificial Intelligence.
69 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
3 credits · NCCRSEnroll →