启发式算法
Intro
首先考虑一个经典问题:旅行商问题(Traveling Salesman Problem, TSP).
或许你的第一想法式dijastra算法.但问题在于dijastra解决的是点到点的最短路径,而旅行商要转一圈回到原点,这是dijastra算法无法解决的问题.
或许你还会想到贪心算法.事实上,贪心算法正是启发式算法的一个子类.但是在这个问题中,什么贪心策略都无法保证全局最优解.
为什么我能这么肯定呢?因为旅行商问题是一个$NP难(NP-hard)$问题,要想得到最优解,就必须把所有可能枚举出来然后再做比较.
如果你能做到不枚举所有可能就得到最优解,那么今年的菲尔兹奖,图灵奖等等等等你肯定是要拿到手软了.
我们继续分析旅行商问题.如果有$n$个城市,则路径有$(n-1)!$种可能,显然当n变大时,计算量就要爆炸了.
当我们无法接受计算量带来的成本时,我们就需要找到一种虽然成本较低,但最终结果仍然不错的算法,而这就是$启发式算法$
启发式算法
启发式算法是基于直观或经验构造的算法,在可接受的计算时间和空间条件下,给出待
解决优化问题的一个可行解.
启发式算法并不保证找到最优解,只是在有限资源下找到还不错的解.
经典的启发式算法包括模拟退火、遗传算法、蚁群算法、神经网络等.
但问题来了:我们如何找到一个好的启发式算法?正如名字一样,我们是从大自然中获得的启发.
模拟退火算法
1983年,约翰·米尔斯·卡尔曼提出了模拟退火算法(Simulated Annealing, SA),这是一种启发式算法.
模拟退火算法得益于材料统计力学的研究成果.
统计力学表明材料中粒子的不同结构对应于粒子的不同能量水平.在高温条件下,粒子
的能量较高,可以自由运动和重新排列.在低温条件下,粒子能量较低.
如果从高温开始,非常缓慢地降温（这个过程被称为退火）,粒子就可以在每个温度下
达到热平衡.当系统完全被冷却时,最终形成处于低能状态的晶体.
一群没有”智商”的粒子,是在什么样的规则下,才能默契地互相地让自己达到一个能量最低的状态?这个规则就是我们需要的.
模拟退火算法的基本思想是:
- 为了不被局部最优解困住,需要以一定概率跳出当前位置,暂时接受一个不太好的解.
- 在搜索最优解时逐渐降温,初期跳出去概率大,进行广泛搜索;后期跳出去概率小,尽量收敛到最优解.
再将思想进行建模,步骤如下:
- 随机生成一个初始解X，设定一个初始温度T
- 在上一次解的基础上进行调整，生成新的解X’，并对比旧解f(X’)和新解f(X)
- 如果新解更好了，那就接受
- 如果新解更差了，那就以e^-(f(X’)-f(X)/T)作为概率接受
- delta f(x) : 这个解变差了多少,越少接受概率越大
- T : 温度高接受概率大,低就小
- 降温并重复上述步骤，直至迭代一定的次数
- 用整个搜索过程中的最优解作为输出解
tips:
- 初始解可以随意选取,但好的初始解可以帮助算法快速收敛
- 可先随机生成几个序列,选一个较好的初始解;或使用贪心算法选择初始解;或使用启发式算法选择初始解
- 降温方法
- 初始温度,降温方法的选择比较tricky ,没有固定标准,只能试.例如:初始温度为1,每次降温* 99%,降到 10^-30 就停止.需要根据具体问题分析确定
- 也不需要每次迭代都降温,可以迭代几次后再降一次温
- 如何生成新的解
- 如何根据旧解生成新解并保证新解valid是算法核心部分
运行实例
遗传算法
遗传算法来源于自然选择原理和遗传机制,它模拟了自然界中的生命进化机制.
基因突变是进化的原因,遗传算法通过群体搜索技术,根据适者生存的原则逐代进化,最终得到较优解.
遗传算法的步骤如下:
- 产生M个初始解,构成初始种群
- 每一对父母以一定概率生成一个新解
- 每个新个体以一定概率产生突变
- 父代与子代合在一起,留下M个最好的个体进入下一轮迭代
- 重复直到达成结束条件(次数或精度达到要求),输出最优解
tips:
- 遗传算法中的很多参数没有固定标准,如种群数量M,变异概率…
- M越大,找到最优解概率越大,消耗也越大
- 较好的初始种群可以帮助更快收敛,通模拟退火算法.
- 如何交配产生子代
- 交配方法是遗传算法的核心,应该尽量继承父代的同时进行足够的调整
- 如何突变产生新的解
- 突变就是根据已有解生成新解,方法参考模拟退火算法.
运行实例
蚁群算法
蚁群算法来自于蚂蚁寻找食物过程中发现路径的行为.蚂蚁并没有视觉却可以寻找到食
物,这得益于蚂蚁分泌的信息素,蚂蚁之间相互独立,彼此之间通过信息素进行交流,
从而实现群体行为
蚁群算法的基本原理就是蚂蚁觅食的过程.首先,蚂蚁在觅食的过程中会在路径上留下
信息素(pheromone),并在寻找食物的过程中感知这种物质的强度,并指导自己的行
为方向,他们总会朝着浓度高的方向前进
因此可以看得出来,蚂蚁觅食的过程是一个正反馈的过程,该路段经过的蚂蚁越多,信
息素留下的就越多,浓度越高，更多的蚂蚁都会选择这个路段
蚁群算法的步骤如下:
- 设置蚂蚁的数量,每个蚂蚁随机选择一个起点,初始化所有路线上信息素的浓度相等
- 每一个蚂蚁从不同顶点出发,依次选择自己的路径
- 在每一个节点处,根据路径本身信息x和信息素浓度y选择下一个节点
- 选择每个节点的概率正比于y^a * x^
- 选择路径后,在被选择的路径上留下信息素 y - Q/路径长
- 每一轮的信息素以一定比例挥发,更新信息素浓度 y = py0 + delta y;
- 重复到结束,输出最优解
tips:
- 蚂蚁数量:一般蚂蚁数量与顶点数量相同即可
- a,b:影响路径本身信息和信息素浓度的相对重要性
- 挥发系数p,信息素总量Q,根据具体问题试.
运行实例
游戏中的启发式算法
CCD(Cyclic visiting Decent)
CCD算法是一种用于解决游戏中IK(Inverse Kinematics)问题的算法.
问题描述
假如桌上有一个苹果,你要如何操作你的手臂去拿到这个苹果呢?
给定几个joint(关节)和bone(骨骼).骨骼是一条不可伸缩的线段,关节是链接两条骨骼的点.
这些joint和bone组成了一条链,一端定义为root,另一端定义为tip.
现给定一个目标点target.
求:如何通过一系列的关节动作,使得tip到达目标点并不更改root的位置.
算法步骤
- 从tip遍历到root
- 对于遍历的每一个joint,计算一个使tip”最”靠近target的旋转(即将tip旋转到该点与target的连线上)
- Iterate 直到结束
FABRIK(Forward And Backward Reaching Inverse Kinematics)
FABRIK 也是一种用于解决IK问题的算法.
算法步骤
FABRIK 分为两个步骤:
Forward:
- 先将tip移至目标点.
- 旋转上级骨骼到此节点与上级节点的连线上
- 移动上级节点到正确位置.
- 对上级节点重复步骤2-3
Backward:
与Forward步骤相同,但是这次是让root移动到src(root的初始位置)
重复Forward与Backward步骤,直到结束.
wechat
alipay