机器学习实践：利用优化算法，实现StumbleUpon系统原型

30 Sep 2013 ###背景&相关知识点 优化算法是针对NP Hard问题暴力搜索解法的优化，算是一种启发式搜索 。比起暴力搜索，通过优化算法来进行启发搜索的好处是，效率更高，更快的逼近最优解；缺点则是最终结果很可能并不是全局最优解，它只能保证向最优解靠拢。这在现实的很多系统中是可以接受的。毕竟有一个可行的较优解比没有解要好很多。
之所以想到网址推荐，还是受到《集体智慧编程》相关章节里延伸应用的启发。StumbleUpon鼓励用户对网站进行人工标注，然后根据标注的tag对其他用户进行推荐，注意，这里显然也可以利用推荐系统算法来推荐网址。但是利用搜索算法同样可以实现快速为指定用户寻找指定大小的网址候选集合。
优化算法的核心是“估价函数”，又叫“惩罚函数”，这个函数主要是算法对一个可行解进行代价判定时使用。如果通过估价函数判定后，解空间A花费的代价要小于解空间B，那么A胜出，然后进行下一轮的迭代, 注意，并非每一轮迭代更优的解都会取代旧的解，这主要是为了避免陷入局部最优解的陷阱中。是否更新当前解的概率和具体算法相关。不同优化算法的区别就在迭代过程中凸显出来。这里择其1，2说一下

• 模拟退火算法：这个算法如其名字表述的那样，模拟现实世界中金属退火的物理过程。金属退火时，随着温度的降低，分子活跃度逐渐减弱。这个算法就是根据这一物理过程，设定一个初始最高温度和降火速率，这里分子活跃度就是我们搜索可行解过程中，使用新的可行解取代旧可行解的可能性。初始温度很高，分子很活跃，相应的几乎每次迭代都会更新当前解空间。每次迭代后，温度就会降低，降低幅度由降火速率决定。随着迭代的进行，温度越来越低，算法向最优解收敛，最终温度降到0点，算法停止。当然中间我们也可以手动指定迭代次数，并不一定要等温度降到最低。

• 遗传算法：遗传算法相对简单一点，就是模仿自然界基因变异的过程对可行解进行再构造,初始会有一个种群代表初始的解空间集合，然后每轮的进化中通过变异和杂交进行优胜劣汰，种群规模决定了有多少个体进入下一轮进化。再构造的方式包括变异和杂交，当然你也可以克隆技术，但是克隆技术在很多问题中是没有意义的。举例说明：如果当前可行解是【1，2，3，4】，那么经过变异后可行解可能是【1，3，3，4】,经过杂交后,此时需要借助另一个解空间【7，8，9，0】,因为杂交至少有2个个体参与，杂交后的结果可能是【1，2，9，0】。然后经过估价函数对每个解进行判定打分，然后排序，淘汰分数较低的个体。

###项目地址 https://github.com/zuojie/MichineLearningCases/tree/master/Optimization