Creations tend to inherit its creators' traits.

Genetic algorithms

Genetic algorithms are optimization techniques inspired by biological evolution. They simulate natural selection and genetics to iteratively improve a population of candidate solutions to a problem.

Imagine a music producer crafting the perfect song. They start with 100 random melodies (initial generation). Listeners vote (evaluation) for their favorite tunes. The top 20 melodies are chosen (selection). Producer mixes (crossover) parts of two popular melodies (e.g., chorus from one, verse from another). Occasionally, a note or rhythm is randomly changed (mutation) to spark creativity. New mixes and mutants (new generation) replace old songs. Over time, melodies evolve into a chart-topping hit.

The inner machinations of genetic algorithms can be separated into parts of:

• Population: Represents a set of candidate solutions to a problem. Each individual (solution) in the population is called a chromosome.

• Genes: Basic building blocks of a solution, analogous to biological genes. Each gene represents a specific parameter, feature, or decision variable (e.g., binary values like 0 or 1, weights, or behavioral flags).

• Chromosomes: A complete encoded solution formed by a sequence of genes. Acts as DNA of an individual in the population.

Think of a full contest recipe (chromosome) with ingredient list and steps (genes) among a bunch of submitted recipes (population). Over contest rounds, the best recipes (highest fitness) are combined and tweaked to create even better dishes.

More on how genetic algorithms learn:

• Fitness function: Problem-specific metric that quantifies how well a candidate solution (individual) solves the target problem. Directs evolutionary process by assigning a numerical 'fitness score' to each individual.

• Evaluation: Process of calculating fitness values for all individuals in the population. First applies fitness function to each candidate solution, then normalizes or scales values if necessary (e.g., to handle large disparities).

• Selection: Mechanism for choosing individuals to reproduce and pass their traits to the next generation. Favors fitter individuals while maintaining diversity.

Imagine a judge (fitness function) scoring athletes in a competition. By calculating each athlete's score (evaluation), they choose (selection) which athletes get to train the next generation of competitors.

Crossover is a genetic operator that combines genetic material (chromosomes) of two parent solutions to create offspring for the next generation. It mimics biological reproduction, enabling the algorithm to explore new regions of the solution space by mixing traits from high-fitness individuals. Two variants of crossover are:

• Single-point crossover: One crossover point is randomly selected in parent chromosomes. Segments after this point are swapped between said parents to create two offspring. Simple, computationally efficient, and maintains contiguous gene blocks, preserving useful schemata. Limited exploration compared to other crossovers, however.

• Uniform crossover: Each gene (bit or feature) in offspring is independently selected from either parent with a specified probability (typically 50% for each parent). Encourages thorough mixing of genes, enhancing exploration, while being flexible (mixing ratio can be adjusted, e.g., 70% from Parent A). Can disrupt beneficial gene combinations (e.g., breaking up linked traits).

Single-point is preferred for problems where gene order matters (e.g., traveling salesman problem, scheduling), while uniform is better for problems where gene interactions are non-sequential (e.g., feature selection, neural network weight optimization). From the perspective of needs, the former emphasizes exploitation of existing good solutions, while the latter prioritizes exploration of new combinations.

Mutation is another genetic operator that introduces random changes to individual chromosomes (i.e., their weights), ensuring population diversity and enabling exploration of new regions in solution space. It prevents premature convergence to suboptimal solutions by occasionally disrupting existing gene patterns. Several mutation types include:

• Swap mutation: Two randomly selected genes swap positions.

• Insertion mutation: One gene is removed and inserted at a new position.

• Inversion mutation: Subset of genes is reversed in order. Ideal for order-sensitive problems (e.g., traveling salesman) alongside swap.

• Displacement mutation: Contiguous block of genes is moved to a new position. Suited for dynamic sequencing tasks alongside insertion.

Imagine mutation as the process of tweaking a recipe randomly — adding a new spice (insertion), swapping ingredients (swap), or reversing steps (inversion). Most tweaks fail, but occasionally, these efforts may lead to a tastier dish.

Neuroevolution of augmenting topologies

NeuroEvolution of Augmenting Topologies (NEAT) is a genetic algorithm designed to evolve artificial neural networks (ANNs) by optimizing both their structure (topology) and connection weights. Unlike traditional neuroevolution methods that fix the network architecture, NEAT starts with minimal networks and gradually increases complexity through mutations, enabling efficient exploration of diverse solutions. Elaborating on its components:

