Skip to content
CampusPrep
AD-702 (C) · Computational Intelligence/Quick Revision Short Notes

Computational Intelligence (AD-702 (C)) - Unit 3 Short Notes

How unit 3 is examined

This unit covers the genetic algorithm from biological ideas to operators and benefits; no topic was asked in the supplied papers, so every topic is short but complete for a surprise question.

Basic Genetics, Concepts

<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. <mark>Genetics is the study of heredity, in which genes arranged on chromosomes carry traits from parents to offspring.</mark>

Key points.

  1. A gene is the basic unit of heredity, and the different values a gene can take are called its alleles.
  2. A chromosome is a string of genes, and the complete set of chromosomes of an individual is its genotype.
  3. The genotype determines the observable traits, called the phenotype, and natural selection favours the fitter phenotypes.
  4. In a genetic algorithm a chromosome is one candidate solution, a gene is one parameter or bit, and the population is the set of candidates.
Biology Genetic algorithm
Chromosome Candidate solution string
Gene One position (bit or value)
Allele Value of a gene, such as 0 or 1
Population Set of candidate solutions
Fitness Quality score of a solution

Working Principle

<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. <mark>A genetic algorithm is a search method that evolves a population of candidate solutions by selection, crossover and mutation, following survival of the fittest.</mark>

Key points.

  1. It starts from a random initial population and computes the fitness of each chromosome.
  2. Fitter parents are selected, and crossover and mutation create offspring that form the next generation.
  3. The cycle repeats until a stopping condition holds, such as a maximum number of generations or a satisfactory fitness.
  4. It needs only the fitness value and no derivatives, so it suits complex, non-linear search spaces.
Step 1: Initialise a random population.
Step 2: Evaluate the fitness of every chromosome.
Step 3: Select parents according to fitness.
Step 4: Apply crossover, then mutation, to make offspring.
Step 5: Form the new generation; repeat from Step 2 until the stop condition.

