Evolutionary algorithms and dynamic programming

Recently, it has been proven that evolutionary algorithms produce good results for a wide range of combinatorial optimization problems. Some of the considered problems are tackled by evolutionary algorithms that use a representation which enables them to construct solutions in a dynamic programming fashion. We take a general approach and relate the construction of such algorithms to the development of algorithms using dynamic programming techniques. Thereby, we give general guidelines on how to develop evolutionary algorithms that have the additional ability of carrying out dynamic programming steps. Finally, we show that for a wide class of the so-called DP-benevolent problems (which are known to admit FPTAS) there exists a fully polynomial-time randomized approximation scheme based on an evolutionary algorithm.     

Surface approximation with rational B-splines

Many modern geometric modelers use nonuniform rational B-spline curves and surfaces as their canonical representations. Rational B-splines are a versatile representation, encompassing integral B-splines and the basic classical primitives such as conics, quadrics, and torii. However, rational B-splines representations other than these classical primitives have found little application in surface modeling. In this paper we develop approximation algorithms based on the general rational B-spline formulation. Numerical experiments indicate that rational B-splines allow a significantly more compact approximation of two classes of parametric surfaces in comparison to integral B-splines. The two classes of surfaces studied are generalized cylinders and offsets of a rational B-spline surface patch progenitor.     

求解随机时变背包问题的精确算法与进化算法

随机时变背包问题(RTVKP)是一种新的动态背包问题,也是一种新的动态组合优化问题,目前它的求解算法主要是动态规划的精确算法、近似算法和遗传算法.本文首先利用动态规划提出了一个求解RTVKP问题的新精确算法,对算法时间复杂度的比较结果表明:它比已有的精确算法更适于求解背包载重较大的一类RTVKP实例.然后,分别基于差分演化和粒子群优化与贪心修正策略相结合,提出了求解RTVKP问题的两个进化算法.对5个RTVKP实例的数值计算结果比较表明: 精确算法一般不宜求解大规模的RTVKP实例,而基于差分演化、粒子群优化和遗传算法与贪心修正策略相结合的进化算法却不受实例规模与数据大小的影响,对于振荡频率大且具有较大数据的大规模RTVKP实例均能求得的一个极好的近似解.     

A comparison of object-oriented programming in four modern languages

Object-oriented programming has become a widely used, important programming paradigm that is supported in many different languages. C++ has become the most widely used object-oriented language and many C++ programmers are unfamiliar with the different approaches taken by other languages in the paradigm. This paper is intended as an introduction to a broad range of ideas in object-oriented programming. Specifically, we introduce four modern programming languages that support object-oriented programming (Oberon-2, Modula-3, Sather and Self), and show how a simple application is coded in these languages. While each of these programming languages provide support for inheritance, dynamic dispatch, code reuse, and information hiding, they do so in very different ways and with varying levels of efficiency and simplicity. The use of a simple example, based on a common programming problem, facilitates our comparison. We have coded the application in all of these languages, including C++, and we compare the compile times, object code sizes, and run times of the available implementations. Implementations of all the languages compared and all of the programs we measure are available on the Internet. Ultimately, our goal is to encourage and facilitate programmers in understanding and exploring a variety of object-oriented programming languages.     

An approximate dynamic programming approach to solving a dynamic, stochastic multiple knapsack problem

We model a multiperiod, single resource capacity reservation problem as a dynamic, stochastic, multiple knapsack problem with stochastic dynamic programming. As the state space grows exponentially in the number of knapsacks and the decision set grows exponentially in the number of order arrivals per period, the recursion is computationally intractable for large-scale problems, including those with long horizons. Our goal is to ensure optimal, or near optimal, decisions at time zero when maximizing the net present value of returns from accepted orders, but solving problems with short horizons introduces end-of-study effects which may prohibit finding good solutions at time zero. Thus, we propose an approximation approach which utilizes simulation and deterministic dynamic programming in order to allow for the solution of longer horizon problems and ensure good time zero decisions. Our computational results illustrate the effectiveness of the approximation scheme.     

构造移动通信中降低能耗的前缀码的动态规划加速

动态规划是一种常用的寻找问题最优解的算法设计方案。当将动态规划中的各个子问题考虑成有向图上的节点时,我们可以将动态规划看作是一个有向无圈图。一些问题的动态规划的有向无圈图有着特殊的结构,我们可以利用这些结构加速动态规划。本文考虑了一种从基站将能源"转移"到移动通信宿主的二进制编码方案构造时采用的动态规划。移动通信中,常常需要考虑优化通信编码方案来降低移动通信宿主的能耗。本文研究的编码方案通过以下方式降低能耗:基站猜测移动通信宿主所要发出的信息并询问宿主,而宿主则在一定的情况下才做出回应,以此来降低宿主发送信息的能耗。对于有n个单词的编码,我们的算法比之前提出的算法降低了O(n2)的时间复杂度。     

Kernel-based reinforcement learning in average-cost problems

