Unit 2 - Practice Quiz

Evolutionary computation is a field of artificial intelligence inspired by the principles of biological evolution, such as natural selection, reproduction, and mutation.

A defining feature of evolutionary algorithms is that they maintain and evolve a population of potential solutions, rather than just refining a single solution.

The term 'chromosome' is used to describe the data structure that encodes a single potential solution, analogous to a biological chromosome encoding genetic information.

A binary string is a natural fit for subset selection problems. Each bit can represent an item, where '1' means the item is included in the subset and '0' means it is not.

The fitness function acts as the objective function, assigning a score to each solution that indicates its quality or suitability for solving the problem.

For minimization problems, the goal is to find the solution with the lowest possible value. Therefore, a lower fitness score indicates a better solution.

Tournament selection works by holding 'tournaments' among a few randomly selected individuals, with the winner (the one with the best fitness) being chosen for crossover.

Elitism ensures that the best solution found so far is never lost. It guarantees that the quality of the best solution in the population will not decrease from one generation to the next.

Crossover, also known as recombination, mimics biological reproduction by creating one or more new offspring solutions from two selected parent solutions.

Mutation introduces random changes, which helps the algorithm escape local optima and explore new, potentially better, regions of the solution space.

Convergence refers to the state where the genetic diversity of the population has decreased significantly, and most individuals represent similar solutions, leading to little or no improvement in fitness over generations.

Premature convergence occurs when the population loses diversity too quickly and converges on a solution that is good, but not the best possible one (a local optimum).

Mutation is the primary mechanism for introducing new genetic material into the population, which helps maintain diversity and allows the search to escape from local optima.

In the fitness landscape metaphor, the height of the landscape corresponds to fitness. Therefore, peaks represent solutions with high fitness, which are considered optimal or good solutions.

A rugged landscape makes the search difficult because the algorithm can easily get trapped on one of the many suboptimal peaks (local optima) instead of finding the highest peak (global optimum).

Neuroevolution uses evolutionary algorithms, like GAs, to automatically design and optimize neural networks, including their connection weights, structure, and hyperparameters.

Hyperparameter optimization often involves a complex and non-differentiable search space. GAs are well-suited for this as they are a global search method that doesn't rely on gradients.

In the common binary representation for feature selection, each gene (or bit) corresponds to a specific feature, indicating whether it should be included ('1') or excluded ('0') from the model.

A good fitness function for feature selection balances two goals: the predictive performance of the model (like accuracy) and the simplicity of the model (fewer features), often by penalizing solutions that use too many features.

A single-bit flip mutation changes the value of exactly one randomly chosen gene (bit). In this case, 11011 is the only option that differs from the original by just one bit.

Evolutionary Algorithms are stochastic, population-based methods that do not rely on gradient information. This makes them well-suited for complex, non-differentiable, or discontinuous search spaces where gradient-based methods would fail.

TSP requires visiting each city exactly once. A permutation representation naturally enforces this constraint, as each city appears once in the sequence. Other representations would require complex repair mechanisms or penalty functions to handle invalid solutions (e.g., visiting a city twice or not at all).

Since the neural network weights are continuous values (real numbers), the most direct and effective representation is a real-valued vector. Each gene in the chromosome corresponds to a specific weight in the network.

For a regression problem, the goal is to minimize the prediction error. RMSE is a standard metric for this. Using a validation set prevents overfitting to the training data, leading to a more generalizable model. The fitness function should be minimized to find the best solution.

The weight (where ) balances the two competing objectives. A higher value of prioritizes maximizing accuracy, while a lower value prioritizes minimizing the number of selected features (i.e., reducing complexity).

A penalty function reduces the fitness score of an individual in proportion to how much it violates the problem's constraints. This penalizes infeasible solutions, guiding the search towards the feasible region of the search space without explicitly forbidding their existence.

In Tournament Selection, a random subset of individuals is chosen, and only the best one is selected for reproduction. This creates a direct competition where fitter individuals are more likely to win. In Roulette Wheel, even low-fitness individuals have a non-zero chance of selection. Increasing the tournament size further increases the selection pressure.

Elitism involves copying one or more of the best-performing individuals from the current generation directly into the next generation without subjecting them to crossover or mutation. This prevents the loss of good solutions due to the stochastic nature of the selection and genetic operators.

Fitness Proportional Selection assigns a selection probability proportional to the raw fitness value. In this scenario, the super individual would have an overwhelmingly large slice of the "roulette wheel," causing it to be selected very frequently and quickly dominate the population's gene pool. Rank Selection and Tournament Selection are less affected as they depend on relative fitness rankings, not absolute values.

With no crossover, offspring are just mutated clones of their parents. The algorithm loses its ability to combine building blocks from different parents. Each lineage evolves independently through mutation alone, which is analogous to running multiple, parallel hill-climbing searches, where each search explores the neighborhood of its current solution.

