Genetic algorithm (GA) is a heuristic search algorithm that is inspired by evolution. It is a powerful optimization tool that uses the stochastic procedure with populations of initial guesses rather than using a singl...
详细信息
ISBN:
(数字)9781728123394
ISBN:
(纸本)9781728123400
Genetic algorithm (GA) is a heuristic search algorithm that is inspired by evolution. It is a powerful optimization tool that uses the stochastic procedure with populations of initial guesses rather than using a single value like gradient-based methods. This prevents GA from being trapped in a local optimum. In the present work, GA applications to industrial optimization problems are thoroughly reviewed to get a perspective on different variations of genetic algorithms being used in industries. Subsequently, GA is applied to an industrial tubular reactor system where the technique is used to determine the optimum feed temperature at reactor inlet so that the product attains desirable temperature at the reactor outlet. In addition to successful application of GA, some other performances such as effect of mutation function and selection technique on the number of iterations are also investigated.
Modern compilers use dozens of optimizations which are typically applied serially one after the other and at the same order. Theoretically, for a given program, some of these optimizations, and the order in which they...
详细信息
ISBN:
(纸本)9781538634417
Modern compilers use dozens of optimizations which are typically applied serially one after the other and at the same order. Theoretically, for a given program, some of these optimizations, and the order in which they are applied, can degrade the performance or produce suboptimal performance. In this work we formally define the problem of finding an optimized sequence of optimizations (OSO) for a given program based on information on conflicting pairs of optimizations alone. Previous works studied heuristic search algorithms covering the space S of all possible optimization sequences. These works proposed various heuristic techniques to search S by reducing the number of s is an element of S that need to be evaluated (compiled and executed). In this work we show, for the first time, an algorithmic solution to this problem of finding an OSO. We do not search or evaluate sequences s is an element of S. Instead, we build a directed conflict graph G with a weighted directed edge x ->(g) y between every pair of optimizations x, y wherein g is the outcome of applying optimization y after optimization x compared to applying only x or y alone. The optimal OSO is therefore a directed sub-path in G with the maximal sum of triangle weights over all other sub-paths in G. The proposed algorithm uses transitive closure steps done by selecting every three edges x ->(gi) y, y ->(gj) z, x ->(gk )z that form a triangle and contracting them to a new edge x ->(g' = f(gi, gj, gk)) z. By selecting the triangle with maximal g' in every step, the algorithm finds the maximal OSO including repetitions. This technique was implemented in the LLVM compiler and applied to 9 programs from SPEC 2006. The resulting OSOs obtained and average of 10% improvement in execution time compare to using the -O3 optimizations sequence. This is the first algorithmic solution to this problem and the first technique that can handle repetitions of optimizations in the compilation sequence.
This paper introduces a very fast heuristic search algorithm for unit-selection speech synthesis. The algorithm modifies commonly used Viterbi search framework by introducing zero-concatenation-cost (ZCC) chains of un...
详细信息
ISBN:
(纸本)9781479928941
This paper introduces a very fast heuristic search algorithm for unit-selection speech synthesis. The algorithm modifies commonly used Viterbi search framework by introducing zero-concatenation-cost (ZCC) chains of unit candidates that immediately neighbored in a source speech corpus. ZCC chains are preferred as they represent perfect speech segment concatenations (so there is no need to compute concatenation costs inside the chains) unless a so-called target specification is violated. The number of ZCC chains is reduced based on statistics calculated upon the synthesis of a large number of utterances. ZCC chains are then combined with single unit candidates to fill possible gaps in the sequence of candidates. The proposed method reduces the computational load of a unit selection system up to hundreds of times. According to listening tests, the quality of synthetic speech was not deteriorated.
作者：
Qian XuePeng ChengNong ChengNavigation and Control Research Center
Department of AutomationTsinghua UniversityBeijing100084 P.R.China Department of AutomationTsinghua UniversityBeijing100084P.R.China Department of AutomationTsinghua UniversityBeijing100084 P.R.China
This paper presents a path planning algorithm called D* lite-IPRM algorithm for Unmanned Aerial Vehicles (UAVs) in complex *** operational environment consists of various shapes of obstacles,threatened areas and no-fl...
详细信息
ISBN:
(纸本)9781479946983
This paper presents a path planning algorithm called D* lite-IPRM algorithm for Unmanned Aerial Vehicles (UAVs) in complex *** operational environment consists of various shapes of obstacles,threatened areas and no-fly zones,which are usually called a joint name “obstacles” below to *** algorithm can be divided into two steps,firstly Improved Probabilistic Roadmap Method (IPRM) is applied for local obstacle avoidance; secondly D* lite is used to plan a global trajectory.D* is an extension of A*,both of which are heuristic search algorithms.D* lite is a simplification of D* and at least of the same *** can repeatedly plan the optimal track from current point to the *** our research,minimum flight distance is considered as the ultimate *** have discussed two-dimensional (2D) D* lite-IPRM and extended to 3D *** algorithm is demonstrated to be effective on both offline path planning and online replanning.
heuristic search algorithms for online POMDP planning have shown great promise in creating successful policies for maximizing agent rewards using heuristics typically focused on reducing the error bound in the agent&#...
详细信息
ISBN:
(纸本)9781634391313
heuristic search algorithms for online POMDP planning have shown great promise in creating successful policies for maximizing agent rewards using heuristics typically focused on reducing the error bound in the agent's cumulative future reward estimations. However, error bound-based heuristics are less informative in highly uncertain domains requiring long sequences of information gathering, such as robotics. In these domains, all possible plan improvements look similar under error bound-based heuristics until the agent's belief uncertainty has been resolved, leaving the agent initially confused on how best to improve its plan under the real-time constraints of online planning. We propose (1) a novel heuristic guiding the agent towards policies that first reduce the agent's belief uncertainty, after which error bound-based heuristics are more effective, and (2) a novel selection mechanism for choosing which type of heuristic (error bound or uncertainty-based) to use during the current stage of planning to most quickly form a good plan. We evaluate our solution in several benchmark POMDP problems, demonstrating that our solution yields successful policies with less planning time in highly uncertain domains and comparable performance in simpler problems.
Multi-agent planning in stochastic environments can be framed formally as a decentralized Markov decision problem. Many real-life distributed problems that arise in manufacturing, multi-robot coordination and informat...
详细信息
Multi-agent planning in stochastic environments can be framed formally as a decentralized Markov decision problem. Many real-life distributed problems that arise in manufacturing, multi-robot coordination and information gathering scenarios can be formalized using this framework. However, finding the optimal solution in the general case is hard, limiting the applicability of recently developed algorithms. This paper provides a practical approach for solving decentralized control problems when communication among the decision makers is possible, but costly. We develop the notion of communication-based mechanism that allows us to decompose a decentralized MDP into multiple single-agent problems. In this framework, referred to as decentralized semi-Markov decision process with direct communication (Dec-SMDP-Com), agents operate separately between communications. We show that finding an optimal mechanism is equivalent to solving optimally a Dec-SMDP-Com. We also provide a heuristic search algorithm that converges on the optimal decomposition. Restricting the decomposition to some specific types of local behaviors reduces significantly the complexity of planning. In particular, we present a polynomial-time algorithm for the case in which individual agents perform goal-oriented behaviors between communications. The paper concludes with an additional tractable algorithm that enables the introduction of human knowledge, thereby reducing the overall problem to finding the best time to communicate. Empirical results show that these approaches provide good approximate solutions.
To solve the constraint multi-solution problem, the constraints are separated to two sets, the original constraint set and the additional constraint set. First, the solver finds out multiple solutions. Then genetic al...
详细信息
ISBN:
(纸本)9781424429141
To solve the constraint multi-solution problem, the constraints are separated to two sets, the original constraint set and the additional constraint set. First, the solver finds out multiple solutions. Then genetic algorithm and ant algorithm are combined in the process of searching optimal solution. We adopt genetic algorithm in the former process to produce the initiatory distribution of information elements, and then ant algorithm in the latter process. The random colony is adopted in genetic algorithm, which can not only accelerate the convergence process of ant algorithm but also avoid the local best solution. The heuristicsearching algorithm maximizes the fitness of the additional constraint set, thereby reaches the final result that can satisfy the user's expectation.
This paper proposes an improved merit order (IMO) and augmented Lagrange Hopfield network (ALHN) for unit commitment (UQ). IMO is a merit-order method which is based on average production cost of generating units impr...
详细信息
This paper proposes an improved merit order (IMO) and augmented Lagrange Hopfield network (ALHN) for unit commitment (UQ). IMO is a merit-order method which is based on average production cost of generating units improved by heuristic search algorithms, whereas ALHN is a continuous Hopfield neural network with its energy function based on augmented Lagrange relaxation. The proposed IMO-ALHN solves UC problem in three stages. In the first stage, IMO is applied for unit scheduling. In the second stage, ALHN is used to solve ramp rate constrained economic dispatch (RED) based on the obtained unit schedule, and a strategy for repairing ramp rate constraint violation is performed if a feasible solution is not found. In the last stage, a heuristic search for unit decommitment is applied on the obtained solution from RED for further improvement and ALHN is again applied to solve RED if there is any change in the unit schedule. The proposed method is tested on systems up to 1000 generating units with schedule time horizon up to 168 h. Test results indicate that the proposed method is very attractive and favourable over many other methods due to substantial production cost savings and faster computational times.
We describe how to convert the heuristic search algorithm A* into an anytime algorithm that finds a sequence of improved solutions and eventually converges to an optimal solution. The approach we adopt uses weighted h...
详细信息
We describe how to convert the heuristic search algorithm A* into an anytime algorithm that finds a sequence of improved solutions and eventually converges to an optimal solution. The approach we adopt uses weighted heuristic search to find an approximate solution quickly, and then continues the weighted search to find improved solutions as well as to improve a bound on the suboptimality of the current solution. When the time available to solve a search problem is limited or uncertain, this creates an anytime heuristic search algorithm that allows a flexible tradeoff between search time and solution quality. We analyze the properties of the resulting Anytime A* algorithm, and consider its performance in three domains;sliding-tile puzzles, STRIPS planning, and multiple sequence alignment. To illustrate the generality of this approach, we also describe how to transform the memory-efficient search algorithm Recursive Best-First Search (RBFS) into an anytime algorithm.
Given one instance of an NP- hard optimization problem, can we tell in advance whether it is exactly solvable or not? If it is not, can we predict which approximate algorithm is the best to solve it? Since the behavio...
详细信息
Given one instance of an NP- hard optimization problem, can we tell in advance whether it is exactly solvable or not? If it is not, can we predict which approximate algorithm is the best to solve it? Since the behavior of most approximate, randomized, and heuristic search algorithms for NP- hard problems is usually very difficult to characterize analytically, researchers have turned to experimental methods in order to answer these questions. In this paper we present a machine learning-based approach to address the above questions. Models induced from algorithmic performance data can represent the knowledge of how algorithmic performance depends on some easy-to-compute problem instance characteristics. Using these models, we can estimate approximately whether an input instance is exactly solvable or not. Furthermore, when it is classified as exactly unsolvable, we can select the best approximate algorithm for it among a list of candidates. In this paper we use the MPE ( most probable explanation) problem in probabilistic inference as a case study to validate the proposed methodology. Our experimental results show that the machine learning-based algorithm selection system can integrate both exact and inexact algorithms and provide the best overall performance comparing to any single candidate algorithm.
暂无评论