This article investigates
for pseudo-Boolean optimization problems composed of
subfunctions, where each subfunction accepts at most
variables. We will refer to these as Mk Landscapes. In Gray Box ...Optimization, the optimizer is given access to the set of
subfunctions. We prove Gray Box Optimization can efficiently compute hyperplane averages to solve non-deceptive problems in
time. Bounded separable problems are also solved in
time. As a result, Gray Box Optimization is able to solve many commonly used problems from the evolutional computation literature in
evaluations. We also introduce a more general class of Mk Landscapes that can be solved using dynamic programming and discuss properties of these functions. For certain type of problems Gray Box Optimization makes it possible to enumerate all local optima faster than brute force methods. We also provide evidence that randomly generated test problems are far less structured than those found in real-world problems.
Bit-flip mutation is a common mutation operator for evolutionary algorithms applied to optimize functions over binary strings. In this paper, we develop results from the theory of landscapes and ...Krawtchouk polynomials to exactly compute the probability distribution of fitness values of a binary string undergoing uniform bit-flip mutation. We prove that this probability distribution can be expressed as a polynomial in
, the probability of flipping each bit. We analyze these polynomials and provide closed-form expressions for an easy linear problem (Onemax), and an NP-hard problem, MAX-SAT. We also discuss a connection of the results with runtime analysis.
When working in an unfamiliar online environment, it can be helpful to have an observer that can intervene and guide a user toward a desirable outcome while avoiding undesirable outcomes or ...frustration. The
is deciding when to intervene in order to help a user. The Intervention Problem is similar to, but distinct from, Plan Recognition because the observer must not only recognize the intended goals of a user but also when to intervene to help the user when necessary. We formalize a family of Intervention Problems and show that how these problems can be solved using a combination of Plan Recognition methods and classification algorithms to decide whether to intervene. For our benchmarks, the classification algorithms dominate three recent Plan Recognition approaches. We then generalize these results to Human-Aware Intervention, where the observer must decide in real time whether to intervene human users solving a cognitively engaging puzzle. Using a revised feature set more appropriate to human behavior, we produce a learned model to recognize when a human user is about to trigger an undesirable outcome. We perform a human-subject study to evaluate the Human-Aware Intervention. We find that the revised model also dominates existing Plan Recognition algorithms in predicting Human-Aware Intervention.
The Air Force Satellite Control Network (AFSCN) coordinates communications to more than 100 satellites via nine ground stations positioned around the globe. Customers request an antenna at a ground ...station for a specific time window along with possible alternative slots. Typically, 500 requests per day result in more than 100 conflicts, which are requests that cannot be satisfied because other tasks need the same slot. Scheduling access requests is referred to as the Satellite Range Scheduling Problem (SRSP).
This paper presents an overview of three key issues: (1) how has the problem changed over the last 10 years, (2) what algorithms work best and (3) what objective function is appropriate for AFSCN. We compared data sets from 1992 and from 2002/2003 and found significant differences in the problems. Our evaluation of solutions focuses on three algorithms: local search, Gooley’s algorithm from AFIT, and the
Genitor genetic algorithm. It can be shown that local search (and therefore metaheuristics based on local search) fail to compete with Gooley’s algorithm and Genitor. Finally, while all prior work on AFSCN minimizes request conflicts, we explore an alternative objective function. Because human schedulers must eventually schedule all requests, it might be better to optimize schedules for “repairability”. Our results suggest that minimizing schedule overlaps makes it easier to fit larger requests into the schedule.
Enabled by rapid advances in computational sciences,
logical modeling of complex and large biological networks is more and more feasible making it an increasingly popular approach among biologists. ...Automated high-throughput, drug target identification is one of the primary goals of this
network biology. Targets identified in this way are then used to mine a library of drug chemical compounds in order to identify appropriate therapies. While identification of drug targets is exhaustively feasible on small networks, it remains computationally difficult on moderate and larger models. Moreover, there are several important constraints such as off-target effects, efficacy and safety that should be integrated into the identification of targets if the intention is translation to the clinical space. Here we introduce numerical constraints whereby efficacy is represented by efficiency in response and robustness of outcome. This paper introduces an algorithm that relies on a Constraint Satisfaction (CS) technique to efficiently compute the Minimal Intervention Sets (MIS) within a set of often complex clinical safety constraints with the aim of identifying the smallest least invasive set of targets pharmacologically accessible for therapy that most efficiently and reliably achieve the desired outcome.
A small number of combinatorial optimization problems have search spaces that correspond to elementary landscapes, where the objective function
is an eigenfunction of the Laplacian that describes the ...neighborhood structure of the search space. Many problems are not elementary; however, the objective function of a combinatorial optimization problem can always be expressed as a superposition of multiple elementary landscapes if the underlying neighborhood used is symmetric. This paper presents theoretical results that provide the foundation for algebraic methods that can be used to decompose the objective function of an arbitrary combinatorial optimization problem into a sum of subfunctions, where each subfunction is an elementary landscape. Many steps of this process can be automated, and indeed a software tool could be developed that assists the researcher in finding a landscape decomposition. This methodology is then used to show that the subset sum problem is a superposition of two elementary landscapes, and to show that the quadratic assignment problem is a superposition of three elementary landscapes.
The
study and reverse engineering of regulatory networks has gained in recognition as an insightful tool for the qualitative study of biological mechanisms that underlie a broad range of complex ...illness. In the creation of reliable network models, the integration of prior mechanistic knowledge with experimentally observed behavior is hampered by the disparate nature and widespread sparsity of such measurements. The former challenges conventional regression-based parameter fitting while the latter leads to large sets of highly variable network models that are equally compliant with the data. In this paper, we propose a bounded Constraint Satisfaction (CS) based model checking framework for parameter set identification that readily accommodates partial records and the exponential complexity of this problem. We introduce specific criteria to describe the biological plausibility of competing multi-valued regulatory networks that satisfy all the constraints and formulate model identification as a multi-objective optimization problem. Optimization is directed at maximizing structural parsimony of the regulatory network by mitigating excessive control action selectivity while also favoring increased state transition efficiency and robustness of the network's dynamic response. The framework's scalability, computational time and validity is demonstrated on several well-established and well-studied biological networks.
Recent advances in nucleic acid sequencing technologies have led to a dramatic increase in the number of markers available to generate genetic linkage maps. This increased marker density can be used ...to improve genome assemblies as well as add much needed resolution for loci controlling variation in ecologically and agriculturally important traits. However, traditional genetic map construction methods from these large marker datasets can be computationally prohibitive and highly error prone.
We present
, a method which implements both approximate and exact Traveling Salesperson Problem solvers to generate linkage maps. We demonstrate that for datasets with large numbers of genomic markers (e.g. 10,000) and in multiple population types generated from inbred parents,
can rapidly produce high quality linkage maps with low sensitivity to missing and erroneous genotyping data compared to two other benchmark methods,
and
.
is open source and freely available as an R package.
With the advancement of low cost sequencing technologies, the number of markers used in the generation of genetic maps is expected to continue to rise.
will be a useful tool to handle such large datasets into the future, quickly producing high quality maps using a large number of genomic markers.
We present the first coupled formal and empirical analysis of the Satellite Range Scheduling application. We structure our study as a progression; we start by studying a simplified version of the ...problem in which only one resource is present. We show that the simplified version of the problem is equivalent to a well-known machine scheduling problem and use this result to prove that Satellite Range Scheduling is NP-complete. We also show that for the one-resource version of the problem, algorithms from the machine scheduling domain outperform a genetic algorithm previously identified as one of the best algorithms for Satellite Range Scheduling. Next, we investigate if these performance results generalize for the problem with multiple resources. We exploit two sources of data: actual request data from the U.S. Air Force Satellite Control Network (AFSCN) circa 1992 and data created by our problem generator, which is designed to produce problems similar to the ones currently solved by AFSCN. Three main results emerge from our empirical study of algorithm performance for multiple-resource problems. First, the performance results obtained for the single-resource version of the problem do not generalize: the algorithms from the machine scheduling domain perform poorly for the multiple-resource problems. Second, a simple heuristic is shown to perform well on the old problems from 1992; however it fails to scale to larger, more complex generated problems. Finally, a genetic algorithm is found to yield the best overall performance on the larger, more difficult problems produced by our generator.
Over the last decade and a half, tabu search algorithms for machine scheduling have gained a near-mythical reputation by consistently equaling or establishing state-of-the-art performance levels on a ...range of academic and real-world problems. Yet, despite these successes, remarkably little research has been devoted to developing an understanding of why tabu search is so effective on this problem class. In this paper, we report results that provide significant progress in this direction. We consider Nowicki and Smutnicki's i-TSAB tabu search algorithm, which represents the current state-of-the-art for the makespan-minimization form of the classical job-shop scheduling problem. Via a series of controlled experiments, we identify those components of i-TSAB that enable it to achieve state-of-the-art performance levels. In doing so, we expose a number of misconceptions regarding the behavior and/or benefits of tabu search and other local search metaheuristics for the job-shop problem. Our results also serve to focus future research, by identifying those specific directions that are most likely to yield further improvements in performance.
PDF
