CHAPTER 6 - Computational Intelligence

Computational Intelligence

CI

CI

nature-inspired computing approaches that enable systems to learn from data, adapt, make intelligent decisions. Handles uncertainty, imprecision, incomplete information - unlike rule based AI. Emphasizes learning, adaptation, self organization, evolutionary computation

Neural Networks

Historical Background of Computational Intelligence. 1940s: (McCulloch & Pitts)

Neural Networks

Historical Background of Computational Intelligence. 1960-1970s: (Emergence of Evolutionary Algorithms)

Swarm Intelligence and Fuzzy Logic

Historical Background of Computational Intelligence. 1980-1990s

ML, DL

Historical Background of Computational Intelligence. 2000s to present: Integration with __ and __

strict logic

"Historically, CI developed as researchers sought methods to handle complex, nonlinear problems—those that couldn't be solved with ______ _____ or classical computation."

Neural networks, fuzzy logic, evolutionary computation, swarm intelligence, heuristic and metaheuristic search

5 major paradigms of CI (NFESH). These paradigms are not isolated they often integrate

Neural Networks (NN)

major paradigm of CI. Learn from data by adjusting weights.

Fuzzy Logic (FL)

major paradigm of CI. Models uncertainty using degrees of truth.

Evolutionary Computation (EC)

major paradigm of CI. Mimics natural evolution.

Swarm Intelligence (SI)

major paradigm of CI. Models collective behavior of agents.

Heuristic and Metaheuristic Search

major paradigm of CI. Uses guided search strategies for problem solving.

Ill-defined, nonlinear, uncertain, mathematical, adapts, large, optimization

Why Computational Intelligence is needed?

1. Handles ___-_______, _________, and _________ problems.

2. Does not require exact ____________ models.

3. ______ and learns in real-time.

4. Efficient in _____ search spaces.

5. High performance in ____________ and classification problems.

Hybrid systems

combine the strengths of multiple CI paradigms — examples are Neuro-Fuzzy and Genetic-Fuzzy systems

Symbolic AI vs CI

symbolic AI uses explicit models — CI uses experiential learning and optimization

Applications of CI

healthcare diagnostics, robotics and autonomous systems, energy optimization and smart grids, financial forecasting and fraud detection, supply chain and logistics optimization, natural language and image processing

Optimization

finding the best solution among many possible solutions

Formal definition of optimization

minimize f(x) subject to constraints g(x)

Objective function f(x)

the goal you want to minimize (or maximize) in an optimization problem

Constraints g(x)

the rules a solution must follow to be valid

Search space

all the possible choices (values of x) that can be checked

Continuous optimization

variables take real-valued (decimal) numbers

Discrete optimization

variables are distinct choices — such as picking from a list or yes/no decisions

Unconstrained optimization

no rules limit the solution — any point in the search space is allowed

Constrained optimization

solutions must satisfy rules (constraints) to be valid

Single-objective optimization

only one goal is optimized

Multi-objective optimization

two or more goals are optimized at the same time

Convex optimization

only one valley (a single optimum) — easy to find the bottom

Non-convex optimization

many valleys and hills (many local optima) — harder to solve

Global optimum

the best solution in the entire search space

Local optimum

a solution better than its neighbors but not the best overall — traditional methods get stuck here

Exploration

trying new areas of the search space to escape local optima — CI aims to escape local optima this way

Exploitation

using what is already known to be good — such as mixing good parents through crossover

Work

total fitness evaluations (total operations = sequential time) — work-efficient algorithms avoid extra useless work

Span

the longest dependence chain — the time taken with infinite processors

Parallelism

work divided by span (work/span)

Fitness evaluation

the most expensive (work-heavy) GA step — can be parallelized

Genetic Algorithms (GAs)

search and optimization methods inspired by Darwinian evolution. Solutions evolve using operators like selection, crossover, and mutation

John Holland

proposed Genetic Algorithms in 1975

Survival of the fittest, inheritance, variation, mutation

key ideas of Genetic Algorithms

Selection, crossover, mutation

3 main operators used to evolve solutions in a GA

Uses of GA

function optimization, scheduling, Traveling Salesman Problem, feature selection, neural network optimization — all are optimization problems

Population

the set of potential solutions (chromosomes) that a GA evolves over generations

Chromosome

a complete candidate solution

Gene

smallest unit (variable) of a chromosome

Initialization, Evaluation, Selection, Crossover, Mutation, Replacement, Termination

7 steps of the GA workflow in order. (IESCMRT). Loop steps 2-6 until termination — output best chromosome

Initialization

GA workflow step 1. Generate random population of solutions

Evaluation

GA workflow step 2. Compute fitness for each solution

Selection

GA workflow step 3. Select best individuals based on fitness

Crossover (Recombination)

GA workflow step 4. Exchange information between parents

Mutation

GA workflow step 5. Randomly alter some genes to maintain diversity

Replacement

GA workflow step 6. Form a new generation

Termination

GA workflow step 7. Stop when maximum generations or target fitness achieved

Binary, real-valued, permutation

3 representation types / encoding methods

Binary encoding

