[其他资源] 最值算法小论

[复制链接]

字体大小: 正常放大

czzc829z

3 主题	3 听众	64 积分

升级 62.11%

该用户从未签到

电梯直达

1^#

发表于 2010-8-18 14:49 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

目前所有最值搜索算法虽然有很多不一致之处，但是最根本的思想都是通过随机洒出一组初始点
（一个或多个），通过某种迭代规律来确定下一组点使得这些点不断的的趋近于最值点
（其实输入变量x其实未必一定是点，我自认为准确的说是有某种意义的特定矩阵，
点只是其的特殊情况，比如TSP问题就是典型代表）然后，迭代满足某些条件，退出循环，
得到的当前点就是趋近于最值点的
下面我就这个迭代点的思想基础上给大家重新介绍理解一下各种最值算法
无约束条件下的问题：
单点迭代：（原始的牛顿法、模拟退火法SA）
原始的牛顿法：
      不扯了，大家都知道，迭代规则很明确，显然会陷入local extremum
模拟退火法SA：
      一、算法来源
         现在我们从迭代点趋近最值点的角度来理解SA
         牛顿法陷入局部极值的的原因显然是因为收敛方向一致所导致的，于是，
         有一个非常直观的想法就诞生了，不要一致收敛就好了嘛，是不？举个例子说明：
         求y=x^2的最小值，显然是0。不妨假设初始随机点为x=1，在牛顿法中x将会一致逼近到0，
         而在SA中，x有可能到x=0，也可能到x=2,只是概率不一样罢了，
         下面就求最大值问题y=f(x)来说明（x是数值输入，也就是一个一维函数）
         （特别说明：真正的来源和算法创造思想当然不是上述，而是高温退火的物理过程，
         这里就不说了，物理不好的根本没法理解）
      二、迭代规律
         所有算法中初始点可以随机也可以指定
         在当前点附近随机搜索（可以理解为邻域内，比如步长为0.001的圆（应该说是概念圆）
         内随机找一点），在上面所说最大值问题y=f(x)中，假定步长0.001，
         也就是在x-0.001到x+0.001的区间中按某种分布（通常是均匀概率分布）随机一点x_new
               如果y_new>y 就让x_new成为新的x
               如果y_new<y 就让x_new成为按照概率exp(y_new-y/T)成为新的x,否则x就是新的x
                           （这里先暂时假定T是一个常数，比如T=100）
               以上就是迭代规则，很明显可以感觉到按照上述规则迭代可以到达最值点。
      三、效率改进
         按照上述改则，即使x位于最值点，也有可能跳出，这显然不是我们希望看到的，
         随着迭代次数的增加，我们可以认为迭代点是总是大致趋于最值点的
         所以点的稳定性应该逐渐增强（也就是exp(y_new-y/T)应该减小），x应该尽可能不变，
         显然我们可以减小T就可以达到这个目的T的减小规律可以自己设一个递减函数就行，
         比如每迭代一次T->T*0.99或者T->T-0.01之类的
      四、退出条件
         显然迭代要有退出条件，这里有2中常见办法
         第一种就是T小于某个值就可以退出迭代（比如初始T=100，T<0.1时退出循环）
         第二种就是迭代了N（比如100）次x值（x值就是平均值啦，也可以取y值变化量）
         的变化小于某数（比如0.001）
      五、注意事项
         上面我把SA的原理说的十分简单，但是实际上显然不是那么好实施的，
         因为里面很多数的取值没有固定的说法，只能靠经验（后面介绍的算法也是）
         一个没弄好还不如枚举法（一些离散最值问题所有可行解事可以列出的）的效率高，
         那就搞笑了是不？建议设置参数的时候逐渐调试，先从显然不用迭代几次
         的参数开始逐渐调试到满意解，免得一下参数没设置好MATLAB就跑个几天没结果
         （我刚学的时候就老犯这个错误），这里介绍的是无约束问题，
         有约束条件的改进将在后面介绍

