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