Single-point crossover involves choosing a crossover point and swapping the segments of the parents after that point. Crossing P1 ([1, 1, 1 | 0, 0, 0]) and P2 ([0, 0, 0 | 1, 1, 1]) after the 3rd gene results in Offspring 1 ([1, 1, 1] from P1 + [1, 1, 1] from P2) and Offspring 2 ([0, 0, 0] from P2 + [0, 0, 0] from P1).

Standard crossover operators, when applied to permutations, can easily break the fundamental constraint of a valid tour. For example, crossing [1,2,3,4] and [4,3,2,1] might produce [1,2,2,1], which is not a valid permutation. Specialized operators like Partially Mapped Crossover (PMX) or Order Crossover (OX) are required to ensure the offspring remain valid permutations.

This pattern is characteristic of convergence. The initial rapid improvement occurs as the GA exploits promising regions of the search space. The subsequent plateau indicates that the population has lost diversity and is stuck in one region, which may or may not be the global optimum. Without further improvement, it is often a sign of premature convergence.

High selection pressure (e.g., high elitism or large tournament size) causes the best individuals to dominate quickly. A low mutation rate prevents the introduction of new genetic material. A small population size makes it easier for a few good individuals to take over the entire gene pool. This combination is a classic recipe for losing diversity and converging too early.

The Island Model divides the main population into several smaller subpopulations (islands). Each island evolves independently for a number of generations, which encourages exploration of different search space regions. Periodically, a few individuals migrate between islands, sharing genetic information but preventing a single solution from dominating the entire global population too quickly.

A deceptive landscape has misleading gradients. Combinations of good, low-order building blocks (schemata) guide the search towards a locally optimal point, but the global optimum is located in a different region of the search space and is composed of less-fit lower-order building blocks. This "deceives" the GA into converging on the wrong peak.

The Building Block Hypothesis posits that a GA works by identifying and combining small, beneficial patterns (building blocks or schemata) to form progressively better solutions. Crossover is the key operator for this process. This works well on landscapes where such a compositional structure exists, but can fail on deceptive or highly complex, unstructured landscapes.

This is a classic application of GAs in AutoML. The GA doesn't train the model itself. Instead, each individual in the GA's population represents a specific set of hyperparameters (e.g., {'kernel': 'rbf', 'C': 10.5, 'gamma': 0.01}). The fitness function evaluates this set by training an SVM with these parameters and measuring its performance on a validation set. The GA then evolves the population of hyperparameters to find the optimal combination.

In the wrapper method, the GA "wraps" around a machine learning model. For each individual (which represents a subset of features), the fitness function involves training the chosen model (e.g., a decision tree) using only those features and then evaluating its performance (e.g., accuracy) on a validation set. This is computationally expensive but often yields better results than filter methods because it evaluates features based on their utility to a specific model.

The binary chromosome acts as a mask. A '1' at a certain position indicates that the corresponding feature is included, while a '0' indicates it is excluded. Therefore, the chromosome [1, 0, 1, 0, 1] represents the feature subset containing the first, third, and fifth features from the original dataset. The fitness function will evaluate the performance of the logistic regression model trained only on this subset.

In a flat landscape, crossover between two parents of similar (low) fitness simply shuffles non-informative genetic material, providing no gradient to follow. A very low mutation rate makes it extremely unlikely to randomly generate the 'needle'. Elitism would just preserve the mediocre individuals, leading to rapid stagnation. This combination is least likely to find the peak.

Fitness Sharing directly modifies an individual's fitness value based on its proximity to other individuals in the population, creating 'niches'. An individual in a dense region has its fitness derated, effectively lowering the fitness peaks that are heavily populated and raising the relative fitness of individuals in unexplored regions. Crowding is a replacement strategy, elitism is a preservation strategy, and increasing mutation just adds random exploration without altering the perceived landscape.

Rank Selection mitigates the effect of super-individuals by mapping fitness values to ranks. The difference in selection probability between rank 1 and rank 2 is fixed, regardless of how much better the rank 1 individual's fitness score is. In contrast, while Tournament Selection's pressure is consistent, a super-individual would still have a strong advantage. Proportional methods like Roulette Wheel are the most susceptible. Rank Selection provides a more controlled and stable selection pressure.

The Building Block Hypothesis posits that a GA works by combining short, low-order, high-fitness schemata (building blocks) to form better solutions. In high-dimensional feature selection, important interacting features might be represented by bits that are far apart on the chromosome. A standard crossover is highly likely to place a cut point between these bits, destroying the beneficial combination. This is a primary challenge for GAs in this domain.

With a single-point crossover at the midpoint, the offspring would be O1 = 11111111 and O2 = 00000000. The Hamming distance between P1 and O1 is 4, and P2 and O1 is 4. The same applies to O2. Uniform crossover could produce anything, including the parents themselves. Two-point crossover would produce 11000011 and 00111100, which are closer to the parents. Therefore, in this specific, symmetrical case, midpoint crossover creates the most distant offspring.

The survival probability of a schema through crossover is approximately . For a schema to be a 'building block', it should be short (small ). If the defining length is large, the probability of a crossover point falling within its bounds and disrupting it is high. While mutation is also disruptive (probability ), the crossover term is often the dominant disruptive force for long schemata.

