12984676
Hybrid Evolutionary And Annealing Algorithms For Nonlinear Discrete Constrained Optimization
This paper presents a procedural framework that unifies various mechanisms to look for discrete-neighborhood saddle points in solving discrete constrained optimization problems (DCOPs). Our approach is based on the necessary and sufficient condition on local optimality in discrete space, which shows the one-to-one correspondence between the discrete-space constrained local minima of a problem and the saddle points of the corresponding Lagrangian function. To look for such saddle points, we study various mechanisms for performing ascents of the Lagrangian function in the original-variable subspace and descents in the Lagrange-multiplier subspace. Our results show that CSAEA, a combined constrained simulated annealing and evolutionary algorithm, performs well when using mutations and crossovers to generate trial points and accepting them based on the Metropolis probability. We apply iterative deepening to determine the optimal number of generations in CSAEA and show that its performance is robust with respect to changes in population size. To test the performance of the procedures developed, we apply them to solve some continuous and mixed-integer nonlinear programming (NLP) benchmarks and show that they obtain better results than those of existing algorithms.
2308649
Subgoal ordering and granularity control for incremental planning
In this paper, we study strategies in incremental planning for ordering and grouping subproblems partitioned by the subgoals of a planning problem when each sub-problem is solved by a basic planner. To generate a rich set of partial orders for ordering subproblems, we propose a new ordering algorithm based on a relaxed plan built from the initial state to the goal state. The new algorithm considers both the initial and the goal states and can effectively order subgoals in such a way that greatly reduces the number of invalidations during incremental planning. We have also considered trade-offs between the granularity of the subgoal sets and the complexity of solving the overall planning problem. We show an optimal region of grain size that minimizes the total complexity of incremental planning. We propose an efficient strategy to dynamically adjust the grain size in partitioning in order to operate in this optimal region. We further evaluate a redundant-execution scheme that uses two different subgoal orders in order to improve the quality of the plans generated without greatly sacrificing run-time efficiency. Experimental results on using three basic planners (metric-FF, YAHSP, and LPG-TD-speed) show that our strategies are general for improving the time and quality of each of these planners across various benchmarks
9555510
Long-Distance Mutual Exclusion for Propositional Planning
The use of mutual exclusion (mutex) has led to significant advances in propositional planning. However, previous mutex can only detect pairs of actions or facts that cannot be arranged at the same time step. In this paper, we introduce a new class of constraints that significantly generalizes mutex and can be efficiently computed. The proposed long-distance mutual exclusion (londex) can capture constraints over actions and facts not only at the same time step but also across multiple steps. Londex provides a powerful and general approach for improving planning efficiency. As an application, we have integrated londex into SATPLAN04, a leading optimal planner. Experimental results show that londex can effectively prune the search space and reduce the planning time. The resulting planner, MaxPlan, has won the First Place Award in the Optimal Track of the 5th International Planning Competition.
16524073
Partitioning of temporal planning problems in mixed space using the theory of extended saddle points
We study the partitioning of temporal planning problems formulated as mixed-integer nonlinear programming problems, develop methods to reduce the search space of partitioned subproblems, and propose algorithms for resolving unsatisfied global constraints. The algorithms are based on the necessary and sufficient extended saddle-point condition for constrained local minimization developed in this paper. When compared with the MIPS planner in solving some PDDL2.1 planning problems, our distributed implementation of MIPS shows significant improvements in time and quality.
10621466
Regression Cubes with Lossless Compression and Aggregation
As OLAP engines are widely used to support multidimensional data analysis, it is desirable to support in data cubes advanced statistical measures, such as regression and filtering, in addition to the traditional simple measures such as count and average. Such new measures allow users to model, smooth, and predict the trends and patterns of data. Existing algorithms for simple distributive and algebraic measures are inadequate for efficient computation of statistical measures in a multidimensional space. In this paper, we propose a fundamentally new class of measures, compressible measures, in order to support efficient computation of the statistical models. For compressible measures, we compress each cell into an auxiliary matrix with a size independent of the number of tuples. We can then compute the statistical measures for any data cell from the compressed data of the lower-level cells without accessing the raw data. Time- and space-efficient lossless aggregation formulae are derived for regression and filtering measures. Our analytical and experimental studies show that the resulting system, regression cube, substantially reduces the memory usage and the overall response time for statistical analysis of multidimensional data
12806220
Temporal Planning using Subgoal Partitioning and Resolution in SGPlan
In this paper, we present the partitioning of mutual-exclusion (mutex) constraints in temporal planning problems and its implementation in the SGPlan4 planner. Based on the strong locality of mutex constraints observed in many benchmarks of the Fourth International Planning Competition (IPC4), we propose to partition the constraints of a planning problem into groups based on their subgoals. Constraint partitioning leads to significantly easier subproblems that are similar to the original problem and that can be efficiently solved by the same planner with some modifications to its objective function. We present a partition-and-resolve strategy that looks for locally optimal subplans in constraint-partitioned temporal planning subproblems and that resolves those inconsistent global constraints across the subproblems. We also discuss some implementation details of SGPlan4, which include the resolution of violated global constraints, techniques for handling producible resources, landmark analysis, path finding and optimization, search-space reduction, and modifications of Metric-FF when used as a basic planner in SGPlan4. Last, we show results on the sensitivity of each of these techniques in quality-time trade-offs and experimentally demonstrate that SGPlan4 is effective for solving the IPC3 and IPC4 benchmarks.
34404148
Stochastic sketching: a new method for global optimization
Abstract In this paper, we propose Stochastic sketching for global optimization based on a simulation of human behaviour. Stochastic sketching tries to do things simply in the human way without too much interpretation instead of modeling the thought and strategies of human beings and applying an artificial model to problems. We introduce and discuss concepts and components essential to stochastic sketching in detail, including sampling guide, zooming controller, sketching model, precision threshold, and satisfaction probability. Experimental results of stochastic sketching on several test functions and a set of recommended parameter settings are given, as well as preliminary comparisons between stochastic sketching and related evolutionary algorithms including evolution strategies, evolutionary programming, and genetic algorithms.
3257005
Voting multi-dimensional data with deviations for Web services under group testing
Web services (WS) need to be trustworthy to be used in critical applications. A technique called WS group testing has been proposed which can significantly reduce the cost of testing and ranking a large number of WS. A main feature of WS group testing is that it is able to establish the test oracles for the given test inputs from multiple WS and infer the oracles by plural voting. Efficient voting of complex and large number of data is critical to the success of group testing. Current voting techniques are not designed to deal with such a situation. This paper presents efficient voting algorithms that determine the plural value on multi-dimensional data and large number of data. The algorithm uses a clustering method to classify data into regions to identify the plural value. Experiments are designed and performed to concept-prove the algorithms and their applications with group testing.
894881
Performance improvement of TCP Vegas over heterogeneous networks
Current IP network has become the dominant paradigm for all networking environments. The significant cause of packet losses in such heterogenous networks is no longer limited to network congestion. Traditional TCP interprets every packet loss as caused by congestion which may be not the case in the current Internet. Misinterpretation of wireless random loss as an indication of network congestion results in TCP slowing down its sending rate unnecessarily. We propose a new variant of TCP Vegas named RedVegas. By using the innate nature of Vegas and congestion indications marked by routers, RedVegas may detect random packet losses precisely. Through the packet loss differentiation, RedVegas reacts appropriately to the losses, and therefore the throughput of connection over heterogeneous networks can be significantly improved.
34645664
Applying Family Competition to Evolution Strategies for Constrained Optimization
This paper applies family competition to evolution strategies to solve constrained optimization problems. The family competition of Family Competition Evolution Strategy (FCES) can be viewed as a local competition involving the children generated from the same parent, while the selection is a global competition among all of the members in the population. According to our experimental results, the self-adaptation of strategy parameters with deterministic elitist selection may trap ESs into local optima when they are applied to heavy constrained optimization problems. By controlling strategy parameters with non-self adaptive rule, FCES can reduce the computation time of self-adaptive Gaussian mutation, diminish the complexity of selection from (m+1) to (m+m), and avoid to be premature. Therefore, FCES is capable of obtaining better performance and saving the computation time. In this paper, FCES is compared with other evolutionary algorithms on various benchmark problems and the results indicate that FCES is a powerful optimization technique.
46069080
A Graph-Theoretic Model for Optimizing Large Join Queries