GSAT averaging-in strategy
Algorithms AIMech:GSATAveragingIn DRAFT
A GSAT restart-initialization strategy that reuses agreements between earlier complete assignments, randomizes their differing positions, and periodically resets to a fresh random start.
Identity Notes & Concept Scope
This is Strategy II, Averaging in, in the 1993 GSAT extensions paper. The word averaging denotes Boolean agreement preservation and random filling of disagreements, not arithmetic averaging into fractional truth values. It reuses selected earlier near-solutions in a sequence of GSAT attempts; it is not a full genetic algorithm with population selection, crossover and mutation, although the authors note related features. No normalized identity match was found across all 442 pinned AIO labels/scoped synonyms and 319 preceding native IDs/names/aliases. Full-checkout fixed-string searches included ignored and hidden files in worktree and main, returning 11 and 11 lines respectively. All eleven unique lines were inspected, and the sorted checkout hit sets were identical: source-title references and saved review/ledger frontier leads, not existing candidate records. Eight exact AIO CLASS nodes with scoped synonyms/comments and outgoing edges and six full native neighboring records were inspected. Absence is bounded to this snapshot and semantic neighborhood.
Claims & Grounded Evidence
1 Claim
Mechanism
#method
Within a reset block, start the first GSAT attempt from a random complete assignment and retain the best assignment encountered, defined by the fewest unsatisfied clauses. Form the second attempt’s initial assignment by averaging the first initial assignment with that first best assignment. For attempt i from 3 through RESET-TRIES, average the best assignments from attempts i−1 and i−2 to obtain its initial assignment, run the GSAT inner loop, and retain its best assignment. Averaging preserves a bit when both inputs agree and randomly assigns a truth value when they disagree. After the reset block, begin again from a fresh random assignment. The source motivates periodic resets because reused starts and best assignments can become similar; no diversity guarantee follows from the operation alone.
⚠️ Curated Limitations & Negative Results
- The first two attempts use a different recurrence from later attempts: initial2 combines initial1 with best1, while initiali for i>=3 combines the two preceding best assignments. Substituting terminal states for best states, or using the same pair rule from the first attempt onward, changes the specification.
- The pseudocode explicitly performs the first two attempts before its i=3 loop. An implementation must declare RESET-TRIES and budget boundary conventions, including a budget too small to complete that prefix, rather than silently infer arbitrary one-attempt behavior.
- The inspected source says discrepant positions receive random truth values but does not fully specify joint random-number coupling or tied-best-assignment retention. No particular implementation of those boundaries is certified here.
- Assignment reuse can concentrate starts and does not prove faster convergence, eventual SAT success or an UNSAT result on failure. The reported reset settings are empirical choices, not universal constants; no numerical benchmark claim is curated.
Artificial Intelligence Ontology (AIO) Grounding
Explicit AIO Snapshot Assessment: No Match
Rationale: No suitable AIO target was established for this GSAT search extension in the inspected snapshot and semantic neighborhood. Search-history reuse and adaptive penalties do not justify a forced learning-task or language-model mapping.
Search Scope: All 442 pinned AIO labels/scoped synonyms and 319 preceding native IDs/names/aliases; both full checkouts including ignored and hidden text; semantic search for SAT/search, weighting, assignment reuse, stochastic processes and evolutionary terminology; eight exact AIO CLASS nodes and six complete native neighbors.
| Examined AIO Candidate | Rejection Reason |
|---|---|
AIO:ReasoningLLM
|
Solving a supplied CNF formula does not require a language model that performs language-task reasoning. |
AIO:TrainingStrategy
|
The procedure adjusts search costs or initialization rather than requiring preprocessing to train a machine-learning model. |
AIO:MachineLearningTask
|
Retaining solver information between attempts does not by itself identify a process of developing a reusable method that learns from data. |
AIO:ReinforcementLearning
|
Adaptive clause weights or assignment reuse are not learned reward/action-value policies merely because they use search history. |
AIO:MarkovChain
|
A state representation can include search memory, but that mathematical representation alone does not ground this particular retained-weight or retained-assignment algorithm in the pinned network/model class. |
AIO:ArtificialNeuralNetwork
|
The method operates on Boolean assignments and clause scores, not a network of artificial neurons. |
AIO:EvolutionaryLLM
|
The target is a language model optimized with evolutionary computation. Its related evolutionary-algorithms synonym does not make Boolean assignment averaging a language-model architecture. |
AIO:WeightedLayer
|
Weights on SAT clauses are not values applied to cells or neurons in a network. |
Evidence Sources & Primary Literature
1 Source| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
method-source
|
Bart Selman, Henry Kautz
|
primary paper
full_text
|
sha256:f301bd7ff353…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-11T15:33:06Z
Updated: 2026-10-11T15:33:06Z
Source File:
data/curated/GSATAveragingIn.yaml