Module 4 Flashcards
What is a local search and it’s pros and cons
Operates by searching from start state to neighbouring states
Pros
- Uses less memory
- Can find reasonable solutions in large / infinite state spaces
Cons
- does not keep track of paths or set of reached states
- not systematic, may never explore a portion where solution exists
Can local search solve optimization problem
Yes, where objective function is utilized
What is hill climbing
When aim is to find highest peak/ global maximum
What is gradient descent
When aim is to find lowest valley / global minimum
Describe the hill climbing algorithm idea
- Start wherever
- move to neighbouring state
- if no neighbour better than current state then quit
- does not look beyond direct neighbours of current state
Local search complexities
State space - set of complete configurations
What is local maxima, ridge, shoulder and plateau
Local maxima - higher than neighbourhood , lower than global maxima
Ridge - sequence of local max , /\/\
Shoulder - flat neighbour’s then ascends
Plateau - No uphill or shoulder , flat
How to increase hill climbing efficiency
Increase sideways moves
What are sideways moves
When reaching plateau, restart search from another point. Moves can be limited but is also more expensive
Variations of hill climbing
Stochastic - chose randomly among uphill neighbours
First-choice - generate random successors until one is better
Random restart - conducts a series of hill climbing searches
Evolutionary - stores potential solutions and performs random mutations. Keeps mutations that are better states ( ancestor of GA )
What is simulated annealing
Minimizing algorithm Variation that Allows for bad moves according to temperature. Combines random walk with hill climbing
When are bad/good moves allowed in simulated annealing
High temp - more bad moves
How does simulated annealing expand
Change in energy
E > 0 - move to neighbour
E < 0 - move to neighbour with probability e ^ (-DE/T)
What is local beam search
K copies of local search are initialized
What does each iteration of local beam search do
Generates all successors from k current states and chooses the best k to be current state - searches communicate with each other - evolution hc
What is Genetic algorithm
Directed search algorithm based on biological evolution
What are the components of GA
- Encoding technique ( Gene / chromosome)
- Initialization procedure ( creation )
- Evaluation function ( environment )
- Selection of parents ( reproduction )
- Genetic operator ( mutation )
- Parameter settings ( practice )
Flow chart of GA
Population initialization -> fitness function -> crossover -> Mutation -> Survivor selection -> terminate + return best
Loops fitness - survivor until termination condition reached
What is a fitness calculation
Compromises of fitness function which takes solution candidate and measures the solution using fitness score
What is a selection process
Selects individuals to be parents
Select individuals with probably proptional to fitness score or randomly where (n>p) and select p most fit parents
What is GA crossover
Recombination procedure , combines different parts of parents to create offspring
- one with 1P1 and 2P2
- one with 2P1 and 1P2
What is mutation rate
How often offspring have random mutations
Every bit in offspring composition is flipped with probability = mutation rate
What is elitism
Make up of next generation
- could be offspring or elite parents
- guarantees overall fitness never decreases
What is culling
Removing parents below certain thresholds
What is a solution and evaluation function for games
Solution is strategy - evaluation function is evaluation goodness of game position.
What are the environment type for games
Fully observable , Multi agent , sequential, discrete
What is a game
Task env with more than 1 agent
List game axes
Determ or stochastic Fully observable Players Teams/indiv Turns/simul Zero sum
Which plan do algorithms help with in game search trees
Contingent plan / strategy
List different types of games
Standard, zero sum, general sum , team
List env types of standard games
Observable, deterministic, two player, turn taking, zero sum
List formulation of standard game
Initial state Players Actions Transition model -Results(s,a) Terminal test , true when game over Terminal value, utility for player
What is the search objective of standard games
Find sequence of players decisions maximizing utility / pay off
Also considers opponent moves/utility
List basic idea of zero sum games
Agents have opposite utilities , pure competition, one maximizes other minimizes
List basic idea of general sum games
Agents have independent utilities. Here cooperation, indifference, competition, shifting alliance is possible.
List basic idea of team games
Common pay off for players in a team
Key feature of zero sum
Gain or loss is exactly balanced through opponents. Adds to 0
How does minmax algorithm traverse and what does it assume
Back tracking algorithm with recursion using dfs
Assumes opponent will be rational and optimize, and all future moves are optimal
What if minmax doesn’t not play optimally
Opponent benefits further
What is minmax efficiency
Search O(b^m) Space O(bm)
What if more than one player / zero sum
Terminal nodes are tuples associated with tuple node. Each player maximizes their tuple.
What is alpha beta
Modified version of mini max , cuts depth to half. Utilizes alpha beta as thresholds.
Initial value of beta
Positive infinity , min changes
Initial value of alpha
Negative infinity, max can change
