Answer Key
- A Genetic Algorithm (GA) is a search-based optimization technique based on the principles of Genetics and Natural Selection. It is a subset of the larger field of Evolutionary Computation and was developed by John Holland and his colleagues.
- A fitness function takes a candidate solution as input and produces an output that measures how “fit” or “good” that solution is for the problem. It is calculated repeatedly to evaluate individuals, and its speed is crucial for the GA’s overall performance.
- Premature convergence occurs when one extremely fit solution takes over the entire population in a few generations, leading to a loss of diversity. This is undesirable because it can cause the GA to get stuck at a local optimum without exploring the full solution space.
- In a Generational model, a new set of n offspring is generated, where n is the population size, and this new population entirely replaces the old one at the end of an iteration. In a Steady State (or Incremental) model, only one or two offspring are generated in each iteration, and they replace one or two individuals from the existing population.
- NP-Hard problems can take even the most powerful computing systems a very long time to solve. GAs are useful because they can provide usable, near-optimal solutions in a much shorter amount of time, making them an efficient tool for these “difficult problems.”
- The mutation operator introduces a small, random tweak in a chromosome to get a new solution, which helps maintain and introduce diversity into the population. If the mutation probability (pm) is set too high, the GA is reduced to a random search, losing its exploitative power.
- Elitism is a survivor selection policy where the current fittest member of the population is always propagated to the next generation. This guarantees that under no circumstance can the best solution found so far be replaced by a less fit individual.
- The Darwinian model, which is standard for GAs, states that only information in the genotype can be transmitted to the next generation. In contrast, the Lamarckian model posits that traits an individual acquires during its lifetime can be passed on to its offspring, which in a GA means a locally improved chromosome becomes the new offspring.
- In K-Way Tournament Selection, K individuals are selected at random from the population. The best individual out of this group is then chosen to be a parent, and the process is repeated to select the next parent.
- The Building Block Hypothesis states that GAs progress by successively identifying and recombining “building blocks.” These blocks are low-order, low-defining-length schemata with above-average fitness that serve as the foundation for the GA’s success.