Author name cluster

L. Darrell Whitley

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

10 papers

2 author rows

SoCS Conference 2016 Conference Paper

Stochastic Local Search over Minterms on Structured SAT Instances

Wenxiang Chen
L. Darrell Whitley
Adele E. Howe
Brian W. Goldman

We observed that Conjunctive Normal Form (CNF) encodings of structured SAT instances often have a set of consecutive clauses defined over a small number of Boolean variables. To exploit the pattern, we propose a transformation of CNF to an alternative representation, Conjunctive Minterm Canonical Form (CMCF). The transformation is a two-step process: CNF clauses are first partitioned into disjoint subsets such that each subset contains CNF clauses with shared Boolean variables. CNF clauses in each subset are then replaced by Minterm Canonical Form (i. e. , partial solutions), which is found by enumeration. We show empirically that a simple Stochastic Local Search (SLS) solver based on CMCF can consistently achieve a higher success rate using fewer evaluations than the SLS solver WalkSAT on two representative classes of structured SAT problems.

Details

TCS Journal 2012 Journal Article

Computing the moments of k -bounded pseudo-Boolean functions over Hamming spheres of arbitrary radius in polynomial time

Andrew M. Sutton
L. Darrell Whitley
Adele E. Howe

We show that given a k -bounded pseudo-Boolean function f, one can always compute the c th moment of f over regions of arbitrary radius in Hamming space in polynomial time using algebraic information from the adjacency structure (where k and c are constants). This result has implications for evolutionary algorithms and local search algorithms because information about promising regions of the search space can be efficiently retrieved, even if the cardinality of the region is exponential in the problem size. Finally, we use our results to introduce a method of efficiently calculating the expected fitness of mutations for evolutionary algorithms.

Details DOI

TCS Journal 2011 Journal Article

Elementary landscape decomposition of the frequency assignment problem

Francisco Chicano
L. Darrell Whitley
Enrique Alba
Francisco Luna

The Frequency Assignment Problem (FAP) is an important problem that arises in the design of radio networks, when a channel has to be assigned to each transceiver of the network. This problem is a generalization of the graph coloring problem. In this paper we study a general version of the FAP that can include adjacent frequency constraints. Using concepts from landscapes’ theory, we prove that this general FAP can be expressed as a sum of two elementary landscapes. Further analysis also shows that some subclasses of the problem correspond to a single elementary landscape. This allows us to compute the kind of neighborhood information that is normally associated with elementary landscapes. We also provide a closed form formula for computing the autocorrelation coefficient for the general FAP, which can be useful as an a priori indicator of the performance of a local search method.

Details DOI

SoCS Conference 2010 Conference Paper

Directed Plateau Search for MAX-k-SAT

Andrew M. Sutton
Adele E. Howe
L. Darrell Whitley

Local search algorithms for MAX-k-SAT must often explore large regions of mutually connected equal moves, or plateaus, typically by taking random walks through the region. In this paper, we develop a surrogate plateau "gradient" function using a Walsh transform of the objective function. This function gives the mean value of the objective function over localized volumes of the search space. This information can be used to direct search through plateaus more quickly. The focus of this paper is on demonstrating that formal analysis of search space structure can direct existing algorithms in a more principled manner than random walks. We show that embedding the gradient computation into a hill-climbing local search for MAX-k-SAT improves its convergence profile.

Details

ICAPS Conference 2007 Conference Paper

Using Adaptive Priority Weighting to Direct Search in Probabilistic Scheduling

Andrew M. Sutton
Adele E. Howe
L. Darrell Whitley

Many scheduling problems reside in uncertain and dynamic environments -- tasks have a nonzero probability of failure and may need to be rescheduled. In these cases, an optimized solution for a short-term time horizon may have a detrimental impact over a broader time scale. We examine a scheduling domain in which time and energy on a phased array radar system is allocated to track objects in orbit around the earth. This domain requires probabilistic modeling to optimize the expected number of successful tasks on a particular day. Failed tasks must be attempted again on subsequent days. Given a set of task requests, we study two long-term objectives: percentage of requests initially successful, and the average time between successful request updates. We investigate adaptive priority weighting strategies that directly influence the short-term objective function and thus indirectly influence the long-term goals. We find that adapting priority weights based on when individual tasks succeed or fail allows a catalog of requests to be filled more quickly. Furthermore, with adaptive priorities, we observe a Pareto-front effect between the two long-term objectives as we modify how priorities are weighted, but an inverse effect of weighting when the priorities are not adapted.

