随机算法的一般性原理

最近十几年来,国际上对随机算法(randomized algo-rithm)的研究有了巨大进展。在此期间,随机算法从一个计数理论的工具发展到今天在许多类型的算法中都得到了广泛应用,显示了随机算法本身强大的生命力。所谓随机算法,就是在执行过程中要做出随机选择的算法。随机算法有两种不同类型:其一是总能给出正确的解,两次运行之间唯一的区别是运行时间不同,我们把这种随机算法叫做Las Vegas算法;其二是有时会产生不正确解的算法,然而我们能够界定产生不正确解的概率,我们把这种随机算法叫做Monte Carlo算法。这两种算法哪种更好些,要看它应用于哪类问题,Las Vegas算法可以看成是Monte Carlo算法当错误的概率为零的情况。     

基于微粒群算法的单阶段投资组合优化

投资组合优化问题是NP难解问题,通常方法很难达到全局最优,文章对微粒群算法在投资组合优化中的具体应用进行了研究,在具体应用过程中为了提高算法的收敛性和稳定性对算法进行了改进,通过多次具体的真实历史数据的验证和试验结果分析。结果表明在解决单阶段投资组合优化问题中,微粒群算法是一种高效的、可靠的优化算法,具有一定的实用价值。     

求解组合优化问题的一种新的宏启发式算法：IBS

随着科学研究和工程技术的发展，许多科学研究领域和工程应用问题都涉及到了一些组合优化问题，而这些问题中存在着大量的NP难解(NP—hard)问题，所以NP难解问题的研究具有十分重要的理论意义和广泛的应用背景，而其研究成果对科学研究的发展以及国民经济的建设都起着极大的推动作用。     

高密度子集和问题的归化算法

子集和问题是典型的NP难解问题,本文介绍了Galil和Marglit最近给出的解高密度子集和问题的算法,这一算法是子集和求解算法的重大突破,本文分析了将一般高密度子集和问题归化到特殊情况的算法,并且严格证明了该算法的一些性质。     

欧氏Steiner最小树问题的智能优化算法

欧氏平面内连接固定原点的最小树长问题，即欧氏Steiner最小树问题，为组合优化中的NP难题，因此合理的方法是寻找启发式算法。该文给出了两种智能优化算法——模拟退火法和蚂蚁算法。首先概述智能优化算法并将中面划分成网格，然后分别介绍两种算法的原理及实现过程，最后通过一系列计算实验，测试了算法的运行性能，获得了较好的效果。     

用蚂蚁算法和模拟退火算法解大规模TSP问题的研究

TSP问题是一个NP完全问题。随着问题规模的增大,其解空间呈指数增长,无法在多项式时间内完成问题的求解。近几十年来,人们提出了许多基于生物理论的解决该问题的 新方法。本文应用蚂蚁算法、模拟退火算法对TSP问题进行求解。在求解过程中对各算法中参数的作用和设置方法作了一些分析,使用不同参数进行多次实验,验证参数设置原则;对不同规模的TSP问题进行实验,比较两个算法的性能,分析造成其性能差异的原因,并提出了改进建议。     

一种新的拥塞控制算法-PVegas

针对源端算法TCP Vegas在持续拥塞和公平性等方面的不足，该文引入非线性最优化流控理论．把TCP Vegas和中间结点算法有效地结合起来，提出了一种新拥塞控制算：PVegas（价格Vegas算法）。仿真结果表明，该算法不但能很好地解决网络的持续拥塞，而且相对于TCPVegas有更好的公平性、稳定性以及低丢包率。     

火力优化分配问题的小生境遗传蚂蚁算法

火力分配问题是NP难题，经典的求解算法存在指数级的时间复杂度。文中提出一种小生境遗传算法与蚁群优化算法相结合的小生境遗传蚂蚁算法，并针对具体问题提出蚂蚁搜索的禁忌规则。对该算法进行了实验，并将实验结果与其他算法进行比较分析，分析结果表明：新算法无论是在优化性能还是在时间性能都取得了非常好的效果。文中算法对其他的NP问题同样适用。     

基于核心化技术的点覆盖改进算法

点覆盖是一个著名的NP难解问题，在通信网络和生物信息学等领域具有重要应用。针对点覆盖的研究主要集中在启发式或近似算法，其主要不足是无法实现全局最优。核心化是处理难解问题的一种新方法。提出融合启发式操作和核心化操作的算法框架，利用核心化技术进行点覆盖启发式算法优化。核心化操作挖掘出全局最优的顶点集，而启发式操作改变网络拓扑，使下一轮核心化操作能够继续，两者交叉执行实现解精度优化。实验结果表明，提出的算法在不同网络中均能实现不同程度的优化，在几乎所有稀疏网络实例中获得了最优解。     

一种求解单机成组作业优化调度的启发算法

优化目标为总流程时间的单机成组作业优化调度问题，明显是NP－hard的。该文在利用优化性质的基础上，提出了一种构造性的启发算法。该算法计算量小，可应用于大规模优化调度问题，仿真结果表明该算法能够找到次优解，其性能优于已的启发算法。     

随机竞争策略在Monte Carlo算法中的性能分析

随机算法在组合优化问题中具有广泛的应用,Ｌａｓ Ｖｅｇａｓ算法和Ｍｏｎｔｅ Ｃａｒｌｏ算法是主要的两类随机算法,随机算法的性能和稳定性常常得不到保证,以往的研究针对Ｌａｓ Ｖｅｇａｓ算法提出了一种有效的性能改进策略－随机竞争策略,但其在Ｍｏｎｔｅ Ｃａｒｌｏ算法中的准确尚未被研究。文中研究了随机竞争策略对Ｍｏｎｔｅ Ｃａｒｌｏ算法性能和稳定性的影响,分析了使其效率大于１的条件,在求解ＴＳＰ问题时的     

