marketing Assignment 代写作业

100%原创包过,高质代写&免费提供Turnitin报告--24小时客服QQ&微信：120591129

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,

charles.gretton@nicta.com.au

This material addresses topics from Chapter 4 (“Beyond Classical Search”) of the prescribed text.I am Charles Gretton, NICTA Researcher,ph:0262676326,charles.gretton@nicta.com.au

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,charles.gretton@nicta.com.au

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,charles.gretton@nicta.com.au

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,charles.gretton@nicta.com.au

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,charles.gretton@nicta.com.au

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,charles.gretton@nicta.com.au

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,charles.gretton@nicta.com.au

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,charles.gretton@nicta.com.au

Properties of simulated annealing

At fixed “temperature” T, state occupation probability reaches

Boltzman distribution

p(x) = αe

E(x)

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,charles.gretton@nicta.com.au

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,charles.gretton@nicta.com.au

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,charles.gretton@nicta.com.au