Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Heuristic Optimisation > Heuristic Optimisation > Flashcards

Heuristic Optimisation Flashcards

1
Q

Define:

representation of problem

A

Encodes the alternative solutions for further manipulation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Define:

objective of problem

A

The purpose to be achieved

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Define:

evaluation function for a problem

A

Tells us how good soln is (given rep)

OR how good compared to another solution

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Representation of SAT

A

String of binary variables of length n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Representation of TSP

A

Permutation of 1,…n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Representation of NLP

A

Real numbers in [0,10] with 7 digits?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Evaluation func of TSP

A

Sum of distances along route

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Evaluation func of NLP

A

Value of obj function for solution

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Give 4 things to consider when choosing evaluation function

A
  1. Soln that meets objective should also have best evaluation
  2. Soln fails to meet objective cannot be evaluated to be better than a soln that meets the objective
  3. Objective may suggest evaluation function (or not)
  4. Feasible reigion of search space must be considered
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Define:
optimisation problem
global solution

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Give 4 reasons for using heuristics

A
  1. Avoid combinatorial explosion
  2. Rarely need optimal soln, good approximations are usually sufficient
  3. Approximations may not be very good in worst case, but worst case is very rare
  4. Helps with understanding of problem
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Define:

distance function on search space S along with some axioms it may satisfy

A

dist: S x S -> reals

  1. d(x,x)=0
  2. d(x,y)=d(y,x)
  3. d(x,z) <= d(x,y) + d(y,z)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Define:

neighbourhood for epsilon>0 for dist function d

A

