Computational Intelligence (CS-702 (A)) Unit 3 Notes

How unit 3 is examined

This unit covers genetic algorithms end to end: biology borrowed, the GA cycle, encoding, fitness, selection, crossover, mutation, schema modelling and benefits. Encoding (crew-roster and techniques), the GA procedure, mutation with crossover, and advantages with disadvantages carry the marks.

Basic Genetics

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. Genetics is the study of heredity: how characteristics pass from parents to offspring through genes carried on chromosomes.

Key points.

A chromosome is a string of genes, and each gene controls one characteristic at a fixed position called its locus.
The values a gene can take are its alleles, and the gene set of an individual is its genotype, while the visible traits are its phenotype.
Offspring inherit half their chromosome material from each parent through crossover, and random changes called mutations add new traits.
Natural selection lets fitter individuals survive and breed, which is the idea a GA copies.

Concepts

Definition. A genetic algorithm is a population-based, probabilistic search and optimisation technique inspired by natural selection and genetics.

Key points.

A GA keeps a population of candidate solutions (chromosomes) instead of a single solution.
A fitness function scores each candidate, and better candidates get a higher chance of reproducing.
Crossover and mutation create new candidates, so the population improves over generations.
A GA uses only fitness values, not derivatives, so it works on discontinuous and noisy problems.

Working Principle

Definition. A GA starts with a random population and repeatedly applies evaluation, selection, crossover and mutation until a stopping condition is met.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-01" viewBox="0 0 474 209" width="474" height="209" role="img" aria-label="GA cycle: Init = initial population, Fit = fitness evaluation, Sel = selection, Xov = crossover, Mut = mutation, Stop = termination test"><style>#dsfig-u3-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-01 .t{fill:#16181D;font-weight:500}#dsfig-u3-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-01 .dot{fill:#16181D}#dsfig-u3-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-01 .ah{fill:#454C5A}#dsfig-u3-01 .ah.hi{fill:#2340B8}#dsfig-u3-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-01 .e{stroke:#B1B7C3}html.dark #dsfig-u3-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-01 .t{fill:#E6E8ED}html.dark #dsfig-u3-01 .t.inv{fill:#0F1115}html.dark #dsfig-u3-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-01 .dot{fill:#E6E8ED}html.dark #dsfig-u3-01 .ann{fill:#8FA3FF}html.dark #dsfig-u3-01 .lbl{fill:#858D9C}html.dark #dsfig-u3-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-01 .ah{fill:#B1B7C3}html.dark #dsfig-u3-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah4" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh4" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M66,40 L148,40" marker-end="url(#ah4)"/><path class="e" d="M188,40 L277,40" marker-end="url(#ah4)"/><path class="e" d="M317,40 L406,40" marker-end="url(#ah4)"/><path class="e" d="M427,59 L427,148" marker-end="url(#ah4)"/><path class="e" d="M410,160.5 L187.8,49.4" marker-end="url(#ah4)"/><path class="e" d="M169,59 L169,141" marker-end="url(#ah4)"/><g class="wl"><rect x="148.6" y="95.5" width="40.8" height="18" rx="9"/><text class="t" x="169" y="104.5" dy=".35em" text-anchor="middle">done</text></g><rect class="n" x="15" y="25" width="50" height="30" rx="15"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">Init</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">Fit</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">Sel</text><circle class="n" cx="427" cy="40" r="18"/><text class="t" x="427" y="40" dy=".35em" text-anchor="middle">Xov</text><circle class="n" cx="427" cy="169" r="18"/><text class="t" x="427" y="169" dy=".35em" text-anchor="middle">Mut</text><rect class="n" x="144" y="154" width="50" height="30" rx="15"/><text class="t" x="169" y="169" dy=".35em" text-anchor="middle">Stop</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">GA cycle: Init = initial population, Fit = fitness evaluation, Sel = selection, Xov = crossover, Mut = mutation, Stop = termination test</figcaption></figure>

Key points.

Initialise a random population of chromosomes, then compute the fitness of each one.
Select fitter parents, apply crossover with probability $p_c$ and mutation with probability $p_m$ to form the next generation, and repeat.
Terminate at a maximum generation count, a target fitness, or when fitness stops improving.
Representations (binary, real-valued, permutation) are explained with examples under Encoding.

