Piecewise Linear Time Series Estimation with GRASP

This paper describes a heuristic to build piecewise linear statistical models with multivariate thresholds, based on a Greedy Randomized Adaptive Search Procedure (GRASP). GRASP is an iterative randomized sampling technique that has been shown to quickly produce good quality solutions for a wide variety of optimization problems. In this paper we describe a GRASP to sequentially split an n-dimensional space in order to build a piecewise linear time series model.     

学习时间的数学模型与概率分布

根据长期教学经验总结建立出学习量与时间的关系曲线.通过曲线讨论了学习知识过程中所获知识量的时间分配和关键时间点,对学习者或教育者提出在自学或教学中关键时间点起的作用.后将学习曲线引入到概率理论分析,提出学习时间分布和密度函数观点,从而运用概率理论研究学习与时间的关系.     

概率分布的实函数实现问题

基于一维随机变量,通过阐释概率分布实函数实现的内在本质,给出了概率分布实函数实现的一个充分必要条件,得到分布函数族及其连续性特征,揭示出概率论中分布函数定义所蕴含的合理性和深刻性.     

巧妙设计概率论习题

给出了一组有一定难度和实用价值的概率论习题 ,并巧妙地予以解答 .     

指数分布在概率统计教学中的纽带作用

讨论指数分布在概率统计教学中的作用.从指数分布的定义及特征出发,分五个方面提出指数分布的知识点连接教学法,以此说明指数分布在概率统计教学中的纽带作用.     

修正积分水平集算法的一个实现算法及其收敛性证明

郑权等（1978）在“一个求总极值的方法”一文中给出了一个积分水平集求总极值的概念性算法及Monte-Carlo随机投点的实现算法,其收敛性一直未得以解决,本文在张连生,邬冬华等提出的修正算法的基础上,利用数论中一致分布佳点集列,给出了一个实现算法及全局收敛性的证明,为了提高算法的计算效率,文中对算法进行了并行化处理。     

凸概率密度分布簇下的多损失鲁棒优化等价模型及在直营连锁企业中的应用

首先,证明了凸概率密度分布簇的单周期期望均值下单损失鲁棒优化等价模型定理,以及凸概率密度分布簇的单周期期望均值下多损失鲁棒优化等价模型。然后,提出了直营连锁企业的产品在凸概率密度分布簇下的期望均值的单周期生产分配供应问题,建立了直营连锁企业的单周期生产分配供应期望均值鲁棒模型,在获得近似周期概率分布簇情形下给出了单周期生产分配供应鲁棒模型,这种近似鲁棒模型等价于一个线性规划问题。最后,通过已知一个产品的4个周期构成的混合分布簇进行了数值实验,数值结果表明了期望均值准则下的生产分配供应鲁棒模型的生产分配供应策略更加稳健。     

连续时间遗传算法模型及其强收敛性分析

本文在隐马尔可夫链的框架下利用隐马尔可夫链{Xt:t∈[0,∞)}的观测链的概率分布提出一个连续化遗传算法模型，并给出其一个强收敛结果，讨论了其离散骨架的性质。     

Probability Distribution Functions of Succession Quotas in the Case of Markov Dependent Trials

