Randomised restarted search in ILP

Recent statistical performance studies of search algorithms in difficult combinatorial problems have demonstrated the benefits of randomising and restarting the search procedure. Specifically, it has been found that if the search cost distribution of the non-restarted randomised search exhibits a slower-than-exponential decay (that is, a “heavy tail”), restarts can reduce the search cost expectation. We report on an empirical study of randomised restarted search in ILP. Our experiments conducted on a high-performance distributed computing platform provide an extensive statistical performance sample of five search algorithms operating on two principally different classes of ILP problems, one represented by an artificially generated graph problem and the other by three traditional classification benchmarks (mutagenicity, carcinogenicity, finite element mesh design). The sample allows us to (1) estimate the conditional expected value of the search cost (measured by the total number of clauses explored) given the minimum clause score required and a “cutoff” value (the number of clauses examined before the search is restarted), (2) estimate the conditional expected clause score given the cutoff value and the invested search cost, and (3) compare the performance of randomised restarted search strategies to a deterministic non-restarted search. Our findings indicate striking similarities across the five search algorithms and the four domains, in terms of the basic trends of both the statistics (1) and (2). Also, we observe that the cutoff value is critical for the performance of the search algorithm, and using its optimal value in a randomised restarted search may decrease the mean search cost (by several orders of magnitude) or increase the mean achieved score significantly with respect to that obtained with a deterministic non-restarted search. Editors: Rui Camacho     

Planning as Propositional CSP: From Walksat to Local Search Techniques for Action Graphs

Graphplan-style of planning can be formulated as an incremental propositional CSP where the (boolean) variables correspond to operator instantiations (actions) that are or are not scheduled at certain time steps. In this paper we present a framework for solving this class of propositional CSPs using local search in planning graphs. The search space consists of particular subgraphs of a planning graph corresponding to (complete) variable assignments, and representing partial plans. The operators for moving from one search state to the next one are graph modifications corresponding to revisions of the current variable assignment (partial plan), or to an extension of the represented CSP.Our techniques are implemented in a planner called LPG using various types of heuristics based on a parametrized objective function, where the parameters weight different constraint violations, and are dynamically evaluated using Lagrange multipliers. LPG's basic heuristic was inspired by Walksat, which in Kautz and Selman's Blackbox can be used to solve the SAT-encoding of a planning graph. An advantage of LPG is that its heuristics exploit the structure of the planning graph, while Blackbox relies on general heuristics for SAT-problems, and requires the translation of the planning graph into propositional clauses. Another major difference is that LPG can handle action execution costs to produce good quality plans. This is achieved by an anytime process minimizing an objective function based on the number of constraint violations in a plan and on its overall cost. Experimental results illustrate the efficiency of our approach, showing, in particular, that LPG is significantly faster than Blackbox and other planners based on planning graphs.     

A GA-based approach for optimizing single-part flow-line configurations of RMS

Generating economical single-part flow-line (SPFL) configurations as candidates for a given demand period is an important optimization problem for reconfigurable manufacturing systems (RMS). The optimization problem addresses the questions of selecting number of workstations, number and type of paralleling identical machines as well as operation setups (OSs) for each workstation. The inputs include a precedence graph for a part, relationships between OSs and operations, machine options for each OS. The objective is to minimize the capital costs of the SPFL configurations. A 0–1 nonlinear programming (NLP) model is developed to handle the key issue of sharing machine utilization over consecutive OSs which is ignored in existing 0–1 integer linear programming (ILP) model. Then a GA-based approach is proposed to identify a set of economical solutions. To overcome the complexity of search space, a novel procedure is presented to guide GA to search within a refined solution space comprising the optimal configurations associated with feasible OS sequences. A case study shows that the best solution derived from the 0–1 NLP model through GA is better than the optimum of existing 0–1 ILP model. The results illustrate the effectiveness of our model and the efficiency of the GA-based approach.     

Efficient reordering of Prolog programs

