Search & Optimization: Cheat Sheet

Search parameters

≡FactsThe setup, in three lines

• b = branching factor, d = depth of the shallowest goal, m = maximum depth.
• Judge a strategy by completeness, time, space, optimality.
• Five components: states, start, goal, actions, cost, plus frontier, explored set and back pointers.

Uninformed search

	Frontier	Complete	Time	Space	Optimal
BFS	FIFO	yes	O(bᵈ)	O(bᵈ)	yes (uniform)
UCS	PQ on g	yes	O(b^(1+C*/ε))	same	yes
DFS	LIFO	no	O(bᵐ)	O(bm)	no
DLS	stack + ℓ	no	O(b^ℓ)	O(bℓ)	no
IDS	iterated DFS	yes	O(bᵈ)	O(bd)	yes (uniform)

Informed search

≡FactsBest-first, greedy, A*

• Best-first expands the lowest $f(n)$. The heuristic $h(n)$ estimates the cost to the goal, and $h(\text{goal}) = 0$.
• Greedy: $f = h$. Fast, not optimal, not complete.
• A*: $f = g + h$. Optimal and complete when $h$ is admissible (tree) or consistent (graph).
• Admissible = never overestimates. Consistent = $h(n) \le c(n,a,n') + h(n')$, the triangle inequality. Consistent implies admissible.

Genetic algorithms

≡FactsThe core

• A GA is a metaheuristic optimiser from natural selection (Holland). It uses only the objective function, no derivatives, and explores many points at once so it escapes local optima.
• Terms: population, chromosome (a solution), gene (a position), allele (a value), genotype (encoded), phenotype (real). Fitness measures suitability.
• Loop: init → fitness → selection → crossover ($p_c$) → mutation ($p_m$) → survivor selection → best.

#NumbersFormulas and the numbers that go in them

• Binary decode: $X = X^l + \frac{X^u - X^l}{2^n - 1} \times \text{decoded}$. With $n=4$, $X^l=4$, $X^u=25$, 1010 decodes to 10 and gives 18.
• String length: $S_l = \log_2\!\left(\frac{X^u - X^l}{p}\right)$.
• Prüfer code length is $n - 2$.
• Roulette example: $1089 < 1279 < 1311$ selects the 7th chromosome.
• The full worked example minimises $f(x) = x\sin(10\pi x) + 1$ over $[-1, 2]$ by directional crossover, $C_1 = P_1 + R(P_2 - P_1)$. Crossover rate 0.5 over 10 gives 5 crossovers; mutation rate 0.1 gives 1 mutation.

≡FactsRepresentations and operators

• Representations: binary, real, integer, permutation (TSP), random key, tree / Prüfer.
• Hypothesis encoding: one bit per value, 1 means allowed, 111 means don't care. (Outlook = Overcast ∨ Rain) ∧ (Wind = Strong) is 101 10.
• Selection: roulette wheel (proportional to fitness), tournament, rank, elitism (keep the best).
• Crossover: single, double, multi-point, uniform (p = 0.5), masking, matrix, order and position for permutations.
• Mutation: uniform, boundary, one's complement, inversion, insertion, heuristic. It escapes local optima and prevents premature convergence.

Neuro-genetic

≡FactsGA instead of backprop

• A GA replaces backpropagation for weight learning, because backprop hits local minima and is slow.
• A gene is five digits $d_1d_2d_3d_4d_5$: $d_1$ gives the sign (even is +, odd is −) and $d_2d_3d_4d_5 / 100$ is the magnitude. So 14345 is −43.45.
• A 2-3-1 net gives a chromosome of $(2+1) \cdot 3 \cdot 5 = 45$ digits.
• Fitness $F = 1/E$ where $E = \frac{1}{2}\sum (TO - O)^2$.

Swarm intelligence and PSO

≡FactsPSO in five lines

• PSO (Kennedy and Eberhart, 1995): particles fly through the space. No crossover, no mutation. Each has memory (pbest) and follows the swarm (gbest).
• $v^{t+1} = v^t + c_1 rand_1(pbest - x) + c_2 rand_2(gbest - x)$, then $x^{t+1} = x^t + v^{t+1}$.
• The three terms are momentum + cognitive + social.
• Velocity clamp $|v| \le V_{max}$; inertia weight $w$ goes large to small.
• Constriction $\varphi = 2 / |2 - \psi - \sqrt{\psi^2 - 4\psi}|$ with $\psi = c_1 + c_2 > 4$.