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

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

How unit 5 is examined

This unit covers swarm intelligence and its main techniques; Ant Colony Optimization carries the marks (14 marks), while PSO, Bee Colony and the fuzzy-logic application each came as a 7-mark question.

Introduction to Swarm Intelligence

<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>Swarm intelligence is the collective, decentralised and self-organised behaviour of many simple agents that interact locally with each other and with their environment, so that useful global behaviour emerges without any central controller.</mark>

Key points.

  1. Each agent is simple and follows local rules, yet the group solves hard tasks such as finding the shortest path to food.
  2. Control is decentralised and behaviour is self-organised, so there is no leader and no agent knows the whole problem.
  3. Agents communicate directly or indirectly through the environment, which is called stigmergy (ants leave pheromone).
  4. Swarm systems are robust, scalable and flexible: losing some agents does not stop the system.
  5. Examples are ant colonies, bird flocks, fish schools and bee hives; the main algorithms are ACO, PSO and ABC.

Swarm Intelligence Techniques: Ant Colony Optimization

<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">High weight</span>

Definition. <mark>Ant Colony Optimization (ACO) is a population-based metaheuristic, inspired by ants finding shortest paths to food using pheromone trails, in which artificial ants build solutions step by step using probabilistic choice guided by pheromone and heuristic information.</mark>

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u5-01" viewBox="0 0 338 338" width="338" height="338" role="img" aria-label="Ants from Nest (N) to Food (F): the short path via S gets pheromone faster than the long path via L"><style>#dsfig-u5-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u5-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u5-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u5-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u5-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u5-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u5-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u5-01 .t{fill:#16181D;font-weight:500}#dsfig-u5-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u5-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u5-01 .dot{fill:#16181D}#dsfig-u5-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u5-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u5-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u5-01 .ah{fill:#454C5A}#dsfig-u5-01 .ah.hi{fill:#2340B8}#dsfig-u5-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u5-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u5-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u5-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u5-01 .e{stroke:#B1B7C3}html.dark #dsfig-u5-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u5-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u5-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u5-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u5-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u5-01 .t{fill:#E6E8ED}html.dark #dsfig-u5-01 .t.inv{fill:#0F1115}html.dark #dsfig-u5-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u5-01 .dot{fill:#E6E8ED}html.dark #dsfig-u5-01 .ann{fill:#8FA3FF}html.dark #dsfig-u5-01 .lbl{fill:#858D9C}html.dark #dsfig-u5-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u5-01 .ah{fill:#B1B7C3}html.dark #dsfig-u5-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u5-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u5-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u5-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah7" 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="ahh7" 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="M53.4,155.6 L154.2,54.8" marker-end="url(#ah7)"/><path class="e" d="M182.4,53.4 L283.2,154.2" marker-end="url(#ah7)"/><path class="e" d="M53.4,182.4 L154.2,283.2" marker-end="url(#ah7)"/><path class="e" d="M182.4,284.6 L283.2,183.8" marker-end="url(#ah7)"/><g class="wl"><rect x="81" y="95.5" width="47.1" height="18" rx="9"/><text class="t" x="104.5" y="104.5" dy=".35em" text-anchor="middle">short</text></g><g class="wl"><rect x="210" y="95.5" width="47.1" height="18" rx="9"/><text class="t" x="233.5" y="104.5" dy=".35em" text-anchor="middle">short</text></g><g class="wl"><rect x="84.1" y="224.5" width="40.8" height="18" rx="9"/><text class="t" x="104.5" y="233.5" dy=".35em" text-anchor="middle">long</text></g><g class="wl"><rect x="213.1" y="224.5" width="40.8" height="18" rx="9"/><text class="t" x="233.5" y="233.5" dy=".35em" text-anchor="middle">long</text></g><circle class="n" cx="40" cy="169" r="18"/><text class="t" x="40" y="169" dy=".35em" text-anchor="middle">N</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">S</text><circle class="n" cx="169" cy="298" r="18"/><text class="t" x="169" y="298" dy=".35em" text-anchor="middle">L</text><circle class="n" cx="298" cy="169" r="18"/><text class="t" x="298" y="169" dy=".35em" text-anchor="middle">F</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Ants from Nest (N) to Food (F): the short path via S gets pheromone faster than the long path via L</figcaption></figure>