Restart strategies in optimization: parallel and serial cases

This paper addresses the problem of minimizing the average running time of the Las Vegas type algorithm, both in serial and parallel setups. The necessary conditions for the existence of an effective restart strategy are presented. We clarify the counter-intuitive empirical observations of super linear speedup and relate parallel speedup with the restart properties of serial algorithms. The general property of restart distributions is derived. The computational experiments involving the state-of-the-art optimization algorithm are provided.     

Probabilistic sorting and stabilization of switched systems

In this paper, we consider Lyapunov stability of switched linear systems whose switching signal is constrained to a subset of indices. We propose a switching rule that chooses the most stable subsystem among those belonging to the subset. This rule is based on an ordering of the subsystems using a common Lyapunov function. We develop randomized algorithms for finding the ordering as well as for finding a subset of systems for which a common Lyapunov function exists. It is shown that the class of randomized algorithms known as the Las Vegas type is useful in the design procedure. A third-order example illustrating the efficacy of the approach is presented.     

A method for obtaining randomized algorithms with small tail probabilities

We study strategies for converting randomized algorithms of the Las Vegas type into randomized algorithms with small tail probabilities.Supported by ESPRIT U Basic Research Actions Program of the EC under Contract No. 3075 (project ALCOM).Supported by ESPRIT II Basic Research Actions Program of the EC under Contract No. 3075 (Project ALCOM).Research supported by NSF Grant No. CCR-9005448.Partially supported by a Wolfson Research Award administered by the Israel Academy of Sciences and Humanities.     

On the Power of Las Vegas for One-Way Communication Complexity, OBDDs, and Finite Automata

The study of the computational power of randomized computations is one of the central tasks of complexity theory. The main goal of this paper is the comparison of the power of Las Vegas computation and deterministic respectively nondeterministic computation. We investigate the power of Las Vegas computation for the complexity measures of one-way communication, ordered binary decision diagrams, and finite automata.(i) For the one-way communication complexity of two-party protocols we show that Las Vegas communication can save at most one half of the deterministic one-way communication complexity. We also present a language for which this gap is tight.(ii) The result (i) is applied to show an at most polynomial gap between determinism and Las Vegas for ordered binary decision diagrams.(iii) For the size (i.e., the number of states) of finite automata we show that the size of Las Vegas finite automata recognizing a language L is at least the square root of the size of the minimal deterministic finite automaton recognizing L. Using a specific language we verify the optimality of this lower bound.     

针对逆向流的Reno和Vegas算法性能的仿真分析

网络拥塞已经成为制约网络发展和应用的一个瓶颈.在TCP中已经实现的Reno和Vegas均是基于端到端的拥塞控制算法,它们虽然减轻了前向路径上的拥塞程度,但不能改善后向路径上数据流拥塞所导致的诸如吞吐率、丢包率等网络性能降低这一状况.基于"包丢失是由于网络拥塞引起"的假定,利用OPNET网络仿真软件,建立了单个瓶颈网络,设定了吞吐量、丢包率以及拥塞窗口(cwnd)等参数,对Reno和Vegas两种算法在逆向流中的性能进行比较,分析影响网络吞吐量的因素.仿真结果表明,在非对称网络中,Reno比Vegas更灵活且更实用,后向路径上逆向流的拥塞会极大地降低Vegas的吞吐量,使得Vegas和Reno不能很好地兼容.     

Performance comparison between TCP Reno and TCP Vegas

This paper compares the performance, throughput and stability of Reno and Vegas in network environments with homogeneous and heterogeneous versions of TCP. Simulation results indicate that while TCP Vegas obtains a better throughput and stability in homogeneous cases than TCP Reno, the former performs poorly in heterogeneous cases, accounting for the reluctance among users to adopt it. Thus we propose a simple approach, parameter adjustment for Vegas, to solve this problem. This approach enables Vegas to achieve its fair share of bandwidth, even gaining an advantage over Reno, encouraging users to switch their TCP from Reno to Vegas.     

LEO卫星网络TCP拥塞控制算法改进研究

基于Vegas拥塞控制算法提出了一个适合于LEO卫星网络环境的TCP拥塞控制算法(Vegas-AB)，该算法是Vegas算法和Vegas-A算法的调和，可以动态地改变Alpha、Beta，Vegas-AB算法与Vegas-A算法的主要分支大体保持一致。在拥塞避免阶段，Vegas-AB算法更激进、更富有侵略性。仿真结果表明，在TCP吞吐量上，Vegas-AB算法优于Vegas算法和Vegas-A算法。     

LEO卫星网络中TCP Vegas拥塞控制算法研究

对TCP Vegas拥塞控制算法进行了研究改进．主要分析了类Iridium系统的LEO卫星网络环境下Vegas拥塞控制算法的性能表现，提出了一种改进的TCP拥塞控制算法-Vegasl算法，并将之与原算法进行了比较．与以往的研究不同，本文研究的侧重点是各种性能参数在整个网络上总的平均结果，关心网络的整体性能．仿真结果表明：在平均往返时延上改进后的Vegas1算法优于原Vegas算法．与单一链路的仿真结果比较，本文的结果有所不同，这说明使用完整的整个网络进行仿真具有积极的意义．     

基于仿真的TCP拥塞控制研究

研究了几种不同的TCP拥塞控制算法原理。通过对于TCP Reno和TCP Vegas协议的实验仿真，研究在不同的数据流和不同的网络条件下算法的性能差异。提出了一种改进的RTT估计方法，在拥塞避免阶段，采用时延的指数滑动平均值取代瞬时的RTT。实验表明，这种改进增强了TCP Vcgas对于时延扰动的鲁棒性。