N(x) = {y in S : dist(x,y)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Define:
Manhattan distance
which problem is this used on?

A

dist(x,y) = sum from i=1 to n of |x_i - y_i|

NLP

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Define:
Hamming distance
which problem is this used on?

A

Number of bit positions with different truth assignments (between two bit strings)
SAT

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Define:

neighbourhood as a mapping

A

m: S to 2^S

neighbourhood given by m(x)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Define:
2-swap mapping
which problem is this used on?

A

The 2-swap mapping generates for any potential soln x the set of potential solns obtained by swapping two cities in x
TSP

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Define:
2-interchange mapping
which problem is this used on?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Define:
1-flip mapping
which problem is this used on?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Define:

local optimum

A

x in F is a local optimum wrt neighbourhood N(x) if

eval(x) <= eval(y) for all y in N(x)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Give analogy for hill-climbing algorithm

A

Height: quality of nodes
Peaks: optimal solutions
Orientation: evaluating neighbouring positions

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Define:

basic hill-climbing algorithm

A
  1. Evaluation intial pt x. If obj met, RETURN x. Else set x as CURRENT PT.
  2. 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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Define:

iterative hill-climbing algo

A

Hill-climbing algo restarted a predefined number of times.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Give 5 properties of hill-climbing (all bad)

A
  1. can get stuck in local maxima (so backtrack)
  2. plateaus are a problem (when eval func is flat) - make big jumps
  3. no info about how far local opt found is from global opt
  4. soln depends on initial configuration
  5. finding upper bound for computational time generally not possible
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

What is the difference between exploitation and exploration in algortihms. Give an example of an extreme of each.

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Give four reasons why some problems are difficult to solve.

A
  1. Size of search space large
  2. Problem is v. complicated (&solns to simplified model useless)
  3. Eval func varies w/time, so set of solns required
  4. Heavy constraints (hard to construct feasible soln)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Define:

Boolean Satisfiability Problem (SAT)

A

Task is to make a compound statement of Boolean variables, i.e. a Boolean function
F:{0,1}^n -> {0,1}
evaluate to TRUE.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

Size of search space for SAT on n>0 variables

A

2^n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

Define:

Travelling Salesperson Problem

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

Define:

Symmetric TSP

A

Cost of getting from A to B is same as cost from B to A

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

Give:

Size of search space for symmetric TSP on n cities

A

n!/(2n)=(n-1)!/2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

Define:

Nonlinear Programming Problem

A

Problem of maximising objective function subject to several constraint functions, such that at least one of these functions is not linear.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

Give:

Size of search space for NLP on n variables each with 6 digit precision

A

10^(7n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

What are the two modelling approaches to solving a problem? Which do we use in HO?

What are advantages and disadvantages of each?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

Define:

complete solution

A

Complete solution means that all decision variables are specified

36
Q

Define:

algorithm on complete solutions

A

Algorithm which only manipulates complete solutions

37
Q

Give 7 examples of algorithms on complete solutions

A
  1. exhaustive search
  2. local search
  3. hill-climbing
  4. gradient-based optimisation methods
  5. simulated annealing
  6. tabu search
  7. genetic algorithms
38
Q

Define:

two types of algorithms on partial solutions

A
  1. Algos which manipulates incomplete solutions to original problem (i.e. on subset of search space)
  2. Algos which manipulate complete solns to a reduced problem (i.e. decompose orginal prob into smaller/simpler probs + combine the partial solns)
39
Q

Give 3 examples of algorithms on partial solutions

A
  1. Greedy search
  2. Divide and conquer
  3. A* algorithm
40
Q

Define:
conjunctive normal form
clauses/conjuncts

A

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

41
Q

Give 2 problems with partial solutions

A
  1. difficult to devise a way for organising the subspaces of the search space to assure effective search
  2. a new eval func is needed to assess the quality of partial solns
42
Q

Alternative representation for SAT

A

Represent potential solutions as vectors of real numbers in range [-1,1].
xi >= 0 means TRUE
xi < 0 means FALSE

43
Q

Alternative representation for NLP

A

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.

44
Q

Show how to convert binary string [b_(k-1),…,b_0] into decimal value x_i from some interval [l_i,u_i]

A
  1. Convert string from base 2 to base 10 (powers of 2) - x’
  2. Find corresponding decimal value in required interval
    i. e. l_i + x’ ((u_i - l_i)/(2^k -1))
45
Q

Describe:

exhaustive search

A

Looks at every possible solution in search space until global optimum is found

46
Q

Give 1 disadvantage and 3 advantages of exhaustive search

A

disadvg: if global opt not known have to search all pts

advg:

  1. algo is simple
  2. deeper understanding of structure of your representation
  3. backtracking can reduce workload
47
Q

Describe:

backtracking for exhaustive search

A

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.

48
Q

Describe:

how to enumerate SAT (for exhaustive search)

A

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
49
Q

Describe:

how to enumerate TSP (for exhaustive search)

A

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
50
Q

Describe:

how to enumerate NLP (for exhaustive search)

A

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)

51
Q

Give:
- eval function
- neighbourhoods
for SAT local search

A

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

52
Q

GSAT algorithm

A

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”

53
Q

2-opt algorithm for TSP

A

Neighbourhoods are 2-interchange transformations.

Repeat neighbourhood search until cannot improve any more.

54
Q

Define:

delta-path

A

All nodes appear exactly once expect the last node which appears twice

55
Q

Lin-Keringham algorithm for TSP

A

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.

56
Q

Define:

NLP

A

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

57
Q

Describe:

gradient method for NLP

A

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.

58
Q

Steepest descent algo for NLP

A

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.

59
Q

What does the gradient method perform well for?

A

Smooth unimodal evaluation functions of NLP. Where unimodal means that the eval func has a unique local max/min.

60
Q

Give iterative step in Newton’s method for NLP

A

x_(k+1) = x_k - inv((H f(x_k))) grad(f(x_k))

where H is Hessian of f

61
Q

Describe Greedy algo

A

At each tep value for one decision variable is assigned by making best avaliable decision

62
Q

Give 2 pros and 2 cons for Greedy algo

A

Pro: simple + fast
Cons: shortsighted + no-guarntee of global opt

63
Q

Describe
Greedy for SAT
What improvements can be made?

A
  • 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
64
Q

Desribe:
Nearest neighbourhood heurisitc algo for TSP
-what type of algo is this?

A

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

65
Q

Describe:

alternative greedy algo for TSP

A

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

66
Q

Describe:

Divide and Conquer algo for problem P

A

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

67
Q

Define:

0/1 knapsack problem

A

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

68
Q

Describe:

Greedy algo for knapsack prob

A

“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

69
Q

Describe:

graph search algorithm

A
  • 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
70
Q

Describe how to measure quality of node n in A* algorithm

A

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

71
Q

Describe:

A* algorithm

A

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

72
Q

Describe:

greedy best-first algorithm

A

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

73
Q

What are the other names for A* search when:

  • h=0
  • h=0 and g=0
A
  • greedy best-first search

- random search

74
Q

What are the reasons for using a search tree or search graph w/ A* algorithm

A

Search graph has to update g values for alternative paths so slower.
Search tree generates nodes faster but duplicates nodes which uses up memory.

75
Q

Define:

complete algorithm

A

Algorithm is complete if it returns a solution if one exists and no solution if no solution exists.

76
Q

Define:

optimal algorithm

A

Algorithm is optimal if it returns an optimal solution if one exists and reports that there is no optimal solution if none exists.

77
Q

Give 4 properties of h in the A* algorithm

A
  • 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
78
Q

Define:

h admissible in A*

A

h is admissible if it never overestimates the cost to reach the goal

79
Q

What are the conditions on h in A* for A* to find the minimal cost path to the goal

A

h admissible and a path with finite cost from start to goal exists

80
Q

Give 3 observations about A* wrt f(n) and f* and expanding nodes

A
  • A* expands all nodes w/ f(n) < f*
  • A* might expand nodes w/ f(n) = f*
  • A* never expands nodes w/ f(n) > f*
81
Q

Define:

- monotonic/consistent heuristic in A*

A

If along paths in search tree of A* the f-cost never decreases then the heuristic is monotonic

82
Q

Give necessary and sufficient condition for a heuristic f on A* to be monotonic

A

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

83
Q

Define:
path-max equation
- what is it used for?

A

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.

84
Q

State:

the monotonicity theorem for A* algorithm

A

If a monotonic heuristic h is used, when A* expands a node n then it has already found an optimal path to n

85
Q

Define:

more informed A* algorithm

A

A2* is more informed than A1* if h1 < h2 for all nodes that are not goal nodes

86
Q

State:

the informedness theorem for A* algorithm

A

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*

Heuristic Optimisation (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions