Markov Chain Analysis of Noise and Restart in Stochastic Local Search
Authors: Ole J. Mengshoel, Youssef Ahres, Tong Yu
IJCAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In experiments with synthetic and real-world problems, we compare Soft SLS, Adaptive SLS, Adaptive Noise [Hoos, 2002], and Simulated Annealing [Kirkpatrick et al., 1983]. Table 2: Average running time results for optimized Soft SLS, Adaptive SLS, Adaptive Noise (AN), and Simulated Annealing (SA) on synthetic DMC problems. |
| Researcher Affiliation | Academia | Ole J. Mengshoel Electrical and Computer Engineering Carnegie Mellon University, Youssef Ahres Electrical Engineering Stanford University, Tong Yu Electrical and Computer Engineering Carnegie Mellon University |
| Pseudocode | Yes | Algorithm 1: Markov SLS is an algorithm where noise probability pn and restart probability pr can be adapted. |
| Open Source Code | No | No explicit statement or link for open-source code availability found. |
| Open Datasets | Yes | We use both synthetic (deceptive Markov chains) and realworld datasets (feature selection) in our experiments. Table 1 presents the real-world datasets used for feature selection. Please see https://archive.ics.uci.edu/ml and http://www.liacc. up.pt |
| Dataset Splits | Yes | its cross-validation accuracy, using 2-fold cross-validation. |
| Hardware Specification | No | No specific hardware details are mentioned in the paper. |
| Software Dependencies | No | No specific software dependencies with version numbers are mentioned. |
| Experiment Setup | Yes | In this paper, their optimized values are: an = 0.2 and ar = 0.1. For each dataset, we searched exhaustively to predetermine the globally optimal feature subset s , and passed t = f(s ) to both Soft SLS and Adaptive SLS. its cross-validation accuracy, using 2-fold cross-validation. Figure 4 shows the evolution of pr and pn in Adaptive SLS during search, after initialization pr = pn = 0. |