数学建模社区-数学中国

标题: matlab怎么求出全局优化解 [打印本页]

作者: tiancai1234 时间: 2010-8-17 20:38
标题: matlab怎么求出全局优化解
matlab怎么求出全局优化解，需要用什么函数或者是什么工具箱，请教

作者: madanmoumou 时间: 2010-8-17 20:56
可以使用Maple全局优化工具箱

作者: 我就是独狼 时间: 2010-8-18 00:30
help指令~~~~~~~~~~~~·

作者: czzc829z 时间: 2010-8-18 14:44
目前所有最值搜索算法虽然有很多不一致之处，但是最根本的思想都是通过随机洒出一组初始点
（一个或多个），通过某种迭代规律来确定下一组点使得这些点不断的的趋近于最值点
（其实输入变量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不要求函数连续（没求导过程）
      在约束条件外就用绝对不可行值惩罚

我自己写的。。发现无权发帖。。

作者: tiancai1234 时间: 2010-8-18 19:31
回复 czzc829z 的帖子
太牛了啊，我不是斑竹，是的话，肯定给你加积分或者下载币什么的

作者: tiancai1234 时间: 2010-8-18 19:32
回复 czzc829z 的帖子
太牛了啊，我不是斑竹，是的话，肯定给你加积分或者下载币什么的，嗯，是体力，呵呵

作者: tiancai1234 时间: 2010-8-19 15:11
回复 madanmoumou 的帖子
貌似这个工具箱没有啊，怎么办，我想下载，可是官网上手续太烦琐了

作者: birddong2000 时间: 2010-8-26 11:33
我来了~~~~~~~~~ 闪人~~~~~~~~~~~~~~~~

作者: shime 时间: 2010-8-26 11:34
呵呵大家好奇嘛来观看下~~~~

作者: snrl 时间: 2010-8-26 11:35
楼主，你写得实在是太好了。我惟一能做的，就只有把这个帖子顶上去这件事了

作者: chshfxfx 时间: 2010-8-26 11:36
顶顶更健康，越顶吃的越香。

作者: icm 时间: 2010-8-26 11:38
顶顶更健康，越顶吃的越香。

作者: sam68 时间: 2010-8-26 11:45
楼主的帖子实在是写得太好了。可是我立刻想到，这么好的帖子，倘若别人看不到，那么不是浪费楼主的心血吗？经过痛苦的思想斗争，我终于下定决心，牺牲小我，奉献大我。我要拿出这帖子奉献给世人赏阅，我要把这个帖子一直往上顶，往上顶！顶到所有人都看到为止！

