Midterm grind Flashcards

Question 1

Q

In Game Playing Algorithms, what is the evaluation function f(n) (or utility value), where n is a board configuration measure?

Answer

A

The "goodness" of the board configuration n. This is the number of possible wins, which are not blocked by the opponent minus the number of possible wins for the opponent not blocked by the player: 
 f(n) = m(n) - o(n) 
 "m" is the possible winning states, "o" is the opponent's possible winning states

Question 2

Q

What is the open list at a particular state in a search algorithm

Answer

A

The set of nodes in the ready queue AFTER the node has been visited and expanded

Question 3

Q

Briefly describe DLS

Answer

A

Just like DFS but limits the search to a maximum depth parameter "l". Once the algorithm discovers nodes below depth "l", it does not expand them.

Question 4

Q

What is the process of "searching"

Answer

A

Moving from state-to-state in the problem space to find a goal (or to terminate)

Question 5

Q

Describe the Simulated Annealing Algorithm Step-by-step

Answer

A

Set Current Solution S₀,initial temperature T₀, and Select temperature reduction function

Repeat:

Repeat:

Select soliution S_ifrom the neighborhood N(S)

Calculate the change in cost according to the new solutionΔC

IfΔC < 0, then accept this solution (since it is improving) S=S_i

Else, generate a random number x in the range (0, 1)

if x < e^-ΔC/Tthen accept this new solution S=S_i

Until termination criterion met Decrease temperature T using reduction function

Question 6

Q

Give a reason to use 2 heuristics simultaneously in a searching algorithm

Answer

A

Use 1 heuristic as primary, and 1 as secondary to break ties

Question 7

Q

What does SA do to escape from local optimums?

Answer

A

Accepts non-improving solutions depending on what the temperature is

Question 8

Q

What is the motivation behind alpha-beta pruning?

Answer

A

In the game tree, some branches are never played since rational players don't pick sub-optimal moves. Therefore, there is no need to generate the subtree for such moves.

Question 9

Q

What is the difference between trajectory methods and population-based methods?

Answer

A

Trajectory methods handle one solution at a time, whereas Population methods handles multiple solutions at a time

Question 10

Q

Under what conditions does UCS become Dijkstra's single-source shortest path algorithm?

Answer

A

if g(n) is the overall cost function for all nodes to a source node

Question 11

Q

What are Meta-Heuristic algorithms

Answer

A

Meta-Heuristics are algorithms that combine heuristics in a higher level framework aimed at efficiently and effectively exploring the search space.
 
 They are strategies that "guide" the search process

Question 12

Q

Are Meta-Heuristics problem specific? are they at risk of getting trapped in confined areas of the search space?

Answer

A

Meta-Heuristics are not problem-specific
 
 They utilize mechanisms (depending on the method) to avoid getting trapped in dead ends

Question 13

Q

Describe the difference between "A Search" and "A* Search"

Answer

A

"A*" is admissible, in which h(n) <= h*(n). Whereas "A" is not admissible, h(n) has no upper bound in the A algorithm.

Question 14

Q

Is DLS complete?
Does DLS always terminate?
Is DLS optimal?

Answer

A

As long as the solution is within the depth "d", then it is guaranteed to be complete since there is a limit on the depth that it can search to.
 
 DLS always terminates, and it is not optimal

Question 15

Q

How does the min/max algorithm relate to game playing

Answer

A

The game tree alternates between the 2 opponent's moves, and the min/max algorithm can be used to optimize for the best outcome in this game tree.

Question 16

Q

What are search trees, and how are they abstracted from graphs.

Answer

A

Search trees are superimposed over top of graph representation of a problem. The graph might be finite, but the search tree can be either finite or infinite. infinite if we allow for repeated states due to reversible actions or cycles.

Question 17

Q

What do Heuristics Aim to do?

Answer

A

Heuristics aim to efficiently generate good solutions, but does not guarantee optimality.

They guide the algorithm

Question 18

Q

