Evolutionary Computation: Mastering Genetic Algorithms Module IV: Optimization Theory, System Architecture, and Exam Preparation eS eae eRe ‘OOLOiT 11010000011 110100 011101 110100Traditional Optimization Evolutionary Algorithms T Search Space I Search Space Relies on a single trajectory. Highly susceptible to getting trapped in local minina and requires differentiable, smooth search spaces. Employs a population-based stochastic search. Avoids| local minina, handles non-differentiable spaces, mimics natural selection to explore globally. and }>[_Notivation: Moving fron single-point trajectory searches to population-based global exploration. [>|The Bio-Algorithmic Dictionary Chromosome (String/Individual) : A complete candidate solution. values a gene can hold. a + (Gene) Alleles: The possible ss 1 iC 0 dl ala ele 0) 14/ — jl ‘+ Locus: The specific index/position of a gene. Genotype Phenotype The encoded computational representation (the data string). The decoded, real-world manifestation of the solution. b»[_Note: The Fitness Function acts as the natural environment, evaluating how well the Phenotype survives. >The Core Engine: Workflow & System Logic Initial population Selection q Sen tl ft rosare T Mutation Best individuals z Output Canonical GA Pseudocode Initialize P(t) by encoding routine; Evaluate P(t) by decoding routines while (not terminating condition) do Create C(t) from P(t) by crossover; Create C(t) from P(t) by mutation; Evaluate C(t) by decoding routine; Select P(t+1) from P(t) and C(t); t=t+1; end . Output best solution.Data Architecture: Encoding Techniques Binary Encoding Real-Valued Encoding Permutation Encoding [es ~0.4 | 3.14 039]| The simplest format. Uses strings of 1s and Os. Highly effective for boolean logic but computationally heavy for continuous variables. Direct numerical values. Useful for numeric optimization (e.g,, encoding weights for Neural Networks). Overcomes binary precision limits. 1. Completeness: Every solution has a chromosome. Represents an ordered sequence. Essential for ordering problems like the Travelling Salesman Problem (Tsp). Requires special crossover care, Encoding Integrity Rules 2. Uniqueness: 1:1 mapping between ‘genotype and phenotype, 3. Heritability: Crossover consistently creates valid hybrid offspring.The Survival Filter: Selection Operators Roulette Wheel Selection Rank Selection Probability p, = f, / Sum sy Sorts population and selects ariegy ound ‘and 74 based on rank. Trait: Fitness-proportionate, 3rd : 5 Caries a risk of premature Trait: Prevents super-individuals lconvergene If one suger from taking over by normalizing individual dominates early. selection pressure. Tournament Selection Elitism oo, Picks k random individuals, Bypasses the standard filter. Best _ best advances. es F] Advances Trait: Guarantees the |-+@ Tiel Efficient, parallelizable, absolute best configurations and allows tuning of are passed unaltered selection pressure via unaltered directly to the tournament size (k). ® Next Generation next generation.Information Exchange: Crossover Operators ¥ Parent 1 [2] [2 [ef Parent 2 [@ | One random locus is chosen; tails are swapped. Simple but limited. Single-Point Multiple loci chosen; alternating Multi-Point | segments are swapped. Better for long chromosomes. Arandom binary mask dictates Uniform | which parent provides which gene. Disruptive but maximizes mixing, AFTER Child 1 1fe]o]o[o]1[o]1]1[2]Jo]a Convex linear combination of Arithmetic | vectors. Used specifically for floating-pointreal-coded algorithms. | BEFORE | critd2 [o[1Jo]2]1]2[2]1Jolelo[2]Maintaining Diversity: The Ex/Ex Balance EXPLORATION EXPLOITATION Searching completely new areas. —o—> Refining known good areas. Mutation * Bit-fip: inverting a 0to 1. S + Swap: Exchanging positions of two genes (crucial for permutation). * Gaussi ‘ding normally + distributed random values to | / | \* ‘Search Space real-coded genes. Why Mutate? Crossover exploits accumulated information, but can lead to population Core Concept stagnation. Mutation mimics natural biodiversity, acting as a random search element that injects fresh genetic diversity and rescues populations trapped in local minima.Navigating Continuous Space: Real-Coded GAs Context: Binary algorithms require massive string lengths for high precision in continuous spaces, increasing computational complexity. Real-coded GAs map directly to continuous domains. Wright’s Linear Crossover (1991) Given parents P1, P2, three candidate solutions are produced: 1) 0.5(P1 + P2) 2) 1.5P1-0.5P2 3) -0.5P1+1.5P2 Rule: Out of these three candidate solutions, the best two are selected as the actual children. Child 1 Child 2 nama Modern Floating-Point Alternatives: Similated Binary Crossover (S8X) and Blend Crossover (BLX-alpha)Advanced Architectures: Adaptive, Hybrid & Parallel Adaptive GAs Hybrid (Memetic) GAs GA Module Local Search / Neural Net Dynamically adjusts Crossover Probability (P,) and Mutation Probability (?,) based on real-time fitness variance. Prevents stagnation on the fly without manual retuning. Combines global GA search with local gradient or heuristic search. Essential for Neuro-genetic systems and tuning Fuzzy-genetic controllers Parallel GAs Cellular Distributes computation across multiple processors to handle massive search spaces and large population Increases efficiency significantly.Performance Dynamics: Tuning & Convergence Random Search Highly Disruptive pede avon Rapid exploitation but Algorithm loses inherited destroys good building knowledge too quickly. pea ean Sas se High 2 s = ‘Stagnation Premature Convergence Search progresses far High risk of getting too slowly to be useful. | || permanently trapped in local optima, Crossover (P.) {The Schema Theorem Danger A\, GAs depend on combining shor. bgh: fitness Building Blocks (Schemas). However, ifthe fitness landscape is deceptive, these blocks can be misleading. In such cases, the algorithm may face exponentially long waiting times before discovering the true global optimum.System Trade-Offs & Real-World Applications Industrial Applications The Architectural Ledger Travelling Salesman Problem (via Integer Linear Programming). 0) a Job Shop Scheduling (offline makespan minimization). S| ce _ Infrastructure Network Design ob & Routing. Operations Timetable Creation. Advantages + ‘© Highly robust in poorly understood or complex spaces. ‘© Requires no derivative or gradient information. © Easily parallelizable architecture. ‘© Capable of optimizing multiple objectives simultaneously. Disadvantages - ‘© Computationally intensive (fitness evaluated per individual per generation). ‘© Nomathematical guarantee of absolute global optimality. ‘© Performance is highly sensitive to exact parameter tuning.Exam Prep: Formula & Terminology Cheat Sheet Key Probabilities Real-Coded Formulas Core Vocabulary * Roulette Selection © Wright's Linear Crossover: oioior Genotype 611100 Encoded string / internal data * Crossover Probability (P. Typically 0.6 - 0.9 * Mutation Probability (P_,,.) Typically 0.001 - 0.05 ~ Candidate 1: 0.5(P, + P,) ~ Candidate 2: 1.5P, - 0.5?) = Candidate 3: -0.5°, + 1.5P, Po ort ott Pl * Objective Function Must map to a scalar fitness value. Objective Scalar Fitness Function, Value bieoro a+ 4 @ representation. Phenotype Decoded solution / external manifestation, Locus Specific index position of a gene, Allele Allowed specific value of a gene. Schema Atemplate identifying a subset of strings with similarities at certain positions.Exam Prep: Common Written & Viva Questions Q: How do genetic algorithms differ from traditional optimization? Q: Explain the generation cycle of a genetic algorithm. A; GAs use a population of points (not a single trajectory), employ probabilistic transition rules (not deterministic), and do not require derivative or gradient information. A; Initialization — Fitness Evaluation -> Selection (survival filter) > Crossover (mating/exploitation) ~ Mutation (diversity injection/exploration) ~ Repeat until termination. Q: What is the difference between exploration and exploitation? Q: Why do basic binary GAs struggle with continuous search spaces? A: Exploitation refines known good areas of the search space (via Selection and Crossover). Exploration searches completely new areas to avoid local minima (via Mutation). A: They require massive string lengths to achieve high mathematical precision, resulting in computational complexity that scales extremely poorly. Real-coced GAs are required instead.Last-Minute Revision: Module IV Synthesized Bio-Inspiration ‘Survival of Fittest Genatype/Phenotype Fitness Landscape Binar (Losie Hybrid Adaptive Memetic Parallel pia ify Real-Coded |. (Continuous) Permutation (TSP) Encodings System Workflow (Bit-fip, Gaussian) Selection (Poulet, Tournament || F¥!Hsvon [Operators [1>) quarpeit Vem) | leeton Mutation Exploetion