machine learning / 机器学习

全局最优解算法

在计算最优解时,如果是非凸函数,往往会遇到局部最优解和全局最优解的问题,常用的梯度下降算法(Gradient Descent)和爬山算法(Hill Climbing)由于是贪心算法,往往算出来的是局部最优解,那么怎么达到全局最优解?

1.模拟退火算法(Simulated Annealing或SA):简单说就是以一定概率跳出当前最优解继续搜索全局最优解,这个概率会随着时间的增加而降低,以达到趋于稳定,这样有可能达到全局最优解。

2.遗传算法(Genetic Algorithm或GA):类似生物遗传学,通过选择、交叉、变异这三个遗传操作,对个体进行环境适应性评估,以达到优胜劣汰的目的。

3.蚁群算法(Ant Colony Optimization或ACO):各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。当一只找到食物以后,它会向环境释放一种挥发性分泌物pheromone (称为信息素,该物质随着时间的推移会逐渐挥发消失,信息素浓度的大小表征路径的远近)来实现的,吸引其他的蚂蚁过来,这样越来越多的蚂蚁会找到食物。有些蚂蚁并没有像其它蚂蚁一样总重复同样的路,他们会另辟蹊径,如果另开辟的道路比原来的其他道路更短,那么,渐渐地,更多的蚂蚁被吸引到这条较短的路上来。最后,经过一段时间运行,可能会出现一条最短的路径被大多数蚂蚁重复着。

PS1:以上算法仅提高全局最优解的概率,不保证一定达到。

PS2:最小化问题中,最优解是极小值,但不一定是最小值。学习速度等因素的存在导致即使步子迈的再小,两个步子之间也是有距离的,很有可能最小值在两步之间。由于最小值和极小值往往误差很小,因此在应用上可接受。

Leave a Reply

Your email address will not be published. Required fields are marked *