Biologically Inspired Optimisation Methods: Power of Randomness and Local Search

Fundamentals of Randomness in Computer Science

• The Miracle of Randomness: The concept of randomness is central to designing ultra-efficient algorithms for intractable problems.     * Efficiency Gains: Systems utilizing random control can terminate up to a billion times faster than their deterministic counterparts.     * The Cost of Randomness: We trade a guarantee of certainty for a known risk of error probability. The critical question is whether the risk is worth the speed utility.
• Scientific and Mathematical Context:     * Randomness is a fundamental notion discussed across Philosophy, Mathematics, Chemistry, Physics, and Biology.     * In Mathematics, Probability Theory is used to investigate random events.     * In Computer Science, the study focuses on when it is profitable to include randomness in algorithmic design.
• Definitions and Dialectic:     * Determinism: A worldview based on causality. If the current state of the universe and all natural laws are known, the future can be predicted.     * Non-determinism: A paradigm where one cause can result in many different effects without a law determining which outcome occurs.     * Dictionary Definitions:         * An event is random if it happens unpredictably.         * An object is random if it is created without a plan or pattern.

Historical Perspectives on Randomness

• Ancient Philosophical Debate:     * Democritus (460 - 370 BC): Argued that randomness is merely "the unknown." He believed nature is fundamentally determined in its principles.     * Epicurus (341 - 270 BC): Argued that randomness is objective and represents the actual nature of events.
• 20th Century Developments: Discoveries in science shifted the consensus toward true randomness:     * Evolutionary Biology: The discovery of random mutations in DNA.     * Quantum Mechanics: Provides a scientific basis for the belief in true randomness.
• Computer Science Perspective: Regardless of whether true randomness exists, computer scientists utilize it as a source of immense computational efficiency.

Deterministic vs. Randomized Algorithms

• Deterministic Program: Executes an unambiguous, fixed sequence of computing steps on a given input.
• Randomized Algorithm: Can execute many different computation paths on the same input; the specific path is decided at random.
• Methods of Randomization:     1. A deterministic program that performs a "coin flip" at certain decision points (e.g., if "heads" go to step $i$, if "tails" go to step $j$).     2. A program that makes a random choice among several available deterministic strategies.

Example Case Study: The WITNESS Protocol

• The Scenario: Two computers, RI and RII, are located far apart. They maintain identical databases that evolve over time. After a period, they must verify if their contents remain consistent.     * Data Representation: Contents are bit sequences where RI has $x = x_1 x_2 … x_n$ and RII has $y = y_1 y_2 … y_n$.
• Complexity of Deterministic Verification:     * Any deterministic strategy requires exchanging all $n$ bits.     * For a large input, such as $n = 10^{16}$, a transmission speed of $2\,GHz$ would require approximately $58\, ext{days}$, assuming no internet errors occur.
• The Randomized Communication Protocol (WITNESS):     1. RI chooses a prime $p$ from the set of primes $PRIM(n^2)$ at random.     2. RI computes the integer $s = ext{Number}(x) \pmod p$ and sends both $s$ and $p$ to RII.     3. RII computes the integer $q = ext{Number}(y) \pmod p$.     4. If $q \neq s$, RII outputs "fail". If $q = s$, RII outputs "equal".
• Mathematical Representation of Sequences:     * $\text{Number}(x) = \sum_{i=1}^{n} 2^{n-i} \cdot x_i$     * $\text{Number}(y) = \sum_{i=1}^{n} 2^{n-i} \cdot y_i$     * $0 \leq \text{Number}(x), \text{Number}(y) \leq 2^{n}-1$
• Performance Advantage:     * The protocol requires transmitting only $4 \times \lceil \log_2(n) \rceil$ bits.     * For $n = 10^{16}$, this is only $256\, ext{bits}$, requiring only $128\,ns$ for transmission.

Error Probability of WITNESS