Asked: [7 marks] (Nov 2023) Explain the procedures of genetic algorithms and what are the different genetic representations.

Creation of Offsprings

Definition. Offspring are created by selecting two parents, recombining them with crossover and then perturbing the child with mutation.

Key points.

Parents are picked by a selection method so that fitter individuals breed more often.
Crossover swaps parts of the parents' chromosomes to produce one or two children.
Mutation then flips or alters a few genes of each child with a small probability.
The children replace some or all of the old population, forming the next generation.

Encoding

Definition. <mark>Encoding is the method of representing a candidate solution as a chromosome, a string of genes over a chosen alphabet, so that GA operators can act on it.</mark>

Key points.

Binary encoding writes each chromosome as a string of 0s and 1s, for example 101100, and it is the simplest and most common form.
Octal encoding uses digits 0-7, for example 7205, and hexadecimal encoding uses 0-9 and A-F, for example 3F9A, and both give shorter strings than binary.
Permutation encoding uses an ordering of distinct items, for example 3 1 4 2 5, and suits ordering problems such as the travelling salesman problem.
Value (real) encoding uses real numbers, integers or characters directly as genes, for example 1.25 3.40 0.07, and suits parameter and weight optimisation.
Crossover and mutation must suit the encoding, because swapping genes in a permutation can repeat a city, so special operators are needed there.
Alphabet is the set of symbols a gene may take, and the chromosome length is the number of genes.

Example. Airline: 3 planes, 5 crews, one crew per plane per day, so a chromosome has 3 genes, one per plane, and each gene holds a crew ID.

Item	Answer
Chromosome	3 genes, for example `2 5 1` means plane 1 gets crew 2, plane 2 crew 5, plane 3 crew 1
Alphabet	crew identifiers $\{1,2,3,4,5\}$
Alphabet size	5

Repeats are illegal (one crew per plane per day), and the two-days-in-a-row rule is checked against yesterday's chromosome in the fitness or a penalty.

Answer frame. Open with the definition; for the techniques question, take points 1-4 as one example each, then point 5 on operator suitability; for the airline question, write chromosome, alphabet and size 5 in that order; close by naming the encoding chosen and why it fits.

Asked: [7 marks] (Nov 2023) A budget airline operates 3 planes and employs 5 cabin crews; one crew per plane per day, no crew more than two days in a row, all planes used daily. i) Suggest the chromosome representing an individual. ii) Suggest the alphabet and its size. Asked: [7 marks] (Nov 2023) Explain different Encoding Techniques available for Genetic Algorithms with help of examples.

Fitness Function

Definition. The fitness function assigns each chromosome a numeric score showing how good the solution it encodes is.

Key points.

It is the only link between the GA and the problem, so it is built from the objective function.
For maximisation, fitness can equal the objective $f(x)$; for minimisation, use $1/(1+f(x))$ or $f_{max}-f(x)$.
Constraint violations are handled by subtracting a penalty from fitness.
It must be cheap to compute, because it is evaluated for every individual in every generation.

Selection Functions

Definition. Selection chooses parents for reproduction, favouring high fitness while keeping some diversity.

Key points.

Roulette-wheel selection picks an individual with probability $p_i = f_i / \sum f_j$, so a fitter individual gets a larger slice of the wheel.
Tournament selection draws $k$ individuals at random and the fittest of them wins.
Rank selection ranks individuals and selects by rank, which avoids domination by one very fit individual.
Elitism copies the best individuals unchanged into the next generation.

Genetic Operators-Reproduction

Definition. Reproduction (selection) is the operator that copies chromosomes into a mating pool in proportion to their fitness.

Key points.

Above-average chromosomes get more copies in the mating pool and below-average ones get fewer or none.
Reproduction creates no new strings; it only increases the share of good ones.
Crossover and mutation are the operators that then explore new strings.
The three operators together are reproduction, crossover and mutation.

Crossover

Definition. Crossover recombines the genes of two parents to produce children that inherit features of both.

Key points.

Single-point crossover cuts both parents at one random point and swaps the tails: 1011|001 and 0100|110 give 1011110 and 0100001.
Two-point crossover swaps the segment between two cut points.
Uniform crossover picks each gene from either parent by a random mask.
It is applied with a crossover probability $p_c$, typically 0.6 to 0.9.

