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.

User studies to investigate which human traits affect a user's response to cyber security related situations are typically conducted via self-reported surveys. However, it has been observed that factors such as peer perception, socially desirable responding, and responder bias etc. frequently impact the results, which then do not necessarily reflect the actual behavior of the user when subjected to real world security incidents. To mitigate such biases, we developed PsychoRithm - a software system that presents different real-world security scenarios for the subjects and records their real-time reactions to these scenarios. This paper describes the architecture of PsychoRithm, the design choices we had to make, and the challenges we faced in the design process.

In the dynamic traveling salesman problem (DTSP), the weights and vertices of the graph representing the TSP are allowed to change during the optimization. This work first discusses some issues related to the use of evolutionary algorithms in the DTSP. When efficient algorithms used for the static TSP are applied with restart in the DTSP, we observe that only some edges are generally inserted in and removed from the best solutions after the changes. This result indicates a possible beneficial use of memory approaches, usually employed in cyclic dynamic environments. We propose a memory approach and a hybrid approach that combines our memory approach with the elitism-based immigrants genetic algorithm (EIGA). We compare these two algorithms to four existing algorithms and show that memory approaches can be beneficial for the DTSP with random changes.

Stochastic local search (SLS) is the dominant paradigm for incomplete SAT and MAXSAT solvers. Early studies on small 3SAT instances found that the use of “best improving” moves did not improve search compared to using an arbitrary “first improving” move. Yet SLS algorithms continue to use best improving moves. We revisit this issue by studying very large random and industrial MAXSAT problems. Because locating best improving moves is more expensive than first improving moves, we designed an “approximate best” improving move algorithm and prove that it is as efficient as first improving move SLS. For industrial problems the first local optima found using best improving moves are statistically significantly better than local optima found using first improving moves. However, this advantage reverses as search continues and algorithms must explore equal moves on plateaus. This reversal appears to be associated with critical variables that are in many clauses and that also yield large improving moves.

Home computer users present unique challenges to computer security. A user's actions frequently affect security without the user understanding how. Moreover, whereas some home users are quite adept at protecting their machines from security threats, a vast majority are not. Current generation security tools, unfortunately, do not tailor security to the home user's needs and actions. In this work, we propose Personalized Attack Graphs (PAG) as a formal technique to model the security risks for the home computer informed by a profile of the user attributes such as preferences, threat perceptions and activities. A PAG also models the interplay between user activities and preferences, attacker strategies, and system activities within the system risk model. We develop a formal model of a user profile to personalize a single, monolithic PAG to different users, and show how to use the user profile to predict user actions.

Local search methods based on explicit neighborhood enumeration require at least $O(n)$ time to identify all possible improving moves. For k-bounded pseudo-Boolean optimization problems, recent approaches have achieved $O(k^2*2^{k})$ runtime cost per move, where $n$ is the number of variables and $k$ is the number of variables per subfunction. Even though the bound is independent of $n$, the complexity per move is still exponential in $k$. In this paper, we propose a second order partial derivatives-based approach that executes first-improvement local search where the runtime cost per move is time polynomial in $k$ and independent of $n$. This method is applied to NK-landscapes, where larger values of $k$ may be of particular interest.

By converting the MAXSAT problem to Walsh polynomials, we can efficiently and exactly compute the hyperplane averages of fixed order k. We use this fact to construct initial solutions based on variable configurations that maximize the sampling of hyperplanes with good average evaluations. The Walsh coefficients can also be used to implement a constant time neighborhood update which is integral to a fast next descent local search for MAXSAT (and for all bounded pseudo-Boolean optimization problems.) We evaluate the effect of initializing local search with hyperplane averages on both the first local optima found by the search and the final solutions found after a fixed number of bit flips. Hyperplane initialization not only provides better evaluations, but also finds local optima closer to the globally optimal solution in fewer bit flips than search initialized with random solutions. A next descent search initialized with hyperplane averages is able to outperform several state-of-the art stochastic local search algorithms on both random and industrial instances of MAXSAT.

