Cholesky分解的单Pass随机算法

对于大规模数据矩阵,数据的读取成本远高于算法本身的成本;对存储在磁盘外部的流型数据,往往只有一次读取数据的机会。而以往的Cholesky分解的随机算法都至少需要读取输入数据两次,难以满足实际应用中的低成本需求。本文基于矩阵分解的单pass随机算法研究,提出了Cholesky分解的单pass随机算法,并给出了该算法的误差上界,最后通过数值实验验证了该算法的可行性以及有效性。

基于随机算法的新巨龙煤矿物料运输路径规划

针对目前新巨龙煤矿物料运输系统存在运输成本高、时效性难以保证等问题,通过数学建模与计算机启发式算法技术进行解决,设计了一种遍历所有情况的随机算法然后对其求解。在分别限制不同时间、单位运费以及转运费用的条件下,通过算法计算得出不同的总成本最低运输方案,验证了算法的可行性及有效性。

张量TTr1SVD的随机算法

张量序列秩-1奇异值分解(TTr1SVD)自然地将奇异值分解(SVD)推广到张量层面,将任意实张量分解为标准正交秩-1外积的有限和。基于其具有已知数量上限的正交秩-1外积项和易于截断误差量化的良好性质,本文首先给出了一种有利于张量分解和还原的表达形式,并提出了保持分解形式的截断TTr1SVD算法,在固定精度的同时大大降低了计算成本。受低秩矩阵逼近的随机算法的启发,本文还开发了针对固定精度问题的高效随机TTr1SVD算法。最后,给出的数值例子展现了所提算法在数据逼近和压缩方面的应用前景。

突发事件应急医疗物资调度的随机算法

传统的车辆路径问题(VRP)是为车辆设计将物资从仓库运送到各个需求客户的路线,使得总的运输费用(或时间)最小。在本文中,我们更关心的是使得未满足的需求量和总的物资延误时间最小。这个模型的一个非常重要的应用就是当大规模突发事件发生以后如何有效的将应急医疗物资运送到各个医疗单位,例如自然灾难,恐怖袭击之后,各个医院的医疗物资有限,需要从应急中心调集所需物资,在这种情况下,从应急中心分发应急物资过程中的运输费用就不再是最主要的考查因素,而更重要的是考虑物资到达医院的时间以及到达量,因为这两个因素直接与病人生命息息相关。本文的主要工作是改进了已有的局部搜索算法,通过引入随机算法的思想设计了求解模型的改进随机算法,可以得到模型更优的解,并通过计算机模拟案例说明了算法是行之有效的。

基于混合随机算法的可用输电能力计算

提出了一个新颖的基于混合随机算法的互联网络截面可用传输能力的计算方法。由于电力系统中固有的不确定因素会显著影响可用传输能力水平 ,为得到一个可靠而尽可能精确的值 ,文中建立了一个随机计算模型。在该模型中 ,用二次分布函数来模拟发电机组和输电线的故障 ,并认为负荷预测误差符合正态分布。为了有效解决这样一个同时包含离散随机变量和连续随机变量的问题 ,文中提出了一个综合两阶段求索随机规划和概率约束规划优点的混合随机算法。对于 IEEE1 1 8节点系统的结果分析证明了在 ATC计算中考虑不确定因素的必要性。同时 ,计算结果表明所提出的方法新颖实用 ,具有工程应用价值。

O(m^2)时间求解SAT问题的随机算法

传统的求解 SAT问题的随机算法主要是对满足解进行搜索 ,在找不到满足解的情况下 ,则无法正确判断问题的可满足性 .该文提出了两个时间复杂度为 O( m2 )求解 SAT问题的随机算法 Sat Test1和 Sat Test2 ,这里 m为CNF公式中的子句数 .这两个随机算法是通过对不满足解数的估计来判断 SAT问题的可满足性 ,不同于传统的随机算法 .其中第二个算法 Sat Test2在搜索满足解的同时又可以对不满足解数进行估计 ,是对传统随机算法的重要改进 .试验结果表明 ,文中提出的算法对相变区域的难 SAT实例有较好的求解能力 .

基于随机算法的三相异步电动机全局优化

以效率为目标函数的铸铝转子异步电机全局优化是一个复杂的非凸、非线性规划问题。首先使用TABU算法将这一高维问题降维分解并缩小搜索域 ,然后使用遗传算法进行全局寻优。验证结果表明 ,该方法充分利用了长期积累的经验知识 ,与单独使用TABU算法或遗传算法相比 ,计算量较为合理 ,结果满意度较高 ,基本满足了高效电机设计的要求。

随机算法重启策略的构造及其在TSP中的应用

NP难解问题是计算机算法和理论界长期研究的课题 .在求解 NP难解问题时 ,随机算法的性能往往很不稳定 .在以往的实验中 ,人们发现基于重启的优化方法可以提高 L as Vegas算法的性能和稳定性 .尽管它的思想比较直观 ,但对它的性能进行理论分析却并不容易 ,这在很大程度上限制了其应用 .该文使用连续概率分布对算法性能分布建模 ,针对 L as Vegas算法提出了一种高效的重启策略构造方法 .该文从平均性能和稳定性两个角度分析了该方法的效率 ,同时通过将其应用于求解大规模旅行商问题 (TSP)

基于随机算法的级联车速观测器设计