What are the 2 general optimization methods in searching algorithms?

Answer

A

Constructive methods: starting from scratch and getting to the solution one component at a time. Ex: Sudoku solver, N-Queens
 Local Search Methods: Starts from an initial solution and iteratively tries to replace the current solution with better solution Ex: TSP

Question 19

Q

What does a heuristic function do?

Answer

A

Heuristic functions give an estimate of the distance to the goal based on domain-specific information. It guides the algorithm to a better solution by estimating the "goodness" of a node/state.

Question 20

Q

Under what condition is A* complete?

Answer

A

A* is complete if the branching factor is finite, and every operator (evaluation function) has a fixed positive cost

Question 21

Q

What is the difference between well-structured problems and ill-structured problems

Answer

A

Well Structured: The existing state and desired state are clearly identified, and the methods to reach the desired state are fairly obvious
 
 Ill Structured: Existing state is and desired state are unclear and hence the methods of reaching the desired state cannot be found.

Question 22

Q

What is the purpose of the minimax or min/max algorithm

Answer

A

To determine the best next move and the cost of such move

Question 23

Q

What does "admissible" mean with respect to heuristics?

Answer

A

A heuristic is said to be "admissible" if it NEVER overestimates the distance to the goal node.
 
 It is also known as an "optimistic" heuristic

Question 24

Q

List the 5 types of informed search algorithms

Answer

A

Hill Climbing Search
Greedy Best-first Search
Beam Search
A Search
A* Search

Question 25

Q

Under what condition does A* act like UCS?

Answer

A

When h(n) = 0 for all n. This is the null heuristic.

Question 26

Q

What is a rational agent

Answer

A

An agent that for each perceived sequence of events, it does what is expected to maximize performance on the basis of perceptual history and built-in knowledge

Question 27

Q

Describe Fully observable vs Partially observable environments

Answer

A

Fully Observable environment: sensors detect all aspects that are relevant to the action
 Partially Observable environment: Lots of noise and inaccurate sensors due to parts of state missing

Question 28

Q

What does Behaving rationally mean?

Answer

A

Perceiving the “world” and acting to achieve
 some goals given a set of beliefs.

Question 29

Q

Agents work within an environment with certain characteristics. What are these 6 characteristics/dimensions?

Answer

A

Fully Observable vs Partially Observable
<br>Deterministic vs Stochastic
<br>Episodic vs Sequential
<br>Static vs Dynamic
<br>Discrete vs Continuous
<br>Competitive vs Co-operative

Question 30

Q

Briefly describe UCS

Answer

A

Expand the node with the lowest cost in the fringe, use a heap/sorted list, always take the min-cost node. If there are numerous nodes with the same cost, take the most recently added one.
 
 Always finds the minimum-cost path to the goal node.

Question 31

Q

What is the branching factor in a search Tree?

Answer

A

The maximum number of children possible for a node. Denoted with "b"

Question 32

Q

There are 2 types of Games:
 
 Perfect information & Imperfect information
 
 Describe and Contrast them

Answer

A

Perfect information:
 Each player has complete information about the opponent's position and available choices (ex: chess, monopoly)
 
 Imperfect information:
 Each player does NOT have complete information about the opponent's position and available choices (ex: poker)

Question 33

Q

In Simulated Annealing, what is the cost function

Answer

A

The quantity which is trying to be minimized as much as possible. It is a function of the current state

Question 34

Q

What is the purpose of using memory structure in trajectory methods?

Answer

A

To escape local minima
 
 To improve explorative strategy by avoiding visited nodes

Question 35

Q

Describe the "Problem Formulation" of Game Playing as Search

Answer

A

State Description: the configuration of the board
 
 Initial State: initial board position & who's move it is
 
 Operators/Action State: the legal moves that a player can make
 
 Goal: is the game over?
 
 Utility Function: Measures an outcome of the game and its desirability

Question 36

Q

What are the 2 categories of engineering problems in terms of the structure of the problem