• Genome (Genotype)

  • Node genes: Defines neurons, including sensor nodes (input units), hidden nodes (intermediate processing units), and output nodes (final decision/action units).

  • Connection genes: Define synapses between nodes, specifying input/output nodes (e.g., In 1 → Out 4), weight (e.g., 0.7, -0.5), enabled/disabled Status (e.g., DISABLED connections are inactive), and innovation number — a unique ID tracking the historical origin of each connection (e.g., Innov 1, Innov 11) — enabling alignment during crossover.

• Phenotype (Network): Expressed neural network, constructed by activating only the enabled connections from the genotype.

In NEAT, the "add connection" mutation introduces new pathways for information flow within the neural network, allowing the evolutionary process to explore increasingly complex and potentially more effective network architectures over generations.

This new connection can 'loop back' to a node in the same or a previous layer (including itself), enabling the evolution of recurrent neural network architectures capable of processing temporal sequences. It is then assigned the next available innovation number, which is crucial for tracking the evolutionary history of different structural innovations across the population, especially during crossover. Finally, the same new connection is initialized with a random weight, allowing it to have an initial influence on the network's behavior, which can then be refined through evolution.

Another mutation, the "Add Node" mutation increases the depth and complexity of the neural network by inserting a new hidden neuron onto an existing connection. Careful initialization of new connections' weights helps to maintain the network's initial performance while allowing evolution to discover the benefits of the new node.

After the neuron is added into the network, increasing its depth and potentially its ability to learn more complex functions, the existing connection that the new node is inserted into is disabled to ensure that the new structure is explored. Because it is inserted without immediately disrupting the existing input-output mapping, it allows the evolutionary process to gradually explore the new node's potential. Finally, both connection genes receive a new node ID.

Crossovers in NEAT work differently from standard genetic algorithms:

1. Gene alignment by innovation number: Parent genomes are aligned using innovation numbers. Matching genes are directly paired.

2. Inheritance of non-matching genes: Disjoint genes (non-matching innovations between parents’ innovation ranges) and excess genes (non-matching innovations beyond the range of one parent) are handled as follows:

   • If one parent is fitter: All disjoint/excess genes are inherited from fitter parent.

   • If parents have equal fitness: Disjoint/excess genes are inherited randomly from either parent.

3. Handling disabled genes: Disabled genes (e.g., connections marked inactive) are inherited from the fitter parent. However, there is a small probability (e.g., 25%) that disabled genes are re-enabled in the offspring, reintroducing potentially useful traits.

4. Matching genes: For genes with matching innovation numbers, parameters (e.g., weights) are randomly selected from either parent.

In conclusion, NEAT's crossover prevents 'competing conventions,' structurally different but functionally similar networks from being misaligned, re-enables disabled genes and inheriting disjoint/excess traits to promote exploration, and prioritizes genes from fitter parents while allowing randomness to avoid premature convergence.

Crossovers in NEAT differ from the standard genetic algorithm (GA) in ways that I will now elaborate upon:

• Genome structure: Non-NEAT GAs use fixed-length genomes (e.g., binary strings, arrays, permutations), whereas NEAT uses variable-length genomes with evolving neural network topologies with node genes and connection genes — tracked by historical innovation numbers.

• Crossover mechanism: Non-NEAT GAs like single-point or uniform crossover swap segments between fixed-length parents with identical genome structures, whereas NEAT matches parents based on historical IDs to ensure compatible crossover and handles disjoint and excess genes.

• Handling of disabled genes: All genes in non-NEAT GAs are active and contribute to the solution, whereas connections in NEAT can be marked inactive due to mutation but can also be re-enabled during crossover, reintroducing potentially useful traits.

• Diversity and speciation: Non-NEAT GAs rely on mutation rates and selection strategies (e.g., tournament selection) to avoid premature convergence, whereas NEAT groups genomes into species based on structural similarity, ensures novel topologies (e.g., new hidden nodes) are not outcompeted early, and promotes compatibility and preserves topological diversity.

• Use cases: Non-NEAT GAs are more ideal for fixed-structure optimization (e.g., optimizing weights in a fixed neural network), whereas NEAT is designed for evolving neural network topologies (e.g., robotics).