The home computer user is often said to be the weakest link in computer security. They do not always follow security advice, and they take actions, as in phishing, that compromise themselves. In general, we do not understand why users do not always behave safely, which would seem to be in their best interest. This paper reviews the literature of surveys and studies of factors that influence security decisions for home computer users. We organize the review in four sections: understanding of threats, perceptions of risky behavior, efforts to avoid security breaches and attitudes to security interventions. We find that these studies reveal a lot of reasons why current security measures may not match the needs or abilities of home computer users and suggest future work needed to inform how security is delivered to this user group.

When the epistasis of the fitness function is bounded by a constant, we show that the expected fitness of an offspring of the (1+1)-EA can be efficiently computed for any point. Moreover, we show that, for any point, it is always possible to efficiently retrieve the "best" mutation rate at that point in the sense that the expected fitness of the resulting offspring is maximized. On linear functions, it has been shown that a mutation rate of 1/n is provably optimal. On functions where epistasis is bounded by a constant k, we show that for sufficiently high fitness, the commonly used mutation rate of 1/n is also best, at least in terms of maximizing the expected fitness of the offspring. However, we find for certain ranges of the fitness function, a better mutation rate can be considerably higher, and can be found by solving for the real roots of a degree-k polynomial whose coefficients contain the nonzero Walsh coefficients of the fitness function. Simulation results on maximum k-satisfiability problems and NK-landscapes show that this expectation-maximized mutation rate can cause significant gains early in search.

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.

The autocorrelation function and related correlation length are statistical quantities that capture the ruggedness of the fitness landscape: a measure that is directly related to the hardness of a problem for certain heuristic search algorithms. Typically, these quantities are estimated empirically by sampling along a random walk. In this paper, we show that a polynomial-time Walsh decomposition of the k-satisfiability evaluation function allows us to compute the exact autocorrelation function and correlation length for any given k-satisfiability instance. We also use the decomposition to compute a theoretical expectation for the autocorrelation function and correlation length over the ensemble of instances generated uniformly at random. We find that this expectation is invariant to the constrainedness of the problem as measured by the ratio of clauses to variables. However, we show that filtered problems, which are typically used in local search studies, have a bias that causes a significant deviation from the expected correlation structure of unfiltered, uniformly generated problems.

A new recombination operator is introduced for the Traveling Salesman Problem called partition crossover. Theoretical and empirical results indicate that when two local optima are recombined using partition crossover, two offspring are produced that are highly likely to also be local optima. Thus, the operator is capable of jumping or tunneling from two local optima to two new and distinct local optima without searching intermediate solutions. The operator is respectful and it transmits alleles which means that 1) all common edges from the two parents are inherited and 2) the offspring are constructed using only edges inherited from the two parents. Partition crossover is not always feasible: sometimes two new Hamiltonian circuits cannot be constructed by the operator using only edges inherited from the two parents. But empirical results indicate that partition crossover is feasible 95 percent of the time when recombining randomly selected local optima. Furthermore, from a sample of local optima that are within a short random walk of the global optimum, partition crossover typically relocates the global optimum in a single move when crossover is feasible.

The Movielens dataset and the Herlocker et al. study of 1999 have been very influential in collaborative filtering. Yet, the age of both invites re-examining their applicability. We use Netflix challenge data to re-visit the prior results. In particular, we re-evaluate the parameters of Herlocker et al.'s method on two critical factors: measuring similarity between users and normalizing the ratings of the users. We find that normalization plays a significant role and that Pearson Correlation is not necessarily the best similarity metric.

The landscape formalism unites a finite candidate solution set to a neighborhood topology and an objective function. This construct can be used to model the behavior of local search on combinatorial optimization problems. A landscape is elementary when it possesses a unique property that results in a relative smoothness and decomposability to its structure. In this paper we explain elementary landscapes in terms of the expected value of solution components which are transformed in the process of moving from an incumbent solution to a neighboring solution. We introduce new results about the properties of elementary landscapes and discuss the practical implications for search algorithms.