Reinforcement learning (RL) is concerned with the identification of optimal controls in Markov decision processes (MDPs) where no explicit model of the transition probabilities is available. We propose a class of RL algorithms which always produces stable estimates of the value function. In detail, we use "local averaging" methods to construct an approximate dynamic programming (ADP) algorithm. Nearest-neighbor regression, grid-based approximations, and trees can all be used as the basis of this approximation. We provide a thorough theoretical analysis of this approach and we demonstrate that ADP converges to a unique approximation in continuous-state average-cost MDPs. In addition, we prove that our method is consistent in the sense that an optimal approximate strategy is identified asymptotically. With regard to a practical implementation, we suggest a reduction of ADP to standard dynamic programming in an artificial finite-state MDP.     

An Approximation Algorithm and Dynamic Programming for Reduction in Heterogeneous Environments

Network of workstation (NOW) is a cost-effective alternative to massively parallel supercomputers. As commercially available off-the-shelf processors become cheaper and faster, it is now possible to build a cluster that provides high computing power within a limited budget. However, a cluster may consist of different types of processors and this heterogeneity complicates the design of efficient collective communication protocols. For example, it is a very hard combinatorial problem to find an optimal reduction schedule for such heterogeneous clusters. Nevertheless, we show that a simple technique called slowest-node-first (SNF) is very effective in designing efficient reduction protocols for heterogeneous clusters. First, we show that SNF is actually a 2-approximation algorithm, which means that an SNF schedule length is always within twice of the optimal schedule length, no matter what kind of cluster is given. In addition, we show that SNF does give the optimal reduction time when the cluster consists of two types of processors, when the ratio of communication speed between them is at least two. When the communication speed ratio is less than two, we develop a dynamic programming technique to find the optimal schedule. Our dynamic programming utilizes the monotone property of the objective function, and can significantly reduce the amount of computation time. Finally, combined with an approximation algorithm for broadcast 2004, we propose an all-reduction algorithm which sends the reduction answer to all processors, with approximation ratio 3.5. We conduct three groups of experiments. First, we show that SNF performs better than the built-in MPI_Reduce in a test cluster. Second, we observe a factor of 93 times saving in computation time to find the optimal schedule, when compared with a naive dynamic programming implementation. Thirdly, we apply the theoretical results to a branch-and-bound search and show that they can reduce the search time of the optimal reduction schedule by a factor of 500, when the cluster has three kinds of processors.     

Win-VolVis:一个Win95/NT下的可扩展可视化平台

拥有一个可持续开发的可视化实验平台对于图形学研究者十分重要。本文在Unix系统下体数据可视化系统VolVis的基础上实现了一个Win95/NT下的可视化系统——Win-VolVis,叙述了它的关键代码移植及主要功能扩展。Win-VolVis采用了面向对象的封装结构,系统的模块结构与功能相对应;利用MFC和VC 作为开发工具,节省了大量开发用户界面的工作,使研究或开发人员集中精力于核心图形代码的编写。在Win-VolVis中加入基于图像绘制的功能,进一步完善了该可视化系统。     

Exact solution of the robust knapsack problem

We consider an uncertain variant of the knapsack problem in which the weight of the items is not exactly known in advance, but belongs to a given interval, and an upper bound is imposed on the number of items whose weight differs from the expected one. For this problem, we provide a dynamic programming algorithm and present techniques aimed at reducing its space and time complexities. Finally, we computationally compare the performances of the proposed algorithm with those of different exact algorithms presented so far in the literature for robust optimization problems.     

Approximate robust dynamic programming and robustly stable MPC

We present a technique for approximate robust dynamic programming that is suitable for linearly constrained polytopic systems with piecewise affine cost functions. The approximation method uses polyhedral representations of the cost-to-go function and feasible set, and can considerably reduce the computational burden compared to recently proposed methods for exact robust dynamic programming [Bemporad, A., Borrelli, F., & Morari, M. (2003). Min-max control of constrained uncertain discrete-time linear systems. IEEE Transactions on Automatic Control, 48(9), 1600-1606; Diehl, M., & Björnberg, J. (2004). Robust dynamic programming for min-max model predictive control of constrained uncertain systems. IEEE Transactions on Automatic Control, 49(12), 2253-2257]. We show how to apply the method to robust MPC, and give conditions that guarantee closed-loop stability. We finish by applying the method to a state constrained tutorial example, a parking car with uncertain mass.     

A Stronger Model of Dynamic Programming Algorithms

We define a formal model of dynamic programming algorithms which we call Prioritized Branching Programs (pBP). Our model is a generalization of the BT model of Alekhnovich et al. (IEEE Conference on Computational Complexity, pp. 308–322, 2005), which is in turn a generalization of the priority algorithms model of Borodin, Nielson and Rackoff. One of the distinguishing features of these models is that they not only capture large classes of algorithms generally considered to be greedy, backtracking or dynamic programming algorithms, but they also allow characterizations of their limitations. Hence they give meaning to the statement that a given problem can or cannot be solved by dynamic programming. After defining the model, we prove three main results: (i) that certain types of natural restrictions of our seemingly more powerful model can be simulated by the BT model; (ii) that in general our model is stronger than the BT model—a fact which is witnessed by the classical shortest paths problem; (iii) that our model has very real limitations, namely that bipartite matching cannot be efficiently computed in it, hence suggesting that there are problems that can be solved efficiently by network flow algorithms and by simple linear programming that cannot be solved by natural dynamic programming approaches.     