Prolog programs are often inefficient: execution corresponds to a depth-first traversal of an AND/OR graph; traversing subgraphs in another order can be less expensive. It is shown how the reordering of clauses within Prolog predicates, and especially of goals within clauses, can prevent unnecessary search. The characterization and detection of restrictions on reordering is discussed. A system of calling modes for Prolog, geared to reordering, is proposed, and ways to infer them automatically are discussed. The information needed for safe reordering is summarized, and which types can be inferred automatically and which must be provided by the user are considered. An improved method for determining a good order for the goals of Prolog clauses is presented and used as the basis for a reordering system     

拉丁超立方体抽样遗传算法求解图的二划分问题

图的二划分问题是一个典型的NP-hard组合优化问题, 在许多领域都有重要应用. 近年来, 传统遗传算法等各种智能优化方法被引入到该问题的求解中来, 但效果不理想. 基于理想浓度模型的机理分析, 利用拉丁超立方体抽样的理论和方法, 对遗传算法中的交叉操作进行了重新设计, 并在分析图二划分问题特点的基础上, 结合局部搜索策略, 给出了一个解决图二划分问题的新的遗传算法, 称之为拉丁超立方体抽样遗传算法. 通过将该算法与简单遗传算法和佳点集遗传算法进行求解图二划分问题的仿真模拟比较, 可以看出新的算法提高了求解的质量、速度和精度.     

Intelligent backtracking in plan-based deduction

This paper develops a method of mechanical deduction based on a graphical representation of the structure of proofs. Attempts to find a refutation(s) are recorded in the form of plans, corresponding to portions of an AND/OR graph search space and representing a purely deductive structure of derivation. This method can be applied to any initial base (set of nonnecessarily Horn clauses). Unlike the exhaustive (blind) backtracking which treats all the goals deduced in the course of a proof as equally probable sources of failure, his approach detects the exact source of failure. Only a small fragment of the solution space is kept on disk as a collection of pairs, each of which consists of a plan and a graph of constraints. The search strategy and the method of nonredundant processing of individual pairs which leads to a solution (if it exists) is presented. This approach is compared?on a special case?with a blind backtracking algorithm for which an exponential improvement is demonstrated. Some important implementation problems are discussed, and toplevel design of a mechanical deduction system implementing our algorithm is presented. It is proven that the algorithm is complete in the following sense: if for a given base a resolution refutation exists, then this refutation is found by the algorithm.     

Toward leaner binary-clause reasoning in a satisfiability solver

Binary-clause reasoning has been shown to reduce the size of the search space on many satisfiability problems, but has often been so expensive that run-time was higher than that of a simpler procedure that explored a larger space. The method of Sharir for detecting strongly connected components in a directed graph can be adapted to performing lean resolution on a set of binary clauses. Beyond simply detecting unsatisfiability, the goal is to find implied equivalent literals, implied unit clauses, and implied binary clauses.     

On the termination of clause graph resolution

This paper introducesextended clause graph resolution, a variant of Kowalski's clause graph resolution that is terminating at the full first-order level. This terminating variant is obtained by extending the definitions of clause graph and clause graph resolution to include more information about the interdependencies between links and clauses in the graph, by restricting purity slightly and by employing an exhaustive search of eligible links.     

Toward leaner binary-clause reasoning in a satisfiability solver

Binary-clause reasoning has been shown to reduce the size of the search space on many satisfiability problems, but has often been so expensive that run-time was higher than that of a simpler procedure that explored a larger space. The method of Sharir for detecting strongly connected components in a directed graph can be adapted to performing lean resolution on a set of binary clauses. Beyond simply detecting unsatisfiability, the goal is to find implied equivalent literals, implied unit clauses, and implied binary clauses.     

A Neurogenetic approach for the resource-constrained project scheduling problem

A variety of metaheuristic approaches have emerged in recent years for solving the resource-constrained project scheduling problem (RCPSP), a well-known NP-hard problem in scheduling. In this paper, we propose a Neurogenetic approach which is a hybrid of genetic algorithms (GA) and neural-network (NN) approaches. In this hybrid approach the search process relies on GA iterations for global search and on NN iterations for local search. The GA and NN search iterations are interleaved in a manner that allows NN to pick the best solution thus far from the GA pool and perform an intensification search in the solution's local neighborhood. Similarly, good solutions obtained by NN search are included in the GA population for further search using the GA iterations. Although both GA and NN approaches, independently give good solutions, we found that the hybrid approach gives better solutions than either approach independently for the same number of shared iterations. We demonstrate the effectiveness of this approach empirically on the standard benchmark problems of size J30, J60, J90 and J120 from PSPLIB.     

