programming collective intelligence读书笔记四

optimization问题,用于解决多人旅行的机票安排,或者学校排课,sns里面自动画一副关系树的图,让交叉点尽可能少(这样看起来清楚),把许多人分成小组,让每个小组里面的人技能尽可能的不同(不同的兴趣),把一个大工程分拆成工作量差不多的小块...给定一组关键词和网址,把网址分组,让他们尽量内聚...突然想到可以高考根据志愿和分数安排学校,让尽可能多的人满意^_^

先讲了一个取最优点的问题,可以转化成二维曲面找最低点这个模型
hill climbing方法只能有局部最优
然后改进的方法是随机选取一个点然后再探索局部最低,多次尝试取最小点
叫做random-restart hill climbing

simulated annealing算法
这个算法很有意思 p = e^(-x/t) x是当前cost和最低cost的和,t是温度,随着探索次数增加逐渐降低
算法是随机选个点,然后再随机选个新点,算出x,以p的概率使用新的点,然后反复迭代
一开始t高,新点就算cost比较高也容易被选中,随着t的降低,对cost要求越来越严格,需要比较低的才能接受
最后逐渐收敛到比较低的cost...这个方法是用来跳过局部最低点,寻找全局最优点

genetic 基因算法
先随机算一组结果,比如100个,然后算出下一代,然后再反复迭代
算下一代的方法有两种:
mutation变异,就是下一代全是最优秀的那个进行小变动得到...
crossover or breeding...杂交...就是最优秀的几个杂交...取父母中间值...
基于进化论...



--------------
chenjinlai
2008-05-08