Particle Swarm Optimization (PSO) is a population-based optimization method in which search points employ a cooperative strategy to move toward one another. In this paper we show that PSO appears to work well on optimization functions. On more complex optimization problems, PSO tends to converge too quickly and then fail to make further progress. We contend that most benchmarks for PSO have classically been demonstrated on single-funnel functions. However, in practice, optimization tasks are more complex and possess higher problem dimensionality. We present empirical results that support our conjecture that PSO performs well on single-funnel functions but tends to stagnate on more complicated landscapes.

In this paper, we propose a decentralized collaborative filtering (CF) approach based on P2P overlay network for the autonomous agents' environment. Experiments show that our approach is more scalable than traditional centralized CF filtering systems and alleviates the sparsity problem in distributed CF.

The best performing algorithms for a particular oversubscribed scheduling application, Air Force Satellite Control Network (AFSCN) scheduling, appear to have little in common. Yet, through careful experimentation and modeling of performance in real problem instances, we can relate characteristics of the best algorithms to characteristics of the application. In particular, we find that plateaus dominate the search spaces (thus favoring algorithms that make larger changes to solutions) and that some randomization in exploration is critical to good performance (due to the lack of gradient information on the plateaus). Based on our explanations of algorithm performance, we develop a new algorithm that combines characteristics of the best performers; the new algorithm's performance is better than the previous best. We show how hypothesis driven experimentation and search modeling can both explain algorithm performance and motivate the design of a new algorithm.

The World Wide Web is a massive corpus that constantly evolves. Classification experiments usually grab a snapshot (temporally and spatially) of the Web for a corpus. In this paper, we examine the effects of page evolution on genre classification of Web pages. Web genre refers to the type of the page characterized by features such as style, form or presentation layout, and meta-content; Web genre can be used to tune spider crawling re-visits and inform relevance judgments for search engines. We found that pages in some genres change rarely if at all and can be used in present-day research experiments without requiring an updated version. We show that an old corpus can be used for training when testing on new Web pages, with only a marginal drop in accuracy rates on genre classification. We also show that features found to be useful in one corpus do not transfer well to other corpora with different genres.

Tabu search is one of the most effective heuristics for locating high-quality solutions to a diverse array of NP-hard combinatorial optimization problems. Despite the widespread success of tabu search, researchers have a poor understanding of many key theoretical aspects of this algorithm, including models of the high-level run-time dynamics and identification of those search space features that influence problem difficulty. We consider these questions in the context of the job-shop scheduling problem (JSP), a domain where tabu search algorithms have been shown to be remarkably effective. Previously, we demonstrated that the mean distance between random local optima and the nearest optimal solution is highly correlated with problem difficulty for a well-known tabu search algorithm for the JSP introduced by Taillard. In this paper, we discuss various shortcomings of this measure and develop a new model of problem difficulty that corrects these deficiencies. We show that Taillard's algorithm can be modeled with high fidelity as a simple variant of a straightforward random walk. The random walk model accounts for nearly all of the variability in the cost required to locate both optimal and sub-optimal solutions to random JSPs, and provides an explanation for differences in the difficulty of random versus structured JSPs. Finally, we discuss and empirically substantiate two novel predictions regarding tabu search algorithm behavior. First, the method for constructing the initial solution is highly unlikely to impact the performance of tabu search. Second, tabu tenure should be selected to be as small as possible while simultaneously avoiding search stagnation; values larger than necessary lead to significant degradations in performance.

No abstract available.

The use of random test problems to evaluate algorithm performance raises an important, and generally unanswered, question: Are the results generalizable to more realistic problems? Researchers generally assume that algorithms with superior performance on difficult, random test problems will also perform well on more realistic, structured problems. Our research explores this assumption for the permutation flow-shop scheduling problem. We introduce a method for generating structured flow-shop problems, which are modeled after features found in some real-world manufacturing environments. We perform experiments that indicate significant differences exist between the search-space topologies of random and structured flow-shop problems, and demonstrate that these differencescanaffect the performance of certain algorithms. Yet despite these differences, and in contrast to difficult random problems, the majority of structured flow-shop problems were easily solved to optimality by most algorithms. For the problems not optimally solved, differences in performance were minor. We conclude that more realistic, structured permutation flow-shop problems are actually relatively easy to solve. Our results also raise doubts as to whether superior performance on difficult random scheduling problems translates into superior performance on more realistic kinds of scheduling problems.