Mentioned in the list before, speciation in NEAT protects structural innovations and maintain diversity in the population. By grouping genomes into species, NEAT ensures that novel topologies (e.g., new nodes or connections) are not prematurely eliminated, allowing them time to optimize and contribute to the gene pool. Its key components in metric form δ = (c_1 * E) /N + (c_2 * D)/N + c_3 * ˉW include:

• Compatibility distance (δ): Metric quantifying 'genetic difference' between two genomes.

• Coefficients (c_1, c_2, c_3): Adjustable parameters to prioritize structural vs. weight differences that allow NEAT to emphasize exploration of new network structures (by giving higher weight to E and D) or optimization of existing ones (by giving higher weight to ˉW).

• Excess genes (E): Genes in one genome beyond the innovation range of the other.

• Normalization (N): Number of genes in the longer of two genomes being compared.

• Disjoint genes (D): Non-matching genes within the shared innovation range of both genomes.

• Average weight difference (ˉW): Mean difference in weights of matching genes (same innovation numbers).

• Speciation threshold (δ_t): If δ < δ_t, genomes are deemed compatible and grouped into the same species.

Imagine a startup incubator where teams work on unique projects. Teams are grouped by project similarity (species) and segregated by differences (compatibility distance) between each project — which translates into the rule (threshold) of "If projects are too different, they get their own team."  Radical ideas get (protect) their own team, avoiding competition with established projects. Diverse innovations thrive simultaneously, as no idea is overshadowed too soon — just like NEAT’s species shield novel neural structures to let them evolve.

Additionally, to regulate population growth in NEAT, raw fitness is adjusted by dividing by species size. Each species then receives a breeding quota for the next generation proportional to the sum of its adjusted fitness, favoring fitter species but preventing any single species from dominating. This mechanism also provides a survival advantage to small, potentially promising species by inflating their adjusted fitness.

Without this regulation, NEAT would likely:

• Prematurely converge: A single dominant structure (e.g., a simple network) would dominate the population, eliminating diversity.

• Stifle innovation: Novel topologies (e.g., new nodes/connections) would be outcompeted before they could optimize, even if they held long-term potential.

• Lose structural complexity: Evolution would favor slight weight tweaks over structural exploration, resulting in shallow, homogenous networks.

• Overfit to early solutions: The population would exploit suboptimal local maxima rather than exploring the solution space.

The above results in a less robust, less adaptive algorithm that fails to evolve sophisticated architectures for complex tasks.

Double pole balance

Before continuing with NEAT, the lecture introduced the double pole cartpole problem, a classic and challenging reinforcement learning task designed to test an agent’s ability to balance complex dynamical systems. The objective is to simultaneously balance two poles of different lengths hinged to a cart while ensuring the cart remains within a limited track length. The key challenges in this problem are:

• Partial observability (harder version): The agent receives no direct measurements of angular velocities (poles) or cart velocity. Instead, it must infer these values from the history of pole angles and cart positions, requiring temporal reasoning.

• Dual dynamics: The shorter pole reacts faster to disturbances, while the longer pole has slower, larger oscillations. Balancing both necessitates adaptive control strategies.

Fitness evaluation for the agent is the number of time steps it survived without pole angles exceeding a threshold while keeping cart on bounds of track. However, simply surviving for a long time might lead to jerky or highly oscillatory control. Coming up with the idea of penalizing these oscillations encourages smoother, more efficient, and more stable control policies. Minimizing the sum of these state variables is a common way to achieve this.

NEAT demonstrated superior efficiency and effectiveness compared to earlier neuro-evolutionary methods, which were state-of-the-art at the time, in terms of:

1. Performance superiority: NEAT solved the double pole balance task faster than prior methods, achieving the goal with fewer generations. Its success stemmed from unique features like speciation, historical innovation tracking, and complexification (gradual growth of network topologies).

2. Ablation experiments: Studies about systematic removing or disabling components of a system to understand their individual contributions and the overall system's behavior (i.e., ablation studies) systematically removed individual NEAT components to isolate their contributions. These experimented included:

   • Fixed fully-connected networks: Replaced NEAT’s evolving topologies with static, pre-defined architectures. Performance plummeted, as fixed networks lacked adaptability to task complexity.

   • Larger initial networks: Started with non-minimal, oversized networks instead of NEAT’s simple initial structures. Slower learning due to unnecessary complexity and reduced efficiency in exploring useful topologies.

   • Disabled speciation: Removed species protection, forcing all genomes to compete globally. Premature convergence to suboptimal solutions, as novel structures were eliminated early.

   • Disabled crossover: Relied solely on mutation, excluding genetic recombination. Slower evolution, as crossover’s ability to blend high-quality traits was lost.