Mutation

Definition. <mark>Mutation is the random alteration of one or more genes of a chromosome with a small probability $p_m$, which restores lost diversity.</mark> Crossover is the recombination of two parent chromosomes, by exchanging segments at one or more cut points, to produce offspring.

Key points.

In binary strings mutation flips a bit, for example 1011001 becomes 1011101, and other types are swap, inversion and random resetting.
Mutation is rare, typically $p_m \approx 1/L$ for chromosome length $L$, so it does not destroy good solutions.
Crossover exploits existing good genes, while mutation explores new ones and prevents premature convergence.
Single-point crossover of 10|110 and 01|001 gives 10001 and 01110.

Asked: [7 marks] (Dec 2020) Define the term mutation and crossover used in Genetic Algorithm.

Genetic Modeling

Definition. Genetic modelling explains GA behaviour mathematically, mainly through Holland's schema theorem.

Key points.

A schema is a template over $\{0,1,*\}$ such as 1*0*, where * matches either bit.
Order $o(H)$ is the number of fixed positions and defining length $\delta(H)$ is the distance between the first and last fixed positions.
Schema theorem: $E[m(H,t+1)] \ge m(H,t)\,\frac{f(H)}{\bar f}\left[1 - p_c\frac{\delta(H)}{L-1} - o(H)\,p_m\right]$.
Short, low-order, above-average schemata (building blocks) receive exponentially more copies in later generations.

Benefits

Definition. The benefits of a GA are its ability to search large, complex spaces for good solutions without needing derivative information.

Key points.

Advantages: it searches globally, needs no gradient, handles discontinuous and multimodal functions, and works with discrete and continuous variables.
It is parallel by nature and gives a set of good solutions, not just one.
Disadvantages: convergence can be slow, many fitness evaluations are costly, and parameters such as population size, $p_c$ and $p_m$ need tuning.
It gives no guarantee of the global optimum and may converge prematurely; suitable applications are scheduling, routing, design and machine-learning tuning.

Asked: [7 marks] (Dec 2020) Write various advantages and disadvantages of Genetic Algorithm.

Last-minute revision

A GA is a population-based search inspired by natural selection.
Chromosome = string of genes; allele = gene value; locus = gene position.
Cycle: initialise, evaluate fitness, select, crossover, mutate, test termination.
Encodings: binary, octal, hexadecimal, permutation, value.
Airline question: chromosome length 3, alphabet is crew IDs 1-5, size 5.
Roulette-wheel probability is $p_i = f_i/\sum f_j$.
Reproduction copies strings by fitness; it creates nothing new.
Single-point crossover swaps tails after a random cut.
Mutation flips bits with small $p_m$ and keeps diversity.
Schema theorem favours short, low-order, above-average schemata.
Disadvantages: slow, tuning needed, no guarantee of the optimum.

Memory hooks

GA cycle: "I Find Some Cute Mates" (Initialise, Fitness, Select, Crossover, Mutate).
Encodings: "B-O-H-P-V", binary, octal, hex, permutation, value.
Crossover exploits, mutation explores.
Schema: short, low, above average, meaning "SLA".

Coverage checklist

Basic Genetics: no past questions.
Concepts: no past questions.
Working Principle: GA procedure and representations (Nov 2023).
Creation of Offsprings: no past questions.
Encoding: airline chromosome and alphabet (Nov 2023); encoding techniques (Nov 2023).
Fitness Function: no past questions.
Selection Functions: no past questions.
Genetic Operators-Reproduction: no past questions.
Crossover: covered with Mutation question (Dec 2020).
Mutation: define mutation and crossover (Dec 2020).
Genetic Modeling: no past questions.
Benefits: advantages and disadvantages (Dec 2020).

Account

Computational Intelligence (CS-702 (A)) - Unit 3 Short Notes

How unit 3 is examined

Basic Genetics

Concepts

Working Principle

Creation of Offsprings

Encoding

Fitness Function

Selection Functions

Genetic Operators-Reproduction

Crossover

Mutation

Genetic Modeling

Benefits

Last-minute revision

Memory hooks

Coverage checklist