作者: ss256 时间: 2010-8-26 13:52
留个脚印```````

作者: huxiao9026 时间: 2010-8-26 18:58
哦～～

作者: racheltong 时间: 2010-8-26 19:16
顶顶更健康，越顶吃的越香。

作者: xphoenix 时间: 2010-8-27 00:00
我来了~~~~~~~~~ 闪人~~~~~~~~~~~~~~~~

作者: sky71412 时间: 2010-8-27 00:51
你写得实在是太好了。我惟一能做的，就只有把这个帖子顶上去这件事了

作者: net2k 时间: 2010-8-27 08:00
呵呵大家好奇嘛来观看下~~~~

作者: beaugar 时间: 2010-8-27 12:00
偶的天啊!这是什么样的贴子呢？

作者: nn58123 时间: 2010-8-27 15:00
声明一下：本人看贴和回贴的规则，好贴必看，精华贴必回。

作者: yunwuya 时间: 2010-8-27 20:00
强烈支持。楼主万岁

作者: 199311131993 时间: 2010-8-28 08:00
顶顶更健康，越顶吃的越香。

作者: xinyu 时间: 2010-8-28 12:00
我基本上是采用看英语文章的办法，先泛读，再精读，再一句一句看，最后再提纲挈领，总算是明白一点了，当然，也可能还是领悟错了。最后要说的一句话是：楼主，你很牛叉，希望你不是真的有病。

作者: lwx193520 时间: 2010-8-28 15:00
强烈支持。楼主万岁

作者: zjf822 时间: 2010-8-28 20:00
顶顶更健康，越顶吃的越香。

作者: diaohaiq 时间: 2010-8-28 23:59
我要把这个帖子一直往上顶，往上顶！

作者: 37212100 时间: 2010-8-29 08:00
呵呵大家好奇嘛来观看下~~~~

作者: wl2130 时间: 2010-8-29 12:00
我来了~~~~~~~~~ 闪人~~~~~~~~~~~~~~~~

作者: casper 时间: 2010-8-29 15:00
我基本上是采用看英语文章的办法，先泛读，再精读，再一句一句看，最后再提纲挈领，总算是明白一点了，当然，也可能还是领悟错了。最后要说的一句话是：楼主，你很牛叉，希望你不是真的有病。

作者: 星际丑男 时间: 2010-8-29 20:00
强烈支持。楼主万岁

作者: lihe 时间: 2010-8-30 08:00
哦～～

作者: zlk 时间: 2010-8-30 12:00
顶顶更健康，越顶吃的越香。

作者: liguoli 时间: 2010-8-30 15:00
楼主的帖子实在是写得太好了。可是我立刻想到，这么好的帖子，倘若别人看不到，那么不是浪费楼主的心血吗？经过痛苦的思想斗争，我终于下定决心，牺牲小我，奉献大我。我要拿出这帖子奉献给世人赏阅，我要把这个帖子一直往上顶，往上顶！顶到所有人都看到为止！

作者: Hyacinth 时间: 2010-8-30 20:00
我来了~~~~~~~~~ 闪人~~~~~~~~~~~~~~~~

作者: xhh 时间: 2010-8-31 08:00
我要把这个帖子一直往上顶，往上顶！

作者: arrjian 时间: 2010-8-31 12:00
我基本上是采用看英语文章的办法，先泛读，再精读，再一句一句看，最后再提纲挈领，总算是明白一点了，当然，也可能还是领悟错了。最后要说的一句话是：楼主，你很牛叉，希望你不是真的有病。

作者: ilava 时间: 2010-8-31 15:00
试试运气啦~~~~~~~~~~~

作者: gpxsin 时间: 2010-8-31 20:00
顶顶更健康，越顶吃的越香。

作者: xht377 时间: 2010-9-1 08:00
我回不抢呢考虑再三还是不抢了吧 ^_^

作者: 快乐宝宝 时间: 2010-9-1 12:00
强烈支持。楼主万岁

作者: huocch 时间: 2010-9-1 12:00
声明一下：本人看贴和回贴的规则，好贴必看，精华贴必回。

作者: xiayulin 时间: 2010-9-1 15:00
顶顶更健康，越顶吃的越香。

作者: xooe 时间: 2010-9-1 20:00
声明一下：本人看贴和回贴的规则，好贴必看，精华贴必回。

作者: 风云88200 时间: 2010-9-2 08:00
楼主，你写得实在是太好了。我惟一能做的，就只有把这个帖子顶上去这件事了

作者: Marvin41029 时间: 2010-9-2 12:00
留个脚印```````

作者: 天涯逸客 时间: 2010-9-2 15:00
我来了~~~~~~~~~ 闪人~~~~~~~~~~~~~~~~

作者: jcccccccc 时间: 2010-9-2 20:00
试试运气啦~~~~~~~~~~~

作者: dtlsflxbb9 时间: 2010-9-3 08:00
不错不错,我喜欢看

作者: legend2001 时间: 2010-9-3 12:00
哦～～