The exact probability distribution functions (pdf's) of the sooner andlater waiting time random variables (rv's) for the succession quota problemare derived presently in the case of Markov dependent trials. This is doneby means of combinatorial arguments. The probability generating functions(pgf's) of these rv's are then obtained by means of enumerating generatingfunctions (enumerators). Obvious modifications of the proofs provideanalogous results for the occurrence of frequency quotas and such a resultis established regarding the pdf of a frequency and succession quotas rv.Longest success and failure runs are also considered and their jointcumulative distribution function (cdf) is obtained.     

An improvement of the binary merge algorithm

In this paper, we are concerned with the merging of two linearly-ordered listsA andB consisting of elements:a ₁<a ₂<...<b _n . The Hwang-Lin merging algorithm was considered very efficient for merging two lists of arbitrary sizes. Recently, Manacher was able to develop methods which reduce the number of pairwise comparisons required in the Hwang-Lin algorithm by a factor 31/336m. We develop in this paper a new method which further improves this factor to 52/336m. It is possible that even larger improvements could be achieved.     

NSGA-II算法在农业水保措施配置优化中的应用

农业水保措施的配置要考虑其生态效益和经济效益.不同水保措施组合方案有其相应的生态和经济效益,如何配置使综合效益最佳是一个最优化问题.分析了农业水保措施配置最优化需要考虑的两个目标,并将其公式化,建立了水保措施配置优化模型,并应用NSGA-II多目标遗传算法求解该模型.最后,以甘肃天水市罗玉沟流域的水保措施配置为例,进行了初步应用.结果表明,采用NSGA-II算法在水保措施配置优化模型求解时,计算效率较高,优化结果稳定,具有一定的应用价值.     

“穿越沙漠”赛题评述

对2020年"高教社杯"全国大学生数学建模竞赛"穿越沙漠"一题作简要评述,介绍赛题的数学基础和求解思路,探讨答卷所用的方法和存在的问题.     

An ensemble of discrete differential evolution algorithms for solving the generalized traveling salesman problem

In this paper, an ensemble of discrete differential evolution algorithms with parallel populations is presented. In a single populated discrete differential evolution (DDE) algorithm, the destruction and construction (DC) procedure is employed to generate the mutant population whereas the trial population is obtained through a crossover operator. The performance of the DDE algorithm is substantially affected by the parameters of DC procedure as well as the choice of crossover operator. In order to enable the DDE algorithm to make use of different parameter values and crossover operators simultaneously, we propose an ensemble of DDE (eDDE) algorithms where each parameter set and crossover operator is assigned to one of the parallel populations. Each parallel parent population does not only compete with offspring population generated by its own population but also the offspring populations generated by all other parallel populations which use different parameter settings and crossover operators. As an application area, the well-known generalized traveling salesman problem (GTSP) is chosen, where the set of nodes is divided into clusters so that the objective is to find a tour with minimum cost passing through exactly one node from each cluster. The experimental results show that none of the single populated variants was effective in solving all the GTSP instances whereas the eDDE performed substantially better than the single populated variants on a set of problem instances. Furthermore, through the experimental analysis of results, the performance of the eDDE algorithm is also compared against the best performing algorithms from the literature. Ultimately, all of the best known averaged solutions for larger instances are further improved by the eDDE algorithm.     

一种求解物流设施二次分配问题的混合分布估计算法

为了求解物流设施二次分配问题,提出了一种混合分布估计算法(HEDA)。首先,根据QAP的距离和物流量矩阵信息,提出了一种基于假设物流中心启发式规则的种群初始化方法,用于提高初始种群的质量和算法的搜索效率;其次,针对HEDA的概率模型,提出了一种概率矩阵初始构型生成机制和扰动操作,用于提高算法的全局探索能力;最后,在分析QAP的结构性质的基础上,设计了一种基于快速评价的局部搜索策略,用于提高算法的局部开发能力。仿真计算实验和算法比较验证了HEDA的优化性能。     

Tabu Search When Noise is Present: An Illustration in the Context of Cause and Effect Analysis

In the field of combinatorial optimization, it may be possible to more accurately represent reality through stochastic models rather than deterministic ones. When randomness is present in a problem, algorithm designers face new difficulties which complicate their task significantly. Finding a proper mathematical formulation and a fast evaluation of the objective function are two major issues. In this paper we propose a new tabu search algorithm based on sampling and statistical tests. The algorithm is shown to perform well in a stochastic environment where the quality of feasible solutions cannot be computed easily. This new search principle is illustrated in the field of cause and effect analysis where the true cause of an undesirable effect needs to be eliminated. A set of n potential causes is identified and each of them is assumed to be the true cause with a given probability. The time to investigate a cause is a random variable with a known probability distribution. Associated with each cause is the reward obtained if the cause is really the true cause. The decision problem is to sequence the n potential causes so as to maximize the expected reward realized before a specified time horizon.     

A Formula for the Tail Probability of a Multivariate Normal Distribution and Its Applications

An exact asymptotic formula for the tail probability of a multivariate normal distribution is derived. This formula is applied to establish two asymptotic results for the maximum deviation from the mean: the weak convergence to the Gumbel distribution of a normalized maximum deviation and the precise almost sure rate of growth of the maximum deviation. The latter result gives rise to a diagnostic tool for checking multivariate normality by a simple graph in the plane. Some simulation results are presented.     

Parallel computation of two-point boundary-value problems via particular solutions

Nonlinear two-point boundary-value problems (TPBVP) can be reduced to the iterative solution of a sequence of linear problems by means of quasilinearization techniques. Therefore, the efficient solution of linear problems is the key to the efficient solution of nonlinear problems.Among the techniques available for solving linear two-point boundary-value problems, the method of particular solutions (MPS) is particularly attractive in that it employs only one differential system, the original nonhomogeneous system, albeit with different initial conditions. This feature of MPS makes it ideally suitable for implementation on parallel computers in that the following requirements are met: the computational effort is subdivided into separate tasks (particular solutions) assigned to the different processors; the tasks have nearly the same size; there is little intercommunication between the tasks.For the TPBVP, the speedup achievable is ofO(n), wheren is the dimension of the state vector, hence relatively modest for the differential systems of interest in trajectory optimization and guidance. This being the case, we transform the TPBVP into a multi-point boundary-value problem (MPBVP) involvingm time subintervals, withm–1 continuity conditions imposed at the interface of contiguous subintervals. For the MPBVP, the speedup achievable is ofO(mn), hence substantially higher than that achievable for the TPBVP. It reduces toO(m) if the parallelism is implemented only in the time domain and not in the state domain.A drawback of the multi-point approach is that it requires the solution of a large linear algebraic system for the constants of the particular solutions. This drawback can be offset by exploiting the particular nature of the interface conditions: if the vector of constants for the first subinterval is known, the vector of constants for the subsequent subintervals can be obtained with linear transformations. Using decomposition techniques together with the discrete version of MPS, the size of the linear algebraic system for the multi-point case becomes the same as that for the two-point case.Numerical tests on the Intel iPSC/860 computer show that substantial speedup can be achieved via parallel algorithms vis-a-vis sequential algorithms. Therefore, the present technique has considerable interest for real-time trajectory optimization and guidance.Dedicated to the Memory of Professor Jan M. SkowronskiThis paper, based on Refs. 1–3, is a much condensed version of the material contained in these references.The technical assistance of the Research Center on Parallel Computation of Rice University, Houston, Texas is gratefully acknowledged.     

MB-GNG: Addressing drawbacks in multi-objective optimization estimation of distribution algorithms

We examine the model-building issue related to multi-objective estimation of distribution algorithms (MOEDAs) and show that some of their, as yet overlooked, characteristics render most current MOEDAs unviable when addressing optimization problems with many objectives. We propose a novel model-building growing neural gas (MB-GNG) network that is specially devised for properly dealing with that issue and therefore yields a better performance. Experiments are conducted in order to show from an empirical point of view the advantages of the new algorithm.     

Three Cases of Light-Traffic Insensitivity of the Loss Probability in a GI/G/m/0 Loss System to the Shape of the Service Time Distribution

A GI/G/m/0 loss system is considered. Three cases of light-traffic insensitivity of the loss probability to the shape of the service time distribution, given its first moment, are investigated in a triangle array setting.     

A new implementation of an algorithm for the optimal assignment problem: An improved version of Munkres' algorithm

Existing implementations of Munkres' algorithm for the optimal assignment problem are shown to requireO(n ⁴) time in the worstn×n case. A new implementation is presented which runs in worst-case timeO(n ³) and compares favorably in performance with the algorithm of Edmonds and Karp for this problem.The results of this paper were obtained by the author while at the Department of Computer Science, Cornell University. This work was supported in part by a Vanderbilt University Research Council Grant.