Search & Optimization

Every problem on this page is the same problem: a space of candidate solutions too large to enumerate, and a budget too small to try them all. The answers differ in what they are allowed to know. Blind search knows only the problem definition; heuristic search is handed a hint; genetic algorithms and swarms give up on systematic exploration entirely and let a population find the answer.

The pages

Classical search

• Search Strategies: The Setup - the five components of a search problem, and the four criteria a strategy is judged on.
• Uninformed Search - BFS, UCS, DFS, DLS, IDS, and the comparison table you will be asked to reproduce.
• Informed Search - heuristics, greedy best-first, and A*.

Genetic algorithms

• Introduction - what a GA is and why evolution is an optimiser.
• Terminology & Structure - gene, chromosome, population, generation.
• Representation & Encoding - binary, real, integer, permutation.
• Fitness & Selection - roulette wheel, rank, tournament, elitism.
• Genetic Operators - crossover and mutation, variant by variant.
• A Full Worked Example - one GA run, start to finish, by hand.
• GA on Decision Trees - evolving a tree instead of greedily growing one.
• Neuro-Genetic Systems - GAs that train neural networks.

Swarms

• Swarm Intelligence & PSO - particles with velocity, memory, and peer pressure.
• Cheat Sheet - the whole topic on one page.