机器学习入门之《集体智慧编程》优化算法

skywalkerVVV

于 2012-12-26 12:39:36 发布

阅读量1.2k

点赞数

分类专栏：机器学习入门

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

本文链接：https://blog.csdn.net/skywalkerVVV/article/details/8438432

版权

机器学习入门专栏收录该内容

8 篇文章

订阅专栏

优化算法在很多问题中用到，用以寻找最大值或者最小值,其实就是一个搜索问题

在一个指定的搜索空间中，每一个点（也可以说是一个可能的solution）都可能是最小值。

机器学习入门 <wbr>优化算法

每一种搜索算法都必须要有的是一个costFunction函数。

每一个点都可以计算出一个cost值

cost = costFunction(point)

1、随机算法

随机算法最简单,就是随机地找N个点，计算每一个点的cost值，寻找其中最小的点，作为最优解。

这个算法不一定能得到最小解，但是可以多用几遍这个算法，取每最优解中的最优解。

2，爬山法

1> 随机选择一个点p 作为初始点计算cost =costFunction(p)

2>随机地修改这个点的某一个变量，得到p_next

3> 计算cost_next= costFunction(p_next)

4> 比较cost和cost_next，如果cost_next更优 把p_next 作为当前最优值 (即p =p_next)

5> 重复 2>到4> 直到cost不再变化

这个算法纯粹就是一个贪心算法，它只能得到局部最优解，例如图中，随机选的点事A，采用爬山法只能得到B这个局部最优解，最优解是C，但是这个算法得不到.

同样可以多次使用这个算法取最优的那个解

因为每一次迭代必须必当前更优，才做p=p_next，就像爬山一样，一值往上爬（往更优的点靠近）所以叫”爬山法“。

3、模拟退火法

模拟退火法其实是对爬山法的改进.在爬山法中,每一次只接受比当前更优的点,而模拟退火以一定的概率接受比当前更坏的点.

这样就可以再得到局部最优解的时候,跳出这个局部最优解,找到全局最优解.

这个算法有两个参数叫做温度T=1000,和r=0.95（r越小温度降低就越快）

每迭代一次温度就降低一次 T=rT

1> 随机选择一个点p 作为初始点计算cost =costFunction(p)

2>随机地修改这个点的某一个变量，得到p_next

3> 计算cost_next= costFunction(p_next)

4> T=rT,比较cost和cost_next，如果cost_next 更优或者 random *1000 <T 把p_next作为当前最优值 (即p = p_next)

5> 重复 2>到4> 直到cost不再变化或者T小于某个值

随着T越来越小，接受一个更坏的结果的概率就越小，T很小的时候，其实就变成了爬山法了。

4、遗传算法

遗传算法是模拟生物的遗传现象，生物的进化有自己的变异，也有继承自父母两个的优良基因（杂交）

变异也就是当前“基因”的随机变化，交叉是两个“基因”合并为一个基因

故遗传算法必须有两个函数：变异 variation 杂交crossover()

1>随机生成一组solution

2>计算这组solution的 cost并排序

3>取出最优的前n个solution

4>在这n个solution取出p%进行变异(就是随机修改solution的参数）取出q%进行杂交,将变异和杂交的新的solution加入到当前这组solution中

5>重复2>到4>

y

评论

被折叠的条评论为什么被折叠?

到【灌水乐园】发言

查看更多评论

添加红包

成就一亿技术人!

hope_wisdom

发出的红包

实付元

使用余额支付

点击重新获取

扫码支付

钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。