Advanced search options

Sorted by: relevance · author · university · date | New search

You searched for `subject:(pseudo Boolean optimization)`

.
Showing records 1 – 2 of
2 total matches.

▼ Search Limiters

Colorado State University

1.
Chen, Wenxiang.
Step toward constant time local search for optimizing *pseudo* *boolean* functions, A.

Degree: MS(M.S.), Computer Science, 2013, Colorado State University

URL: http://hdl.handle.net/10217/81007

Pseudo Boolean Functions (PBFs) are the objective functions for a wide class of hard optimization problems, such as MAX-SAT and MAX-CUT. Since these problems are NP-Hard, researchers and practitioners rely on incomplete solvers, such as Stochastic Local Search (SLS), for large problems. Best-Improvement Local Search (BILS) is a common form of SLS, which always takes the move yielding the highest improvement in the objective function. Generally, the more runtime SLS is given, the better solution can be obtained. This thesis aims at algorithmically accelerating SLS for PBFs using Walsh Analysis. The contributions of this thesis are threefold. First, a general approach for executing an approximate best-improvement move in constant time on average using Walsh analysis, "Walsh-LS", is described. Conventional BILS typically requires examining all n neighbors to decide which move to take, given the number of variables is n. With Walsh analysis, however, we can determine which neighbors need to be checked. As long as the objective function is epistatically bounded by a constant k (k is the number of variables per subfunctions), the number of neighbors that need to be checked is constant regardless of problem size. An impressive speedup of runtime (up to 449 times) is observed in our empirical studies. Second, in the context of Walsh-LS, we empirically study two key components of SLS from the perspectives of both efficiency and effectiveness: 1) Local optimum escape method: hard random or soft restarts; 2) Local search strategy: first-improvement or best-improvement. Lastly, on average we can perform approximate BILS using the mean over a Hamming region of arbitrary radius as a surrogate objective function. Even though the number of points is exponential in the radius of the Hamming region, BILS using the mean value of points in the Hamming region as a surrogate objective function can still take each move in time independent of n on average. According to our empirical studies, using the average over a Hamming region as a surrogate objective function can yield superior performance results on neutral landscapes like NKq-landscapes.
*Advisors/Committee Members: Whitley, L. Darrell (advisor), Howe, Adele E. (advisor), Cheney, Margaret (committee member).*

Subjects/Keywords: complexity per move; stochastic local search; pseudo Boolean optimization; NK-landscapes

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Chen, W. (2013). Step toward constant time local search for optimizing pseudo boolean functions, A. (Masters Thesis). Colorado State University. Retrieved from http://hdl.handle.net/10217/81007

Chicago Manual of Style (16^{th} Edition):

Chen, Wenxiang. “Step toward constant time local search for optimizing pseudo boolean functions, A.” 2013. Masters Thesis, Colorado State University. Accessed March 09, 2021. http://hdl.handle.net/10217/81007.

MLA Handbook (7^{th} Edition):

Chen, Wenxiang. “Step toward constant time local search for optimizing pseudo boolean functions, A.” 2013. Web. 09 Mar 2021.

Vancouver:

Chen W. Step toward constant time local search for optimizing pseudo boolean functions, A. [Internet] [Masters thesis]. Colorado State University; 2013. [cited 2021 Mar 09]. Available from: http://hdl.handle.net/10217/81007.

Council of Science Editors:

Chen W. Step toward constant time local search for optimizing pseudo boolean functions, A. [Masters Thesis]. Colorado State University; 2013. Available from: http://hdl.handle.net/10217/81007

Colorado State University

2. Sutton, Andrew M. Analysis of combinatorial search spaces for a class of NP-hard problems, An.

Degree: PhD, Computer Science, 2011, Colorado State University

URL: http://hdl.handle.net/10217/50161

Given a finite but very large set of states X and a real-valued objective function ƒ defined on X, combinatorial optimization refers to the problem of finding elements of X that maximize (or minimize) ƒ. Many combinatorial search algorithms employ some perturbation operator to hill-climb in the search space. Such perturbative local search algorithms are state of the art for many classes of NP-hard combinatorial optimization problems such as maximum k-satisfiability, scheduling, and problems of graph theory. In this thesis we analyze combinatorial search spaces by expanding the objective function into a (sparse) series of basis functions. While most analyses of the distribution of function values in the search space must rely on empirical sampling, the basis function expansion allows us to directly study the distribution of function values across regions of states for combinatorial problems without the need for sampling. We concentrate on objective functions that can be expressed as bounded pseudo-Boolean functions which are NP-hard to solve in general. We use the basis expansion to construct a polynomial-time algorithm for exactly computing constant-degree moments of the objective function ƒ over arbitrarily large regions of the search space. On functions with restricted codomains, these moments are related to the true distribution by a system of linear equations. Given low moments supplied by our algorithm, we construct bounds of the true distribution of ƒ over regions of the space using a linear programming approach. A straightforward relaxation allows us to efficiently approximate the distribution and hence quickly estimate the count of states in a given region that have certain values under the objective function. The analysis is also useful for characterizing properties of specific combinatorial problems. For instance, by connecting search space analysis to the theory of inapproximability, we prove that the bound specified by Grover's maximum principle for the Max-Ek-Lin-2 problem is sharp. Moreover, we use the framework to prove certain configurations are forbidden in regions of the Max-3-Sat search space, supplying the first theoretical confirmation of empirical results by others. Finally, we show that theoretical results can be used to drive the design of algorithms in a principled manner by using the search space analysis developed in this thesis in algorithmic applications. First, information obtained from our moment retrieving algorithm can be used to direct a hill-climbing search across plateaus in the Max-k-Sat search space. Second, the analysis can be used to control the mutation rate on a (1+1) evolutionary algorithm on bounded pseudo-Boolean functions so that the offspring of each search point is maximized in expectation. For these applications, knowledge of the search space structure supplied by the analysis translates to significant gains in the performance of search.
*Advisors/Committee Members: Whitley, L. Darrell (advisor), Howe, Adele E. (advisor), Chong, Edwin K. P. (committee member), Bohm, A. P. Willem (committee member).*

Subjects/Keywords: combinatorial optimization; combinatorial search; local search; pseudo-Boolean functions; search space analysis

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Sutton, A. M. (2011). Analysis of combinatorial search spaces for a class of NP-hard problems, An. (Doctoral Dissertation). Colorado State University. Retrieved from http://hdl.handle.net/10217/50161

Chicago Manual of Style (16^{th} Edition):

Sutton, Andrew M. “Analysis of combinatorial search spaces for a class of NP-hard problems, An.” 2011. Doctoral Dissertation, Colorado State University. Accessed March 09, 2021. http://hdl.handle.net/10217/50161.

MLA Handbook (7^{th} Edition):

Sutton, Andrew M. “Analysis of combinatorial search spaces for a class of NP-hard problems, An.” 2011. Web. 09 Mar 2021.

Vancouver:

Sutton AM. Analysis of combinatorial search spaces for a class of NP-hard problems, An. [Internet] [Doctoral dissertation]. Colorado State University; 2011. [cited 2021 Mar 09]. Available from: http://hdl.handle.net/10217/50161.

Council of Science Editors:

Sutton AM. Analysis of combinatorial search spaces for a class of NP-hard problems, An. [Doctoral Dissertation]. Colorado State University; 2011. Available from: http://hdl.handle.net/10217/50161