Heuristic Search & Genetic Algorithms

• Heuristic (Guided) Search: uses a problem-specific estimate function to guide search toward the goal faster than blind/exhaustive search (e.g., A* search using a heuristic distance estimate)
• Genetic Algorithms: optimization technique inspired by natural selection — maintains a population of candidate solutions, applies selection, crossover, and mutation across generations to evolve better solutions; useful for large/complex search spaces where exact methods are infeasible

📌 Sample & Repeated FPSC Questions (2016–2026)

📝 Heuristics for NP-Hard Problems

2020, Paper I, Q8(d) (4 marks) — Optimal problems are generally NP-hard problems. Is it appropriate to use heuristic-based approaches?

Yes — and in practice, usually necessary. Exact algorithms for NP-hard optimization problems require (conjectured) exponential worst-case time, making them infeasible at realistic scale. Heuristic/approximation approaches (greedy algorithms, local search, simulated annealing, genetic algorithms, branch-and-bound with pruning) trade the guarantee of a provably optimal solution for a "good enough" one found in acceptable (typically polynomial) time. For most real applications — route planning, scheduling, network design — a fast near-optimal answer beats a perfect one that takes longer than is practical to compute.

📝 A* and the Informed Search Family

2018, Paper I, Q6(b) (6 marks) — What is informed or heuristic search? What type of algorithm is used to do such a search?

Informed (heuristic) search uses a problem-specific heuristic function h(n) — an estimate of the cost from node n to the goal — to guide search more efficiently than blind/uninformed methods (BFS/DFS).

• Greedy Best-First Search: always expands the node that looks closest to the goal by h(n) alone — fast, but not guaranteed optimal.
• A Search:* the canonical informed-search algorithm; expands nodes by f(n) = g(n) + h(n), where g(n) is the actual cost so far and h(n) the estimated remaining cost. A is guaranteed optimal if h(n) is admissible* (never overestimates the true cost).
• Hill Climbing: always moves to the best neighbouring state by heuristic value, but can get stuck in local optima.

MCQ Trap: A needs an admissible heuristic to guarantee optimality — an inadmissible (overestimating) heuristic can make A return a suboptimal solution, even though it still terminates.

📝 Genetic Algorithms — What They're Good For

2018, Paper I, Q6(d) (5 marks) — Explain what type of problems can be solved by genetic algorithms.

GAs are population-based optimization/search algorithms inspired by natural selection — a population of candidate "chromosomes" evolves via selection, crossover, and mutation, guided by a fitness function. Best suited to:

• Large, complex search spaces where exhaustive/exact search is infeasible.
• Non-linear, multi-modal (many local optima) optimization problems.
• Problems where an approximate solution is acceptable and there's no clean gradient-based method (non-differentiable/discontinuous objectives).

Typical examples: combinatorial optimization (TSP, job-shop scheduling, timetabling, bin packing), engineering design optimization, neuroevolution/feature selection, and game-strategy or control-policy evolution.

📝 Genetic Algorithms — Their Limitations

2019, Paper I, Q6(a) (10 marks) — Discuss the limitations of genetic algorithms.

• Computationally expensive: many generations, each evaluating a whole population's fitness.
• No global-optimum guarantee: premature convergence to a local optimum if diversity is lost early.
• Parameter-sensitive: population size, crossover/mutation rate, and selection strategy strongly affect results and need per-problem tuning.
• Encoding difficulty: a poor chromosome representation can make the search space hard to explore.
• Outperformed on smooth/simple spaces: gradient-based methods converge faster and more reliably when the objective function is well-behaved and differentiable.
• No strong theoretical convergence guarantees, and results vary run-to-run due to stochastic behaviour.

Exam angle: Pair this with the "what problems can GAs solve" question above — examiners like asking both the strengths (large/complex/non-differentiable search spaces) and the weaknesses (no optimality guarantee, tuning overhead) of the same technique in the same paper.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2018 · Paper-I · Q6(b) · 6 marks

Q. What is informed or heuristic search? What type of algorithm is used to do such a search?

Ans.

• Informed (heuristic) search uses problem-specific knowledge, a heuristic function h(n) that estimates the cost from node n to the goal, to decide which node to expand next. This avoids blind exploration and is much faster than uninformed search (BFS, DFS).
• Algorithms:
  • Greedy best-first search: expands the node with the smallest h(n).
  • A search:* expands the node with the smallest f(n) = g(n) + h(n), where g is the cost so far. It is optimal if h never overestimates (admissible).
  • Hill climbing, beam search, simulated annealing, IDA.*
• Example: finding a route on a map using straight-line distance to the destination as h(n).

2018 · Paper-I · Q6(d) · 5 marks

Q. Explain what type of problems can be solved by genetic algorithms.

Ans.

• Genetic algorithms (GA) search for good solutions by imitating evolution: a population of candidate solutions is improved by selection, crossover and mutation, guided by a fitness function.
• Suitable problems:
  • optimisation with huge search spaces: travelling salesman, scheduling, timetabling, routing
  • design problems (circuit and structure design)
  • machine learning tasks: feature selection, tuning neural-network parameters
  • problems with no mathematical formula or gradient, only a way to score a solution

2019 · Paper-I · Q6(a) · 10 marks

Q. Discuss the limitations of genetic algorithms.

Ans.

• No guarantee of the optimum: the result is only a good solution.
• Premature convergence: the population may become similar and get stuck in a local optimum.
• Parameter tuning: population size, crossover and mutation rates, and selection method strongly affect results and must be tuned by trial.
• Expensive fitness evaluation: thousands of evaluations are needed, which is slow for complex simulations.
• Representation difficulty: the problem must be encoded as chromosomes, and a poor encoding gives poor results.
• Randomness: results vary from run to run and are hard to reproduce.
• Inefficient on simple problems: where gradients or exact algorithms exist, they are faster and more accurate.
• Constraint handling is awkward, and invalid offspring have to be repaired or penalised.

2020 · Paper-I · Q8(d) · 4 marks

Q. Optimal problems are generally NP-hard. Is it appropriate to use heuristic-based approaches?

Ans.

• Yes. For NP-hard problems, exact algorithms take exponential time and become impractical for large inputs.
• Heuristics (greedy rules, local search, simulated annealing, genetic algorithms) give good solutions quickly, although without a guarantee of optimality.
• Approximation algorithms are better when available, because they guarantee a bound on how far the answer is from optimal.
• Use exact methods only for small inputs or when optimality is essential.