多点迭代：（原始的二分法和0.618法、粒子流PSO
      （还有个叫鱼群算法的我没仔细看，貌似就是PSO的中国学者抄袭版，阿弥豆腐了。。）、
         遗传算法GA）
   原始的二分法和0.618法：
      不扯了，大家都知道，迭代规则很明确，显然会陷入local extremum
   粒子流PSO：
      一、算法来源
         我这里给个比较简单的说法让理解一下，假想一群瞎子在一块地方要找最高点，
         他们可以用这么一个策略:先瞎子们随机站在这边土地上，
         每一个人根据当前站在最高处的人的方向，该人自己曾经找到过的最高点，
         某个大家统一的随机方向，三个方向来确定自己要行进的方向，并迈出一步，之后，
         重复这个动作，最终大家会在最高点相聚,显然这个寻找最值点方法不像SA那么明显，
         其实实际上PSO的成功率也确实不是特别高
         （文献上80%—90%，我个人实验就只有60%—70%。。。）
      二、迭代规律
         x_new=x+w*velocity+c1*rand()*(p_best-x)+c2*rand()*(g_best-x)
         这是矩阵/向量/点解的集合的迭代方式 x是当前迭代解的集合
         （比如要求y=x^2的最小值，先随机洒出100点，每一个点都按照上述规律迭代）
         w是一个自己固定的权值，取法不一，我目前习惯使用0.8附近
         c1 c2称学习因子，也是一个自己固定的权值，通常取0~2
               rand()就不用解释吧，0~1的随机数
         velocity也是自己取，也可以用rand()加权
         p_best就是这个点自己找到过的最值
         g_best就是当前所有点的最值（也有取当前所有点找到过的最值，
                                    不过文献上都说，经过测试，这样不如取当前最值点的好）
      三、退出条件
         显然，瞎子们聚在一起就是最值了嘛，可以取比如这些洒出的点（100点）
         方差小于某值（比如0.01），或者迭代前后找到的平均最值点变化量小于某数之流
         也可以像SA那样迭代N次点变化量小于某数
      四、注意事项
         鉴于有人说大家看到最高点就走过去。。（囧）所以这里举例用的是瞎子。。
         希望没人介意，先行道歉。。
         大家可以很明显发现PSO和SA类似的都是很多值待定，所以也是要一步一步去取值，
         怎么才能效率高，我没法回答，只能说凭经验设置参数。。

   遗传算法GA：
      一、算法来源
         没有人对达尔文的进化论有意见吧？意思就是越趋近最值就是越好的进化嘛。
      二、迭代规律
         GA和PSO一样都是撒点进行搜索（所以，这两种算法可以用同一种退出条件，囧吧。。），
         不同之处就在于迭代方法，GA的迭代让人蛋疼
         下面就洒出100点的基因算法，分析其迭代过程
         首先，你要把散出的点按照某些方法编成二进制（比如54=110110）,
         这里还要引入一些参数（比如对于0.1,可以0.1*100=10010，所有数都乘100）
         这里要求你把这些二进制代码限制在某个长度，比如6位（10=000010）
         然后，这些01串就称作gene（。。囧。。）有交叉和变异两中算子，
         从而产生一些新的gene（也就是洒出点数就增加了比如100->150）
         所谓交叉，举个例子，111000和000111交叉就成了111111和000000，
         或者取110111和001000，交叉长度随机，产生几个交叉基因也随机
         所谓变异，就是0->1和1->0，基因局部变化产生新基因
         再下来，就是淘汰了，基因数量增多了，就淘汰到原有数量，
         淘汰过程就是把基因反编码（解码啦），观察哪些值更趋近于最值
         （求最大值是就是大的数值嘛）
         留下前面的基因（比如基因个数100-（交叉变异）>150-（淘汰）>100），
         使得种群（洒出点数）不变化。具体怎么取值，一句话，经验。。
         当然，这里有很多思路，别急
      三、效率改进
         在遗传变异淘汰这个迭代体系中，方法并不一样，也可以只淘汰
         （减少点数，在交叉变异过程中，原基因就不要了），如果这样那就要很大的初始点数
         还有就是最为推荐的概率淘汰法，按照概率淘汰淘汰基因（取当前最优基因为对比，
         最优基因保留率为1，其他基因按照y/y_best概率保留）这是个很多办法的地方，
         我不敢做评价，只能说变异交叉淘汰的迭代过程可以有很多优化办法，
         洒出点数不一定是定值，可能减少也可能增多（PSO点数固定）
      四、退出条件
         和PSO一致，不推荐用方差法（因为有的GA洒出点增多了，程序就近乎死循环啦）
      五、注意事项
         这里参数就更加复杂啦，怎么取，怎么设计算法貌似还没共识。。凭经验。。
         SA PSO GA三种算法的参数都没那么好取，简单的问题（比如5个变量一下之流）
         都方便的很，但是一旦变量多了就是维数灾，参数没调好就跑不出来啦,参数全靠经验流。
         另外就是很明显这算法要看RP的。。。运气好1秒就OK了。。。运气不好就悲剧了。。。

有约束条件的解决办法：
算法改进：（不推荐，需要比较高深的功力）
      由于不推荐，这里只是简单介绍
      SA：
         迭代每一次随机点满足约束就好了，SA有约束时非常好解决，因为迭代式独立的
      PSO:
               反射壁衰减墙之流，麻烦的蛋疼
      GA：
         类似PSO
惩罚法：（推荐）
      这里我距离说明，求y=x^2在|x|<2的区间中的最小值
      这里令y为分段函数  y=x^2                      if |x|<2
                                          x^2+100000       else
         懂了吧，反正SA PSO GA不要求函数连续（没求导过程）
      在约束条件外就用绝对不可行值惩罚

另注：一开始是幼儿园。。发现无权发帖。。回帖之后才发现。。囧。。
      求分求加精，本人独创。。

zan