3. Key findings: All ablated versions underperformed the full NEAT implementation. Some failed to solve the task entirely. Others required significantly more generations to succeed. Every NEAT component — speciation, complexification, crossover, and minimal starting networks — is critical to its efficiency and success.

These experiments validated NEAT’s design philosophy: Complexification avoids over-parameterization by growing networks incrementally, speciation preserves diversity, enabling exploration of novel structures, and crossover accelerates evolution by combining effective traits.

Embodied AI

Case study: Polly

Polly was a pioneering visually navigated robot, achieving animal-like speeds (1 m/s) in 1993. It served as a demonstration of Australian roboticist Rodney Brooks' philosophy of employing simplifying assumptions to develop robots effective within specific environments.

Much like a simple animal, such as a cockroach, Polly was designed through an evolutionary approach to fulfill its environmental needs without requiring high-level understanding. For several years, Polly provided tours of the MIT AI Lab's 7th floor, playing pre-recorded speech at designated locations.

Polly operated based on several simplifying environmental assumptions:

• Environment: It assumed an uncluttered office setting with corridors and uniform, un-patterned carpet. This allowed for significant computational shortcuts.

• Carpet/object detection: The system could differentiate between the uniform carpet and obstacles. Anything with patterns was classified as an obstacle.

• Ground plane constraint: Polly assumed objects rested on a flat floor, enabling it to infer that objects appearing higher in the image were further away.

• Corridor constraint: The narrowness of corridors restricted the potential locations of distant landmarks within its visual field, thus reducing the visual search space.

Polly's visual system processed a low-resolution 64 * 48 image captured every 66 milliseconds, enabling computation with minimal power. For each frame, it generated a set of mostly Boolean 'precepts' derived from the image data.

The operations used to compute these precepts (read image below) included generating a radial depth map, leveraging the ground plane constraint to interpret height as depth, and performing edge detection, which prioritized identifying strong, straight corridor edges based on environmental assumptions.

Polly's navigation and control relied on a stored library of low-resolution visual landmark records from various directions and distances, which were surprisingly computationally efficient to search. It maintained an approximate sense of its facing direction through rotational odometry, tracking left and right turns.

Polly also recognized 'districts'; for instance, if traveling east and detecting a left turn, it could infer it was in the southern corridor and update its internal y-coordinate to a fixed value (e.g., 10), aiding in recovery if it became lost. Visitors initiated a tour by waving their foot, as the system lacked speech recognition, and its camera was positioned to observe people's feet and legs.

Cast study: predecessors of Polly

Allen, a predecessor to Polly (1986), demonstrated Rodney Brooks' concept of a layered control system, utilizing sonar sensors to detect obstacle ranges. Its movement direction was determined by combining forces from three behavioral levels:

• Level 0 — Avoid: Generated a repulsive force inversely proportional to the square of the distance to obstacles, causing it to veer away or stop.

• Level 1 — Wander: Selected a random direction and moved that way for 10 seconds.

• Level 2 — Explore: Headed towards areas of wide-open space.

This simple programming, requiring minimal computation and power, enabled Allen to successfully wander the lab, often being seen but readily moving to avoid collisions. Despite lacking any genuine knowledge or a master plan, Allen provided a robust, flexible, and low-compute foundation for more sophisticated robots.

Other than Allen, there were other robots outsdie of Polly that explored layered control systems:

• Squirt: Tiny robot (one cubic inch) employed a layered architecture similar to Allen's but utilized different sensors. Its primary behavior was to seek dark areas and remain stationary in a corner. A higher-level behavior would override this: after a loud noise, Squirt would pause briefly and then move rapidly towards the sound, after which its primary behavior would resume, leading it to hide closer to the sound's origin.

• Herbert: Equipped with an arm, programmed to locate and pick up empty soda cans.

• Gengis: Six-legged robot that demonstrated a 'loose control' approach, where its legs were not explicitly coordinated. Despite this, it could effectively move around by following infrared sources.

Case study: BigDog

Description

Physical architecture

Dynamic balancing

Systems

Case study: robots on Mars

Reasons and tasks

Space travel hassle

Joint reasoning

STEAM (a Shell for TEAMwork) is 

Agent based modeling

Bird flock rules

Boids

Boid details

Coordinate