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

Copyright By cscodehelp代写 加微信 cscodehelp

• 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

• Start with initial state = random position.

• Move to an adjacent position.

• Terminate when goal is reached.

• Case 2: Traveling Salesman Problem

• Start with initial state = a random (possibly incomplete/illegal) tour.

• 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 >EthenXXi and EEi .

• 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

bad” moves.

• A value that depends on on how much worse the bad move is.

What value should we use for p?

• If the new value Ei is better than the old value E, move to Xi.

• If the new value is worse (Ei < E) then move to the neighboring solution with probability: p = e-(E-Ei)/T (Boltzmann distribution)
• T > 0 is a parameter called the temperature, which typically starts high, then decreases over time towards 0.

• If T is very close to 0, the probability of moving to a worse solution is almost 0.

• We can gradually decrease T by multiplying by constant 0 < < 1 at every iteration.
Properties of simulated annealing
• What happens when T is high?
• Algorithm is in an exploratory phase (even bad moves have a high
chance of being picked).
• What happens when T is low?
• Algorithm is in an exploitation phase (the “bad” moves have very low probability).
Properties of simulated annealing
• If T decreases slowly enough, simulated annealing is guaranteed to reach the optimal solution (i.e., find the global maximum).
• But it may take an infinite number of moves! This result is not practically useful.
TSP example: Searching configurations
TSP Example: Energy
Simulated annealing in practice
• Very useful algorithm, used to solve hard optimization problems.
• E.g. Protein design, scheduling large transportation fleets.
• The temperature annealing schedule is crucial (design choice!)
• Cool too fast: converge to sub-optimal solution.
• Cool too slow: don’t converge.
• Simulated annealing is an example of a randomized search or Monte-Carlo search.
• Basic idea: run around through the environment and explore it, instead of systematically sweeping. Very powerful idea!
Mitigating the local optimum problem
• Even simulated annealing can get stuck in local maxima!
• More strategies to find a good solution:
• Parallel search
• Beam search
• Genetic algorithms
Parallel search
• Run many separate searches (hill climbing or simulated annealing) in parallel.
• Keep the best solution found.
• Search speed can be greatly improved by using many
processors (including, most recently, GPUs).
• Especially useful when actions have non-deterministic outcomes (many possible successor states).
Local beam search
• Similar to parallel search; run many instances of local search or simulated annealing at the same time
• Key difference: information sharing across searches
• Algorithm:
• Start k searches in parallel
• At each step, keep the top k solutions in the sets of neighbourhoods, discard the remaining
• k is called the beam width
Local beam search schematic
Image source: , http://slideplayer.com/slide/4897669/
Evolutionary computing
• Refers generally to computational procedures patterned after biological evolution
• Many solutions (individuals) exist in parallel
• Nature looks for the best individual (i.e., the fittest)
• Evolutionary search procedures are also parallel, perturbing probabilistically several potential solutions
Genetic algorithms
• A candidate solution is called an individual.
• In a traveling salesman problem, an individual is a tour
• Each individual has a fitness
• fitness = numerical value proportional to quality of that solution
• A set of individuals is called a population.
• Populations change over generations, by applying operations to individuals.
• operations = {mutation, crossover, selection}
• Individuals with higher fitness are more likely to survive &
reproduce.
• Individual typically represented by a binary string:
• allows operations to be carried out easily.
• A way to generate desirable features that are not present in
the original population by injecting random change.
• Typically, mutation just means changing a 0 to a 1 (and vice versa).
• The mutation rate controls prob. of mutation occurring
• We can allow mutation in all individuals, or just in the offspring.
• Combine parts of individuals to create new individuals
• Single-point crossover:
• Choose a crossover point, cut individuals there, swap the pieces.
E.g. 101|0101 101|1110 011|1110 011|0101
• Implementation:
• Use a crossover mask, which is a binary string
E.g. mask = 1110000
• Multi-point crossover can be implemented with arbitrary mask
Encoding operators as binary masks
Typical genetic algorithm
GA(Fitness, threshold, p, r, m)
• Initialize: P p random individuals
• Evaluate: for each h P, compute Fitness(h)
• While maxh Fitness(h) < threshold
• Select: Probabilistically select (1-r)p members of P to include in Ps
• Crossover: Probabilistically select rp/2 pairs of individuals from P.
For each pair (h1, h2), produce two offspring by applying a crossover operator. Include all offspring in Ps.
• Mutate: Invert a randomly selected bit in m*p randomly selected members of Ps
• Update: P Ps
• Evaluate: for each h P, compute Fitness(h)
• Return the individual from P that has the highest fitness.
Selection: Survival of the fittest
• As in natural evolution, fittest individuals are more likely to survive.
• Several ways to implement this idea:
1. Fitness proportionate selection:
Can lead to crowding (multiple copies being propagated).
2. Tournament selection:
Pick i, j at random with uniform probability. With prob p select the fitter
one. Only requires comparing two individuals.
3. Rank selection:
Sort all hypothesis by fitness. Probability of selection is proportional to rank.
4. Softmax (Boltzman) selection:
• Elitism: separately, store the best solution ever encountered 43
Genetic algorithms as search
• States: possible solutions
• Search operators: mutation, crossover, selection
• Relation to previous search algorithms:
• Parallel search, since several solutions are maintained in parallel
• Hill-climbing on the fitness function, but without following the gradient
• Mutation and crossover should allow us to get out of local minima
• Very related to simulated annealing.
Example: Solving TSP with a GA
• Each individual is a tour.
• Mutation swaps a pair of edges (many other operations
are possible and have been tried in literature.)
• Crossover cuts the parents in two and swaps them. Reject
any invalid offsprings.
• Fitness is the length of the tour.
• Note that GA operations (crossover and mutation) described here are fancier that the simple binary examples given before.
Example: Solving TSP with a GA
TSP example: Initial generation
TSP example: Generation 15
TSP example: Generation 30
The good and bad of GAs
• Intuitively appealing, due to evolution analogy.
• If tuned right, can be very effective (good solution with few steps.)
• Performance depends crucially on the problem encoding. Good
encodings are difficult to find!
• Many parameters to tweak! Bad parameter settings can result in very slow progress, or the algorithm is stuck in local minima.
• With mutation rate is too low, can get overcrowding (many copies of the identical individuals in the population).
• Optimization problems are widespread and important.
• It is infeasible to enumerate lots of solutions.
• Goal is to get a reasonable (not necessarily optimal) solution.
• Apply a local search and move in a promising direction.
• Hill climbing always moves in the (locally) best direction
• Simulated annealing allows some moves towards worse solutions
• Parallelism and beam search can be exploited to improve results;
find a better local optimum
• Genetic algorithms are an alternative related to simulated annealing which has an analogy to biological evolution
程序代写 CS代考 加微信: cscodehelp QQ: 2235208643 Email: kyit630461@163.com