Heuristic Optimisation Flashcards
Define:
representation of problem
Encodes the alternative solutions for further manipulation
Define:
objective of problem
The purpose to be achieved
Define:
evaluation function for a problem
Tells us how good soln is (given rep)
OR how good compared to another solution
Representation of SAT
String of binary variables of length n
Representation of TSP
Permutation of 1,…n
Representation of NLP
Real numbers in [0,10] with 7 digits?
Evaluation func of TSP
Sum of distances along route
Evaluation func of NLP
Value of obj function for solution
Give 4 things to consider when choosing evaluation function
- Soln that meets objective should also have best evaluation
- Soln fails to meet objective cannot be evaluated to be better than a soln that meets the objective
- Objective may suggest evaluation function (or not)
- Feasible reigion of search space must be considered
Define:
optimisation problem
global solution
Given a search space S with its feasible part F ss S, find x in F s.t.
eval(x) <=eval(y) for all y in F (minimisation)
Such x is called global solution.
Give 4 reasons for using heuristics
- Avoid combinatorial explosion
- Rarely need optimal soln, good approximations are usually sufficient
- Approximations may not be very good in worst case, but worst case is very rare
- Helps with understanding of problem
Define:
distance function on search space S along with some axioms it may satisfy
dist: S x S -> reals
- d(x,x)=0
- d(x,y)=d(y,x)
- d(x,z) <= d(x,y) + d(y,z)
Define:
neighbourhood for epsilon>0 for dist function d
N(x) = {y in S : dist(x,y)
Define:
Manhattan distance
which problem is this used on?
dist(x,y) = sum from i=1 to n of |x_i - y_i|
NLP
Define:
Hamming distance
which problem is this used on?
Number of bit positions with different truth assignments (between two bit strings)
SAT
Define:
neighbourhood as a mapping
m: S to 2^S
neighbourhood given by m(x)
Define:
2-swap mapping
which problem is this used on?
The 2-swap mapping generates for any potential soln x the set of potential solns obtained by swapping two cities in x
TSP
Define:
2-interchange mapping
which problem is this used on?
The 2-interchange mapping generates for any potential soln x the set of potential solns obtained by replacing two non-adjacent edges AB and CD with AC and BD
TSP
Define:
1-flip mapping
which problem is this used on?
The 1-flip mapping flips exactly on bit of a potential soln x (with the representation of x as a Boolean string w/string entries 0 or 1)
SAT
Define:
local optimum
x in F is a local optimum wrt neighbourhood N(x) if
eval(x) <= eval(y) for all y in N(x)
Give analogy for hill-climbing algorithm
Height: quality of nodes
Peaks: optimal solutions
Orientation: evaluating neighbouring positions
Define:
basic hill-climbing algorithm
- Evaluation intial pt x. If obj met, RETURN x. Else set x as CURRENT PT.
- Loop till soln found:
a) Generate all neighbours of x. Select best (or
randomly on of best) y
b) If x is at least as good as y, RETURN x.
Else set y as CURRENT PT.
Define:
iterative hill-climbing algo
Hill-climbing algo restarted a predefined number of times.
Give 5 properties of hill-climbing (all bad)
- can get stuck in local maxima (so backtrack)
- plateaus are a problem (when eval func is flat) - make big jumps
- no info about how far local opt found is from global opt
- soln depends on initial configuration
- finding upper bound for computational time generally not possible
What is the difference between exploitation and exploration in algortihms. Give an example of an extreme of each.
Exploitation uses the solns that you already have to find/make new solns.
Exploration searches the rest of the search space without using current soln.
Hill-climbing: exploitation
Random search: Exploration
Give four reasons why some problems are difficult to solve.
- Size of search space large
- Problem is v. complicated (&solns to simplified model useless)
- Eval func varies w/time, so set of solns required
- Heavy constraints (hard to construct feasible soln)
Define:
Boolean Satisfiability Problem (SAT)
Task is to make a compound statement of Boolean variables, i.e. a Boolean function
F:{0,1}^n -> {0,1}
evaluate to TRUE.
Size of search space for SAT on n>0 variables
2^n
Define:
Travelling Salesperson Problem
Travelling salesperson must visit every city in their territory exactly once and return to their hometown covering the lowest cost.
OR
Given cost of travel between all pairs of cities, the itinerary for the minimum cost is sought.
Define:
Symmetric TSP
Cost of getting from A to B is same as cost from B to A
Give:
Size of search space for symmetric TSP on n cities
n!/(2n)=(n-1)!/2
Define:
Nonlinear Programming Problem
Problem of maximising objective function subject to several constraint functions, such that at least one of these functions is not linear.
Give:
Size of search space for NLP on n variables each with 6 digit precision
10^(7n)
What are the two modelling approaches to solving a problem? Which do we use in HO?
What are advantages and disadvantages of each?
Simplify model and use traditional optimiser:
Problem -> Model approx -> Soln precise (Model approx)
Adv: can be solved exactly w/traditional optimisation methods
Disadv: soln of simplified model could be far from soln of original prob
Keep exact model and find near-opt soln (using non-trad optimiser):
Problem -> Model precise -> Soln approx (Model precise)
Adv: keeps original complexity of problem and solns are normally close to perfect soln
Disadv: soln sometimes far from global soln (rare)
^ Used in HO
Define:
complete solution
Complete solution means that all decision variables are specified
Define:
algorithm on complete solutions
Algorithm which only manipulates complete solutions
Give 7 examples of algorithms on complete solutions
- exhaustive search
- local search
- hill-climbing
- gradient-based optimisation methods
- simulated annealing
- tabu search
- genetic algorithms
Define:
two types of algorithms on partial solutions
- Algos which manipulates incomplete solutions to original problem (i.e. on subset of search space)
- Algos which manipulate complete solns to a reduced problem (i.e. decompose orginal prob into smaller/simpler probs + combine the partial solns)
Give 3 examples of algorithms on partial solutions
- Greedy search
- Divide and conquer
- A* algorithm
Define:
conjunctive normal form
clauses/conjuncts
If F = F1 AND F2 AND F3 AND…AND Fn
where F1,…F2 are formed by using negations and/or disjunctions (OR)
F1 etc are called clauses/conjunts
Give 2 problems with partial solutions
- difficult to devise a way for organising the subspaces of the search space to assure effective search
- a new eval func is needed to assess the quality of partial solns
Alternative representation for SAT
Represent potential solutions as vectors of real numbers in range [-1,1].
xi >= 0 means TRUE
xi < 0 means FALSE
Alternative representation for NLP
Represent potential solns as binary strings of length kn, where each variable xi in [li , ui] is endcoded as a binary string of length k.
Show how to convert binary string [b_(k-1),…,b_0] into decimal value x_i from some interval [l_i,u_i]
- Convert string from base 2 to base 10 (powers of 2) - x’
- Find corresponding decimal value in required interval
i. e. l_i + x’ ((u_i - l_i)/(2^k -1))
Describe:
exhaustive search
Looks at every possible solution in search space until global optimum is found
Give 1 disadvantage and 3 advantages of exhaustive search
disadvg: if global opt not known have to search all pts
advg:
- algo is simple
- deeper understanding of structure of your representation
- backtracking can reduce workload
Describe:
backtracking for exhaustive search
If after assigning values to some variables it turns out that there is no solution that has those values then we do not continue assigning values but go back one step and try a different option.
Describe:
how to enumerate SAT (for exhaustive search)
Want to generate all binary strings of length n.
- eval function will be: 1 if Boolean statement is satisfied and 0 otherwise
- partition search space into tree and use depth-first search:
- -visit current node
- -for each child of current node perform depth-first search
- if dead end then can backtrack
Describe:
how to enumerate TSP (for exhaustive search)
Want to generate all possible permutations of 1,2,…n
- enumerate by successively exchanging adjacent elements
- the cost of evaluating the next solution is then just reduced to calculating the effect of the change on the current solution
Describe:
how to enumerate NLP (for exhaustive search)
Divide continuous domain into finite number of intervals (call these cells)
For each cell evaluate at one point.
For best cell found repeat (divide again)
Give:
- eval function
- neighbourhoods
for SAT local search
eval(F) is number of unsatisfied clauses (where F is in conjunctive normal form)
neighbourhood of x is set of Boolean strings defined by the 1-flip mapping
GSAT algorithm
1) Repeat steps 2-3 MAX_TRIES times:
2) Assign values to X=[x1,…,xn] randomly
3) Repeat MAX_FLIPS times:
- if formula satisfied, return X
- else make a flip
4) return “no solution found”
2-opt algorithm for TSP
Neighbourhoods are 2-interchange transformations.
Repeat neighbourhood search until cannot improve any more.
Define:
delta-path
All nodes appear exactly once expect the last node which appears twice
Lin-Keringham algorithm for TSP
1) Generate tour T and store as best.
2) for all nodes k on tour T and each edge (i,k):
- if node j exists s.t. cost(i,j)<=cost(i,k) then create delta-path p where edge (i,j) replaces edge (i,k)
a) repair p into tour T1 and store if better than best
b) if switch from p to p1 with cost(p1)<=cost(T1) then replace p with p1
c) repeat from a
3) Return best.
Define:
NLP
Given f: R^n -> R optimise f(x), x=(x1,…,xn)
s.t. for x in F ss S ss R^n
where search space S is given by
l_i <=x_i <= u_i for all 1<=i<=n
feasible region F ss S:
g_j (x) <= 0 for 1<=j<=q
h_j(x) =0 for q
Describe:
gradient method for NLP
Use grad of eval func at a particular candidate soln to direct search towards improved solns. Essential to find the right step size to guarntee the best rate of convergence over the iterations.
Steepest descent algo for NLP
1) Start with initial candiate soln x_1. Let k=1
2) Generate new soln x_(k+1) = x_k - alpha_k grad(f(x_k))
3) If norm(x_(k+1)-x_k) > epsilon let k=k+1 and go to 2.
What does the gradient method perform well for?
Smooth unimodal evaluation functions of NLP. Where unimodal means that the eval func has a unique local max/min.
Give iterative step in Newton’s method for NLP
x_(k+1) = x_k - inv((H f(x_k))) grad(f(x_k))
where H is Hessian of f
Describe Greedy algo
At each tep value for one decision variable is assigned by making best avaliable decision
Give 2 pros and 2 cons for Greedy algo
Pro: simple + fast
Cons: shortsighted + no-guarntee of global opt
Describe
Greedy for SAT
What improvements can be made?
- Fix order of variables considering, we will assign truth value to variables one at a time
- Choose 0 or 1 depending on which satisfies the greatest number of presently unsatisfied clauses
Improvements:
- sort all vars according to freq of appearance
- forbid any assignment that makes a clause FALSE
- consider freq of vars for remaining unsatfisfied clauses
- consider length of clause
Desribe:
Nearest neighbourhood heurisitc algo for TSP
-what type of algo is this?
Greedy algo
1) Select arbitrary starting city
2) Select city from cities not visited yet that is closest to the current city (and feasible). Go to this city
3) Repeat 2 until all cities visited
Describe:
alternative greedy algo for TSP
1) From all possible edges, select shortest and add it to the tour
2) Reduce set of possible edges that would lead to illegal tours
3) Repeat 1-2 till tour complete
Describe:
Divide and Conquer algo for problem P
1) Split P into subproblems P1,…,Pk
2) for i=1,…,k:
- if size(Pi) < rho : solve Pi and get it’s soln Si
- else: apply divide&conquer(Pi) and assign result to Si
3) Combine S1,…,Sk into soln S for P
4) Return soln S
Define:
0/1 knapsack problem
Given set of N items w/value v_i and weight w_i and bag of finite capacity k (max weight).
Prob: fill bag w/items w/o exceeding its capactiy, so that value of items in bag is maximised
- cannot use parts of an item
Describe:
Greedy algo for knapsack prob
“best value for money”
select item with max vi/wi and put in bag if bag can hold it
Stopping criterion: no more items can fit in bag
Describe:
graph search algorithm
- choose node at each step and expand by generating successors (expanded node added to CLOSED list)
- each step the algo chooses between nodes in OPEN list
Describe how to measure quality of node n in A* algorithm
f(n) = g(n) + h(n)
where
g(n) is measure of cost of initial state to current state n
h(n) is estimate of cost of current state n to goal state
Describe:
A* algorithm
OPEN is list of generated but not yet examined nodes
1) start w/OPEN containing intial state
2) do until goal state found or no nodes left in OPEN:
a) take best node (lowest f) value in OPEN and generate its successors
b) For each successor:
i) if not generated before, evaluate and add to OPEN
ii) otherwise if change parent if path better:
if node OPEN: modify parent and g,f values. If node in CLOSED modify f,g values of children
Describe:
greedy best-first algorithm
At each step choose one of the generated nodes which has the lowest value (i.e. best node from OPEN list) - just A* with h=0
What are the other names for A* search when:
- h=0
- h=0 and g=0
- greedy best-first search
- random search
What are the reasons for using a search tree or search graph w/ A* algorithm
Search graph has to update g values for alternative paths so slower.
Search tree generates nodes faster but duplicates nodes which uses up memory.
Define:
complete algorithm
Algorithm is complete if it returns a solution if one exists and no solution if no solution exists.
Define:
optimal algorithm
Algorithm is optimal if it returns an optimal solution if one exists and reports that there is no optimal solution if none exists.
Give 4 properties of h in the A* algorithm
- if h is a perfect estimator then A* will never leave the optimal path
- the better h estimates the real distance, the closer A* is to the “direct path”
- if h never overestimates the real distance then A* is guaranteed to find an optimal solution
- if h overestimates then the optimal path is only found if all paths in the search space longer than the optimal solution have been expanded
Define:
h admissible in A*
h is admissible if it never overestimates the cost to reach the goal
What are the conditions on h in A* for A* to find the minimal cost path to the goal
h admissible and a path with finite cost from start to goal exists
Give 3 observations about A* wrt f(n) and f* and expanding nodes
- A* expands all nodes w/ f(n) < f*
- A* might expand nodes w/ f(n) = f*
- A* never expands nodes w/ f(n) > f*
Define:
- monotonic/consistent heuristic in A*
If along paths in search tree of A* the f-cost never decreases then the heuristic is monotonic
Give necessary and sufficient condition for a heuristic f on A* to be monotonic
f(A) <= f(B) iff h(A) <= h(B) + c(A,B)
for any nodes A,B with a path from A to B
c(A,B) is the cost of the subpath from A to B
f = g + h
Define:
path-max equation
- what is it used for?
f(B) = max( f(A), g(B) + h(B) )
where A and B are two nodes s.t. A is a parent of B
Used for making heuristic monotonic.
State:
the monotonicity theorem for A* algorithm
If a monotonic heuristic h is used, when A* expands a node n then it has already found an optimal path to n
Define:
more informed A* algorithm
A2* is more informed than A1* if h1 < h2 for all nodes that are not goal nodes
State:
the informedness theorem for A* algorithm
If A2* is more informed than A1, then at the termination of their searches on any graph etc., every node expanded by A2 is also expanded by A1*