TSP requires a permutation representation to define a valid tour. Standard crossovers like single-point or two-point on a path representation would produce invalid offspring with duplicate or missing cities (e.g., [3, 1, 4, 2] and [1, 2, 3, 4] could produce [3, 1, 3, 4]). PMX is a specialized crossover operator designed for permutation-based problems that guarantees the offspring are also valid permutations by intelligently resolving collisions.

Direct encoding provides a one-to-one mapping between genes and network parameters (like weights or connections). This gives the GA maximum freedom to tweak every single detail, which can lead to the discovery of novel and highly optimized solutions that a rule-based (indirect) system might never generate. The main drawback is the immense search space and poor scalability, which are advantages of indirect encoding.

Accuracy is typically in [0, 1], while training time could be in seconds, minutes, or hours (e.g., values from 10 to 10000). Without normalization, the training time term would completely dominate the fitness calculation, making small changes in accuracy irrelevant. The GA would then just optimize for the fastest possible model, ignoring accuracy. Normalizing both components is a crucial pre-requisite before balancing them with and .

The NFL theorem's core message is that an algorithm's performance comes from exploiting the structure of a problem. A GA works well only when its biases (e.g., the tendency of crossover to combine building blocks) match the problem's structure (i.e., the problem is decomposable into building blocks). If there is a mismatch, the GA can perform worse than random search. Thus, success is not guaranteed; it's contingent on this alignment.

This is a key distinction. Crowding distance in NSGA-II specifically measures the density of solutions in the objective space to favor individuals that are farther apart on the current Pareto front. This promotes a well-distributed front. Fitness sharing, a more general technique, typically measures distance in the decision variable space (genotype) to maintain population diversity throughout the entire search landscape, not just on the non-dominated front.

Single-point and multi-point crossovers have a strong positional bias; genes that are far apart are much more likely to be separated than genes that are close together. This implicitly assumes that linked genes are close on the chromosome. When this assumption is false, these crossovers are disruptive. Uniform crossover has no positional bias, as the exchange of any gene is an independent event, making it more suitable when gene linkage is not encoded by proximity.

Deceptive problems mislead the GA because combinations of 'good' low-order schemata produce a suboptimal solution. The global optimum requires a specific, less-obvious combination of genes (a higher-order schema). A small population will quickly converge on the deceptive attractor. A much larger population provides the necessary diversity and sampling to allow these more complex, higher-order schemata to emerge, survive selection, and eventually lead the search toward the global optimum.

Roulette Wheel involves N independent 'spins', so due to sampling error, an individual with an expected selection count of, say, 3.5 could be selected 1 time or 6 times. A very fit individual might even be missed entirely. SUS uses a single wheel spin with N equally spaced pointers. This ensures that the number of copies an individual receives is very close to its expected value, providing a much fairer and less noisy sampling of the population based on fitness.

The GA is a powerful optimization algorithm. If the fitness of a chromosome is calculated on a single, fixed validation set over many generations, the GA will effectively 'mine' that validation set for statistical quirks. It will discover a feature subset that is not just good, but perfectly tailored to that specific data split. This is a form of overfitting, and the resulting feature subset will likely fail to generalize to new data.

Early in the run, the population is diverse, so crossing over two very different parents can produce radical new offspring, making crossover a powerful exploration tool. As the run progresses and the population converges on a region of the search space, individuals become more similar. Crossover between similar parents produces offspring that are also similar, thus becoming a more exploitative, fine-tuning operator. At this stage, mutation is the main way to introduce new genetic material and escape the local optimum.

In standard binary, adjacent integers can have very different bit representations (e.g., 7 is 0111, 8 is 1000). A single bit mutation from 7 to 8 would require flipping all 4 bits. More importantly, a single flip on 0111 could result in 1111 (15), a huge jump in the problem space. Gray codes are designed so that adjacent values differ by only one bit. This creates a smoother mapping from the genotype search space to the phenotype problem space, making local search via mutation more effective.

Gradient-based methods are entirely dependent on the existence of a computable, informative gradient. If the objective function or activation functions have discontinuities or are non-differentiable (e.g., step functions), backpropagation fails. GAs are gradient-free optimization methods; they only require an evaluatable fitness score. This makes them applicable to a broader class of problems where gradient information is unavailable or unreliable.

High epistasis means the problem is not additively decomposable. The 'goodness' of a gene cannot be determined in isolation. This directly contradicts the Building Block Hypothesis, which assumes that good, short schemata can be combined to form better solutions. When epistasis is high, combining two high-fitness parents can result in a low-fitness child because the beneficial gene combinations are destroyed. This makes the landscape rugged and challenging for a GA.

In self-adaptation, the strategy parameters (like mutation rate) and the solution variables are linked on the chromosome. When an individual is selected, its strategy parameters are selected along with it. An individual at a fitness peak will have a higher chance of producing successful offspring if its mutation rate is low (exploitation). An individual in a low-fitness area benefits from a higher mutation rate to explore new regions. This creates a dynamic where selection pressure on the solution indirectly optimizes the search strategy itself.