Summarized_Chapter 6_Computational Intelligence

Computational Intelligence (CI)

• Nature-inspired computing approaches that enable systems to learn from data, adapt, and make intelligent decisions.

• Handles uncertainty, imprecision, and incomplete information (unlike rule-based AI).

• Emphasizes learning, adaptation, self-organization, and evolutionary computation.

• Needed because it handles ill-defined, nonlinear, and uncertain problems;

• does not require exact mathematical models;

• adapts and learns in real time;

• is efficient in large search spaces;

• and performs well in optimization and classification problems.

Neural Networks (NN)

Learn from data by adjusting weights.

Fuzzy Logic (FL)

Models uncertainty using degrees of truth.

Evolutionary Computation (EC)

Mimics natural evolution.

Swarm Intelligence (SI)

Models the collective behavior of agents.

Heuristic and Metaheuristic Search

Uses guided search strategies for problem solving.

Optimization

• Find the best solution among many;

• the heart of CI.

• Formal definition: minimize f(x) subject to constraints g(x) ≤ 0, x in the search space.

Global vs Local Optimum

CI aims to escape a local optimum via exploration to reach the global optimum.

Work

• Total fitness evaluations (Blelloch work-efficient goal);

• a measure of optimization.

Span

• Longest dependence chain;

• a measure of optimization.

DRR Objective

Example optimization objective: minimize evacuation time + flood risk penalty.

Genetic Algorithms (GAs)

• Search and optimization methods inspired by Darwinian evolution.

• Proposed by John Holland in 1975.

• Key ideas: survival of the fittest, inheritance, variation, and mutation.

• Solutions evolve using the operators selection, crossover, and mutation.

Initialization (GA Step)

Generate a random population of solutions.

Evaluation (GA Step)

Compute fitness for each solution.

Replacement (GA Step)

Form a new generation.

Chromosome

A complete candidate solution.

Gene

The smallest unit (variable) of a chromosome.

Binary Representation

• Encoding such as 10110010;

• simple, used in theoretical models,

• e.g., knapsack yes/no.

Real-Valued Representation

• Encoding such as [1.2, 3.4];

• continuous, faster convergence, higher precision,

• e.g., sensor coordinates.

Permutation Representation

• Encoding such as [2, 3, 1, 5, 4];

• ordered sequences for routing/scheduling;

• needs specialized OX crossover.

Population

• P(t) at generation t contains chromosomes: P(t) = {C₁, C₂, C₃, …, Cₙ}.

• Randomly generated initially.

• Its size affects exploration: larger → better coverage but slower;

• smaller → faster but may miss the global optimum.

Fitness Function

• Mathematical formulation evaluating solution quality;

• the guiding force.

• A higher value = a better solution (or lower, if minimization is handled via the inverse).

• Problem-specific design is the most important part.

• Determines selection probability.

• Minimization problem (e.g., shortest route, minimal error): f(Cᵢ) = 1 / cost(Cᵢ).

• Maximization problem (e.g., profit, score): f(Cᵢ) = value(Cᵢ).

• Examples: TSP – total distance of route (smaller = better);

• Knapsack – total profit without exceeding capacity.

Selection

Goal: prefer individuals with higher fitness.

Roulette Wheel Selection (Fitness Proportionate Selection)

• Selection probability is proportional to fitness (Probability ∝ fitness value);

• Pᵢ = fᵢ / F_total.

• Steps: compute total fitness, compute probability, compute cumulative probability, spin the wheel (random number r in [0, 1]).

• Chromosomes with higher fitness are more likely to be chosen.

• Example: A = 10, B = 20, C = 10 (F_total = 40) gives P = 0.25, 0.50, 0.25 and cumulative 0.25, 0.75, 1.00;

• r = 0.6 → since 0.25 < 0.6 ≤ 0.75, chromosome B is selected.

Tournament Selection

• Randomly select k individuals, pick the best (highest fitness) among them, and repeat until there are enough parents.

• Example: k = 3, fitness A = 10, B = 25, C = 35, D = 40, E = 15;

• group {A, C, D} → D (40);

• group {B, C, E} → C (35);

• selected parents are D and C.

Rank Selection

• Rank individuals and assign probability based on rank.

• Steps: sort by fitness lowest → highest, assign ranks (1 = worst, n = best), compute probability = rank / total ranks, spin the wheel like roulette using rank probabilities.

