Parameter tuning of a choice-function based hyperheuristic using Particle Swarm Optimization

A Constraint Satisfaction Problem is defined by a set of variables and a set of constraints, each variable has a nonempty domain of possible values. Each constraint involves some subset of the variables and specifies the allowable combinations of values for that subset. A solution of the problem is defined by an assignment of values to some or all of the variables that does not violate any constraints. To solve an instance, a search tree is created and each node in the tree represents a variable of the instance. The order in which the variables are selected for instantiation changes the form of the search tree and affects the cost of finding a solution. In this paper we explore the use of a Choice Function to dynamically select from a set of variable ordering heuristics the one that best matches the current problem state in order to show an acceptable performance over a wide range of instances. The Choice Function is defined as a weighted sum of process indicators expressing the recent improvement produced by the heuristic recently used. The weights are determined by a Particle Swarm Optimization algorithm in a multilevel approach. We report results where our combination of strategies outperforms the use of individual strategies.     

Mixing Static and Dynamic Partitioning to Parallelize a Constraint Programming Solver

This paper presents an external parallelization of Constraint Programming (CP) search tree mixing both static and dynamic partitioning. The principle of the parallelization is to partition the CP search tree into a set of sub-trees, then assign each sub-tree to one computing core in order to perform a local search using a sequential CP solver. In this context, static partitioning consists of decomposing the CP variables domains in order to split the CP search tree into a set of disjoint sub-trees to assign them to the cores. This strategy performs well without adding an extra cost to the parallel search, but the problem is the load imbalance between computing cores. On the other hand, dynamic partitioning is based on preservation of the search state to generate, dynamically or on demand, the sub-trees that are assigned to the cores. This strategy offers good load balancing between the different computing cores, but computing overcosts appear due to the initialisation of the search when a sub-tree is migrated from one core to another. In this paper, we propose a new partitioning strategy that mixes the static and dynamic partitioning and enjoys the benefits of each strategy. This mixed partitioning is designed to run on shared and distributed memory architectures. The performances obtained are illustrated by solving the CP problems modelled using the FlatZinc format and solved using the Google OR-Tools solver on top of the parallel Bobpp framework.     

Parallel heterogeneous genetic algorithms for continuous optimization

In this paper we address the physical parallelization of a very efficient genetic algorithm (GA) known as gradual distributed real-coded GA (GD-RCGA). This search model naturally provides a set of eight subpopulations residing in a cube topology having two faces for promoting exploration and exploitation. The resulting technique has been shown to yield very accurate results in continuous optimization by using crossover operators tuned to explore and exploit the solutions inside each subpopulation. Here, we encompass the actual parallelization of the technique, and get deeper into the importance of running a synchronous versus an asynchronous version of the basic GD-RCGA model. We also present the evaluation of the parallel execution of GD-RCGA over two local area networks, a Fast-Ethernet network and a Myrinet network. Our results indicate that the GD-RCGA model maintains a very high level of accuracy for continuous optimization when run in parallel, and we also demonstrate the relative advantages of each algorithm version over the two networks. Finally, we show that the async parallelization scales better than the sync one, what suggests future research lines for WAN execution and new models of search based on the original two-faced cube.     

Inference of regular languages using state merging algorithms with search

State merging algorithms have emerged as the solution of choice for the problem of inferring regular grammars from labeled samples, a known NP-complete problem of great importance in the grammatical inference area. These methods derive a small deterministic finite automaton from a set of labeled strings (the training set), by merging parts of the acceptor that corresponds to this training set. Experimental and theoretical evidence have shown that the generalization ability exhibited by the resulting automata is highly correlated with the number of states in the final solution.As originally proposed, state merging algorithms do not perform search. This means that they are fast, but also means that they are limited by the quality of the heuristics they use to select the states to be merged. Sub-optimal choices lead to automata that have many more states than needed and exhibit poor generalization ability.In this work, we survey the existing approaches that generalize state merging algorithms by using search to explore the tree that represents the space of possible sequences of state mergings. By using heuristic guided search in this space, many possible state merging sequences can be considered, leading to smaller automata and improved generalization ability, at the expense of increased computation time.We present comparisons of existing algorithms that show that, in widely accepted benchmarks, the quality of the derived solutions is improved by applying this type of search. However, we also point out that existing algorithms are not powerful enough to solve the more complex instances of the problem, leaving open the possibility that better and more powerful approaches need to be designed.     