Answer

A

Well-Structured Problems & Ill-Structured Problems

Question 37

Q

Does SA find an approximation or exact value? What size search space does it work well in?

Answer

A

SA works very well in large search spaces, and provides a good approximation

Question 38

Q

Briefly describe BFS

Answer

A

traverse layer-by-layer, use a FIFO structure (queue) as the fringe.
 
 Always finds the closest path, but takes long.

Question 39

Q

What is cooperation

Answer

A

A group to solve a join problem or perform a common task, based on sharing the responsibility for reaching a goal.
 
 OR
 
 Cooperation is the practice of software/hardware entities working together in order to achieve certain objective

Question 40

Q

Alpha-Beta Pruning is an optimization of the minimax searching algorithm.
 
 What are the tradeoffs? does it affect the completeness of minimax?

Answer

A

Alpha-Beta is guaranteed to return exactly the same value as the min/max algorithm.
 
 It is a pure optimization of min/max without any tradeoffs. It does not affect the completeness, but reduces the number of computations

Question 41

Q

What are the 4 properties of search algorithms?

Answer

A

Completeness:
Whether or not the algorithm is guaranteed to find a goal node (if it exists).

Optimality:
Is the algorithm guaranteed to find the BEST goal node - with the cheapest cost.

Time Complexity:
How many nodes are expanded?

Space Complexity:
What is the maximum number of nodes stored in memory?

Question 42

Q

Are meta-heuristics exhaustive?

Answer

A

Meta-Heuristics are non-exhaustive, and they use their own internal heuristic

Question 43

Q

What are strong vs weak methods?

Answer

A

Strong methods are those designed to address a specific type of problem.
 
 Weak methods are general approaches that may be applied to many types of problems. Weak methods are extremely general and not tailored to a specific situation. They are called "weak" because they do not take advantage of more powerful domain-specific heuristics.

Question 44

Q

Suppose “h” us a heuristic function.
What does can you say about the current state if:
1. h(n) = 0
2. h(n) = infinity

Answer

A

h(n)=0 means that the state is a goal node. h(n) = infinity means that the state "n" is a dead-end that can never lead to a goal

Question 45

Q

Is Greedy Best-first search Complete? is it Optimal?

Answer

A

No and No, it purely depends on the heuristic that it uses

Question 46

Q

What happens to the expanded nodes in A* search if h(n) is too high or too low?

Answer

A

h(n) too high: Optimal solution will be overlooked (non admissible heuristic)
 
 h(n) too low: More nodes than needed are expanded

Question 47

Q

Compare Hill Climbing Search to Beam Search

Answer

A

Hill Climbing search is equivalent to Beam search with ß=1. Beam is like the middle ground between Hill Climbing and Greedy Best First Search

Question 48

Q

At what point do you prune in minimax alpha beta pruning

Answer

A

If there is an alpha/beta value assigned to a parent node, and ANY grandchild node is below/above the cutoff, then you prune the other grandchildren

Question 49

Q

Under what condition does A* perform like a perfect algorithm, only expanding the nodes which lead to the solution?

Answer

A

When h(n) = h*(n) for all n. This means that h(n) = actual cost to goal node. In this case, the heuristic gives a perfect distance to the solution for all nodes

Question 50

Q

Under what circumstances is DFS incomplete? is DFS optimal?

Answer

A

spaces with loops, or infinite-depth spaces.
 
 DFS is not optimal for finding the shortest path

Question 51

Q

What is the strategy for solving ill-structured problems?

Answer

A

Retrieve a solution/answer, Start from a guess, and improve it. Search among alternatives. Exploring surrounding states.

Question 52

Q

in SA, what is the acceptance probability?

Answer

A

if delta C <= 0: P = 1
 
 if delta C > 0: P = exp(-1*delta C / T)

Question 53

Q

What is Greedy Best-First search?

Answer

A

A searching algorithm in which the next state is picked using the evaluation function f(n)=h(n). The fringe is a priority queue (heap or self-sorted list).