• Example: A = 10 (rank 1, 0.1), B = 20 (rank 2, 0.2), C = 30 (rank 3, 0.3), D = 40 (rank 4, 0.4);

• r = 0.23 falls in 0.10–0.30, so chromosome B is selected.

Crossover

• Produces new offspring by mixing genes of parents (also called recombination);

• exchanges information between parents.

• Encourages exploration of new areas.

Single-Point Crossover

• One point is randomly chosen on the parent chromosomes;

• genes before that point come from Parent 1 and genes after it come from Parent 2.

• Two offspring are created by exchanging segments after the point.

• Example: P1 = 11001101, P2 = 10101011, point = 4 → Child 1 = 1100 + 1011 = 11001011; Child 2 = 1010 + 1101 = 10101101.

Two-Point Crossover

• Two points are randomly selected and the genes between them are swapped between parents.

• Example: P1 = 11001101, P2 = 10101011, points 3 and 6 → Child 1 = 110 (P1) + 010 (P2) + 01 (P1) = 11001001; Child 2 = 101 (P2) + 011 (P1) + 11 (P2) = 10101111.

Uniform Crossover

• Each gene in the offspring is chosen randomly from either parent with equal probability, using a random mask: take “1” from P1 and “0” from P2 to build Child 1;

• Child 2 is the complement of Child 1. Example: P1 = 11001101, P2 = 10101011, mask = 10110010 → Child 1 = 10001001; Child 2 = 01110110.

Order (OX) Crossover

• Preserves the relative order of genes from the parents (used for permutations).

• Steps: copy a segment of genes from Parent 1, then fill the remaining positions from Parent 2 in order, skipping duplicates.

• Example: P1 = [1, 2, 3, 4, 5], P2 = [3, 5, 4, 1, 2]; copy genes 2, 3, 4 from P1 → [, 2, 3, 4, ];

• fill from P2 with [5, 1] → Child 1 = [5, 2, 3, 4, 1]; same process for Child 2 = [2, 5, 4, 1, 3].

Mutation

• Introduces random changes in an individual’s chromosome (randomly alters some genes).

• Helps the GA maintain diversity in the population.

• Avoids premature convergence (getting stuck in a local optimum).

Bit-Flip Mutation

• Randomly flips bits (0 → 1 or 1 → 0).

• Example: C1 = 10110010, rate = 0.125 (12.5%),

• 3rd bit chosen and flipped → 10010010.

Swap Mutation

• Swaps positions of two genes.

• Example: [A, B, C, D, E], positions 1 and 4 swapped → [D, B, C, A, E].

Scramble Mutation

• Randomly rearranges a subset of genes.

• Example: [1, 2, 3, 4, 5, 6, 7, 8], positions 3 to 6 rearranged as [5, 3, 6, 4] → [1, 2, 5, 3, 6, 4, 7, 8].

Gaussian Mutation

• Adds small random noise to real-valued genes.

• Example: [3.5, 2.1, 5.0, 4.3], rate = 0.25, position 2, noise (mean 0, std 0.2) = +0.2 → 2.1 + 0.2 = 2.3 → [3.5, 2.3, 5.0, 4.3].

Elitism

• A strategy that ensures the best individuals (chromosomes) from the current generation are copied directly into the next generation without modification.

• With population size N and E elites: sort the population by fitness (highest → lowest), copy the top E directly to the next generation, and fill the remaining N − E spots with offspring from crossover and mutation.

• Example (maximization, f(x) = x²): C1 = 0101 (5, 25), C2 = 1100 (12, 144), C3 = 0110 (6, 36), C4 = 1001 (9, 81);

• with _____ = 1, C2 (144) is copied to the next generation;

• the new generation (Elite C2 = 144, Child1 = 1101 → 169, Child2 = 1000 → 64, Child3 random = 0111 → 49) preserved the best, and Child1 produced a better offspring.

Termination

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

Maximum Generations Reached

• Stop when a preset number of generations have been produced.

• Example: stop after 100 generations.

Fitness Threshold Achieved

• Stop when the best fitness value is good enough (meets or exceeds a target).

• Example: stop if fitness ≥ 0.95.

No Improvement (Convergence)

• Stop if fitness doesn’t improve for a number of generations.

• Example: stop if best fitness hasn’t changed for 20 generations.

Time Limit Reached

• Stop if the algorithm has run for a set duration.

• Example: stop after 60 seconds.