Parallel Remapping of Adaptive Problems

In this paper we present fast parallel algorithms for remapping a class of irregular and adaptive problems on coarse-grained distributed memory machines. We show that the remapping of these applications, using simple index-based mapping algorithm, can be reduced to sorting a nearly sorted list of integers or merging an unsorted list of integers with a sorted list of integers. By using the algorithms we have developed, the remapping of these problems can be achieved at a fraction of the cost of mapping from scratch.     

Semantic partitioning of peer-to-peer search space

Peer-to-peer (P2P) networks are beginning to form the infrastructure of future applications. Computers are organized in P2P overlay networks to facilitate search queries with reasonable cost. So, scalability is a major aim in design of P2P networks. In this paper, to obtain a high factor of scalability, we partition network search space using a consistent static shared upper ontology. We name our approach semantic partition tree (SPT). All resources and queries are annotated using the upper ontology and queries are semantically routed in the overlay network. Also, each node indexes addresses of other nodes that possess contents expressible by the concept it maintains. So, our approach can be conceived as an ontology-based distributed hash table (DHT). Also, we introduce a lookup service for the network which is very scalable and independent of the network size and just depends on depth of the ontology tree. Further, we introduce a broadcast algorithm on the network. We present worst case analysis of both lookup and broadcast algorithms and measure their performance using simulation. The results show that our scheme is highly scalable and can be used in real P2P applications.     

State agnostic planning graphs: deterministic,non-deterministic,and probabilistic planning

Planning graphs have been shown to be a rich source of heuristic information for many kinds of planners. In many cases, planners must compute a planning graph for each element of a set of states, and the naive technique enumerates the graphs individually. This is equivalent to solving a multiple-source shortest path problem by iterating a single-source algorithm over each source.We introduce a data-structure, the state agnostic planning graph, that directly solves the multiple-source problem for the relaxation introduced by planning graphs. The technique can also be characterized as exploiting the overlap present in sets of planning graphs. For the purpose of exposition, we first present the technique in deterministic (classical) planning to capture a set of planning graphs used in forward chaining search. A more prominent application of this technique is in conformant and conditional planning (i.e., search in belief state space), where each search node utilizes a set of planning graphs; an optimization to exploit state overlap between belief states collapses the set of sets of planning graphs to a single set. We describe another extension in conformant probabilistic planning that reuses planning graph samples of probabilistic action outcomes across search nodes to otherwise curb the inherent prediction cost associated with handling probabilistic actions. Finally, we show how to extract a state agnostic relaxed plan that implicitly solves the relaxed planning problem in each of the planning graphs represented by the state agnostic planning graph and reduces each heuristic evaluation to counting the relevant actions in the state agnostic relaxed plan. Our experimental evaluation (using many existing International Planning Competition problems from classical and non-deterministic conformant tracks) quantifies each of these performance boosts, and demonstrates that heuristic belief state space progression planning using our technique is competitive with the state of the art.     

Temporal-difference search in computer Go

Temporal-difference learning is one of the most successful and broadly applied solutions to the reinforcement learning problem; it has been used to achieve master-level play in chess, checkers and backgammon. The key idea is to update a value function from episodes of real experience, by bootstrapping from future value estimates, and using value function approximation to generalise between related states. Monte-Carlo tree search is a recent algorithm for high-performance search, which has been used to achieve master-level play in Go. The key idea is to use the mean outcome of simulated episodes of experience to evaluate each state in a search tree. We introduce a new approach to high-performance search in Markov decision processes and two-player games. Our method, temporal-difference search, combines temporal-difference learning with simulation-based search. Like Monte-Carlo tree search, the value function is updated from simulated experience; but like temporal-difference learning, it uses value function approximation and bootstrapping to efficiently generalise between related states. We apply temporal-difference search to the game of 9×9 Go, using a million binary features matching simple patterns of stones. Without any explicit search tree, our approach outperformed an unenhanced Monte-Carlo tree search with the same number of simulations. When combined with a simple alpha-beta search, our program also outperformed all traditional (pre-Monte-Carlo) search and machine learning programs on the 9×9 Computer Go Server.     

