启发性算法

Posted on

启发性算法

  • 非常狭义定义：
    • 用来设计最优化问题的随机算法的鲁棒性技术；
    • 不能保证解的效率和质量
    • 没有有界常数概率

模拟退火 Simulated Annealing

概念

  • 局部搜索+跳出局部最优的随机决策
  • 局部搜索：找到一个可行解；找到邻域中的最优解替换并且循环这一步
  • 多起点局部搜索
  • threshold local search：允许移动到较差解
  • 模拟退火的基本思想:
    • 初始化：初始温度T，初始可行解$\alpha \in M(x)$(是算法迭代的起点)，温度关于温度和时间的下降函数f
    • 时间$I=0$，当温度大于0(或不太靠近0)时，重复一下操作：
      • 随机选取$\alpha$邻域中的解$\beta$
      • 如果$cost(\beta)\le cost(\beta)$, $\alpha:=\beta$;
      • 否则生成一个(0, 1)间的随机数r
        • 如果$r<\exp(-\frac{cost(\beta)-cost(\alpha)}{T})$, 则$\alpha:=\beta$;
      • $I =I+1$
      • $T=f(T,I)$
    • 输出$\alpha$

理论和经验

  • 如果下列条件成立, 模拟退火是渐进收敛的, 即取全局最优解的概率随迭代次数的增加趋向于1
    • 每个可行解都是任意其他可行解可达的
    • 初始温度T至少为最深的非全局最优的局部最优解的深度
  • 初始温度选择:
    • cost的最大差值
    • 或者任选T, 过程中增大T值保证接受概率小于1
  • 温度下降函数选择:
    • 通常选取常数r, $0.8\le r \le 0.99$, $T := r\cdot T$
    • 或者选取$T_k:=\frac{T}{\log_2(k+2)}$
    • 每个固定温度的迭代次数d为邻域的大小
  • 终止条件:
    • 一段时间cost不变
    • T < term, 通常$term\le \frac{\epsilon}{\ln [(|M(x)|-1)/p]}$
  • 观察结果:
    • 可能解质量好但是计算开销极大
    • 解的质量实际上未必和初始解选取有关
    • 最重要的参数是邻域和温度下降率
    • 平均时间接近最坏时间
    • 相同邻域下效果比局部搜索好
  • 应用: MAX-CUT, MIN-CUT; (TSP效果很差)

随机禁忌搜索

  • 模拟退火推广版
  • 记录搜索过的最优解, 并且在邻域和TABU的差集中搜索, 搜索后更新TABU
  • TABU有多种选择策略, 可以前k步搜索过的解以免重复
  • 随机禁忌搜索算法:
    • 选初始解$\alpha$, TABU = {$\alpha$}, STOP = FALSE, BEST = $\alpha$
    • 选$Neigh_x(\alpha)-TABU$中最优解$\beta$, 同模拟退火选择是否接受$\beta$
    • 更新TABU和STOP
    • 重复直至STOP

遗传算法 genetic algorithm

概念

  • 遗传算法:
    • 创造一个初始化人口$P=\{\alpha_1, \cdots, \alpha_k\}$; 已经创造的人口数$t=0$
    • 计算fitness($\alpha_i$), i = 1, 2, …, k, 据此评估P的分布律$Prob_P$, 满足高fitness有较高概率
    • 根据$Prob_P$随机选取$k/2$对可行解$(\beta_1^1, \beta_1^1)$, …, $(\beta_{k/2}^1, \beta_{k/2}^1)$
    • 计算每一对的crossover生成新个体, 加入P
    • 对P中每个个体随机使用变异mutation
    • 对于P中每个个体再次计算fitness, 据此选择k个组成P’ $\subseteq$P
    • 可能对于P’中元素在邻域中搜索最优解来替代
    • $t:=t+1$; $P:=P’$; 满足停止条件则输出, 不然重复上述步骤
  • 定义: M(x)的计划为任意向量$s=(s_1, s_2,…,s_n)\in \\{0,1, \\} ^ n$(表示free); 对于计划s的可行解集合为
    $Schema(s_1, …, s_n) = \{ \gamma_1, …, \gamma_n\in M(x)|\gamma_i = s_i \text{ for all }i \in \{1,…,n\} $
    $\text{ such that }s_i\in \{0,1\};\gamma_i \in\{0,1\}\text{ for all }j\in \{1,2,…,n \}\text{ such that }s_j=* \}$
  • length(s): s中第一个和最后一个非位置间的距离;
    order(s): 非    位置数
    $Fitness(s, P) = \frac{1}{|Schema(s)\cap P|}\cdot \sum_{\gamma\in Schema(s)\cap P}cost(\gamma)$
    $Fit-ratio(s, P) = \frac{Fitness(s, P)}{\sum_{\beta \in P}cost(\beta)/|P|}$, 分母为平均fitness
  • The Schema Thm for GAS: 对任意Schema s 和任意 t= 1, 2, …, Schema(s)在(t+1)-st人口的期望个体数为
    $E[Z_{t+1}]=Fit-ratio(s, P_t)\cdot \frac{n-length(s)}{n}\cdot (1-order(s)\cdot pr_m)\cdot |P_t\cap Schema(s)|$

参数选择

  • 人口大小:
    • 太小容易局部最优, 太大计算开销大
    • 30或者区间[n, 2n]内(n为实例的大小)
  • 初始人口选择:
    • 随机选择
    • 选择较高质量的初始人口会增快收敛速度, 但容易收敛到局部最优
  • fitness选择:
    • 最大化问题直接选取cost作为fitness, 或再减去一个小于最小值的常数; 减去的值越接近最小cost, 越偏向于高cost个体
  • 父母的选择:
    • 选最好的一半和剩下的随机组合
    • 或者按照从小到大排序后, 根据$Prob(\alpha_i)=\frac{2i}{n(n+1)}$的概率选择
  • 个体的表示和crossover
    • 例如TSP中个体表示为1-n的排列, crossover可以选择为一个排列中的某部分按照另一个排列中的顺序重排
    • 或者将父母的某些特征crossover, 然后选择满足crossover后性质的解作为孩子
  • 突变概率:
    • 1/100
    • 或1/n
    • 或$\frac{1}{k^{0.93}\sqrt{n}}$
    • 如果人口数量k较小, 就要增大突变率防止局部最优
  • 新人口选择机制
    • en block strategy: 孩子完全替代父母
    • elite model: 选一小部分父母中的高fitness个体, 其余的大部分选孩子
    • 父母孩子放一起, 选择高fitness的
    • 选完之后可以在小邻域中提升个体fitness
  • 停止策略:
    • 确定的代数
    • 根据平均fitness(不怎么变)和个体差异(小)