Population-Based Search Flashcards
What is population based search?
A search conducted by maintaining a population.
What are the advantages of population search?
Search diversification and combination of promising traits in different candidate solutions
What is local beam search?
An adaptation of iterative best improvement by maintaining M assignments where M is a parameter.
1. Initialise size-M population randomly x1,…,xm
2. At every step, examine all successors of the current population and pick the top M successors that have the lowest cost.
3. Replace the population with M successors
How does local beam search compare to M random restarts?
For random restart, each search process runs independently of the others. In local beam search, useful information is passed among the parallel search threads. The random restart searches may concentrate on one search branch after a few steps.
What is stochastic beam search?
An alternative to local beam search by introducing randomness. Choosing the M successor using Boltzmann distribution
How do genetic algorithms work?
The following steps are repeated:
1. Reproduce a pool of individuals
2. Select some individuals with high fitness as winners
3. perform crossover and mutation between winners to generate new individuals
What is needed for genetic algorithms
- candidate solution representation
- Fitness function measures how desirable a candidate solution looks.
- Crossover operation.
How does crossover operation work?
Take two chromosomes s = s1s2…sk, t = t1t22…tk and crossing site 1 < c < k. The crossover operation returns s1…sctc+1…tk, t1…tcsc+1…sk
How does mutation operation work?
Take a chromosome s = s1s2…sk, themutation operation returns s1s2…sl, where si doesnt equal si with some small chance.
What is the pseudocode of a genetic algorithm?
Input: Search problem, crossover probability, mutation probability, population size.
Initialise population
Repeat:
1. Reproduction: preferentially selected from a mating pool
2. crossover breeding: Apply probability to either add a new copy of X and Y or perform crossover according to crossover probability.
3. Random mutation: randomly select a small portion of solutions and artificially change it.
do until population is stabilised.
What is evolutionary computation?
A computational problem solving technique inspired by the process of natural evolution. Artificial life refers to a field of research that focuses on creating and simulating lifelike behaviours, processes and systems using computer models and simulations.
