Combining Adaptive Noise and Look-Ahead in Local Search for SAT Export

@inproceedings{citeulike:6102484, abstract = {The adaptive noise mechanism was introduced in Novelty+ to automatically adapt noise settings during the search [4]. The local search algorithm G 2 WSAT deterministically exploits promising decreasing variables to reduce randomness and consequently the dependence on noise parameters. In this paper, we first integrate the adaptive noise mechanism in G 2 WSAT to obtain an algorithm adaptG 2 WSAT, whose performance suggests that the deterministic exploitation of promising decreasing variables cooperates well with this mechanism. Then, we propose an approach that uses look-ahead for promising decreasing variables to further reinforce this cooperation. We implement this approach in adaptG 2 WSAT, resulting in a new local search algorithm called adaptG 2 WSAT P . Without any manual noise or other parameter tuning, adaptG 2 WSAT P shows generally good performance, compared with G 2 WSAT with approximately optimal static noise settings, or is sometimes even better than G 2 WSAT. In addition, adaptG 2 WSAT P is favorably compared with state-of-the-art local search algorithms such as R+adaptNovelty+ and VW.}, author = {Li, Chu and Wei, Wanxia and Zhang, Harry}, booktitle = {Theory and Applications of Satisfiability Testing (SAT '07)}, citeulike-article-id = {6102484}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/978-3-540-72788-0_15}, citeulike-linkout-1 = {http://www.springerlink.com/content/l60287431756851m}, doi = {10.1007/978-3-540-72788-0_15}, journal = {Theory and Applications of Satisfiability Testing – SAT 2007}, keywords = {local\_search, satisfiability, ubcsat}, pages = {121--133}, posted-at = {2009-11-12 17:38:10}, priority = {2}, title = {{Combining Adaptive Noise and Look-Ahead in Local Search for SAT}}, url = {http://dx.doi.org/10.1007/978-3-540-72788-0_15}, year = {2007} }

TY - CONF ID - citeulike:6102484 L3 - citeulike-article-id:6102484 N2 - The adaptive noise mechanism was introduced in Novelty+ to automatically adapt noise settings during the search [4]. The local search algorithm G 2 WSAT deterministically exploits promising decreasing variables to reduce randomness and consequently the dependence on noise parameters. In this paper, we first integrate the adaptive noise mechanism in G 2 WSAT to obtain an algorithm adaptG 2 WSAT, whose performance suggests that the deterministic exploitation of promising decreasing variables cooperates well with this mechanism. Then, we propose an approach that uses look-ahead for promising decreasing variables to further reinforce this cooperation. We implement this approach in adaptG 2 WSAT, resulting in a new local search algorithm called adaptG 2 WSAT P . Without any manual noise or other parameter tuning, adaptG 2 WSAT P shows generally good performance, compared with G 2 WSAT with approximately optimal static noise settings, or is sometimes even better than G 2 WSAT. In addition, adaptG 2 WSAT P is favorably compared with state-of-the-art local search algorithms such as R+adaptNovelty+ and VW. JF - Theory and Applications of Satisfiability Testing – SAT 2007 EP - 133 TI - {Combining Adaptive Noise and Look-Ahead in Local Search for SAT} T2 - Theory and Applications of Satisfiability Testing (SAT '07) SP - 121 KW - local_search KW - satisfiability KW - ubcsat AU - Li, Chu AU - Wei, Wanxia AU - Zhang, Harry PY - 2007/// UR - http://dx.doi.org/10.1007/978-3-540-72788-0_15 ER -