命令式动态规划类算法程序推导及机械化验证

动态规划是一种递归求解问题最优解的方法,主要通过求解子问题的解并组合这些解来求解原问题.由于其子问题之间存在大量依赖关系和约束条件,所以验证过程繁琐,尤其对命令式动态规划类算法程序正确性验证是一个难点.基于动态规划类算法Isabelle/HOL函数式建模与验证,通过证明命令式动态规划类算法程序与其的等价性,避免证明正确性时处理复杂的依赖关系和约束条件,提出命令式动态规划类算法程序设计框架及其机械化验证.首先,根据动态规划类算法的优化方法(备忘录方法)和性质(最优子结构性质和子问题重叠性质)描述问题规约、归纳递推关系式和形式化构造出循环不变式,并且基于递推关系式生成IMP (Minimalistic Imperative Programming Language)代码;其次,将问题规约、循环不变式和生成的IMP代码输入VCG (Verification Condition Generator),自动生成正确性的验证条件;然后,在Isabelle/HOL定理证明器中对验证条件进行机械化验证.算法首先设计为命令式动态规划类算法的一般形式,并进一步实例化得到具体算法.最后,例证了所提框架的有效性,为动态规划类算法的自动化推导和验证提供参考价值.     

Caching Documents with Variable Sizes and Fetching Costs: An LP-Based Approach

Abstract. We give an integer programming formulation of the paging problem with varying sizes and fetching costs. We use this formulation to provide an alternative proof that a variant of the algorithm greedy-dual-size previously considered in [4] and [5] is (k+1)/(k-h+1) competitive against the optimal strategy with cache size h≤ k . Our proof provides further insights to greedy-dual-size. We also indicate how the same integer programming formulation has been recently used [1], [2] to obtain approximation algorithms to the NP-complete ``offline' problem.     

Mathematical programming algorithms for bin packing problems with item fragmentation

In this paper we consider a class of bin packing problems from the literature having the following distinctive feature: items may be fragmented at a price. Problems of this kind arise in diverse application fields like logistics and telecommunications, and have already been extensively tackled from an approximation point of view. We focus on the case in which splitting produces no overhead, a fixed number of bins is given and the number of fragments or fragmentations needs to be minimized. We first investigate the theoretical properties of the problem. Then we elaborate on them to devise mathematical programming models and algorithms, yielding both exact optimization algorithms and effective heuristics. An extensive experimental campaign proves that our approach is very effective, and highlights which features make an instance computationally harder to solve.     

A minisum location problem with regional demand considering farthest Euclidean distances

We consider a continuous multi-facility location-allocation problem that aims to minimize the sum of weighted farthest Euclidean distances between (closed convex) polygonal and/or circular demand regions, and facilities they are assigned to. We show that the single facility version of the problem has a straightforward second-order cone programming formulation and can therefore be efficiently solved to optimality. To solve large size instances, we adapt a multi-dimensional direct search descent algorithm to our problem which is not guaranteed to find the optimal solution. In a special case with circular and rectangular demand regions, this algorithm, if converges, finds the optimal solution. We also apply a simple subgradient method to the problem. Furthermore, we review the algorithms proposed for the problem in the literature and compare all these algorithms in terms of both solution quality and time. Finally, we consider the multi-facility version of the problem and model it as a mixed integer second-order cone programming problem. As this formulation is weak, we use the alternate location-allocation heuristic to solve large size instances.     

Graphical simulation for sensor based robot programming

The programming of robots is slowly evolving from traditional teach pendant methods to graphical Off-Line Programming (OLP) methods. Graphical simulation tools, such as OLP, are very useful for developing and testing robot programs before they are run on real industrial equipment. OLP systems are also used to develop task level programs. Traditional OLP systems, however, suffer from the limitations of using only position control which does not account for inherent robot inaccuracies and dynamic environments. This paper describes our work on improving and supplementing traditional position control programming methods. A baseline OLP system was implemented at NIST's Automated Manufacturing Research Facility (AMRF). Experience gained in implementing this system showed that an effective OLP system must accurately simulate the real world and must support sensor programming to compensate for real-world changes that cannot be simulated. The developed OLP geometric world model is calibrated using robot mounted ultrasound ranging sensors. This measurement capability produces a baseline geometric model of relatively good static accuracy for off-line programming. The graphical environment must also provide representations of sensor features. For this specific application, force is simulated in order to include force based commands in our robot programs. These sensor based programs are able to run reliably and safely in an unpredictable industrial environment. The last portion of this paper extends OLP and describes the functionality of a complete system for programming complex robot tasks.     

基于Pipeline的一类动态规划并行算法

动态规划是解决组合优化问题的有效方法之一，本文基于Ｐｉｐｅｌｉｎｅ结构，提出并分析了三个相似的动态规划并行算法（求简单最短路径，求最长公共子串和解背包问题），获得了较理想的加速比、并行效率等指标，进而提出并讨论了这一类问题之动态规划并行处理的一般化思想及方法。