<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: Ini initial population, Fit fitness evaluation, Sel selection, Cro crossover, Mut mutation, Stop terminate"><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="ah3" 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="ahh3" 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="M59,40 L148,40" marker-end="url(#ah3)"/><path class="e" d="M188,40 L277,40" marker-end="url(#ah3)"/><path class="e" d="M317,40 L406,40" marker-end="url(#ah3)"/><path class="e" d="M427,59 L427,148" marker-end="url(#ah3)"/><path class="e" d="M410,160.5 L187.8,49.4" marker-end="url(#ah3)"/><path class="e" d="M169,59 L169,141" marker-end="url(#ah3)"/><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><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">Ini</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">Cro</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: Ini initial population, Fit fitness evaluation, Sel selection, Cro crossover, Mut mutation, Stop terminate</figcaption></figure>

Creation of Offspring

<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. <mark>Offspring are new chromosomes produced from selected parents by crossover and mutation, and together they form the next generation.</mark>

Key points.

  1. Two parents are picked by a selection function according to their fitness.
  2. Crossover mixes the genes of the parents to give one or two children.
  3. Mutation then alters a few genes of the children to add variety to the population.
  4. The children replace weaker members, and elitism may copy the best parent unchanged so that the best solution is never lost.

Example: parents 1100 and 0011 with a cut after two bits give children 1111 and 0000.

Encoding

<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. <mark>Encoding is the representation of a candidate solution as a chromosome string on which the genetic operators can act.</mark>

Key points.

  1. Binary encoding uses a string of 0s and 1s; for example, $x=13$ is 01101 in 5 bits, and it is the most common scheme.
  2. Real-value (value) encoding uses actual numbers as genes and suits continuous problems.
  3. Permutation encoding lists an order of items and suits ordering problems like the travelling salesman.
  4. A good encoding must be decodable and must keep the offspring from crossover and mutation valid.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-02" viewBox="0 0 355 130" width="355" height="130" role="img" aria-label="Common encoding schemes"><style>#dsfig-u3-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-02 .t{fill:#16181D;font-weight:500}#dsfig-u3-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-02 .dot{fill:#16181D}#dsfig-u3-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-02 .ah{fill:#454C5A}#dsfig-u3-02 .ah.hi{fill:#2340B8}#dsfig-u3-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-02 .e{stroke:#B1B7C3}html.dark #dsfig-u3-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-02 .t{fill:#E6E8ED}html.dark #dsfig-u3-02 .t.inv{fill:#0F1115}html.dark #dsfig-u3-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-02 .dot{fill:#E6E8ED}html.dark #dsfig-u3-02 .ann{fill:#8FA3FF}html.dark #dsfig-u3-02 .lbl{fill:#858D9C}html.dark #dsfig-u3-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-02 .ah{fill:#B1B7C3}html.dark #dsfig-u3-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-02 .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><line class="e" x1="155.8" y1="37" x2="47.5" y2="101"/><line class="e" x1="155.8" y1="37" x2="146" y2="101"/><line class="e" x1="155.8" y1="37" x2="264" y2="101"/><rect class="n" x="114.3" y="22" width="83" height="30" rx="8"/><text class="t" x="155.8" y="37" dy=".35em" text-anchor="middle">Encoding</text><rect class="n" x="14" y="86" width="67" height="30" rx="8"/><text class="t" x="47.5" y="101" dy=".35em" text-anchor="middle">Binary</text><rect class="n" x="97" y="86" width="98" height="30" rx="8"/><text class="t" x="146" y="101" dy=".35em" text-anchor="middle">Real-value</text><rect class="n" x="211" y="86" width="106" height="30" rx="8"/><text class="t" x="264" y="101" dy=".35em" text-anchor="middle">Permutation</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Common encoding schemes</figcaption></figure>

Fitness Function

<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. <mark>The fitness function assigns each chromosome a numerical score that measures how good it is as a solution.</mark>

Key points.

  1. It is derived from the objective function; for maximising $f(x)$, the fitness can be $f(x)$ itself.
  2. For minimisation a transform is used, such as $F(x)=\dfrac{1}{1+f(x)}$, so that smaller cost gives higher fitness.
  3. Higher fitness gives a higher chance of being selected as a parent.
  4. It should be fast to compute, since it is evaluated for every chromosome in every generation.

Example: for $f(x)=x^2$ and $x=13$, fitness is $13^2=169$.

Selection Functions

<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. <mark>A selection function chooses parent chromosomes from the population, giving fitter ones a higher probability.</mark>

Key points.

  1. Roulette wheel selection gives chromosome $i$ the probability $p_i=\dfrac{f_i}{\sum f_j}$.
  2. Tournament selection picks $k$ random chromosomes and takes the fittest of them.
  3. Rank selection ranks the chromosomes and selects by rank, which stops one very fit member dominating.
  4. Elitism carries the best chromosomes into the next generation unchanged.

Example: fitness 4, 6 and 10 has sum 20, so selection probabilities are 0.2, 0.3 and 0.5.

Genetic Operators-Reproduction

<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. <mark>Reproduction (selection) is the genetic operator that copies chromosomes into a mating pool in proportion to their fitness.</mark>

Key points.

  1. Above-average chromosomes get more copies in the mating pool, and weak ones may get none.
  2. The expected number of copies of chromosome $i$ is $f_i/\bar f$, where $\bar f$ is the average fitness.
  3. It creates no new strings; it only raises the average quality of the pool.
  4. The other two operators, crossover and mutation, create the new genetic material.

Example: with average fitness 5, a chromosome of fitness 10 gets 2 copies.

Crossover

<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. <mark>Crossover (recombination) exchanges parts of two parent chromosomes to produce offspring that inherit features of both.</mark>

Key points.

  1. In single-point crossover a cut point is chosen and the tails are swapped: parents 11001|10 and 01110|01 give 11001|01 and 01110|10.
  2. Two-point crossover swaps the segment between two cut points.
  3. Uniform crossover decides gene by gene, using a random mask, which parent supplies each gene.
  4. It is applied with a high crossover probability, typically 0.6 to 0.9.
P1: 11001|10      C1: 11001|01
P2: 01110|01      C2: 01110|10

Mutation

<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. <mark>Mutation randomly changes a gene of a chromosome, for example by flipping a bit, to keep diversity in the population.</mark>

Key points.

  1. In bit-flip mutation, 11001 with its third gene flipped becomes 11101.
  2. The mutation probability is kept very low, typically 0.001 to 0.05 per gene.
  3. It restores lost genes and helps the search escape local optima.
  4. Too high a rate turns the genetic algorithm into a random search.

Pitfall: Mutation is a rare, background operator; crossover is the main operator, so do not give mutation a high probability.

Genetic Modelling, Benefits

<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. <mark>Genetic modelling builds the GA for a problem by choosing the encoding, fitness function, operators and parameters, and schema theory explains why it works.</mark>

Key points.

  1. A schema is a template with fixed bits and wildcards, such as 1**0*; short, low-order, above-average schemata grow exponentially in number over generations.
  2. Benefits: the GA is robust, needs no derivatives, searches in parallel from many points, and handles non-linear and multi-modal problems.
  3. It gives good solutions for optimisation, scheduling and machine learning.
  4. Limits: it does not guarantee the global optimum, and its fitness evaluations can be costly.

Last-minute revision

  • Genetic algorithm: population-based search using selection, crossover and mutation.
  • Chromosome is a candidate solution; gene is one position; allele is a gene value.
  • Genotype is the encoded string; phenotype is the decoded solution.
  • Encodings: binary, real-value, permutation.
  • Roulette probability: $p_i=f_i/\sum f_j$.
  • Minimisation fitness: $1/(1+f(x))$.
  • Reproduction copies chromosomes to the mating pool by fitness; expected copies $f_i/\bar f$.
  • Single-point crossover swaps the tails after a cut point; typical probability 0.6 to 0.9.
  • Mutation is rare, roughly 0.001 to 0.05, and gives diversity.
  • Elitism keeps the best chromosome unchanged.
  • Stop on a maximum number of generations or an acceptable fitness.
  • Schema: template with wildcards; short, above-average schemata grow.

Memory hooks

  • Operators SCM: Selection picks, Crossover mixes, Mutation spices.
  • Fitness drives both selection and reproduction.
  • Roulette wheel: a bigger slice of fitness means a bigger chance.
  • Mutation is the pinch of salt: too much spoils the dish.
  • Encodings BRP: Binary, Real, Permutation.

Coverage checklist

  • Basic Genetics, Concepts: definition, gene, allele, genotype, phenotype, GA mapping table; no past questions.
  • Working Principle: definition, steps, cycle diagram; no past questions.
  • Creation of Offspring: parents, crossover, mutation, elitism; no past questions.
  • Encoding: binary, real-value, permutation; no past questions.
  • Fitness Function: maximise and minimise forms with example; no past questions.
  • Selection Functions: roulette, tournament, rank, elitism; no past questions.
  • Genetic Operators-Reproduction: mating pool and expected copies; no past questions.
  • Crossover: single-point, two-point, uniform with trace; no past questions.
  • Mutation: bit-flip and rate; no past questions.
  • Genetic Modelling, Benefits: schema, benefits and limits; no past questions.
Go to where you left off?

Quick Add to Notes

Save questions, your own notes and screenshots into notes filed by unit. It takes a free account.

Create free account

Have an account? Log in