Recent trends in planning research have led to empirical comparison becoming commonplace. The field has started to settle into a methodology for such comparisons, which for obvious practical reasons requires running a subset of planners on a subset of problems. In this paper, we characterize the methodology and examine eight implicit assumptions about the problems, planners and metrics used in many of these comparisons. The problem assumptions are: PR1) the performance of a general purpose planner should not be penalized/biased if executed on a sampling of problems and domains, PR2) minor syntactic differences in representation do not affect performance, and PR3) problems should be solvable by STRIPS capable planners unless they require ADL. The planner assumptions are: PL1) the latest version of a planner is the best one to use, PL2) default parameter settings approximate good performance, and PL3) time cut-offs do not unduly bias outcome. The metrics assumptions are: M1) performance degrades similarly for each planner when run on degraded runtime environments (e.g., machine platform) and M2) the number of plan steps distinguishes performance. We find that most of these assumptions are not supported empirically; in particular, that planners are affected differently by these assumptions. We conclude with a call to the community to devote research resources to improving the state of the practice and especially to enhancing the available benchmark problems.

Error recovery testing is an important part of software testing, especially for safety-critical systems. We show how an AI planning system and the concepts of mutation testing can be combined to generate error recovery tests for software. We identify a set of mutation operations on the representation that the planner uses when generating test cases. These mutations cause error recovery test cases to be generated. The paper applies these concepts to the testing of a large tape storage system.

Many two layer robot architectures have been proposed and implemented. While justification for the design can be well argued, how does one know it is really a good idea? In this paper, one describes a two layer architecture (reinforcement learning in the bottom layer and POMDP planning at the top) for a simulated robot and summarize a set of three experiments in which one evaluated the design. To address the many difficulties of evaluating robot architectures, one advocates an experimental approach in which design criteria are elucidated and then form the basis for the evaluation experiments. In our case, one tests the implementation for its reliability and generalization (our design criteria) by comparing our architecture to one in which a key component is substituted; in these experiments, one demonstrates significant performance gains on the design criteria for our architecture.

We compare several techniques for scheduling shipment of customer orders for the Coors Brewing warehouse and production line. The goal is to minimize time at dock for trucks and railcars while also minimizing inventory. The techniques include a genetic algorithm, local search operators, heuristic rules, systematic search and hybrid approaches. Initial results show a hybrid genetic algorithm to be superior to the other methods. The evaluation function is a fast approximate form of a warehouse simulation. We also assess the sensitivity of the search algorithms to noise in an approximate evaluation function using a more detailed (and costly) simulation.

We compare several techniques for scheduling shipment of customer orders for the Coors Brewing warehouse and production line. The goal is to minimize time at dock for trucks and railcars while also minimizing inventory. The techniques include a genetic algorithm, local search operators, heuristic rules, systematic search and hybrid approaches. Initial results show a hybrid genetic algorithm to be superior to the other methods. The evaluation function is a fast approximate form of a warehouse simulation. We also assess the sensitivity of the search algorithms to noise in an approximate evaluation function using a more detailed (and costly) simulation.

This paper reports on a software understanding field study during the enhancement of large-scale software. The participants were professional software maintenance personnel from industry. The paper reports on the general understanding process, the kinds of actions programmers preferred during the enhancement task, the level of abstraction at which they were working, and role of hypotheses in the enhancement strategies they used. The results of the observations are also interpreted in terms of the information needs of these personnel during the enhancement task. We found that programmers work predominantly at the code and algorithmic levels with differences depending on the stage of the enhancement. They frequently switch between levels of abstraction. The programmers' main concerns are with what software does and how this is accomplished, not why software was built a certain way. These questions guide the work process. There was strong indication that memory (over)load is an issue. This is, of course, related to the size of the software. Information is sought and cross-referenced from a variety of sources from application domain concepts to code-related information, outpacing current maintenance environments' capabilities which are mostly stratified by information sources, making cross-referencing difficult. © 1997 John Wiley & Sons, Ltd.