• Defining Primes:     * $PRIM(m) = {p \text{ is a prime } | p \leq m }$     * $Prim(m) = |PRIM(m)|$
• Prime Number Theorem:     * $Prim(m) \approx \frac{m}{\ln(m)}$     * For all m > 67 (where $n \geq 9$), Prim(n^2) > \frac{n^2}{2 \ln(n)}
• Partitioning Primes for Input $(x, y)$: Primes are classified as "good" or "bad" based on whether they yield the correct verdict.
• Analysis of Outcomes:     * Case 1 ($x = y$): If sequences are equal, then $Number(x) = Number(y)$, making $s = q$ always true. The error probability is $0$. This is a one-sided error algorithm.     * Case 2 ($x \neq y$): An error (wrongly returning "equal") occurs if a prime $p$ is chosen such that $Number(x) \pmod p = Number(y) \pmod p$.     * Bad Primes: A prime is bad if it divides the difference $Dif(x, y) = |Number(x) - Number(y)|$.
• Upper Bounding the Error:     * Since $Dif(x, y) < 2^n$, by the Fundamental Theorem of Arithmetic, the number of prime factors $k$ must be such that $k! < 2^n$.     * Given that $n! > 2^n$ for $n \geq 4$, the number of bad primes $k \leq n - 1$.     * $\text{Error}_{\text{WITNESS}}(x, y) \leq \frac{n - 1}{n^2 / 2 \ln(n)} \leq \frac{2 \ln(n)}{n}$.     * For $n = 10^{16}$, the error probability is approximately $0.36841 \times 10^{-14}$.     * Observation: The probability of hardware failure during a 58-day deterministic run is significantly higher than this random choice error.

Solving NP-hard Problems

• The Challenge of NP-Hardness: For many problems, no deterministic polynomial-time method is known. Finding one would imply $P = NP$.
• Reasonable Time Strategies:     * Approximation: Find solutions within a specific range of the global optimum.     * Transformation: Solve a related problem (e.g., using linear programming to solve Integer Linear Programs).     * Heuristic/Local Search: Start at a random solution and iteratively improve it.
• Complexity Classes:     * APX: Optimization problems allowing polynomial-time approximation algorithms with a constant-bounded ratio. (Example: Metric TSP has a 1.5-approximation).     * PTAS (Polynomial-Time Approximation Scheme): Can find solutions within $1 + \epsilon$ bound in time $O(n^{1/\epsilon})$.

Heuristic Search - Local Search

• Complexity Example: For the MAX-3-SAT problem with $n = 76$, checking all possible assignments ($\phi$) using an Intel Core i7 (300 billion IPS) would take over a year.
• Mechanics of Local Search:     * Employs randomness to examine only a subset of the search space.     * Starts with a random initial solution.     * Applies small, local changes to preserve good features while improving the current solution.
• The Energy Landscape:     * Search Space ($R$): The set of all possible solutions (e.g., all $\phi$ assignments).     * Neighbourhood Function ($S(\phi)$): Defines local moves (e.g., flipping a single bit in $\phi$).     * Objective/Energy Function ($C(\phi)$): Measures the quality of a solution (e.g., number of satisfied clauses).
• Landscape Features:     * Local Optimum: A configuration $\phi$ where all neighbors in $S(\phi)$ have a cost $C(\phi_i) \leq C(\phi)$.     * Global Optimum: A configuration $\phi$ where all potential configurations in the entire set $R$ have a cost $C(\phi_i) \leq C(\phi)$.     * Plateau: A set of solutions $B$ where all solutions have the same cost and are reachable from one another through neighborhood moves.

Local Search Procedures and Observations

• Guided Walk Strategy:     1. Start with a random $\phi$.     2. Evaluate $\phi$.     3. Select a neighbor $\phi'$ randomly from $S(\phi)$.     4. Evaluate $\phi'$.     5. If $\phi'$ is better, move to it and check if it’s the best found so far.     6. If $\phi'$ is not better, decide whether to move to it anyway (to escape local optima).
• Random Hill-Climbing: High-speed iterative improvement that maintains one current configuration and moves only to better neighbors. It is prone to terminating at local optima.
• Key Observations:     * Global optima are always local ones, but the converse is not true.     * To find better optima, methodologies must include ways to leave local optima.     * Neighborhood function design heavily influences performance.     * Storing the "best-so-far" solution allows the search to be stopped at any point (anytime algorithm).     * There is a trade-off between total iterations and output quality.     * Search processes can easily become "lost" in plateaus.
• Advanced Metaheuristics:     * Tabu Search: Keeps a memory of visited neighbors to prevent cycling.     * Simulated Annealing: Uses the Boltzmann distribution for probabilistic acceptance of worse solutions to navigate landscapes.     * Genetic Local Search: Maintains a population of independent walks and uses crossover to find shortcuts.