有限状态机模型测试序列生成算法研究

在测试工程学中,应用测试生成树构建测试序列是相关测试方法的基础步骤,在传统测试生成树的基础上加入约束集的概念,使产生的测试生成树符合生产实际。同时在面向状态识别的测试方法中,考虑约束集对所生成状态区分序列的影响,基于带约束的测试生成树产生相应的特征集、状态识别集和UIO序列,提出或者改进了相应的算法。同时将测试方法扩展到了NFSM的情形下,提出了NFSM模型中前缀序列的生成算法和状态识别集的构建算法;结合状态识别矩阵与有限状态机同步乘积,提出在NFSM模型中的适应性测试方法,扩展了FSM应用于测试理论的完备性。建立了相应的测试方法工具集,实现了上述算法,验证了其可行性。最后给出了下一步的工作。     

Using relevance feedback in content-based image metasearch

MetaSeek is an image metasearch engine developed to explore the querying of large, distributed, online visual information systems. The current implementation integrates user feedback into a performance-ranking mechanism. MetaSeek selects and queries the target image search engines according to their success under similar query conditions in previous searches. The current implementation keeps track of each target engine's performance by integrating user feedback for each visual query into a performance database. We begin with a review of the issues in content-based visual query, then describe the current MetaSeek implementation. We present the results of experiments that evaluated the implementation in comparison to a previous version of the system and a baseline engine that randomly selects the individual search engines to query. We conclude by summarizing open issues for future research     

Branch-and-bound task allocation with task clustering-based pruning

We propose a task allocation algorithm that aims at finding an optimal task assignment for any parallel programs on a given machine configuration. The theme of the approach is to traverse a state–space tree that enumerates all possible task assignments. The efficiency of the task allocation algorithm comes from that we apply a pruning rule on each traversed state to check whether traversal of a given sub-tree is required by taking advantage of dominance relation and task clustering heuristics. The pruning rules try to eliminate partial assignments that violate the clustering of tasks, but still keeping some optimal assignments in the future search space. In contrast to previous state–space searching methods for task allocation, the proposed pruning rules significantly reduce the time and space required to obtain an optimal assignment and lead the traversal to a near optimal assignment in a small number of states. Experimental evaluation shows that the pruning rules make the state–space searching approach feasible for practical use.     

The performance of message-passing using restricted virtual memory remapping

DASH is a distributed operating system kernel. Message-passing (MP) is used for local communication, and the MP system uses virtual memory ( VM) remapping instead of software memory copying for moving large amounts of data between virtual address spaces. Remapping eliminates a potential communication bottleneck and may increase the feasibility of moving services such as file services to the user level. Previous systems that have used VM remapping for message transfer, however, have suffered from high per-operation delay, limiting the use of the technique. The DASH design reduces this delay by restricting the generality of remapping: a fixed part of every space is reserved for remapping, and a page's virtual address does not change when it is moved between spaces. We measured the performance of the DASH kernel for Sun 3/50 workstations, on which memory can be copied at 3·9 MB/s. Using remapping, DASH can move large messages between user spaces at a rate of 39 MB/s if they are not referenced and 24·8 MB/s if each page is referenced. Furthermore, the per-operation delay is low, so VM remapping is beneficial even for messages containing only one page. To further understand the performance of the DASH MP system, we broke an MP operation into short code segments and timed them with microsecond precision. The results show the relative costs of data movement and the other components of MP operations, and allow us to evaluate several specific design decisions.     

Decentralized remapping of data parallel applications in distributed memory multiprocessors

