多指标动态规划的交互式满意置换率法

提出了一种新的求解多指标动态规划问题的算法,它是由多目标静态规划的交互式满意 置换率法[1]推广得到的.通过增加附加状态变量进行数学模型转换,将单指标动态规划问题 转化为静态规划问题,再进行迭代.这样既减少了计算量,又使各指标间的置换关系易于求 得.所提方法在人机交互过程中对决策者的要求不高,对于一类常见的多指标动态规划问题, 可以迅速获得满意的解.     

多指标动态规划的人机交互式满意权衡法

1984年,Nakayama和Sawaragi提出了一种求解静态多目标决策问题的人机交互式满 意权衡方法.本文结合动态规划的结构特点,进一步发展了Nakayama方法的基本思想,表明 该方法可以推广到用来求解多指标动态规划问题,而且通过对原方法的改进,消除了其存在的 一些不足之处.本文所提方法,在较弱的限制条件下,针对一类普遍使用的多指标动态规划模 型,可以获得决策者充分满意的解.     

Decomposition methods in multiobjective discrete-time dynamic problems

Decomposition methods for multicriteria dynamic (discrete-time) problems are derived. In these methods, the original problem is reduced to a series of multicriteria subproblems related to individual stages. Hence, the dimensionality of decision variables in each subproblem is smaller than in the original problem. The following decomposition procedures for such problems are developed: (1) a dynamic programming method, (2) a two-point boundary value problem method, (3) multilevel methods, and (4) the formulation of a temporal hierarchy. For completeness, methods for multicriteria dynamic problems are reviewed that, at the outset, transform a problem into a series of single-objective problems. Formulation of the multiobjective problem in the context of a multilayer temporal hierarchy is also presented. The temporal structure motivates problem simplification by decomposing the overall decision-making problem according to relative time scales.     

Computing leximin-optimal solutions in constraint networks

