# CS代考 COMP 424 – Artificial Intelligence Local search for optimization – cscodehelp代写

COMP 424 – Artificial Intelligence Local search for optimization
Instructor: Jackie CK Cheung and Readings: R&N Ch. 4.1 (3rd or 4th ed)

Scheduling McGill’s Final Exams

• How would you design the final exam schedule for McGill?

Scheduling McGill’s Final Exams
• It’s not so hard to find a solution (though it might be terrible).
• We want a good solution, or even an optimal solution
• Today’s lecture: solve this by search!

Uninformed search
• Assumes no knowledge about the problem.
• BFS, DFS, Iterative deepening
Informed search
• Use knowledge about the problem, in the form of a heuristic.
• Best-first search, heuristic search, A* (and extensions)
Search for optimization problems:
• Search over large-dimensional spaces
• Iterative improvement algorithms:
1. Hill climbing
2. Simulated annealing
3. Parallelism and beam search
4. Genetic algorithms

Search and Optimization
• Search so far:
• Finding the solution with the minimal cost, where the cost is the
sum of edge weights (e.g., A* search)
• Case where solution cost is some arbitrary function (Eval(X))
• Want to find best solution (X*) – optimization problem

Optimization problems are everywhere
Scheduling
• Given: a set of tasks to be completed, with durations and mutual constraints (e.g. task ordering, joint resources).
• Goal: generate shortest schedule (assignment of start times to tasks.)
Digital circuit layout
• Given: a board, components and connections.
• Goal: place each component on the board such as to maximize
energy efficiency, minimize production cost, …
User customization
• Given: customers described by characteristics (age, gender, location, etc.) and previous purchases.
• Goal: find a function from characteristics to products that maximizes expected gain.

Types of search for optimization problems
1. Constructive methods: Start from scratch and build up a solution.
• This is the type of method we have seen so far.
2. Iterative improvement/repair methods: Start with a solution (which may be broken / suboptimal) and improve it.
• Focus of today’s lecture

Characteristics
• An optimization problem is described by:
• A set of states (= configurations)
• An evaluation function
• For interesting optimization problems, the state space is too big to enumerate all states, or the evaluation function is too expensive to compute for all states.
• In iterative improvement, a state is a candidate solution, not a description of the world!
• It might be a partial or incorrect solution; if so, should be reflected in evaluation function.

Travelling Salesman Problem (TSP)
• Given: a set of vertices and distance between pairs.
• Goal: construct the shortest path that visits every vertex exactly once (a tour)
• e.g., consider these seven cities on a map
• A state in the iterative improvement paradigm is a candidate tour; the evaluation function would be length of the tour.
• X1 (above) is a tour, but not an optimal one.
• Provably very hard (NP-complete) to find the best solution

Visualizing iterative improvement
• Intuition: Consider all possible solutions laid out on a landscape. We want to find the highest (or lowest) point.
• This landscape is often very high-dimensional.

A generic local search algorithm
• Start from an initial configuration X0.
• Repeat until satisfied:
• Generate the set of neighbours of Xi and evaluate them.
• Select one of the neighbours, Xi+1.
• The selected neighbor becomes the current configuration.

A generic local search algorithm
• Start from an initial configuration X0.
• Repeat until satisfied:
• Generate the set of neighbours of Xi and evaluate them.
• Select one of the neighbours, Xi+1.
• The selected neighbor becomes the current configuration.
Important questions:
1. How do we choose the set of neighbours to consider?
2. How do we select one of the neighbours?
• Defining the set of neighbours is a design choice (like choosing the heuristic for A*) and has crucial impact on performance.

What moves should we consider?
• Case 1: Search for high ground
• Move to an adjacent position.
• Terminate when goal is reached.
• Case 2: Traveling Salesman Problem
• Swap cities to obtain a new partial tour.
• Terminate when constraints are met.

Hill climbing
• Also called greedy local search
• In continuous state space, related to gradient ascent
Start from an initial configuration X0 with value E(X0) X  X0 , and E  E(X0)
Repeat until satisfied:
Generate the set of neighbours of Xi and their value E(Xi).
Let Emax = maxi E(Xi) be the value of the best successor,
i* = argmaxi E(Xi) be the index of the best successor. if Emax  E:
return X (we are at an optimum) else:
let X  Xi* , and E  Emax. (take a greedy step)

Properties of hill climbing
• Very popular in AI:
• Trivial to program!
• Requires no memory of where we’ve been (no backtracking).
• Can handle very large problems.
• Neighbourhood function is important
• Small neighbourhood: fewer neighbours to evaluate, but possibly
worse solution.
• Large neighbourhood: more computation, but maybe fewer local optima, so better final result.

Local vs. Global Optimum
• Global optimum: The optimal point over the full space of possible configurations.
• Local optimum: The optimal point over the set of neighbours. One of the (possibly many) optimums.

Example: TSP
• What neighbours should we consider?
• How many neighbours is that?

Example: TSP swapping 2 nodes

Example: TSP swapping 3 nodes

Problems with hill climbing
• Can get stuck in a local maximum or in a plateau
objective function
global maximum
local maximum
“flat” local maximum
• Relies heavily on having a good evaluation
current state
state space

Improvements to hill climbing
• Quick fix:
• When stuck in a plateau or local maximum, use random re-starts.
• Slightly better fix:
• Instead of picking the next best move, pick any move that
produces an improvement. (Called randomized hill climbing.)

Improvements to hill climbing
• Quick fix:
• When stuck in a plateau or local maximum, use random re-starts.
• Slightly better fix:
• Instead of picking the next best move, pick any move that
produces an improvement. (Called randomized hill climbing.)
• But sometimes we need to pick apparently worse moves to eventually reach a better state.

Simulated annealing

Simulated annealing
Similar to hill climbing, but:
• allows some “bad moves” to try to escape local maxima.
• decrease size and frequency of “bad moves” over time.
Algorithm:
• Start from an initial configuration X0 with value E(X0).
• Repeat until satisfied:
• Let Xi be a random neighbour of X with value E(Xi).
• If Ei > Emax, let Xi*  Xi and let Emax = Ei (we found a new better sol’n). • IfEi >EthenXXi and EEi .
• Else, with some probability p, still accept the move: X Xi and E  Ei .
• Return Xi* .

What value should we use for p?
• Many possible choices:
• A given fixed value.
• A value that decays to 0 over time.
• A value that decays to 0, and gives similar chance to “similarly