随机算法

数值随机化算法

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

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

随机投点法

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

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

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

平均值法

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

计算黎曼积分

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

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

  $$\begin{align*} E(g^{*}(\eta)) & = \int_a^b g^{*}f(x) dx \\ & = \int_a^b g(x) dx = I \end{align*}$$

• 由强大数定理

  $$P_r(\lim_{x \rightarrow \infty} \frac 1 n \sum_{i=1}^n g^{*}(\eta_i) = I) = 1$$

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

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

  $$\left \{ \begin{array}{l} f(x) \neq 0, & g(x) \neq 0, a \leq x \leq b \\ \int_a^b f(x) dx = 1 \end{array} \right.$$

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

  $$f(x) = \left \{ \begin{array}{l} \frac 1 {b-a}, & a \leq x \leq b \\ 0, & x < a, x > b \end{array} \right.$$

• 则积分

  $$I = \int_a^b g(x)dx = (b-a) \int_a^b g(x) \frac 1 {b-a}dx$$

  取均值

  $$\bar I = \frac {b-a} n \sum_{i=1}^n g(x_i)$$

  可作为求分I的近似值

解非线性方程组

$$\left \{ \begin{array}{l} f_1(x) & = f_1(x_1, x_2, \cdots, x_n) & = 0 \\ f_2(x) & = f_2(x_1, x_2, \cdots, x_n) & = 0 \\ \vdots \\ f_n(x) & = f_n(x_1, x_2, \cdots, x_n) & = 0 \end{array} \right.$$

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

步骤

• 构造目标函数

  $$\Phi(x) = \sum f_i^2(x)$$

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

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

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

• 真正的随机次梯度下降

Monte Carol Method

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

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

Las Vegas Method

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

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

Sherwood Method

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

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

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

思想

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

  $$\bar t_A(n) = \sum_{x \in X_n} t_A(x) / |X_n|$$

  • $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的随机实例平均时间为

    $\begin{align*} \bar t_B(n) & = \sum_{x \in X_n} t_B(x) / (X_n) \\ & = \bar t_A(n) + s(n) \end{align*}$K

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

todo