Question 54

Q

What does the min/max algorithm assume for the opposing player’s strategy?

Answer

A

Assumes the opponent is rational and optimizes their behaviour & considers their best response/move

Question 55

Q

Is the min/max search complete? is it optimal?
 
 If so, under what conditions

Answer

A

It is complete if the tree is finite,
 
 it is optimal assuming that the opponent plays rationally & optimally

Question 56

Q

What do α and β parameters denote in alpha-beta pruning?
 
 Why do these matter?

Answer

A

α: the best value for MAX seen so far. This is the lower bound on the value that a MAX node can be assigned.
 
 β: the best value for MIN seen so far. This is the upper bound on the value that a MIN node can be assigned.
 
 We use these values to prune cousin nodes and assign cutoff values

Question 57

Q

What is Beam Search

Answer

A

A greedy best-first search variant which tries to minimize the amount of memory which greedy best-first search uses by only storing ß nodes in the fringe, and using a heuristic. Evaluation function is f(n) = h(n), and the algorithm will not add new nodes to the fringe if it is full.

Question 58

Q

Briefly describe IDS

Answer

A

Iteratively increases the limit of the search. Algorithm performs DLS for d=0, if no solution is found, it increases d=1 and restarts the DLS. If no solution is found it increases again to d=2 and restarts. It keeps on iteratively increasing the maximum depth and restarting the DLS until a solution is found

Question 59

Q

Is Beam search Optimal? is it Complete?

Answer

A

No and No, it purely depends on the heuristic that it uses

Question 60

Q

What are the 3 variations of Hill Climbing Search? Describe them

Answer

A

Stochastic Hill Climbing:
Random Selection among the uphill moves

First-Choice Hill Climbing:
Keeps generating successors until a better one is found & takes it (good when there are many successors)

Random-Restart hill climbing:
Tries to avoid getting stuck in local maxima

Question 61

Q

Why do we limit the depth in expanding the game tree for min/max search?

Answer

A

Typically, the number of states (board configurations) is too large, leading to an unreasonable depth in the game tree. We optimize this by limiting the depth of the game tree in the traversal.

Question 62

Q

Describe the step-by-step process of using the min/max algorithm

Answer

A

Generate the game tree (alternating max & min) 
 
 Apply the utility function to all leaf nodes to give them their utility values 
 
 From bottom to top; use the leaf nodes’ utility values to determine the utility values of their parents. Repeat this until you get to the root node. 
 
 Pick the most optimal move from the root node

Question 63

Q

Describe Hill-Climbing Search

Answer

A

For all successors, it strictly only picks a state which has a lower heuristic value (not even equal), and lower than all the other neighbouring states' heuristic value. It picks this state and ignores all other options.
 
 Hill-Climbing search strictly looks just 1 step ahead to determine if a successor is better than the current state, and moves to the best successor. Very memory efficient.
 
 It is like climbing a mountain with a thick fog around you

Question 64

Q

In SA, what happens when a neighbouring state has higher cost?

Answer

A

A random number is generated between 0 and 1. If P is greater than this random number, it is accepted. In this case P = exp(-1*delta C / T)
 
 Note that in this case, the probability of accepting depends on the magnitude of change in cost, and the temperature

Answer 65

A

Problems which have well-defined rules with moves that can be searched intelligently

Answer 66

A

The ability to improve behaviour, evolve, adjust to new or different situations

Answer 67

A

No zero-cost edges or negative-cost edges

Answer 68

A

We decide which aspects we are interested in, and which aspects can be ignored.
 
 We need goals to limit search and allow termination.

Answer 69

A

Exact Algorithms and Approximate Algorithms

Answer 70

A

The Science and Engineering of making intelligent machines, especially intelligent computer programs. Examples: Visual perception, speech recognition, decision making, language translation

Answer 71

A

MAX: label node will take the maximum value of its children
 
 MIN: label node will take the minimum node of its children

Answer 72