Key points.

  1. Real ants leave a chemical called pheromone on the ground while walking, and other ants prefer to follow stronger trails.
  2. Ants on the shorter path return sooner, so the short path is reinforced more often; this positive feedback makes almost all ants use it.
  3. Pheromone evaporates with time, so poor paths fade and the colony forgets bad choices; this avoids early convergence to a poor route.
  4. An artificial ant at node $i$ chooses the next node $j$ with probability depending on pheromone $\tau_{ij}$ and heuristic desirability $\eta_{ij}$ (usually $1/d_{ij}$).
  5. After all ants finish a tour, pheromone is evaporated and then deposited in proportion to the quality of each tour.
  6. The process repeats for many iterations until the maximum iterations are reached or the best solution stops improving.

Formula. $$P_{ij}=\frac{[\tau_{ij}]^{\alpha}[\eta_{ij}]^{\beta}}{\sum_{k\in allowed}[\tau_{ik}]^{\alpha}[\eta_{ik}]^{\beta}}$$ $$\tau_{ij}\leftarrow(1-\rho)\,\tau_{ij}+\sum_{m=1}^{M}\Delta\tau_{ij}^{m},\qquad \Delta\tau_{ij}^{m}=\frac{Q}{L_m}$$ Here $\alpha,\beta$ weight pheromone and heuristic, $\rho$ is the evaporation rate, $Q$ a constant and $L_m$ the tour length of ant $m$.

Steps.

Step 1: Initialise pheromone tau_ij on every edge to a small constant and set parameters (alpha, beta, rho, Q, number of ants).
Step 2: Place each ant on a start node.
Step 3: Each ant builds a complete solution (tour) by choosing next nodes with probability P_ij, never revisiting a node.
Step 4: Compute the length L_m of every tour and keep the best one.
Step 5: Update pheromone: evaporate all edges, then deposit Q/L_m on edges used by each ant.
Step 6: Repeat Steps 2-5 until the stopping criterion is met; output the best tour.

Why ACO is used for optimization.

  1. Positive feedback quickly reinforces good solutions, while evaporation gives negative feedback and keeps exploration alive.
  2. It is distributed and parallel, since every ant works independently, and it is robust because losing ants does not break the search.
  3. It suits combinatorial problems such as the travelling salesman problem, vehicle routing, scheduling and network routing, where exact methods are too slow.
  4. It adapts to dynamic changes such as a changed network, because pheromone keeps being updated.

Answer frame. Open with the definition and the real-ant pheromone behaviour; draw the nest-food two-path figure; then develop points 1-6, the formula, and the six steps; then write the four "why used" points as the second half of the 14 marks; close with "ACO is therefore well suited to combinatorial problems like TSP."

Pitfall: Answering only the algorithm and skipping the second part of the question, "why ACO is used", loses about half the marks.

Asked: [14 marks] (Dec 2020) Explain Ant colony optimization techniques and discuss why Ant colony techniques used for optimization.

Particle Swarm Optimization

<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">Low weight</span>

Definition. <mark>Particle Swarm Optimization (PSO) is a population-based optimisation technique, inspired by bird flocking, in which each particle is a candidate solution that moves through the search space with a velocity adjusted by its own best position (pbest) and the swarm's best position (gbest).</mark>

Key points.

  1. Each particle has a position $x$ and velocity $v$; its personal best position pbest is the best it has visited, and gbest is the best found by the whole swarm.
  2. Velocity and position are updated every iteration by the formulas below.
  3. $w$ is the inertia weight, $c_1,c_2$ are acceleration constants, and $r_1,r_2$ are random numbers in $[0,1]$.
  4. The algorithm stops when the maximum iterations are reached, or gbest no longer improves, or the error is small enough.

Formula. $$v_i(t+1)=w\,v_i(t)+c_1r_1\,(pbest_i-x_i(t))+c_2r_2\,(gbest-x_i(t))$$ $$x_i(t+1)=x_i(t)+v_i(t+1)$$

Example. Minimise $f(x)=x^2$ with two particles, $x_1=4$, $x_2=-3$, $v=0$, $w=0.5$, $c_1=c_2=1$. Initially pbest = position, so gbest = $-3$ (f = 9). Take $r_1=0.5,r_2=0.3$ for particle 1.

Particle Velocity update New v New x f(x)
1 $0.5(0)+0.5(0)+0.3(-3-4)$ -2.1 1.9 3.61 (better than 16, pbest = 1.9)
2 (r=0.4, 0.6) $0+0.4(0)+0.6(-3-(-3))$ 0 -3 9 (unchanged)

Result: gbest becomes 1.9 (f = 3.61); the swarm moves towards the minimum at 0 in the next iteration.

