Applying Genetic Algorithm with Saltations to MAX-3SAT

EasyChair Preprint 15890

Abstract

Punctuated evolution, (synonymous with Saltations, Evolutionary Jumps)—the pattern of rapid, significant mutational change—had not been observed in real-time until SARS-CoV-2 viral variants emerged with multiple mutations occurring together. By using Epistasis as a framework to understand this phenomenon, where the effect of one mutation depends on the influence of one or more other mutations (ie. combinations of mutations) we can model the fitness landscape of viral variants with an Epistatic network, and capture this relationship between different combinations of mutations as a result\cite{edevv}. In exploring these relationships, it has been found that dense subgraphs (where the density of the subgraph increases with the number of edges, given a number of vertices) within the network correspond to emerging saltations, which can uncover high fitness regions seemingly distant from the variant(s) they originally derived from\cite{edevv}. We incorporate this pattern into the Genetic Algorithm (GA+EJ) as a means to produce new solutions that escape the inherent tendency to produce solutions converging to a local maximum. We applied GA+EJ to the MAX-3SAT problem, and found improvement for satisfiable problem instances with 600 variables and 2550 clauses, as well as 100 varibles and 429 clauses, allowing us to find solutions giving a better approximation of the optimum when using jumps, than without them.

Keyphrases: Clique SNV, Evolutionary jumps, Genetic Algorithm, Max 3SAT Problem, Punctuated evolution, Saltations

@booklet{EasyChair:15890,
  author    = {Ryan Alomair and Hafsa Farooq and Daniel Novikov and Akshay Juyal and Alex Zelikovsky},
  title     = {Applying Genetic Algorithm with Saltations to MAX-3SAT},
  howpublished = {EasyChair Preprint 15890},
  year      = {EasyChair, 2025}}