Contents

Genetic Algorithms and Evolutionary Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii

1.1 Evolutionary Operators in Detail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
1.1.1 Selection: Survival of the Fittest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
1.1.2 Crossover (Recombination) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
1.1.3 Mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii
1.2 The Prototypical Genetic Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii
1.2.1 Algorithm Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii
1.2.2 Formal Algorithm Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii
1.3 The Prototypical GA: Step-by-Step Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix
1.4 GABIL: Learning Rule Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix
1.4.1 Knowledge Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix
1.4.2 Genetic Operators in GABIL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x
1.4.3 Extension Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x
1.4.4 Evolving the Learning Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi
1.4.5 Fitness Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi
1.4.6 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi
1.5 The Schema Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi
1.6 Genetic Programming (GP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii
1.6.1 Representation: Programs as Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii
1.6.2 GP Crossover: Subtree Swapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii
1.6.3 GP Mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii
1.6.4 Evolutionary Success: The Block Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii
1.6.5 Summary of Genetic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii
1.7 Biological Evolution and the Baldwin Effect . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii
1.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiv

v
Chapter 1
Genetic Algorithms and Evolutionary Computation

Genetic Algorithms (GAs) provide a robust learning method motivated by the process of natural selec-
tion. Unlike gradient-based methods, GAs conduct a randomized, parallel, hill-climbing search through a
hypothesis space without requiring the error function to be differentiable.

1.1 Evolutionary Operators in Detail

Before examining the formal algorithm, we define the mechanisms that allow a population of bit strings
(chromosomes) to evolve.

1.1.1 Selection: Survival of the Fittest

Selection determines which strings stay in the mating pool.

• Fitness Proportionate (Roulette Wheel): If individual ℎ1 has fitness 10 and ℎ2 has fitness 2, ℎ1 is five
times more likely to be picked.
• Tournament Selection: Pick two individuals at random. With probability 𝑝 (e.g., 0.8), the fitter one wins;
otherwise, the weaker one wins. This maintains diversity.

1.1.2 Crossover (Recombination)

Crossover combines ”genetic material” from two parents.

1. Single-Point Crossover: A random index is chosen.
• Parent A: 111|11
• Parent B: 000|00
• Offspring: 11100 and 00011

vii
viii 1 Genetic Algorithms and Evolutionary Computation

2. Two-Point Crossover: Swaps the middle segment.

• Parent A: 11|00|11
• Parent B: 00|11|00
• Offspring: 111111 and 000000
3. Uniform Crossover (Masking): A bit-mask is generated. If mask bit is 1, take from Parent A; if 0, take
from Parent B.
• Parent A: 11111
• Parent B: 00000
• Mask: 10101
• Offspring: 10101

1.1.3 Mutation

Mutation prevents the population from converging on a local optimum by flipping random bits.
• Example: String 11011 with mutation at pos 3 becomes 11111.

1.2 The Prototypical Genetic Algorithm

The GA treats learning as an optimization problem, aiming to maximize a Fitness function.

1.2.1 Algorithm Parameters

• 𝑝 (Population Size): The number of hypotheses in the population.

• 𝑟 (Replacement Rate): The fraction of the population replaced by crossover.
• 𝑚 (Mutation Rate): The probability that a bit will be mutated.

1.2.2 Formal Algorithm Definition

GA(𝐹𝑖𝑡𝑛𝑒𝑠𝑠, 𝐹𝑖𝑡𝑛𝑒𝑠𝑠 𝑡ℎ𝑟𝑒𝑠ℎ𝑜𝑙𝑑, 𝑝, 𝑟, 𝑚)

Initialize: 𝑃 ← 𝑝 random hypotheses
Evaluate: For each ℎ ∈ 𝑃, compute 𝐹𝑖𝑡𝑛𝑒𝑠𝑠(ℎ)
while [maxℎ 𝐹𝑖𝑡𝑛𝑒𝑠𝑠(ℎ)] < 𝐹𝑖𝑡𝑛𝑒𝑠𝑠 𝑡ℎ𝑟𝑒𝑠ℎ𝑜𝑙𝑑 do
1. Select: Probabilistically select (1 − 𝑟) 𝑝 members to 𝑃𝑆 via Fitness Proportionate Selection.
2. Crossover: Select 𝑟 2· 𝑝 pairs. Apply crossover to produce two offspring and add to 𝑃𝑆 .
3. Mutate: Invert a random bit in 𝑚 · 𝑝 random members of 𝑃𝑆 .
4. Update: 𝑃 ← 𝑃𝑆
1.3 The Prototypical GA: Step-by-Step Example ix

5. Evaluate: For each ℎ in 𝑃, compute 𝐹𝑖𝑡𝑛𝑒𝑠𝑠(ℎ)

end while
return highest fitness hypothesis in 𝑃

1.3 The Prototypical GA: Step-by-Step Example

Problem: Find the bit string that maximizes the ”One-Max” function (count of 1s). Params: 𝑝 = 4, 𝑟 = 0.5
(50% crossover), 𝑚 = 0.01.
1. Initialize: 𝑃 = {ℎ1 : 10001, ℎ2 : 01010, ℎ3 : 11000, ℎ4 : 00010}
2. Evaluate Fitness: 𝐹𝑖𝑡𝑛𝑒𝑠𝑠(ℎ1 ) = 2, 𝐹𝑖𝑡𝑛𝑒𝑠𝑠(ℎ2 ) = 2, 𝐹𝑖𝑡𝑛𝑒𝑠𝑠(ℎ3 ) = 2, 𝐹𝑖𝑡𝑛𝑒𝑠𝑠(ℎ4 ) = 1. Total = 7.
3. Select: Probabilities: ℎ1 = 2/7, ℎ2 = 2/7, ℎ3 = 2/7, ℎ4 = 1/7. Let’s say ℎ1 , ℎ2 , ℎ3 are selected for 𝑃𝑠 .
4. Crossover: Select pairs for replacement (50% of 4 = 2 offspring). Swap ℎ1 and ℎ3 at pos 2: ℎ1 : 10|001,
ℎ3 : 11|000 → Offspring: 10000, 11001.
5. Mutate: Flip a bit in a random string: 11001 → 11101.
6. Repeat: New population is evaluated until a string of all 1s appears.

1.4 GABIL: Learning Rule Sets

GABIL is a system that uses Genetic Algorithms to learn sets of propositional rules. It treats the problem
of learning rules as an optimization task, evolving a population of hypotheses that compete based on their
classification accuracy.

1.4.1 Knowledge Representation

In GABIL, each hypothesis is represented as a bit string that encodes a set of rules (a disjunction of rules).

[Link] Encoding a Single Attribute

Each attribute is represented by a bit string where each bit corresponds to a possible value of that attribute.
A bit is set to 1 if that value is permitted by the rule.
Example: Consider the attribute Outlook with values {𝑆𝑢𝑛𝑛𝑦, 𝑂𝑣𝑒𝑟𝑐𝑎𝑠𝑡, 𝑅𝑎𝑖𝑛}.
• 100 represents the constraint 𝑂𝑢𝑡𝑙𝑜𝑜𝑘 = 𝑆𝑢𝑛𝑛𝑦.
• 011 represents the constraint 𝑂𝑢𝑡𝑙𝑜𝑜𝑘 = 𝑂𝑣𝑒𝑟𝑐𝑎𝑠𝑡 ∨ 𝑅𝑎𝑖𝑛.
• 111 represents a ”don’t care” condition (any value is allowed).
x 1 Genetic Algorithms and Evolutionary Computation

[Link] Encoding a Rule

A single rule is formed by concatenating the bit strings for all attributes, followed by the target classification
bit.
Example Rule: IF (Outlook = Rain) AND (Wind = Strong) THEN (PlayTennis = No) As-
suming Outlook has 3 values, Wind has 2 values {𝑆𝑡𝑟𝑜𝑛𝑔, 𝑊 𝑒𝑎𝑘 }, and PlayTennis is binary:
Outlook Wind PlayTennis
001 10 0
The resulting bit string for this rule is 001100.

[Link] Encoding a Rule Set

GABIL represents a set of rules by concatenating multiple rules into a single, longer bit string.

Hypothesis ℎ = Rule1 Rule2 . . . Rule𝑛

1.4.2 Genetic Operators in GABIL

GABIL employs standard selection and mutation, but it uses a specialized version of crossover to handle the
multi-rule structure.

[Link] Variable-Length Crossover

Since hypotheses can contain different numbers of rules, the bit strings can have different lengths. To ensure
offspring are semantically valid:
1. Pick a crossover point 𝑑1 in the first parent ℎ1 at any bit boundary.
2. Pick a crossover point 𝑑2 in the second parent ℎ2 such that 𝑑2 ≡ 𝑑1 (mod 𝐾), where 𝐾 is the length of a
single rule.
This ensures that the segments being swapped correspond to the same attribute positions within the rules,
preventing the ”slicing” of an attribute encoding.

1.4.3 Extension Operators

GABIL includes two specialized operators to perform generalization:

• AddAlternative: A randomly selected 0 bit is changed to 1. This generalizes the rule by adding a permitted
value to an attribute constraint.
• DropCondition: All bits for a chosen attribute in a rule are set to 1. This effectively removes the attribute
from the precondition, making the rule more general.
1.5 The Schema Theorem xi

1.4.4 Evolving the Learning Strategy

A unique feature of GABIL is that it can evolve its own learning parameters. Each hypothesis bit string can
be extended with two additional bits: AA (AddAlternative) and DC (DropCondition).
• If the AA bit is 1, the AddAlternative operator is permitted for this individual.
• If 0, the operator is disabled.
This allows the GA to discover which generalization operators are most effective for the specific dataset being
learned.

1.4.5 Fitness Function

The fitness of a rule set ℎ is defined based on its classification performance:

𝐹𝑖𝑡𝑛𝑒𝑠𝑠(ℎ) = (correct(ℎ)) 2

Squaring the accuracy provides a higher selective advantage to nearly perfect hypotheses, accelerating
convergence in the later stages of evolution.

1.4.6 Performance

Experimental results show that GABIL is competitive with symbolic learning methods. In a study of 12
synthetic problems:
• GABIL (Standard): 92.1% accuracy.
• GABIL (With AA/DC): 95.2% accuracy.
• C4.5/AQ14: Ranged from 91.2% to 96.6% accuracy.
Variable Length: Rule sets can have different numbers of rules. GABIL uses ”Semantically valid” crossover,
ensuring cuts only happen between full rules or specific attribute boundaries.

1.5 The Schema Theorem

A Schema 𝑠 represents a template. E.g., 1 ∗ 0 ∗ ∗ represents all strings with a 1 at pos 1 and a 0 at pos 3.
• Defining Length 𝑑 (𝑠): Distance between first and last fixed bits. (In 1 ∗ 0 ∗ ∗, 𝑑 (𝑠) = 3 − 1 = 2).
• Order 𝑜(𝑠): Number of fixed bits. (In 1 ∗ 0 ∗ ∗, 𝑜(𝑠) = 2).
The theorem proves that schemas with high fitness, short 𝑑 (𝑠), and low 𝑜(𝑠) survive and dominate the
population.
xii 1 Genetic Algorithms and Evolutionary Computation

1.6 Genetic Programming (GP)

Genetic Programming (GP) is a significant departure from standard Genetic Algorithms. Instead of searching
for optimal parameters within a fixed string, GP searches for an optimal executable program.

1.6.1 Representation: Programs as Trees

In GP, programs are represented as hierarchical tree structures. This allows the GA to explore hypotheses of
varying complexity and length.
• Functions (Internal Nodes): Arithmetic operators (+, ×), logical operators, or domain-specific functions.
• Terminals (Leaves): Constants or variables relevant to the problem.

1.6.2 GP Crossover: Subtree Swapping

Crossover in GP is performed by selecting a random node in each of two parent trees and swapping the entire
subtrees rooted at those nodes. This allows for the recombination of functional logic ”building blocks.”

[Link] TikZ Diagram: GP Crossover

The following TikZ code illustrates two parents swapping subtrees to produce a new offspring.

+ × +

Crossover
sin 5 𝑦 − sin 5

𝑥 𝑥 2 −

Parent 1 Parent 2 𝑥 Offspring

2

Fig. 1.1 GP Crossover: The subtree ( 𝑥 − 2) from Parent 2 replaces the node 𝑥 in Parent 1.
1.7 Biological Evolution and the Baldwin Effect xiii

1.6.3 GP Mutation

Mutation in GP involves selecting a random node and replacing the subtree rooted there with a completely
new, randomly generated subtree. This ensures the search does not prematurely converge on a local optimum
by introducing entirely new logic.

1.6.4 Evolutionary Success: The Block Problem

A primary example of GP’s power is the Block Problem. The objective is to find a program that stacks blocks
on a table to spell a target word (e.g., ”UNIVERSAL”).

• Terminals:
– CS (Current Stack): Top block on the arm’s stack.
– TB (Top Correct Block): The highest block currently in the correct sequence.
– NN (Next Necessary): The block required to follow TB.
• Functions:
– MS(x): Move block 𝑥 to the stack.
– MT(x): Move block 𝑥 to the table.
– DU(x, y): ”Do Until” loop—executes 𝑥 until 𝑦 returns True.

After several generations, GP discovered a general-purpose solution:

(EQ (DU (MT CS)(NOT CS)) (DU (MS NN)(NOT NN)))
This program is notable because it is not just a hard-coded sequence of moves; it is a generalized algorithm
capable of solving stacking problems of varying initial configurations.

1.6.5 Summary of Genetic Programming

Unlike traditional GAs that optimize static parameters, GP optimizes processes. It is uniquely suited for tasks
where the structure of the solution (the program’s logic) is unknown at the start.

1.7 Biological Evolution and the Baldwin Effect

Can individual learning affect evolution?

• Lamarckian: Traits learned during life are passed to offspring (False).
• Baldwin Effect: If individuals can learn, they can survive in environments where they would otherwise
die. This keeps their genes in the pool, allowing evolution to eventually ”hard-wire” that learned trait as
an instinct.
xiv 1 Genetic Algorithms and Evolutionary Computation

1.8 Summary

GAs are parallel, robust, and effective for complex optimization. They are particularly useful when the fitness
landscape is ”jagged” or when the learning task requires discovering structural logic (GP).