随机算法

数值随机化算法

数值化随机算法:常用于数值问题求解,往往得到的是近似解

  • 近似解的精度随计算时间、采样数量增加不断提高
  • 很多情况下计算问题的精确解不可能、无必要,数值化随机算法 可以得到较好的解

随机投点法

随机投点法:在给定范围内生成均匀分布随机数模拟随机投点

  • 计算$\pi$值:在正方形、内切圆中随机撒点,计算圆内、 正方形内点数量之比

  • 计算黎曼积分:在包括积分区域单位矩形内随机投点,计算 积分区域、矩形区域点数量之比

平均值法

平均值法:结合随机数分布、目标问题构造统计量,估计目标问题

计算黎曼积分

  • 假设独立同分布随机变量${\eta_i}$在$[a, b]$中服从分布 $f(x)$、待积函数为$g(x)$

  • 记$g^{*}(x) = \frac {g(x)} {f(x)}$,则有

  • 由强大数定理

    选择$\bar I = \frac 1 n \sum_{i=1}^n g^{*}(\eta_i)$, 则$\bar I$依概率收敛为$I$

  • 选择抽样方法简单的概率密度函数$f(x)$满足

    可以取$f(x)$为均匀分布

  • 则积分

    取均值

    可作为求分I的近似值

解非线性方程组

  • 线性化方法、求函数极小值方法有时会遇到麻烦,甚至使方法 失效而不能获得近似解
  • 随机化方法相较而言要耗费较多时间,但设计简单、易于实现
  • 对于精度要求较高的问题,随机化方法可以提供一个较好的初值

步骤

  • 构造目标函数

    则目标函数的极小值点即为所求非线性方程组的一组解

  • 随机选择点$x_0$作为出发点,不断随机生成搜索方向, 迭代为使得目标函数值下降的搜索点

    • 一般以目标函数变化幅度、迭代轮数作为终止条件
    • 搜索方向为随机生成,迭代步长比例每轮缩小指定幅度
  • 真正的随机次梯度下降

Monte Carol Method

蒙特卡洛算法:一定能给出问题解,但未必正确

  • 要求在有限时间、采样内必须给出解,解未必正确
  • 求得正确解的概率依赖于算法所用时间,算法所用时间越多, 得到正确解概率越高
  • 无法有效判断得到的解是否肯定正确

Las Vegas Method

拉斯维加斯算法:找到的解一定是正确解,但是可能找不到解

  • 找到正确解的概率随着计算所用时间增加而提高
  • 用同一拉斯维加斯算法反复对实例求解多次,可使得求解失效 概率任意小

Sherwood Method

舍伍德算法:能求得问题的一个解,所求得得解总是正确的

  • 确定性算法在最好情况、平均情况下计算复杂度有较大差别, 在确定性算法中引入随机性将其改造成舍伍德算法,消除、减少 问题的好坏实例间差别

  • 精髓不是改进算法在最坏情形下的行为,而是设法消除最坏情形 与特定问题实例的关联性

思想

  • 问题输入规模为n时,算法A所需的平均时间为

    • $X_n$:算法A输入规模为n的实例全体
    • $t_A(x)$:输入实例为x时所需的计算时间

    显然存在$x \in X_n, t_A(x) >> \bar t_A(x)$

  • 希望获得随机化算法B,使得对问题的输入规模为n的每个实例 $x \in X_n$均有$t_B(x) = \bar t_A(x) + s(n)$

    • 对具体实例,存在$x \in X_n$,算法B需要时间超过 $\bar t_A(x) + s(n)$,但这是由于算法所做的概率引起, 与具体实例无关

    • 算法B关于规模为n的随机实例平均时间为

      K

      当$s(n)$与$\bar t_A(n)$相比可以忽略时,舍伍德算法 可以获得较好平均性能

todo

Author

UBeaRLy

Posted on

2019-07-21

Updated on

2019-07-21

Licensed under

Comments