In this paper we present a decentralized remapping method for data parallel applications on distributed memory multiprocessors. The method uses a generalized dimension exchange (GDE) algorithm periodically during the execution of an application to balance (remap) the system's workload. We implemented this remapping method in parallel WaTor simulations and parallel image thinning applications, and found it to be effective in reducing the computation time. The average performance gain is about 20% in the WaTor simulation of a 256 × 256 ocean grid on 16 processors, and up to 8% in the thinning of a typical image of size 128 × 128 on eight processors. The performance gains due to remapping in the image thinning case are reasonably substantial given the fact that the application by its very nature does not necessarily favor remapping. We also implemented this remapping method, using up to 32 processors, for partitioning and re-partitioning of grids in computational fluid dynamics. It was found that the GDE-based parallel refinement policy, coupled with simple geometric strategies, produces partitions that are comparable in quality to those from the best serial algorithms. © 1997 John Wiley & Sons, Ltd.     

Efficient Algorithms for the Inference of Minimum Size DFAs

This work describes algorithms for the inference of minimum size deterministic automata consistent with a labeled training set. The algorithms presented represent the state of the art for this problem, known to be computationally very hard.In particular, we analyze the performance of algorithms that use implicit enumeration of solutions and algorithms that perform explicit search but incorporate a set of techniques known as dependency directed backtracking to prune the search tree effectively.We present empirical results that show the comparative efficiency of the methods studied and discuss alternative approaches to this problem, evaluating their advantages and drawbacks.     

Experimentation-Driven Knowledge Acquisition for Planning

Knowledge engineering for planning is expensive and the resulting knowledge can be imperfect. To autonomously learn a plan operator definition from environmental feedback, our learning system WISER explores an instantiated literal space using a breadth-first search technique. Each node of the search tree represents a state, a unique subset of the instantiated literal space. A state at the root node is called a seed state. WISER can generate seed states with or without utilizing imperfect expert knowledge. WISER experiments with an operator at each node. The positive state, in which an operator can be successfully executed, constitutes initial preconditions of an operator. We analyze the number of required experiments as a function of the number of missing preconditions in a seed state. We introduce a naive domain assumption to test only a subset of the exponential state space. Since breadth-first search is expensive, WISER introduces two search techniques to reorder literals at each level of the search tree. We demonstrate performance improvement using the naive domain assumption and literal-ordering heuristics. To learn the effects of an operator, WISER computes the delta state, composed of the add list and the delete list, and parameterizes it. Unlike previous systems, WISER can handle unbound objects in the delta state. We show that machine-generated effects definitions are often simpler in representation than expert-provided definitions.
     

On the complexity of distributed query optimization

While a significant amount of research efforts has been reported on developing algorithms, based on joins and semijoins, to tackle distributed query processing, there is relatively little progress made toward exploring the complexity of the problems studied. As a result, proving NP-hardness of or devising polynomial-time algorithms for certain distributed query optimization problems has been elaborated upon by many researchers. However, due to its inherent difficulty, the complexity of the majority of problems on distributed query optimization remains unknown. In this paper we generally characterize the distributed query optimization problems and provide a frame work to explore their complexity. As it will be shown, most distributed query optimization problems can be transformed into an optimization problem comprising a set of binary decisions, termed Sum Product Optimization (SPO) problem. We first prove SPO is NP-hard in light of the NP-completeness of a well-known problem, Knapsack (KNAP). Then, using this result as a basis, we prove that five classes of distributed query optimization problems, which cover the majority of distributed query optimization problems previously studied in the literature, are NP-hard by polynomially reducing SPO to each of them. The detail for each problem transformation is derived. We not only prove the conjecture that many prior studies relied upon, but also provide a frame work for future related studies     

Self-stabilizing distributed queuing

Distributed queuing is a fundamental coordination problem arising in a variety of applications, including distributed shared memory, distributed directories, and totally ordered multicast. A distributed queue can be used to order events, user operations, or messages in a distributed system. This paper presents a new self-stabilizing distributed queuing protocol. This protocol adds self-stabilizing actions to the arrow distributed queuing protocol, a simple path-reversal protocol that runs on a spanning tree of the network. We present a proof that the protocol stabilizes to a stable state irrespective of the (perhaps faulty) initial state, and also present an analysis of the time until convergence. The self-stabilizing queuing protocol is structured as a layer that runs on top of any self-stabilizing spanning tree protocol. This additional queuing layer is guaranteed to stabilize in time bounded by a constant number of message delays across an edge, thus establishing that the stabilization time for distributed queuing is not much more than the stabilization time for spanning tree maintenance. The key idea in our protocol is that the global predicate defining the legality of a protocol state can be written as the conjunction of many purely local predicates, one for each edge of the spanning tree.     