Search engines are among the most useful and high-profile resources on the Internet. The problem of finding information on the Internet has been replaced with the problem of knowing where search engines are, what they are designed to retrieve, and how to use them. This article describes and evaluates SavvySearch, a metasearch engine designed to intelligently select and interface with multiple remote search engines. The primary metasearch issue examined is the importance of carefully selecting and ranking remote search engines for user queries. We studied the efficacy of SavvySearch's incrementally acquired metaindex approach to selecting search engines by analyzing the effect of time and experience on performance. We also compared the metaindex approach to the simpler categorical approach and showed how much experience is required to surpass the simple scheme.

System testing of software with command language interfaces can be automated using grammar based test generation or through generating tests from an application domain specification. When viewing test case generation as constructing a sequence of commands to achieve a testing goal, AI planning systems show promise. We report on automated test generation with an AI planning system and compare results to tests generated by Sleuth, a tool for automated application domain testing.

As planning technology improves, artificial intelligence planners are being embedded in increasingly complicated environments: ones that are particularly challenging even for human experts. Consequently, failure is becoming both increasingly likely for these systems (due to the difficult and dynamic nature of the new environments) and increasingly important to address (due to the systems' potential use on real world applications). The paper describes the development of a failure recovery component for a planner in a complex simulated environment and a procedure (called failure recovery analysis) for assisting programmers in debugging that planner. The failure recovery design is iteratively enhanced and evaluated in a series of experiments. Failure recovery analysis is described and demonstrated on an example from the Phoenix planner. The primary advantage of these approaches over existing approaches is that they are based on only a weak model of the planner and its environment, which makes them most suitable when the planner is being developed. By integrating them, failure recovery and failure recovery analysis improve the reliability of the planner by repairing failures during execution and identifying failures due to bugs in the planner and failure recovery itself.>

Statistical causal modeling techniques allow us to develop models of program behavior, but these techniques tend to be limited in what they can model: either continuing, repetitive influences or causal influences without cycles, but not both as appear in many environments. The paper describes how two statistical modeling techniques can be combined to suggest and test specific hypotheses about how the environment and the AI planner's design causally influence the planner's behavior. One technique, dependency detection, is designed to identify relationships (dependencies) between particular failures, the methods that repair them and the occurrence of failures downstream. Another method, path analysis, builds causal models of correlational data. Dependency detection operates over a series of events, and path analysis models within a temporal snapshot. We explain the integration of the techniques and demonstrate it on execution data from the Phoenix planner.>

This paper describes two approaches for detecting patterns of detrimental program behavior, called dependencies, over long periods of time; these dependencies indicate cases where previous events influence the occurrence of later failure. This research extends a previous approach that was limited to temporally adjacent events. The two approaches, heuristic search and local search, are demonstrated on several data sets from an AI planner and are compared on their efficiency and the dependencies they detect.>

The roles of evaluation in empirical artificial intelligence (AI) research are described, in an idealized cyclic model and in the context of three case studies. The case studies illustrate the pitfalls in evaluation and the contributions of evaluation at all stages of the research cycle. Evaluation methods are contrasted with those of the behavioral sciences, and it is concluded that AI must define and refine its own methods. To this end, several experiment schemas and many specific evaluation criteria are described. Recommendations are offered in the hope of encouraging the development and practice of evaluation methods in AI. The first case study illustrates problems with evaluating knowledge-based systems, specifically a portfolio management expert system called FOLIO. The second study focuses on the relationship between evaluation and the evolution of the GRANT system, specifically, how the evaluations changed as GRANT's knowledge base was sealed up. Third, the cyclic nature of a given research model is examined.>