Answer frame. Open with the definition; write the two formulas; list the algorithm steps (initialise, evaluate, update pbest and gbest, update v and x, repeat); show the one-iteration table; close with the stopping criteria.

Asked: [7 marks] (Nov 2023) Explain the working of Particle Swarm Optimization (PSO Algorithm) with suitable help of example.

Bee Colony Optimization etc.

<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">Low weight</span>

Definition. <mark>Artificial Bee Colony (ABC) optimization is a swarm technique, inspired by honey-bee foraging, in which food sources are candidate solutions and the quality (nectar amount) of a source is its fitness.</mark>

Key points.

  1. Employed bees are each attached to one food source, and they search its neighbourhood for a better one.
  2. Onlooker bees wait in the hive, watch the employed bees' dances and choose sources with probability proportional to fitness, which exploits good sources.
  3. Scout bees replace a source that has not improved for a set limit with a random new one, which provides exploration.
  4. Steps: initialise food sources; employed-bee phase; onlooker phase; scout phase; memorise the best source; repeat until the stop criterion.
  5. Onlookers give exploitation and scouts give exploration, so the algorithm balances the two.

Formula. New candidate: $v_{ij}=x_{ij}+\phi_{ij}(x_{ij}-x_{kj})$, with $\phi\in[-1,1]$ and $k$ a random other source.

Answer frame. Open with the definition; list the three bee roles; give the four phases in order; close with the exploration-exploitation balance.

Asked: [7 marks] (Dec 2020) Explain Bee colony optimization techniques.

Applications of Computational Intelligence

<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">Low weight</span>

Definition. <mark>Fuzzy logic control uses linguistic IF-THEN rules to turn imprecise inputs into smooth control actions, which suits machines such as automobiles where exact models are hard.</mark>

Key points.

  1. Fuzzy control has four stages: fuzzification converts crisp sensor values into membership degrees, the rule base holds IF-THEN rules, inference combines fired rules, and defuzzification gives a crisp output.
  2. ABS braking: inputs are wheel slip and speed, and rules such as "IF slip is high THEN reduce brake pressure" prevent wheel locking.
  3. Engine control: fuzzy rules on throttle, speed and temperature adjust fuel and ignition for economy and low emission.
  4. Automatic transmission chooses the gear from vehicle load, speed and throttle, and climate control adjusts fan and cooling from temperature and humidity.
  5. Benefits: it handles nonlinear systems without an exact mathematical model, uses human-like linguistic rules, and is cheap and robust to noisy sensors.

Answer frame. Open with the definition; draw the block Input, Fuzzifier, Inference with rule base, Defuzzifier, Output; develop the four automobile examples; close with the benefits.

Asked: [7 marks] (Dec 2020) Explain in detail how fuzzy logic can be used in Automobile Industry.

Last-minute revision

  • Swarm intelligence is decentralised, self-organised collective behaviour of simple agents.
  • Stigmergy means indirect communication through the environment, such as pheromone.
  • ACO probability: $P_{ij}=\tau^\alpha\eta^\beta/\sum\tau^\alpha\eta^\beta$.
  • ACO pheromone update: $\tau\leftarrow(1-\rho)\tau+\sum Q/L_m$.
  • ACO suits TSP and routing because of positive feedback and distributed search.
  • PSO velocity: $wv+c_1r_1(pbest-x)+c_2r_2(gbest-x)$; position: $x+v$.
  • PSO stops at maximum iterations or when gbest stops improving.
  • ABC has three bees: employed, onlooker, scout.
  • Scouts explore, onlookers exploit.
  • Fuzzy control stages: fuzzification, rules, inference, defuzzification.
  • Automobile uses: ABS, engine control, transmission, climate control.

Memory hooks

  • ACO: "Ants Choose Optimal" paths by pheromone; evaporation forgets.
  • PSO velocity has three pulls: Past (inertia), Personal (pbest), Public (gbest).
  • ABC: Employed work, Onlookers watch, Scouts wander.
  • Fuzzy control order: F-R-I-D (fuzzify, rules, infer, defuzzify).

Coverage checklist

  • Introduction to Swarm Intelligence: definition and key points (no past question).
  • Swarm Intelligence Techniques: Ant Colony Optimization: Q1 (14 marks, Dec 2020).
  • Particle Swarm Optimization: Q4 (7 marks, Nov 2023).
  • Bee Colony Optimization etc.: Q3 (7 marks, Dec 2020).
  • Applications of Computational Intelligence: Q2 (7 marks, Dec 2020).
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