Manual Termination

• Human stops the GA based on inspection.

• Example: researcher halts after checking performance.

Termination by Fitness Threshold Example

• Generations 1–5: best x = 5.0, 6.2, 7.0, 8.5, 9.1;

• fitness (x²) = 25.0, 38.44, 49.0, 72.25, 82.81; at generation 5 the fitness exceeds 80, so the GA stops.

Termination by Convergence Example

• Condition: stop when the best fitness hasn’t improved for 3 consecutive generations.

• Best fitness: 65.2, 68.4, 70.1, then 70.1 for generations 4, 5, 6 (stagnation count 1, 2, 3);

• stop at generation 6 because the population converged.

Convergence (Genetic Algorithm)

• The same combination of items gives the best fitness for several generations.

• The population converged and all chromosomes are now similar (e.g., 11100).

• Termination occurs when no better packing appears.

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 implementation: chromosome = permutation of cities (e.g., [A, C, D, B, E]);

• fitness f = 1 / Total Distance (smaller distance → higher fitness);

• selection = tournament or roulette wheel;

• crossover = Order Crossover (OX) or Partially Mapped Crossover (PMX) to maintain valid tours;

• mutation = swap or inversion;

• termination = convergence (no shorter route found for many generations).

TSP Trace

• Generation 1, 5, 10, 15 – best route and distance: [A,B,C,D,E] = 450 (fitness 0.00222);

• [A,C,E,D,B] = 380 (0.00263, +0.00041);

• [A,C,D,E,B] = 370 (0.00270, +0.00007); [A,C,D,E,B] = 370 (0.00270, no change) → stop.

• The route doesn’t change for several generations, distance no longer improves, the GA converged, and termination is triggered by convergence.

Image Approximation

• Recreate or approximate a target image using a limited number of geometric shapes (like polygons or triangles).

• GA implementation: chromosome = real-valued vector describing shapes (position (x, y), color (R, G, B), opacity);

• fitness f = 1 − MSE(original, generated) (lower MSE → higher fitness), or 1 − MSE / max possible error; selection = tournament or rank; crossover = uniform or arithmetic (mix pixel or shape data);

• mutation = Gaussian (small random changes to colors or positions);

• termination = convergence (fitness improvement < threshold; image visually unchanged).

Image Approximation Trace

• Generation 1, 50, 100, 150 – MSE and fitness: 12000 (0.600); 3000 (0.900, +0.300); 1500 (0.950, +0.050);

• 1475 (0.951, +0.001) → stop.

• Fitness stops improving (the algorithm converges) and the improvement stays below the threshold for multiple generations.

Knapsack Problem

• Given a set of items, each with a weight and value, determine which items to include so that the total weight does not exceed a given capacity and the total value is maximized.

• GA implementation: chromosome = binary vector (e.g., 1 0 1 1 0; 1 = item included, 0 = excluded);

• fitness f = Total Value if weight ≤ capacity, else 0 (or penalty);

• selection = roulette wheel or rank;

• crossover = single-point or two-point on the bit string;

• mutation = bit-flip; termination = convergence (best total value stabilizes).

Knapsack Trace

• Generation 1, 5, 10 – best chromosome and total value: 10101 = 55 (items 1, 3, 5 selected);

• 11100 = 70 (+15); 11100 = 70 (+0) → stop.

• The same combination gives the best fitness for several generations;

• the population converged and all chromosomes are now similar (11100).

N-Queens Puzzle

• Place N queens on an N×N chessboard so that no two queens attack each other (no same row, column, or diagonal).

• GA implementation: chromosome = permutation of numbers (each gene = column position of a queen in a row), e.g., [1, 3, 5, 2, 4]; fitness f = 1 / (1 + number of conflicts);

• selection = rank or tournament; crossover = order or Partially Mapped Crossover to maintain the permutation;

• mutation = swap (exchange queen positions); termination = convergence or perfect fitness (no conflicts).

N-Queens Trace

• Generation 1, 5, 8 – best solution, conflicts, fitness: [1, 5, 8, 6, 3, 7, 2, 4] = 3 conflicts (0.25); [4, 2, 7, 3, 6, 8, 5, 1] = 1 conflict (0.5, +0.25);

• same board = 0 conflicts (1.0, +0.5) → stop.

• Fitness reached 1.0, meaning zero conflicts, a valid configuration;

• the GA terminates by convergence because the optimal solution is found.