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