作者: tianaf 时间: 2010-9-3 15:00
留个脚印```````

作者: peck 时间: 2010-9-3 20:00
我要把这个帖子一直往上顶，往上顶！

作者: marsdiy 时间: 2010-9-4 08:00
不错不错,我喜欢看

作者: l0310 时间: 2010-9-4 12:00
我回不抢呢考虑再三还是不抢了吧 ^_^

作者: hbghr8187 时间: 2010-9-4 15:00
楼主的帖子实在是写得太好了。可是我立刻想到，这么好的帖子，倘若别人看不到，那么不是浪费楼主的心血吗？经过痛苦的思想斗争，我终于下定决心，牺牲小我，奉献大我。我要拿出这帖子奉献给世人赏阅，我要把这个帖子一直往上顶，往上顶！顶到所有人都看到为止！

作者: belman 时间: 2010-9-4 20:00
鉴定完毕！

作者: boy40400 时间: 2010-9-5 08:00
看起来好~~像啊~~~~~

作者: lifelight 时间: 2010-9-5 12:00
我基本上是采用看英语文章的办法，先泛读，再精读，再一句一句看，最后再提纲挈领，总算是明白一点了，当然，也可能还是领悟错了。最后要说的一句话是：楼主，你很牛叉，希望你不是真的有病。

作者: leozzz 时间: 2010-9-5 15:00
顶顶更健康，越顶吃的越香。

作者: liuguilong 时间: 2010-9-5 20:00
哦～～

作者: longren 时间: 2010-9-6 08:00
我基本上是采用看英语文章的办法，先泛读，再精读，再一句一句看，最后再提纲挈领，总算是明白一点了，当然，也可能还是领悟错了。最后要说的一句话是：楼主，你很牛叉，希望你不是真的有病。

作者: xunyicao369 时间: 2010-9-6 12:00
不错不错,我喜欢看

作者: tianfy21st 时间: 2010-9-6 15:00
楼主的帖子实在是写得太好了。可是我立刻想到，这么好的帖子，倘若别人看不到，那么不是浪费楼主的心血吗？经过痛苦的思想斗争，我终于下定决心，牺牲小我，奉献大我。我要拿出这帖子奉献给世人赏阅，我要把这个帖子一直往上顶，往上顶！顶到所有人都看到为止！

作者: greatliu 时间: 2010-9-6 20:00
顶顶更健康，越顶吃的越香。

作者: yewen22 时间: 2010-9-7 08:00
试试运气啦~~~~~~~~~~~

作者: 20040306 时间: 2010-9-7 12:00
楼主，你写得实在是太好了。我惟一能做的，就只有把这个帖子顶上去这件事了

作者: GAOND 时间: 2010-9-7 15:00
楼主，你写得实在是太好了。我惟一能做的，就只有把这个帖子顶上去这件事了

作者: mikerain 时间: 2010-9-7 20:00
哦～～

作者: bobbie 时间: 2010-9-8 08:00
我要把这个帖子一直往上顶，往上顶！

作者: worldhalt 时间: 2010-9-8 12:00
我基本上是采用看英语文章的办法，先泛读，再精读，再一句一句看，最后再提纲挈领，总算是明白一点了，当然，也可能还是领悟错了。最后要说的一句话是：楼主，你很牛叉，希望你不是真的有病。

作者: aslixp 时间: 2010-9-8 15:00
我要把这个帖子一直往上顶，往上顶！

作者: 南柯一小梦 时间: 2010-9-8 19:34
厉害厉害，不怎么看得懂。。。

作者: zf3224145 时间: 2010-9-8 20:00
顶顶更健康，越顶吃的越香。

作者: ssssss 时间: 2010-9-9 08:00
我回不抢呢考虑再三还是不抢了吧 ^_^

作者: sunchuren 时间: 2010-9-9 08:00
来报道!!!!!!!!!!!

作者: wylng 时间: 2010-9-9 12:00
哦～～

作者: jimmy 时间: 2010-9-9 15:00
楼主，你写得实在是太好了。我惟一能做的，就只有把这个帖子顶上去这件事了

作者: linghu 时间: 2010-9-9 20:00
楼主，你写得实在是太好了。我惟一能做的，就只有把这个帖子顶上去这件事了

作者: renwo 时间: 2010-9-9 20:00
强人，佩服死了。呵呵，不错啊

作者: 寻寻觅觅 时间: 2010-9-10 08:00
楼主那种裂纸欲出的大手笔，竟使我忍不住一次次的翻开楼主的帖子……

作者: zzs3782 时间: 2010-9-10 11:40
声明一下：本人看贴和回贴的规则，好贴必看，精华贴必回。

作者: lilei 时间: 2010-9-10 11:52
顶顶更健康，越顶吃的越香。

作者: pconline 时间: 2010-9-10 12:00
我基本上是采用看英语文章的办法，先泛读，再精读，再一句一句看，最后再提纲挈领，总算是明白一点了，当然，也可能还是领悟错了。最后要说的一句话是：楼主，你很牛叉，希望你不是真的有病。

作者: shaoqin 时间: 2010-9-10 15:00
强人，佩服死了。呵呵，不错啊

作者: njtuwangrun 时间: 2010-9-10 20:00
楼主的帖子实在是写得太好了。可是我立刻想到，这么好的帖子，倘若别人看不到，那么不是浪费楼主的心血吗？经过痛苦的思想斗争，我终于下定决心，牺牲小我，奉献大我。我要拿出这帖子奉献给世人赏阅，我要把这个帖子一直往上顶，往上顶！顶到所有人都看到为止！

作者: kekonglin 时间: 2010-9-11 12:00
我基本上是采用看英语文章的办法，先泛读，再精读，再一句一句看，最后再提纲挈领，总算是明白一点了，当然，也可能还是领悟错了。最后要说的一句话是：楼主，你很牛叉，希望你不是真的有病。

作者: wbj 时间: 2010-9-11 15:01
哦～～

作者: lsrj 时间: 2010-9-11 20:00
我来了~~~~~~~~~ 闪人~~~~~~~~~~~~~~~~

作者: zhyqmn 时间: 2010-9-12 15:02
楼主的帖子实在是写得太好了。可是我立刻想到，这么好的帖子，倘若别人看不到，那么不是浪费楼主的心血吗？经过痛苦的思想斗争，我终于下定决心，牺牲小我，奉献大我。我要拿出这帖子奉献给世人赏阅，我要把这个帖子一直往上顶，往上顶！顶到所有人都看到为止！

作者: xqsf 时间: 2010-9-12 20:00
楼主的帖子实在是写得太好了。可是我立刻想到，这么好的帖子，倘若别人看不到，那么不是浪费楼主的心血吗？经过痛苦的思想斗争，我终于下定决心，牺牲小我，奉献大我。我要拿出这帖子奉献给世人赏阅，我要把这个帖子一直往上顶，往上顶！顶到所有人都看到为止！

作者: liwenhong 时间: 2010-9-13 15:00
楼主，你写得实在是太好了。我惟一能做的，就只有把这个帖子顶上去这件事了

作者: Rainhart_Xu 时间: 2010-9-13 20:00
我来了~~~~~~~~~ 闪人~~~~~~~~~~~~~~~~

作者: watchor 时间: 2010-9-14 15:00
鉴定完毕！

作者: hoverchang 时间: 2010-9-14 20:00
鉴定完毕！

作者: dfhe060 时间: 2010-9-15 15:00
我基本上是采用看英语文章的办法，先泛读，再精读，再一句一句看，最后再提纲挈领，总算是明白一点了，当然，也可能还是领悟错了。最后要说的一句话是：楼主，你很牛叉，希望你不是真的有病。

作者: yks2006 时间: 2010-9-15 20:00
哦～～

作者: arthuryuan 时间: 2010-9-15 20:00
楼主的帖子实在是写得太好了。可是我立刻想到，这么好的帖子，倘若别人看不到，那么不是浪费楼主的心血吗？经过痛苦的思想斗争，我终于下定决心，牺牲小我，奉献大我。我要拿出这帖子奉献给世人赏阅，我要把这个帖子一直往上顶，往上顶！顶到所有人都看到为止！

作者: mlfyid 时间: 2010-9-16 15:00
我来了~~~~~~~~~ 闪人~~~~~~~~~~~~~~~~

作者: BESTQINGQING 时间: 2010-9-16 20:00
试试运气啦~~~~~~~~~~~

作者: qibbchyy 时间: 2010-9-17 17:23
全局优化的算法，可以考虑演化算法，这个一般的网站上都可以下载得到，尤其是谢菲尔德大学的和北卡罗来纳大学的

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)