Indexing the solution space: a new technique for nearest neighborsearch in high-dimensional space

Similarity search in multimedia databases requires an efficient support of nearest-neighbor search on a large set of high-dimensional points as a basic operation for query processing. As recent theoretical results show, state of the art approaches to nearest-neighbor search are not efficient in higher dimensions. In our new approach, we therefore precompute the result of any nearest-neighbor search which corresponds to a computation of the Voronoi cell of each data point. In a second step, we store conservative approximations of the Voronoi cells in an index structure efficient for high-dimensional data spaces. As a result, nearest neighbor search corresponds to a simple point query on the index structure. Although our technique is based on a precomputation of the solution space, it is dynamic, i.e., it supports insertions of new data points. An extensive experimental evaluation of our technique demonstrates the high efficiency for uniformly distributed as well as real data. We obtained a significant reduction of the search time compared to nearest neighbor search in other index structures such as the X-tree     

An optimal procedure for minimizing total weighted resource tardiness penalty costs in the resource-constrained project scheduling problem

We present an optimal solution procedure for minimizing total weighted resource tardiness penalty costs in the resource-constrained project scheduling problem. In this problem, we assume the constrained renewable resources are limited to very expensive equipments and machines that are used in other projects and are not available in all periods of time of a project. In other words, for each resource, there is a dictated ready date as well as a due date such that no resource can be available before its ready date but the resources are permitted to be used after their due dates by paying penalty cost depending on the resource type. We also assume that only one unit of each resource type is available and no activity needs more than it for execution. The objective is to determine a schedule with minimal total weighted resource tardiness penalty costs. For this purpose, we present a branch-and-bound algorithm in which the branching scheme starts from a graph representing a set of conjunctions (the classical finish-start precedence constraints) and disjunctions (introduced by the resource constraints). In the search tree, each node is branched to two child nodes based on the two opposite directions of each undirected arc of disjunctions. Selection sequence of undirected arcs in the search tree affects the performance of the algorithm. Hence, we developed different rules for this issue and compare the performance of the algorithm under these rules using a randomly generated benchmark problem set.     

Random Walk Based Heuristic Algorithms for Distributed Memory Model Checking

We explore the use of distributed processing to enhance the performance of explicit state enumeration based safety model-checking. State enumeration based model-checkers employ a hash-table to cut off search when a state is revisited. Distributed model-checkers distribute this table across the processing nodes, employing inter-node messages to perform state lookups. This approach incurs the following penalties: hashing states, looking up hash-tables, and possibly exchanging messages. In this paper, we study how to avoid these penalties in the context of safety model-checking, assuming that completeness can be sacrificed (acceptable for quick error detection). We employ the basic strategy of distributed random walk - a process of multiple processors randomly, and in an uncoordinated fashion, moving through the state-space looking for safety violations, without recording visited states. This process has the potential of maximizing CPU utilization, and consequently greatly increase the rate of state generation, as the pressure on the memory system as well as communication network are minimal. Moreover, the probability that a randomwalk repeats the same sequence of moves can decrease exponentially with the length of the sequence; thus, the work wasted by occasionally repeating short sequences of searches may be more than offset by the increased state generation rate. Our choices are ideal for distributed systems that have low amounts of memory per node, and are interconnected by low bandwidth networks. We also explore techniques that backoff slightly from our extremal choices, by exploring heuristic combinations of breadth-first search (BFS) and random-walk (RW) that require a modest amount of hash-table lookup and message exchanges. These search methods are natural to combine, since BFS requires higher amounts of memory to maintain queues, but guarantees to find the shortest path to a state, while RW has the opposite characteristics. In this paper, we first study these heuristic methods on synthetic benchmarks to gain sharper (more quantifiable) insights. We then conduct studies on some realistic examples as well. We employ up to 10 single-processor CPUs that happen to be connected via 100BASE-T Ethernets. Our code was easily ported to other platforms, thanks to our use of the popular MPI distributed programming library.