marketing Assignment 代写作业
100%原创包过,高质量代写&免费提供Turnitin报告--24小时客服QQ&微信:273427
marketing Assignment 代写作业 Search search search search and more search
What is search anyway?
All material adapted from Stuart Russell’s
2004 Berkeley-course slides
This material addresses topics from Chapter 4 (“Beyond
Classical Search”) of the prescribed text.
I am Charles Gretton, NICTA Researcher,
ph:0262676326,
This material addresses topics from Chapter 4 (“Beyond Classical Search”) of the prescribed text.I am Charles Gretton, NICTA Researcher,ph:0262676326,
[email protected]
marketing Assignment 代写作业
Outline
♦ Hill-climbing
♦ Simulated annealing
♦ Genetic algorithms – Interested people could look at the literature on
“Racing algorithms” and Ant Colony Optimisation.
♦ Local search in continuous spaces
This material addresses topics from Chapter 4 (“Beyond Classical Search”) of the prescribed text.I am Charles Gretton, NICTA Researcher,ph:0262676326,
[email protected]
2
Iterative improvement algorithms
In many optimisation problems, path is irrelevant;
the goal state itself is the solution
Then state space = set of “complete” configurations;
find optimal configuration, e.g., TSP
or, find configuration satisfying constraints, e.g., timetable
In such cases, can use iterative improvement algorithms;
keep a single “current” state, try to improve it
Constant space, suitable for online as well as offline search
This material addresses topics from Chapter 4 (“Beyond Classical Search”) of the prescribed text.I am Charles Gretton, NICTA Researcher,ph:0262676326,
[email protected]
3
Example: Travelling Salesperson Problem
Start with any complete tour, perform pairwise exchanges
Variants of this approach get within 1% of optimal very quickly with thou-
sands of cities
This material addresses topics from Chapter 4 (“Beyond Classical Search”) of the prescribed text.I am Charles Gretton, NICTA Researcher,ph:0262676326,
[email protected]
4
Example: n-queens
Put n queens on an n × n board with no two queens on the same
row, column, or diagonal
Move a queen to reduce number of conflicts
h = 5
h = 2
h = 0
Almost always solves n-queens problems almost instantaneously
for very large n, e.g., n=1million
This material addresses topics from Chapter 4 (“Beyond Classical Search”) of the prescribed text.I am Charles Gretton, NICTA Researcher,ph:0262676326,
[email protected]
5
Hill-climbing (or gradient ascent/descent)
“Like climbing Everest in thick fog with amnesia”
function Hill-Climbing(problem) returns a state that is a local maximum
inputs: problem, a problem
local variables: current, a node
neighbor, a node
current←Make-Node(Initial-State[problem])
loop do
neighbor←a highest-valued successor of current
if Value[neighbor] ≤ Value[current] then return State[current]
current←neighbor
end
This material addresses topics from Chapter 4 (“Beyond Classical Search”) of the prescribed text.I am Charles Gretton, NICTA Researcher,ph:0262676326,
[email protected]
6
Hill-climbing contd.
Useful to consider state space landscape
current
state
objective function
state space
global maximum
local maximum
"flat" local maximum
shoulder
Random-restart hill climbing overcomes local maxima—trivially complete
Random sideways moves
escape from shoulders
loop on flat maxima
This material addresses topics from Chapter 4 (“Beyond Classical Search”) of the prescribed text.I am Charles Gretton, NICTA Researcher,ph:0262676326,
[email protected]
7
Simulated annealing
Idea: escape local maxima by allowing some “bad” moves
but gradually decrease their size and frequency
function Simulated-Annealing(problem,schedule) returns a solution state
inputs: problem, a problem
schedule, a mapping from time to “temperature”
local variables: current, a node
next, a node
T, a “temperature” controlling prob. of downward steps
current←Make-Node(Initial-State[problem])
for t← 1 to ∞ do
T←schedule[t]
if T = 0 then return current
next←a randomly selected successor of current
∆E←Value[next] – Value[current]
if ∆E > 0 then current←next
else current←next only with probability e∆ E/T
This material addresses topics from Chapter 4 (“Beyond Classical Search”) of the prescribed text.I am Charles Gretton, NICTA Researcher,ph:0262676326,
[email protected]
8
Properties of simulated annealing
At fixed “temperature” T, state occupation probability reaches
Boltzman distribution
p(x) = αe
E(x)
kT
T decreased slowly enough =⇒ always reach best state x∗
because e
Fitness
Pairs
This material addresses topics from Chapter 4 (“Beyond Classical Search”) of the prescribed text.I am Charles Gretton, NICTA Researcher,ph:0262676326,
[email protected]
11
Genetic algorithms contd.
GAs require states encoded as strings (GPs use programs)
Crossover helps iff substrings are meaningful components
+
=
GAs 6= evolution: e.g., real genes encode replication machinery!
This material addresses topics from Chapter 4 (“Beyond Classical Search”) of the prescribed text.I am Charles Gretton, NICTA Researcher,ph:0262676326,
[email protected]
12
Continuous state spaces
Suppose we want to site three airports in Romania:
– 6-D state space defined by (x1,y2), (x2,y2), (x3,y3)
– objective function f(x1,y2,x2,y2,x3,y3) =
sum of squared distances from each city to nearest airport
Discretization methods turn continuous space into discrete space,
e.g., empirical gradient considers ±δ change in each coordinate
Gradient methods compute
to increase/reduce f, e.g., by x ← x + α∇f(x)
Sometimes can solve for ∇f(x) = 0 exactly (e.g., with one city).
Newton–Raphson (1664, 1690) iterates x ← x − H−1
f(x)∇f(x)
to solve ∇f(x) = 0, where Hij=∂2f/∂xi∂xj
This material addresses topics from Chapter 4 (“Beyond Classical Search”) of the prescribed text.I am Charles Gretton, NICTA Researcher,ph:0262676326,
[email protected]
13