A

A State Space
Initial State
Goal State, and Goal Test
Set of Actions
Concept of Cost

Answer 73

A

IDS is complete if “b” (branching factor) is finite.

The drawback is that nodes on levels above “d” are generated multiple times

Answer 74

A

Expand nodes in pre-order fashion (root -> left -> right), use a LIFO data structure for the fringe (stack)

Answer 75

A

when the costs of all edges in the search space are equal. g(n) is constant

Answer 76

A

They use either g[n] (distance to goal), or h[n] (heuristic value), or both to evaluate the next move in their evaluation function f[n] = g[n] + h[n], or f[n] = h[n], or f[n] = g[n]

Ex: UCS, Hill-Climbing, A*, Best-First

Answer 77

A

It is always accepted

Answer 78

A

Heuristics are solution strategies or rules by trial and error to produce acceptable (optimal or suboptimal) solutions to complex problems in a reasonable amount of time.

Answer 79

A

A way to reduce the number of nodes that need to be generated and evaluated by pruning.
 
 Avoid processing subtrees that have no effect on the result

Answer 80

A

The ability to acquire and apply knowledge and skills

Answer 81

A

Meta-Heuristics find approximate solutions, and are non-deterministic
 
 The goal with Meta-Heuristics is to efficiently explore the search space in order to find near-optimal solutions

Answer 82

A

If the environment can change while the agent is deliberating, then it is dynamic. Otherwise, it is static

Answer 83

A

If h(n) is infinite, then the algorithm will be stuck in a dead end, and will not be able to find a goal node, making it an incomplete algorithm

Answer 84

A

State is describable in a discrete way, or in a continuous way

Answer 85

A

Uninformed search strategies have no heuristics, and no information about the likely direction of the goal node.
 
 Informed search strategies have a sense of direction, and use heuristics to guide them on their path.

Answer 86

A

State Space: Either a complete configuration of a problem, or a partial configuration of a problem.
 Initial State: The search starts here
 Goal State, and Goal Test: the Search terminates here.
 Set of Actions: This allows movement between states (successor function)
 Concept of Cost: Allows to create a costing solution

Answer 87

A

Assigns a player/state a number denoting the outcome of the game and its desirability

Answer 88

A

Hill Climbing Search does not allow for backtracking, whereas Greedy Best-First Search does, and it jumps to alternative paths & stores the children of previously visited nodes.

Answer 89

A

sqrt (n) where n is the number of states

Answer 90

A

Using logic to achieve goals via logical inferencing

Answer 91

A

The utility of being in the corresponding state, assuming that both players play optimally from that state till the end of the game

Answer 92

A

An iterative generation process which guides a subordinate heuristic by combining intelligently different concepts for exploring and exploiting the search space, learning strategies used to structure information in order to efficiently find near-optimal solutions

Answer 93

A

Probability of accepting a state is directly proportional to temperature.

At high temperatures, explore parameter space, At lower temperatures, restrict exploration.

Answer 94

A

if h(n) < h*(n), then it is admissible. A* is always admissible.
 
 Using an admissible heuristic guarantees that the first solution will be an optimal one

Answer 95

A

Physical annealing. If a liquid material cools and anneals too quickly, then it will solidify into a sub-optimal configuration. If the metal cools slowly, then the crystals within the material will solidify optimally.

Answer 96

A

If the next state of the environment is completely determined by the current state, and the action is executed by the agent, then it is deterministic. Otherwise, it is Stochastic

Answer 97

A

Trajectory methods, and Population-based methods

Answer 98

A

Depth-First Search
 Breadth-First Search
 Uniform-Cost Search
 Depth-Limiting Search
 Iterative-Deepening Search

Answer 99

A

Root node is always MAX (maximizes) player's utility value, and nodes alternate between MIN and MAX layer by layer

Answer 100

A

Rational Systems

Answer 101

A

