Evolving Solutions to Community-Structured Satisfiability Formulas
Authors: Frank Neumann, Andrew M. Sutton2346-2353
AAAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We study the performance of a simple evolutionary algorithm tasked with finding a satisfying assignment to structured (non-uniform) propositional formulas... In order to characterize the leading constants and demonstrate the tightness of the bound, we perform a number of numerical experiments to measure the run time of the (1+1) EA on the community attachment model. In Figure 3, we fix n = 1000, s = 100 and p = 3/4 and vary m to plot the empirical RLD curves. |
| Researcher Affiliation | Academia | Frank Neumann Optimisation and Logistics School of Computer Science The University of Adelaide Adelaide, Australia Andrew M. Sutton Department of Computer Science University of Minnesota Duluth Duluth, MN, USA |
| Pseudocode | Yes | Algorithm 1: (1+1) EA 1 Choose x uniformly at random from {0, 1}n; 2 while stopping criterion not met do 4 foreach i {1, . . . , n} do 5 With probability 1/n, yi (1 yi); 6 if f(y) f(x) then x y; |
| Open Source Code | No | The paper does not contain any statements or links indicating that its source code is publicly available. |
| Open Datasets | No | The paper describes generating synthetic formulas using the "community attachment model" rather than using a publicly available dataset with concrete access information. |
| Dataset Splits | No | The paper does not specify exact training, validation, or test dataset splits. It describes generating formulas for experiments without partitioning a pre-existing dataset. |
| Hardware Specification | No | The paper does not provide specific details about the hardware used to run the experiments. |
| Software Dependencies | No | The paper does not list specific software dependencies with version numbers used for the experiments. |
| Experiment Setup | Yes | For each s = {100, 110, 120, . . . , 1000}, we generate 10 modular formulas using the community attachment model with n = s3/2 and m/n = 5e. On each formula, we measure the run time of the (1+1) EA for 10 trials... We identify t(1 ε) communities as dense and choose localized clauses uniformly from dense communities with probability 1 t ε. The remaining communities are chosen uniformly with probability t ε... We plot the median run time divided by n ln n measured in the experiments for p {3/4, 1/4} and ε = 1/5. |