.png){kind=icon}
.png){kind=icon}
Return
Applying Genetic Algorithm with Saltations to MAX-3SAT
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-032-02489-3_19.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Punctuated equilibrium, the pattern of rapid, significant mutational change, had not been observed in real time until the SARS-CoV-2 viral variants emerged with multiple mutations occurring together. Using epistasis (the circumstance in which the effect of one gene is influenced by the presence of one or more other genes) as a framework to understand this phenomenon, we can capture the relationships between different combinations of mutations, where each node is an individual mutation, and each edge represents the interaction between them, allowing us to effectively model the fitness landscape of viral variants. In exploring these relationships, it has been found that dense subgraphs within the network correspond to emerge saltation. We refer to this as an evolutionary jump and incorporate it with a genetic algorithm (GA + EJ), which can uncover high-fitness regions seemingly distant from the variant(s) from which they originally derived. We applied it to the MAX-3SAT problem and found improvement for satisfiable problem instances with 600 variables and 2550 clauses, as well as 100 variables and 429 clauses.
Keywords:
MAX-3SAT Problem
Evolution
Genetic Algorithm
Epistatic network
Journal
C
IF:
0
Papers:
23
Citations:
0