Depth-First:
 - Low memory requirements
 - Can get stuck exploring infinite paths
 - Better if there are many solutions and you only need one of them
 
 Breadth-First:
 - Uses high amount of memory
 - Doesn't get stuck
 - Finds the shortest path always

Answer 102

A

A2* will expand less nodes, and hence take less time to find the solution than A1*. The closer a heuristic is to h*(n), the better its performance.
 
 The fewer nodes expanded, the better the heuristic

Answer 103

A

Use a data structure to store nodes in a fringe. This will depend on the algorithm/strategy.
 
 Repetitively Choose a node from the list, test it, then expand its children.
 
 A particular search strategy will influence how we choose the next node to consider in the search (depending on what algorithm we're using)

Answer 104

A

In Episodic environments, the choice of action in each state depends only on the state itself.
 
 In Sequential environments, the current decision could affect all future decisions - the agent needs to think ahead. Ex: chess

Answer 105

A

1. The current Temperature

2. The cost difference between the current and next state. This is next cost minus current cost

Answer 106

A

Tabu Tenure is the length of time (number of iterations) for which a move is forbidden.

If tabu tenure is too small, it poses a risk of cycling in the algorithm. If tabu tenure is too large, it may restrict the search too much.

Rule of thumb: Tabu Tenure = sqrt(n)

Answer 107

A

Tabus may sometimes be too powerful: they may prohibit attractive moves, even when there is no danger of cycling, or they may lead to an overall stagnation of the searching process.

It may, therefore, become necessary to revoke tabus at times. Typically if a move results in a solution with an objective value better than that of the current best-‐known solution, then it meets the aspiration criteria

Answer 108

A

No, the temperature will not have aneffect on the acceptance of the neighbouring state if delta C is negative. It will always be accepted in that case

Answer 109

A

The initial temperature

The final temperature
 
 The temperature decrement rule
 
 The number of iterations at each temperature

Answer 110

A

It must be high enough to allow a move to possibly any state in the search space. Must not be too hot since SA would behave like a random number generator in that case. A good initial temperature is one that accepts 60% of worse moves

The Maximum change in the cost function could be used as a guide to set the value of initial temperature

Answer 111

A

No. It might take a very long time to reach zero when some decrement approaches are used

Answer 112

A

- Whenever the temperature is reasonably low
 
 - The system is frozen, and there are no better moves generated, and worse moves are not getting accepted
 
 - Number of iterations reaches a threshold (maybe)

Answer 113

A

Linear: T = T-a
 
 Geometric: T=T*a
 
 Slow Decrease:
 T = T/(1+bT)
 
 a, and b are constants

Answer 114

A

Enough iterations should be allowed at every temperature for the system to be stable at that temperature.

Answer 115

A

SA converges when temperature is reduced to zero slowly enough. It can be likened to a Markov chain but non-homogeneous

Answer 116

A

Pros:
 - Easy to use
 - Provides good solutions for a wide range of problems
 
 Cons:
 - Takes a long time to run
 - There are a lot of tuneable parameters

Answer 117

A

The Cost function / fitness function (which is what the algorithm is trying to minimize)

Answer 118

A

Hill Climbing search

Answer 119

A

If temperature is reduced too fast, then optima are not found
 
 If temperature is reduced too slow, then time is wasted

Answer 120

A

An algorithm is adaptive if its parameters change as it traverses as a result of the feedback from the environment. SA can be made adaptive by making the temperature change change depending on the feedback from the environment.

These parameters are initial temperature, the cooling schedule, and the number of iterations per temperature.

Answer 121

A

Cost functions which return the same value for many different states

Answer 122

A

They can be represented in the cost function as "penalty terms"
 
 SA can be made more adaptive by having dynamically changing weights of the penalty terms

Answer 123

A

Cooperative SA implements synchronous concurrent runs of numerous SA processes.
 
 Cooperative SA manipulates multiple solutions (a population of solutions) at once.
 
 Instead of singular states, Cooperative SA uses a population of states as its nodes.

Answer 124

A

New solutions are iteratively produced from 2 randomly selected states in the population S1 and S2:
 The algorithm looks for neighbours of S1 that are closer to S2 than S1 itself.
 the CLOSER set is generated, and the next solution is randomly selected from it

Note that sometimes it is 2 solutions, sometimes it is more, this depends on the algorithm. They can even pick the best out of all the solutions

Answer 125

A

CLOSER set is all the members S_k of S1's neighbours such that the distance between S_k and S_4 is less than the distance between S_k and S1.
 
 S1 and S4 are members of the current population in the algorithm in Cooperative SA
 
 If the CLOSER set is not empty, then the next solution is randomly selected from it

Answer 126

A

Temperature is updated based on the difference of mean cost value of the new and old populations

If the mean in cost difference between current and previous populations is less than zero, then it doesn’t get updated. Otherwise, it is changed

Answer 127

A

Population size must be initialized to POP₀

For a determined number of transitions K

For i=1 to POP

Select a random cooperator S_jis a member of POP_k_-1

Generate Snew=cotrans(S_i,S_j)

Accept the new solution if it is better

Otherwise, probabilistically determine if a move to be taken to the new solution and update solution accordingly

Update Temperature

Answer 128

A

Tabu Search is a meta-heuristic, a general strategy for guiding and controlling inner heuristics.
 
 It is like a combination of local search strategy and memory structures

Answer 129

A

- To escape local minima
 - To implement an explorative strategy & avoid revisiting nodes

Answer 130

A

It is very computationally demanding to process all possible neighbours.

Answer 131

A

In order to escape from local optima where all the neighbouring solutions are non-improving (dead end)

Answer 132

A

Classifies a subset of moves in the neighbourhood which are not permitted (tabu)

Answer 133

A

- Short term memory which is based on recency of occurrence of a component. This is used to prevent the search from revisiting previously visited solutions
 
 - Long term memory which is based on frequency of occurrence. This is used to diversity the search and explore unvisited areas of the solution space by avoiding frequently visited components

Answer 134

A

The Tabu List.

Recent moves which were used on current solutions are added to the Tabu list. It is used to prevent reverse moves, and promote exploration.

Answer 135

A

Tabu Tenure is the number of iterations in which a certain move and its attributes are stored in the tabu list.
 
 Recent states/components are "tabu-active" during their tabu-tenure

Answer 136

A

To identify adjacent solutions/states that can be reached from the current solution/states

Answer 137

A

- No feasible solution in the neighbourhood of current solution

- Reached the maximum number of iterations allowed
- The number of iterations since the last improvement is larger than a threshold

Answer 138

A

Sometimes it is useful to allow certain moves despite being Tabu - which prevents stagnation.

Answer 139

A

Aspiration Criteria

Answer 140

A

Firstly, generate an initial solution.
 
 While the termination criterion are not met {
 - Chose the best neighbour "s_next" from N(s) = N(s) - T(s) + A(s)
 - Store s_next in A(s) if it improves the best known solution
 - Update T(s) and A(s)
 }

Answer 141

A

Tabu Solutions are excluded from N(s) and not revisited during the tabu tenure.
 
 They are added back if:
 1. The aspiration conditions are met
 2. The tabu tenure is finished (number of iterations in tabu tenure is completed)

Answer 142

A

Improved-best or best solution: If a tabu solution encountered at the current iteration is better than the best solution found so far, then it can be added to the aspiration list

Answer 143

A

- A move that involves the same exchange of positions of a tabu move
 
 - A move that involves any of the positions that were involved in a tabu move

Answer 144

A

Static: choose T to be a constant of as a guideline of the problem size
 
 Dynamic: choose T to vary randomly between some T_min and T_max

Answer 145

A

Fixed length tabu list cannot always prevent cycling

Answer 146

A

A tabu move becomes admissible if it yields a solution that is better than any obtained solution so far (or better than the aspiration value)

Answer 147

A

The process of exploiting a small portion of the search space, and penalizing solutions that are far from the current solution

Answer 148

A

Forcing the search into previously unexplored areas of the search space and penalizing solutions that are close to the current

Answer 149

A

Long-term memory, then frequency memory

Answer 150

A

Restart diversification: Finds components that rarely appear in the solution & restarts the search from these points
 
 Continuous Diversification: Bias the evaluation of possible moves by adding a term which depends on the neighbour's frequency to the evaluation function

Answer 151

A

Pros:
 - Accepts non-improving solutions in order to escape from local optima
 - Uses a Tabu List
 - Can be applied to both discrete and continuous problem spaces
 - For larger and more difficult problems (ex: scheduling), tabu search is very efficient
 
 Cons:
 - Too many parameters to be determined
 - Number of iterations is large
 - Global optimum might not be found, and it depends on the parameter settings

Answer 152

A

Involves the assignment of n objects to n sites. For each assignment, there is a related cost C(i,j) of assignment object "i" to site "j"
 
 There are n! distinct combinations of the solution space

Answer 153

A

Assignment of offices or services in buildings
 
 Assignment of departure gates to an airport
 
 Distribution of files in a database

Answer 154

A

If the length is too small, the search can be trapped into cycles

If the length is too large, then too many moves could be prevented at each iteration

Answer 155

A

Allow the length of the short term memory (tabu list) to vary dynamically

Answer 156

A

Restricting the length of the tabu list to be between L_min and L_max.

In the event that the current solution is better than the best-so-far, then the tabu list length is set to 1

If the move is an improvement, then tabu list length is decreased by 1

If the move is not improving, then the tabu list length is increased by 1

Answer 157

A

The idea is to increase and decrease the tabu list length dynamically in order to draw the solution away from bad regions and towards good regions

Answer 158

A

Set up P independent Tabu Searches working concurrently, and exchanging information as they go

Answer 159

A

A central memory is used to handle the information exchange. Each search process sends its best-so-far solution to the central memory when it gets updated.

The central memory can also have its own limits on size & tenure

The concurrent processes can use the best solution in the central memory as aspiration condition

Answer 160

A

Quickly: the algorithm may result in a suboptimal solution

Slowly: the algorithm will search for much longer and might waste time on a temperature

Answer 161

A

It increased the computational intensity because of the increased message passing overhead

Answer 162

A

Abundant memory space to store the search tree is available
A shallow solution is preferred

Answer 163

A

No. They find accurate approximations

Answer 164

A

When we have a tree with a fixed depth, and the solution is at the leaf of the tree & we want to find ANY solution, not caring about the minimum depth

Answer 165

A

Whenever the cost of finding an exact solution is extremely high.

Answer 166

A

State Space
Initial State
Goal State
Set of Actions
Cost

Answer 167

A

BFS: Yes, if tree is finite
UCS: Yes, if tree is finite
DFS: Yes, if tree is finite
DLS: Yes, if l >= d
IDS: Yes, if tree is finite

Answer 168

A

BFS: Yes, if costs are all constant
UCS: Yes
DFS: No
DLS: No
IDS: Yes, if costs are all constant

Answer 169

A

BFS: b^d
UCS: b^d if costs are the same
DFS: b^m
DLS: b^l
IDS: b^d

Answer 170

A

BFS: b^d
UCS: b^d if costs are the same
DFS: b*m
DLS: b*l
IDS: b*d

Answer 171

A

GBFS: No - it can get stuck in loops
BS: No
HCS: No

Answer 172

A

GBFS: No
BS: No
HCS: No

Optimality will purely depend on the quality of the heuristic

Answer 173

A

GBFS: b^m, but a good heuristic can give a dramatic improvement
BS: ß*m
HCS: d

Answer 174

A

GBFS: b^m, keeps all nodes in memory
BS: ß*m
HCS: 1, there is no memory structure involved

Brainscape's Knowledge GenomeTM

Midterm grind Flashcards

Brainscape's Knowledge Genome^TM