832740
Constrained genetic algorithms and their applications in nonlinear constrained optimization
The paper presents a problem-independent framework that unifies various mechanisms for solving discrete constrained nonlinear programming (NLP) problems whose functions are not necessarily differentiable and continuous. The framework is based on the first-order necessary and sufficient conditions in the theory of discrete constrained optimization using Lagrange multipliers. It implements the search for discrete-neighborhood saddle points (SP/sub dn/) by performing ascents in the original-variable subspace and descents in the Lagrange-multiplier subspace. Our study on the various mechanisms shows that CSAGA, a combined constrained simulated annealing and genetic algorithm, performs well. Finally, we apply iterative deepening to determine the optimal number of generations in CSAGA.
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.
5569010
A Fast Efficient Parallel Hough Transform Algorithm on LARPBS
A parallel algorithm for Hough transform on a linear array with reconfigurable pipeline bus system (LARPBS) is presented. Suppose the number of θ-values to be considered is m, for an image with n × n pixels, the algorithm can complete Hough transform in O(1) time using mn2 processors and achieve optimal speed and efficiency. We also illustrate how to partition data and perform the algorithm on a LARPBS with fewer than mn2 processors, and hence show that the algorithm is highly scalable.
10007833
Constraint Partitioning for Solving Planning Problems with Trajectory Constraints and Goal Preferences
The PDDL3 specifications include soft goals and trajectory constraints for distinguishing highquality plans among the many feasible plans in a solution space. To reduce the complexity of solving a large PDDL3 planning problem, constraint partitioning can be used to decompose its constraints into subproblems of much lower complexity. However, constraint locality due to soft goals and trajectory constraints cannot be effectively exploited by existing subgoal-partitioning techniques developed for solving PDDL2.2 problems. In this paper, we present an improved partition-andresolve strategy for supporting the new features in PDDL3. We evaluate techniques for resolving violated global constraints, optimizing goal preferences, and achieving subgoals in a multivalued representation. Empirical results on the 5th International Planning Competition (IPC5) benchmarks show that our approach is effective and significantly outperforms other competing planners.
14272034
Optimal Anytime Constrained Simulated Annealing for Constrained Global Optimization
In this paper we propose an optimal anytime version of constrained simulated annealing (CSA) for solving constrained nonlinear programming problems (NLPs). One of the goals of the algorithm is to generate feasible solutions of certain prescribed quality using an average time of the same order of magnitude as that spent by the original CSA with an optimal cooling schedule in generating a solution of similar quality. Here, an optimal cooling schedule is one that leads to the shortest average total number of probes when the original CSA with the optimal schedule is run multiple times until it finds a solution. Our second goal is to design an anytime version of CSA that generates gradually improving feasible solutions as more time is spent, eventually finding a constrained global minimum (CGM). In our study, we have observed a monotonically non-decreasing function relating the success probability of obtaining a solution and the average completion time of CSA, and an exponential function relating the objective target that CSA is looking for and the average completion time. Based on these observations, we have designed CSAAT-ID the anytime CSA with iterative deepening that schedules multiple runs of CSA using a set of increasing cooling schedules and a set of improving objective targets. We then prove the optimality of our schedules and demonstrate experimentally the results on four continuous constrained NLPs. CSAAT-ID can be generalized to solving discrete, continuous, and mixed-integer NLPs, since CSA is applicable to solve problems in these three classes. Our approach can also be generalized to other stochastic search algorithms, such as genetic algorithms, and be used to determine the optimal time for each run of such algorithms.
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.
14759214
Real-coded ECGA for economic dispatch
In this paper, we propose a new approach that consists of the extended compact genetic algorithm (ECGA) and split-on-demand (SoD), an adaptive discretization technique, to economic dispatch (ED) problems with nonsmooth cost functions. ECGA is designed for handling problems with decision variables of the discrete type, while the decision variables of ED problems are oftentimes real numbers. Thus, in order to employ ECGA to tackle ED problems, SoD is utilized for discretizing the continuous decision variables and works as the interface between ECGA and the ED problem. Furthermore, ED problems in practice are usually hard for traditional mathematical programming methodologies because of the equality and inequality constraints. Hence, in addition to integrating ECGA and SoD, in this study, we devise a repair operator specifically for making the infeasible solutions to satisfy the equality constraint. To examine the performance and effectiveness, we apply the proposed framework to two different-sized ED problems with nonsmooth cost function considering the valve-point effects. The experimental results are compared to those obtained by various evolutionary algorithms and demonstrate that handling ED problems with the proposed framework is a promising research direction.
6494882
State pruning for test vector generation for a multiprocessor cache coherence protocol
Verification is extremely important in designing digital systems such as a cache coherence protocol. Generating traces for system verification using a model checker and then using the traces to drive the RTL logic design simulation is an efficient method for debugging. This method has been called the witness string method (Abts and Roberts, 1999), which is based on DFS. We investigate a state pruning method that exploits multiple search heuristics in simultaneous DFS searches to choose the most efficient traces. We distribute the hash table of the entire state space among the simultaneous searches so that they cooperate to avoid redundant state exploration. To evaluate this search algorithm, we implant several protocol bugs in the Stanford DASH cache coherence protocol. Using an IBM Power4 system with the Berkeley Active Message library, we show an improvement in witness strings generation through the state pruning method over a pure DFS and a guided DFS.
8410980
Quality-based Score Level Fusion in Multibiometric Systems
The quality of biometric samples has a significant impact on the accuracy of a matcher. Poor quality biometric samples often lead to incorrect matching results because the features extracted from these samples are not reliable. Therefore, dynamically assigning weights to the outputs of individual matchers based on the quality of the samples presented at the input of the matchers can improve the overall recognition performance of a multibiometric system. We propose a likelihood ratio-based fusion scheme that takes into account the quality of the biometric samples while combining the match scores provided by the matchers. Instead of estimating the quality of the template and query images individually, we estimate a single quality metric for each template-query pair based on the local image quality measures. Experiments on a database of 320 users with iris and fingerprint modalities demonstrate the advantages of utilizing the quality information in multibiometric systems
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.
5682504
An Efficient XPath Query Processor for XML Streams
Streaming XPath evaluation algorithms must record a potentially exponential number of pattern matches when both predicates and descendant axes are present in queries, and the XML data is recursive. In this paper, we use a compact data structure to encode these pattern matches rather than storing them explicitly. We then propose a polynomial time streaming algorithm to evaluate XPath queries by probing the data structure in a lazy fashion. Extensive experiments show that our approach not only has a good theoretical complexity bound but is also efficient in practice.