为降低复杂轮胎模型带来的运算负担,首先在数据/机理混合描述的轮胎模型的基础上得到车辆动力学描述并进行了模型验证。然后,采用模块化估计策略,设计非线性级联车速观测器,并利用随机算法对级联车速观测器参数及增益选取进行了讨论。为验证车速观测器的估计效果,在车辆运行的常规和极限工况下进行了仿真研究,并与降阶车速观测器方法及高精度车辆动力学模型进行了对比研究。结果表明,采用随机算法得到的级联车速观测器参数和增益可获得较好的估计效果,同时,采用数据/机理混合建模方法设计观测器可得到较快的计算速度。

基于负载均衡的虚拟网映射随机算法

分析了基于"尽力服务"模式的虚拟网映射算法所存在的问题,并指出了其在资源均衡利用方面的不足,设计了物理网负载均衡代价指标,提出了负载均衡的虚拟网映射随机算法。实验表明,所提出的算法能提高物理网资源的负载均衡度和利用率,从而提高虚拟网构建请求的接受率和物理网提供商的收益。

随机算法的一般性原理

最近十几年来,国际上对随机算法(randomized algorithm)的研究有了巨大进展.在此期间,随机算法从一个计数理论的工具发展到今天在许多类型的算法中都得到了广泛应用,显示了随机算法本身强大的生命力.

随机算法异步并行化的效率分析

随机算法的执行时间具有不确定性,这种不确定性为随机算法的异步并行提供了良好的基础,已有许多计算实验表明了随机算法的异步并行可以达到线性甚至超线性的加速.对于求解SAT问题的随机算法RDP,研究了异步并行效率与运行时间分布和处理器数目之间的关系.应用一种单峰分布──分段线性分布模型来模拟随机算法的运行时间分布.理论分析和计算结果均表明:当处理器数目k较小和单峰位于分布的前部时,随机算法的异步并行具有近线性加速.

基于需求度随机算法在购车摇号中的研究

为解决目前购车摇号系统中所使用的随机算法所存在的购车指标浪费严重,被抽中概率随着等待时间而降低,以及缺乏人性化等一系列问题,提出了一种基于需求度的改进随机算法(demand degree-RA)。将粗糙集理论与模糊综合评价方法相结合,利用对申请人员车辆需求程度的量化计算,完成申请人员的需求分类,并通过同类人员的随机抽取组合成购车摇号的最终结果。实例仿真计算结果表明,该算法能够有效地保证摇号结果在同等需求度下的公平、合理,对比于现有算法在结果构成方面有很强的优越性。

随机算法在安徽省高考招生系统中的应用

分析了现有主要的高考招生系统中有关调剂服从分配志愿的投档算法,结合安徽省的具体招生政策,指出了该算法的不足之处;提出了一种改进的投档算法,阐述了该算法的实现过程,并将其成功地运用于2001年、2002年的安徽省高考招生工作中。

新的求解大规模线性最小二乘问题的随机算法

目的针对传统的求解线性最小二乘问题方法的计算、存储复杂度大,不适于大规模问题的缺点,提出新的随机算法近似求解大规模线性最小二乘问题。方法通过随机采样对超大规模线性最小二乘问题的系数矩阵进行约减,利用快速Walsh-Hadamard对问题进行变换来保留原问题的重要信息,再用QR分解算法求解约减问题,得到原问题的近似解。结果该方法有效降低了问题的求解复杂度和存储复杂度。结论数值实验表明新算法和相关算法相比求解精度可接受,但大大减少求解时间且在同等计算平台下可处理更大规模的问题。

k-median问题反向贪心随机算法

k-median问题的近似算法研究一直是计算机科学工作者关注的焦点。基于均衡限制条件,利用反向贪心策略,给出求解该问题的随机近似算法。证明该算法以较大的概率满足其近似性能比的期望值为(3+O(ln(ln(k)/α))。该算法的时间复杂度为O([kαln(k)]2(n+m)),其中n和m分别代表设施集合以及客户点集的大小。最后,通过计算机实验验证了k-median问题的反向贪心算法的实际计算效果。

确定Ramsey数下界值的随机算法

文[1—2]借助于计算机得到了几个Ramsey数的下界值,但由于计算机确定Ramsey数的下界值往往需要判断多达指数级的各种情况,因此所需的计算时间常使人难以接受.本文提出了一种确定Ramsey数r(k,l)下界值的随机算法,该算法试图随机而有针对性地构造一个有n个顶点的简单图G,使G中既无k个顶点的团又无l个顶点的独立集。

基于随机算法的组卷策略设计

本文以在线考试系统组卷为研究背景,设计了组卷模块架构,在随机组卷算法中引入了题量、题型、知识点、难度和时间等约束条件,采用高分优先、难度限制、时间限制和随机抽取等原则选择试题,组成较为精确的试卷,为在线考试系统的组卷提供了新的方法和思路。

有风险控制的log-最优投资组合问题的一个黎曼几何随机算法

针对有风险控制的log-最优投资组合问题,提出了一个自适应的随机算法.该算法通过引进松弛变量,把对风险控制的不等式约束化为等式约束;再通过引进罚参数,运用罚函数法对风险控制的等式约束进行处理,从而将原来的问题化为一系列新的随机优化问题,再利用黎曼流形上的随机优化算法对其进行自适应求解.最后,使用该算法对上海证券交易所的实际数据进行了模拟计算,得到了很好的计算效果.

随机算法数据的倾向性选择

本文分析了人工智能发展的特点,尝试的用随机算法模拟虫子捕食的生活环境,采用距离参数作为倾向性选择条件,详细的描述了具体程序和结果数据。通过程序运行结果可以看出,运用具备随机算法数据倾向性算法能力的程序得到的数据具有一定的智能性,能广泛的应用于人工智能领域。