In many real-world multiobjective optimization problems one needs to find solutions or alternatives that provide a fair compromise between different conflicting objective functions—which could be criteria in a multicriteria context, or agent utilities in a multiagent context—while being efficient (i.e. informally, ensuring the greatest possible overall agents' satisfaction). This is typically the case in problems implying human agents, where fairness and efficiency requirements must be met. Preference handling, resource allocation problems are another examples of the need for balanced compromises between several conflicting objectives. A way to characterize good solutions in such problems is to use the leximin preorder to compare the vectors of objective values, and to select the solutions which maximize this preorder. In this article, we describe five algorithms for finding leximin-optimal solutions using constraint programming. Three of these algorithms are original. Other ones are adapted, in constraint programming settings, from existing works. The algorithms are compared experimentally on three benchmark problems.     

Decision making with multiple objectives using GAI networks

This paper deals with preference representation on combinatorial domains and preference-based recommendation in the context of multicriteria or multiagent decision making. The alternatives of the decision problem are seen as elements of a product set of attributes and preferences over solutions are represented by generalized additive decomposable (GAI) utility functions modeling individual preferences or criteria. Thanks to decomposability, utility vectors attached to solutions can be compiled into a graphical structure closely related to junction trees, the so-called GAI network. Using this structure, we present preference-based search algorithms for multicriteria or multiagent decision making. Although such models are often non-decomposable over attributes, we actually show that GAI networks are still useful to determine the most preferred alternatives provided preferences are compatible with Pareto dominance. We first present two algorithms for the determination of Pareto-optimal elements. Then the second of these algorithms is adapted so as to directly focus on the preferred solutions. We also provide results of numerical tests showing the practical efficiency of our procedures in various contexts such as compromise search and fair optimization in multicriteria or multiagent problems.     

Parallel genetic algorithms: a survey and problem state of the art

In relation with development of computer capabilities and the appearance of multicore processors, parallel computing made it possible to reduce the time for solution of optimization problems. At present of interest are methods of parallel computing for genetic algorithms using the evolutionary model of development in which the main component is the population of species (set of alternative solutions to the problem). In this case, the algorithm efficiency increases due to parallel development of several populations. The survey of basic parallelization strategies and the most interesting models of their implementation are presented. Theoretical ideas on improvement of existing parallelization mechanisms for genetic algorithms are described. A modified model of parallel genetic algorithm is developed. Since genetic algorithms are used for solution of optimization problems, the proposed model was studied for the problem of optimization of a multicriteria function. The algorithm capabilities of getting out of local optima and the influence of algorithm parameters on the deep extremum search dynamics were studied. The conclusion on efficiency of application of dynamic connections of processes, rather than static connections, is made. New mechanisms for implementation and analysis of efficiency of dynamic connections for distributed computing in genetic algorithms are necessary.     

A new method to solve generalized multicriteria optimization problems using the simple genetic algorithm

Genetic algorithms (GAs), which are directed stochastic hill climbing algorithms, are a commonly used optimization technique and are generally applied to single criterion optimization problems with fairly complex solution landscapes. There has been some attempts to apply GA to multicriteria optimization problems. The GA selection mechanism is typically dependent on a single-valued objective function and so no general methods to solve multicriteria optimization problems have been developed so far. In this paper, a new method of transformation of the multiple criteria problem into a single-criterion problem is presented. The problem of transformation brings about the need for the introduction of thePareto set estimation method to perform the multicriteria optimization using GAs. From a given solution set, which is the population of a certain generation of the GA, the Pareto set is found. The fitness of population members in the next GA generation is calculated by a distance metric with a reference to the Pareto set of the previous generation. As we are unable to combine the objectives in some way, we resort to this distance metric in the positive Pareto space of the previous solutions, as the fitness of the current solutions. This new GA-based multicriteria optimization method is proposed here, and it is capable of handling any generally formulated multicriteria optimization problem. The main idea of the method is described in detail in this paper along with a detailed numerical example. Preliminary computer generated results show that our approach produces better, and far more Pareto solutions, than plain stochastic optimization methods.     

Algorithmic and Computational Aspects of Composite Concave Programming

In this paper we discuss the algorithmic and computational aspects of the parametric nonlinear optimization method c-programming. Our objective in looking at the method from this vantage point is twofold. First, to explain more clearly where c-programming sits in optimization theory. Second, to throw more light on the details of the collaboration that it forges with other optimization methods. The first objective is accomplished through an analysis of c-programming'ys genealogy. The latter is achieved by an examination of the basic structure of c-programming algorithms, and by reporting on extensive numerical experiments conducted with c-programming algorithms in collaboration with linear programming and dynamic programming techniques. These experiments very convincingly show that c-programming has the ability to significantly expand the scope of linear programming, dynamic programming, and possibly other optimization methods.     

Simulation and discrete event optimization for automated decisions for in‐queue flights

The paper discusses simulation and optimization of in‐queue flights, analyzed as discrete‐event systems. Simulation is performed in a platform, based on MATLAB program functions and SIMULINK dynamic models. Regime optimization aims to maximize the controllability of the queue and minimize the fuel consumption of each aircraft (AC). Because of mutual preferential independence, a hierarchical additive value function is constructed, consisting of fuzzily estimated parameter value functions and weight coefficients and a multicriteria decision problem is solved under strict certainty. Two optimization algorithms are applied: one that finds the regime that leads to maximally preferred consequence and another that finds the regime with minimum total fuel consumption among those whose control parameters are set at their most preferred levels. A comparison between the two algorithms is proposed. A scheme describes how the optimization procedures can be used multiple times during the execution of the flight with respect to the occurrence of discrete events. Simulation results are also proposed for the discussed algorithms and procedures. © 2010 Wiley Periodicals, Inc.     

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

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

Dynamic slicing of concurrent AspectJ programs: An explicit context‐sensitive approach

This paper presents a context‐sensitive dynamic slicing technique for the concurrent and aspectized programs. To effectively represent the concurrent aspect‐oriented programs, we propose an intermediate graph called the multithreaded aspect‐oriented dependence graph (MAODG). The MAODG is a dynamic graph generated from the execution trace of a given program with respect to a particular set of values given as an input. Interference dependencies between the statements are shown by a distinguished edge called the interference dependence edge in the MAODG. Based on this intermediate representation, we propose a precise and accurate dynamic slicing algorithm for the concurrent aspect‐oriented programs implemented using AspectJ. The proposed dynamic slicing algorithm is implemented in a slicing tool developed using the ASM framework. Several open source programs are studied and evaluated using the proposed technique along with some existing techniques. The experimentation shows that our proposed slicing algorithm generates slices of the same or smaller size, as compared with the existing algorithms. Furthermore, we found that the slice computation time is significantly less in our proposed algorithm, as compared with the existing algorithms.     

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.     

On the Experiment Design for Direct Dynamic Parameter Identification of Parallel Robots

Accurate robot dynamic models require the estimation and validation of the dynamic parameters through experiments. To this end, when performing the experiments, the system has to be properly excited so that the unknown parameters can be accurately estimated. The experiment design basically consists of optimizing the trajectory executed by the robot during the experiment. Due to the restricted workspace with parallel robots this task is more challenging than for serial robots; thus, this paper is focused on the experiment design aimed at dynamic parameter identification of parallel robots. Moreover, a multicriteria algorithm is proposed in order to reduce the deficiencies derived from the single-criterion optimization. The results of the identification using trajectories based on a single criterion and the multicriteria approaches are compared, showing that the proposed optimization can be considered as a suitable procedure for designing exciting trajectories for parameter identification.     

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

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

Feature-Based Methods for Large Scale Dynamic Programming

We develop a methodological framework and present a few different ways in which dynamic programming and compact representations can be combined to solve large scale stochastic control problems. In particular, we develop algorithms that employ two types of feature-based compact representations; that is, representations that involve feature extraction and a relatively simple approximation architecture. We prove the convergence of these algorithms and provide bounds on the approximation error. As an example, one of these algorithms is used to generate a strategy for the game of Tetris. Furthermore, we provide a counter-example illustrating the difficulties of integrating compact representations with dynamic programming, which exemplifies the shortcomings of certain simple approaches.     

Multicriteria path and tree problems: discussion on exact algorithms and applications

Multicriteria/multiobjective path and tree models are useful in many applications. Particularly, in Internet routing problems they seem to lead to promising approaches. In the first part of this paper, we classify and present the main exact approaches dealing with several multicriteria path problems putting in evidence the shortest path problem. In the second part, we review exact algorithms dedicated to some multicriteria tree problems, namely the minimum spanning tree and the minimum cost/minimum label spanning tree problems. Finally, the application of these models is exemplified.     

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

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

突发灾害下医疗资源供应商选择模型及算法

对医疗资源供应商选择问题进行建模,提出一种权重系数信息不完全的多准则区间直觉模糊集的供应商排序算法。该算法通过逻辑集成得到各供应商的区间直觉模糊集,计算各供应商的区间直觉模糊数的Hamming距离,并利用粒子群优化算法求解建立的非线性优化模型,得出最优准则的权重系数。通过比较各供应商与优等及次等供应商的距离,进行最优排序。以大规模突发灾害事件下的供应商选择为案例,说明该模型及算法的有效性和可行性。     

Dynamic programming interpretation of construction-type plant layout algorithms and some results

This paper presents a dynamic programming interpretation of some existing construction-type algorithms for the CAD of plant layouts. The two sub-problems of constructing a layout by these algorithms are first, the selection of a department for next placement, and second, locating it in the available space in an optimum manner. The first problem is tackled by adopting a heuristic. Successive choices of this nature lend themselves to a dynamic programming interpretation. The second problem is solved by allocating those blocks of area in the vicinity of existing departments which minimize the cost of materials handling between the new and the existing departments. It is found that application of dynamic programming significantly improves the efficiency of existing construction-type procedures. Some new heuristics for the first sub-problem are also examined. Computational results on test problems indicate that more complex policies might yield better results when the number of departments becomes larger.     

一种基于残缺信息的多准则区间直觉模糊决策方法

提出一种权重系数存在残缺信息的多准则区间直觉模糊集的排序算法。该方法通过逻辑集成得到各方案的区间直觉模糊集,计算各种方案的区间直觉模糊数的Hamming距离,并建立非线性规划模型,利用粒子群算法求解所得的优化模型,得出最优准则的权重系数。然后通过比较区间直觉模糊集与优级方案 及次级方案的距离来进行最优排序。最后利用实例对方法的有效性和可行性进行了说明。