Structural pattern recognition using genetic algorithms

This paper presents a genetic algorithm (GA) based optimization procedure for the solution of structural pattern recognition problem using the attributed relational graph representation and matching technique. In this study, candidate solutions are represented by integer strings and the population is randomly initialized. The GA is employed to generate a monomorphic mapping. As all the mapping constraints are not enforced during the search phase in order to speedup the search, an efficient pose clustering algorithm is used to eliminate spurious matches and to determine the presence of the model in the scene. The performance of the proposed approach to pattern recognition by subgraph isomorphism is demonstrated using line patterns and silhouette images.     

Improving statistical MT by coupling reordering and decoding

In this paper we describe an elegant and efficient approach to coupling reordering and decoding in statistical machine translation, where the n-gram translation model is also employed as distortion model. The reordering search problem is tackled through a set of linguistically motivated rewrite rules, which are used to extend a monotonic search graph with reordering hypotheses. The extended graph is traversed in the global search when a fully informed decision can be taken. Further experiments show that the n-gram translation model can be successfully used as reordering model when estimated with reordered source words. Experiments are reported on the Europarl task (Spanish–English and English–Spanish). Results are presented regarding translation accuracy and computational efficiency, showing significant improvements in translation quality with respect to monotonic search for both translation directions at a very low computational cost.     

Multi-Way Distance Join Queries in Spatial Databases

Let a tuple of n objects obeying a query graph (QG) be called the n-tuple. The D_{_distance}-value of this n-tuple is the value of a linear function of distances of the n objects that make up this n-tuple, according to the edges of the QG. This paper addresses the problem of finding the K n-tuples between n spatial datasets that have the smallest D_{_distance}-values, the so-called K-multi-way distance join query (K-MWDJQ), where each set is indexed by an R-tree-based structure. This query can be viewed as an extension of K-closest-pairs query (K-CPQ) [8] for n inputs. In addition, a recursive non-incremental branch-and-bound algorithm following a depth-first search for processing synchronously all inputs without producing any intermediate result is proposed. Enhanced pruning techniques are also applied to n R-trees nodes in order to reduce the total response time and the number of distance computations of the query. Due to the exponential nature of the problem, we also propose a time-based approximate version of the recursive algorithm that combines approximation techniques to adjust the quality of the result and the global processing time. Finally, we give a detailed experimental study of the proposed algorithms using real spatial datasets, highlighting their performance and the quality of the approximate results.     

均匀设计抽样混合遗传算法求解图的二划分问题

遗传算法(GA)的运行机理及特点是具有定向制导的随机搜索技术,其定向制导的原则是:导向以高适应度模式为祖先的"家族"方向。以此结论为基础,利用均匀设计抽样(UDS)的理论和方法,对遗传算法中的交叉操作进行重新设计,并在分析图二划分问题特点的基础上,结合局部搜索策略,给出了一个求解图二划分问题的新遗传算法,称之为基于均匀设计抽样的混合遗传算法。最后将该算法与简单遗传算法和佳点集遗传算法进行比较。通过模拟比较,可以看出新算法不但提高了算法的求解速度和精度,而且避免了常有的早期收敛现象。     

考虑缓冲区的自动生产单元的无死锁调度策略

在制造系统中,必须防止死锁的发生.本文提出了一种在制造系统(带有有限缓冲区)中搜索最优的无死锁调度的算法.为此首先介绍了死锁问题及其图论表示方法,然后在遗传算法的基础上,运用图论算法来保证无死锁的调度结果.为了保证遗传算法生成的调度策略能够满足所要求的约束,运用图论方法选择无死锁个体,或添加缓冲区,从而在基本保证了系统的主要性能指标的同时,得到系统可行的无死锁调度结果.最后给出了一个运用此方法解决死锁问题的实例.     

A propositional theorem prover to solve planning and other problems