chromosome is a string of 1s and 0s — simple and used in theoretical models, such as knapsack yes/no

Real-valued encoding

chromosome holds continuous values — faster convergence and higher precision, such as sensor coordinates

Permutation encoding

chromosome is an ordered sequence — used for routing/scheduling and needs specialized crossover like OX

Population size

affects exploration — larger gives better coverage but is slower, smaller is faster but may miss the global optimum

Fitness function

mathematical formulation evaluating solution quality — the guiding force of the GA. Problem-specific design is the most important. Determines selection probability

Higher fitness

means a better solution quality (or lower if minimization via inverse)

Goal of selection

prefer individuals with higher fitness. Simulates survival of the fittest

Roulette wheel, tournament, rank

3 common techniques for GA Selection operation

Roulette Wheel Selection (Fitness Proportionate Selection)

probability of being selected is proportional to fitness (Probability ∝ fitness value)

Steps of Roulette Wheel Selection

Step 1 compute total fitness — Step 2 compute probability (P_i = f_i / F_total) — Step 3 compute cumulative probability — Step 4 spin the wheel (generate random number r in [0,1])

Premature convergence

population becomes too similar too quickly and gets stuck in a local optimum — roulette wheel selection is prone to it when one fitness dominates

Tournament Selection

randomly select k individuals and pick the best among them — repeat until you have enough parents

Tournament size (k)

number of individuals competing in one tournament — larger k means higher selection pressure and faster convergence, smaller k keeps more diversity

Rank Selection

rank individuals (1 = worst, n = best) then assign probability based on rank (Rank / Total Ranks) — avoids domination by very fit individuals and maintains diversity

Single point, two-point, uniform, order

4 common techniques for GA Crossover operation

Crossover

produces new offspring by mixing genes of parents and encourages exploration of new areas

Crossover rate

chance that crossover is applied to a pair of parents — usually 70-90%, otherwise parents are copied directly

Single Point Crossover

one crossover point is randomly chosen — genes before the point come from Parent 1 and genes after the point from Parent 2. Two offspring are created by exchanging segments after the point

Two-Point Crossover

two points are randomly selected — the genes between the two points are swapped between parents. Mixes larger gene segments for more diversity

Uniform Crossover

each gene in the offspring is chosen randomly from either parent with equal probability — a random mask decides (1 = take from P1, 0 = take from P2) and child 2 takes the opposite parent at each position. Highest diversity

Order (OX) Crossover

preserves relative order of genes from parents — copy a segment from Parent 1 then fill the remaining positions from Parent 2 in order, skipping duplicates. Always gives a valid permutation

Partially Mapped Crossover (PMX)

crossover for permutations that maintains valid tours (no duplicate genes)

Arithmetic crossover

blends parent values to make the child (for example averaging colors or positions) — used for real-valued chromosomes

Mutation

introduces random changes in an individual's chromosome. Helps the GA maintain diversity in the population and avoid premature convergence (getting stuck in a local optimum)

Bit-flip, swap, scramble, Gaussian

4 common mutation types

Bit-Flip Mutation

randomly flips bits (0 → 1 or 1 → 0) — used for binary chromosomes

Swap Mutation

swaps positions of two genes — used for permutation chromosomes because it never creates duplicates

Scramble Mutation

randomly rearranges a subset of genes — a bigger change than swap, still a valid permutation

Inversion Mutation

reverses a segment of genes — used for permutation chromosomes

Gaussian Mutation

adds small random noise to real-valued genes — creates new values never seen before

Mutation rate

probability that a gene mutates — kept very low (typically 0.001 to 0.05) so good solutions are kept

Elitism / Replacement

strategy that ensures the best individuals (chromosomes) from the current generation are copied directly into the next generation without modification. Guarantees the best fitness never decreases

N and E

in elitism, N = population size and E = number of elites

How elitism works

sort population by fitness (highest to lowest) — copy the top E individuals directly to the next generation — fill the remaining N − E spots with offspring from crossover and mutation

Too many elites

the population fills with copies of the same elites — loses diversity and causes premature convergence

Termination

the stopping condition. It is the point when the algorithm decides that further evolution will not significantly improve the solution

Maximum generations reached, fitness threshold achieved, no improvement (convergence), time limit reached, manual termination

5 common termination criteria

Maximum Generations Reached

stop when a preset number of generations have been produced

Fitness Threshold Achieved

stop when the best fitness value is good enough (meets or exceeds a target)

No Improvement (Convergence)

stop if fitness doesn't improve for a number of generations

Time Limit Reached

stop if the algorithm has run for a set duration

Manual Termination

human stops the GA based on inspection

Fitness threshold vs convergence

threshold stops because the result is good enough even if still improving — convergence stops because the search is stuck even if the target was not reached

Traveling Salesman Problem (TSP)

given a list of cities and the distances between each pair, find the shortest possible route that visits every city exactly once and returns to the starting point

GA setup for TSP

representation: permutation of cities — fitness: f = 1 / total distance — selection: tournament or roulette wheel — crossover: OX or PMX — mutation: swap or inversion — termination: convergence