[Paper] S-LCG: Structured Linear Congruential Generator-Based Deterministic Algorithm for Search and Optimization

Source: arXiv - 2605.05198v1

Overview

A new deterministic optimization algorithm called S‑LCG (Structured Linear Congruential Generator) has been introduced. By repurposing a classic pseudo‑random number generator into a structured search engine, the authors achieve high‑quality solutions on a wide range of benchmark and engineering problems while keeping the implementation simple and fully reproducible.

Key Contributions

• Deterministic search framework built on a specially‑structured Linear Congruential Generator (LCG).
• Two‑level architecture: an outer loop that adaptively balances exploration vs. exploitation, and an inner loop that evaluates candidate solutions.
• Memory‑less, non‑overlapping sequences via distinct seeds, eliminating redundant evaluations.
• Bit‑splitting representation that maps LCG states to multi‑dimensional points, mitigating the classic “Marsaglia lattice” bias of plain LCGs.
• Constant information‑gathering rate, reducing premature convergence without needing complex population‑size schedules.
• Minimal hyper‑parameter set – only a single sensitive parameter needs tuning.
• Extensive empirical validation on 26 benchmark functions (2‑30 dimensions) and three real‑world constrained engineering design problems, outperforming eight state‑of‑the‑art binary metaheuristics and a standard Genetic Algorithm (GA).

Methodology

1. Structured LCG core – The algorithm starts from a conventional LCG:

   [ x_{k+1} = (a \cdot x_k + c) \bmod m ]

   but augments it with a structure that treats each generated integer as a binary word. The word is split into blocks of bits; each block is interpreted as a coordinate in the decision space. This “bit‑splitting” turns a 1‑D sequence into a multi‑dimensional point set while preserving the deterministic nature of the generator.

2. Two‑level control

   • Outer loop (exploration‑exploitation controller): a single scalar parameter (\lambda) governs how aggressively the generator’s seed is perturbed. Small (\lambda) values keep the search tight (exploitation); larger values inject fresh seeds (exploration). The controller adapts (\lambda) based on recent improvement rates.
   • Inner loop (solution evaluator): for each seed, the structured LCG produces a batch of candidate points. Because the LCG is memoryless, each seed yields a unique, non‑overlapping batch, guaranteeing that no candidate is evaluated twice.

3. Surrogate‑guided acceptance – The algorithm implicitly builds a smooth surrogate of the objective by observing the deterministic trajectory of the generator. When a new point improves the surrogate, the outer loop tightens (\lambda); otherwise it relaxes it, steering the search toward promising regions without explicit population‑based crossover or mutation operators.

4. Constraint handling – For constrained engineering problems, a simple penalty function is added to the objective. Since the generator already respects bound constraints (by scaling the bit‑split values), only inequality/equality constraints need penalization.

The whole procedure can be coded in a few dozen lines of Python or C, with no external libraries required beyond basic math utilities.

Results & Findings

• Statistical significance: Wilcoxon signed‑rank tests confirm that S‑LCG’s improvements over the competitors are not due to random chance.
• Engineering case studies: The algorithm successfully solved three constrained design problems (e.g., truss sizing, pressure vessel design) achieving feasible, near‑optimal solutions with far fewer objective evaluations than the GA baseline.
• Robustness to dimensionality: Even as the search space grew to 30 dimensions, the success rate stayed above 80 %, indicating that the bit‑splitting scheme effectively combats the lattice effect that typically cripples plain LCGs in high dimensions.

Practical Implications

• Deterministic reproducibility – Because the search is fully defined by the initial seed and the single adaptive parameter, developers can reproduce exact runs across machines and languages—an attractive property for safety‑critical or regulated industries.
• Lightweight implementation – No need for large populations, crossover operators, or complex mutation schedules. This translates to lower memory footprints and faster runtimes, making S‑LCG suitable for embedded optimization (e.g., on‑device hyper‑parameter tuning, real‑time control parameter updates).
• Easy integration with existing pipelines – The algorithm outputs a simple list of candidate vectors; it can be dropped into any existing evaluation loop (simulation, CFD, ML model training) without redesigning the surrounding code.
• Potential for hybridization – Because S‑LCG already provides a high‑quality deterministic backbone, it can be combined with stochastic refinements (e.g., local gradient descent) to further accelerate convergence on smooth problems.
• Reduced hyper‑parameter burden – Only one tunable parameter ((\lambda) adaptation rate) needs calibration, which can often be set to a default value. This lowers the barrier for teams that lack deep expertise in metaheuristic tuning.

Limitations & Future Work

• Scalability beyond 30 dimensions – While results are promising up to 30 variables, the authors note a gradual drop in success rate for higher‑dimensional problems; future research could explore adaptive bit‑block sizing or hierarchical decomposition.
• Constraint handling is simplistic – The current penalty‑based approach may struggle with highly non‑convex feasible regions; integrating more sophisticated constraint‑preserving transformations is an open avenue.
• Benchmark diversity – The study focuses on continuous, unconstrained benchmark functions and a few engineering designs; testing on combinatorial or mixed‑integer problems would broaden applicability.
• Theoretical convergence guarantees – Although empirical evidence is strong, a formal proof of convergence (or bounds on the expected distance to optimum) remains to be established.

Overall, S‑LCG offers a fresh, deterministic take on metaheuristic optimization that aligns well with the practical needs of developers and engineers seeking reproducible, low‑overhead search methods.

Authors

• Ahmed Qasim Mohammed
• Haider Banka
• Anamika Singh

Paper Information

• arXiv ID: 2605.05198v1
• Categories: math.OC, cs.NE
• Published: May 6, 2026
• PDF: Download PDF