Details

ICAPS Conference 2006 Conference Paper

Looking for Shortcuts: Infeasible Search Analysis for Oversubscribed Scheduling Problems

Mark F. Rogers
Adele E. Howe
L. Darrell Whitley

Searches that include both feasible and infeasible solutions have proved to be ef cient algorithms for solving some scheduling problems. Researchers conjecture that these algorithms yield two primary benefits: 1) they tend to focus on solutions close to the boundary between feasible and infeasible solutions, where active constraints are likely to yield optimal values, and 2) moves that include infeasible solutions may uncover short-cuts in a search space. Researchers have published empirical studies that confirm the value of searching along the feasible-infeasible boundary, but until now there has been little direct evidence that infeasible search yields short-cuts. We present empirical results in two oversubscribed scheduling domains for which boundary region search in infeasible space appears to offer advantages over search in strictly feasible space. Our results confirm that infeasible search finds shortcuts that may improve search efficiency more than boundary region search alone. However, our results also reveal that ineffi- cient infeasible paths which we call detours may degrade search performance, potentially offsetting efficiency shortcuts may provide.

Details

ICAPS Conference 2006 Conference Paper

Spacetrack: Trading off Quality and Utilization in Oversubscribed Schedules

Andrew M. Sutton
Adele E. Howe
L. Darrell Whitley

Many scheduling problems are posed as optimization problems where the goal is to find a feasible schedule that maximizes the utilization of some resource. In some domains it is also necessary to consider the quality of the resulting schedule. In most research these two quantities are independent. This paper introduces a real world problem in which radar tasks must be allocated to track objects in space. We explore the trade-off between off-line task resource utilization and a measure of task quality that correlates to whether tasks are actually successfully executed. We develop two general types of algorithms that differ in the way they reason about quality and explore the trade-off between high quality solutions and solutions with high resource utilization.

Details

ICAPS Conference 2004 Conference Paper

Trading Places: How to Schedule More in a Multi-Resource Oversubscribed Scheduling Problem

Laura Barbulescu
Adele E. Howe
L. Darrell Whitley
Mark Roberts

Oversubscribed scheduling problems require removing tasks when enough resources are not available. Prior AI approaches have mostly been constructive or repairbased heuristic search. In contrast, we have found a genetic algorithm (GA) to be the best approach to the overconstrained problem of Air Force Satellite Control Network scheduling. We present empirical results that elucidate sources of difficulty in the application and partially explain why the GA is well suited to this problem. We show that the task interaction compels changes involving many tasks simultaneously and the GA appears to be learning domain specific patterns in the data.

Details

AAAI Conference 1999 Conference Paper

Algorithms Performance and Problem Structure for Flow-Shop Scheduling

Jean-Paul Watson
Laura Barbulescu
Adele E. Howe
L. Darrell Whitley
Colorado State University Search

Test suites for many domains often fail to model features present in real-world problems. For the permutation flow-shop sequencing problem (PFSP), the most popular test suite consists of problems whose features are generated from a single uniform random distribution. Synthetic generation of problems with characteristics present in real-world problems is a viable alternative. We compare the performance of several competitive algorithms on problems produced with such a generator. We find that, as more realistic characteristics are introduced, the performance of a stateof-the-art algorithm degrades rapidly: faster and less complex stochastic algorithms provide superior performance. Our empirical results show that small changes in problem structure or problem size can influence algorithm performance. We hypothesize that these performance differences may be partially due to differences in search space topologies; we show that structured problems produce topologies with performance plateaus. Algorithm sensitivity to problem characteristics suggests the need to construct test suites more representative of real-world applications.

PDF Details

ICAPS Conference 1996 Conference Paper

Comparing Heuristic, Evolutionary and Local Search Approaches to Scheduling

Soraya B. Rana
Adele E. Howe
L. Darrell Whitley
Keith E. Mathias

The choice of search algorithm can play a vital role in the success of a scheduling application. In this paper, we investigate the contribution of search algorithms in solving a real-world warehouse scheduling problem. We compare performance of three types of scheduling algorithms: heuristic, genetic algorithms and local search. Additionally, we assess the in uence of heuristics on search performance and check for bias induced by using a fast objective function to evaluate intermediate search results.

Details