Classical STRIPS-style planning problems are formulated as theorems to be proven from a new point of view: that the problem is not solvable. The result for a refutation-based theorem prover may be a propositional formula that is to be proven unsatisfiable. This formula is identical to the formula that may be derived directly by various “SAT compilers”, but the theorem-proving view provides valuable additional information not in the formula, namely, the theorem to be proven. Traditional satisfiability methods, most of which are based on model search, are unable to exploit this additional information. However, a new algorithm called “Modoc” is able to exploit this information and has achieved performance comparable to the fastest known satisfiability methods, including stochastic search methods, on planning problems that have been reported by other researchers, as well as formulas derived from other applications. Unlike most theorem provers, Modoc performs well on both satisfiable and unsatisfiable formulas. Modoc works by a combination of back-chaining from the theorem clauses and forward-chaining on tractable subformulas. In some cases, Modoc is able to solve a planning problem without finding a complete assignment because the back-chaining methodology is able to ignore irrelevant clauses. Although back-chaining is well known in the literature, a high level of search redundancy existed in previous methods; Modoc incorporates a new technique called “autarky pruning”, which reduces search redundancy to manageable levels, permitting the benefits of back-chaining to emerge, for certain problem classes. Experimental results are presented for planning problems and formulas derived from other applications. This revised version was published online in June 2006 with corrections to the Cover Date.     

A simplifier for propositional formulas with many binary clauses

Deciding whether a propositional formula in conjunctive normal form is satisfiable (SAT) is an NP-complete problem. The problem becomes linear when the formula contains binary clauses only. Interestingly, the reduction to SAT of a number of well-known and important problems--such as classical AI planning and automatic test pattern generation for circuits--yields formulas containing many binary clauses. In this paper we introduce and experiment with 2-SIMPLIFY, a formula simplifier targeted at such problems. 2-SIMPLIFY constructs the transitive closure of the implication graph corresponding to the binary clauses in the formula and uses this graph to deduce new unit literals. The deduced literals are used to simplify the formula and update the graph, and so on, until stabilization. Finally, we use the graph to construct an equivalent, simpler set of binary clauses. Experimental evaluation of this simplifier on a number of bench-mark formulas produced by encoding AI planning problems prove 2-SIMPLIFY to be a useful tool in many circumstances.     

An adaptive hybrid genetic algorithm for the three-matching problem

This paper presents a hybrid genetic algorithm (GA) with an adaptive application of genetic operators for solving the 3-matching problem (3MP), an NP-complete graph problem. In the 3MP, we search for the partition of a point set into minimal total cost triplets, where the cost of a triplet is the Euclidean length of the minimal spanning tree of the three points. The problem is a special case of grouping and facility location problems. One common problem with GA applied to hard combinatorial optimization, like the 3MP, is to incorporate problem-dependent local search operators into the GA efficiently in order to find high-quality solutions. Small instances of the problem can be solved exactly, but for large problems, we use local optimization. We introduce several general heuristic crossover and local hill-climbing operators, and apply adaptation to choose among them. Our GA combines these operators to form an effective problem solver. It is hybridized as it incorporates local search heuristics, and it is adaptive as the individual recombination/improvement operators are fired according to their online performance. Test results show that this approach gives approximately the same or even slightly better results than our previous, fine tuned GA without adaptation. It is better than a grouping GA for the partitioning considered. The adaptive combination of operators eliminates a large set of parameters, making the method more robust, and it presents a convenient way to build a hybrid problem solver     

A model and a first analysis of distributed‐search contraction‐based strategies

While various approaches to parallel theorem proving have been proposed, their usefulness is evaluated only empirically. This research is a contribution towards the goal of machine‐independent analysis of theorem‐proving strategies. This paper considers clausal contraction‐based strategies and their parallelization by distributed search, with subdivision of the search space and propagation of clauses by message‐passing (e.g., à la Clause‐Diffusion). A model for the representation of the parallel searches produced by such strategies is presented, and the bounded‐search‐spaces approach to the measurement of search complexity in infinite search spaces is extended to distributed search. This involves capturing both its advantages, e.g., the subdivision of work, and disadvantages, e.g., the cost of communication, in terms of search space. These tools are applied to compare the evolution of the search space of a contraction‐based strategy with that of its parallelization in the above sense. This revised version was published online in June 2006 with corrections to the Cover Date.