数学建模社区-数学中国

标题: 请问各位大神模拟退火的新解的算法是不是任意都可以？ [打印本页]

作者: eskoslovens 时间: 2012-8-22 08:29
标题: 请问各位大神模拟退火的新解的算法是不是任意都可以？
还是说模拟退火的新解只能按某种特定模式，如交换逆转。。

作者: liwenhui 时间: 2012-8-22 16:56
应该是随意地产生都可以，但是从算法收敛的效率来看，最好是不要产生已经经历过的状态，类似于禁忌搜索，可以让算法更有效。

作者: eskoslovens 时间: 2012-8-23 14:30

liwenhui 发表于 2012-8-22 16:56
应该是随意地产生都可以，但是从算法收敛的效率来看，最好是不要产生已经经历过的状态，类似于禁忌搜索，可 ...

多谢。。那怎么学习算法啊

作者: liwenhui 时间: 2012-8-23 14:41

eskoslovens 发表于 2012-8-23 14:30
多谢。。那怎么学习算法啊

找相关的资料来看，可以先学习“随机搜索”“爬山法”方法，就是随机在定义域上产生大量自变量值，然后逐一比较，得到最大的，这种方法在目标函数是单峰状态时会收敛于全局最优值，而多峰目标函数收敛于局部最优。而SA方法就是在此基础上建立了新的“取舍”标准，即当某自变量的函数值不为局部最优时，并不是直接放弃，而是以一定概率选择保留它。在知道了SA的原理后，去找点别人编写的实例程序，模仿别人的思路，加以时日你就懂了。模仿是一名很不错的老师。

作者: 诡刺风影 时间: 2012-8-23 20:24
搜索的时候什么蚁群可以试试

作者: hao1 时间: 2012-8-24 08:16
不知道，不太熟悉

作者: eskoslovens 时间: 2012-8-24 22:39

liwenhui 发表于 2012-8-23 14:41
找相关的资料来看，可以先学习“随机搜索”“爬山法”方法，就是随机在定义域上产生大量自变量值，然后逐 ...

多谢了~

作者: eskoslovens 时间: 2012-8-24 22:56

liwenhui 发表于 2012-8-23 14:41
找相关的资料来看，可以先学习“随机搜索”“爬山法”方法，就是随机在定义域上产生大量自变量值，然后逐 ...

再请教一个问题，就是多个0-1变量的随机搜索怎么进行啊，怎么保证朝着最优解的方向进行搜索呢？

作者: liwenhui 时间: 2012-8-25 06:55

eskoslovens 发表于 2012-8-24 22:56
再请教一个问题，就是多个0-1变量的随机搜索怎么进行啊，怎么保证朝着最优解的方向进行搜索呢？

这可以看作一个组合优化问题来解决，如果使用随机搜索，就是随机组合这些变量中的0和1,看哪一个组合得到的结果最优。随机搜索不能保证收敛。

作者: eskoslovens 时间: 2012-8-25 19:52

liwenhui 发表于 2012-8-25 06:55
这可以看作一个组合优化问题来解决，如果使用随机搜索，就是随机组合这些变量中的0和1,看哪一个组合得到的 ...

那应该用什么搜索啊。。被这个困扰了。。

作者: liwenhui 时间: 2012-8-26 13:12

eskoslovens 发表于 2012-8-25 19:52
那应该用什么搜索啊。。被这个困扰了。。

可以用随机搜索，只不过得到的解不能保证是最优解。
用模拟退火得到的结果也不一定是全局最优的，但结果会比随机搜索好。
看你的问题具体情况
如果比较简单
简单0-1规划用lingo就解决（它内部的算法可能是单纯型迭代）
如果比较复杂，可以先考虑动态规划
还不行，你就用模拟退火/蚁群/遗传等

个人观点，能简单就尽量简单，不要过分可以去追求用高级的算法解答，实用就好。

作者: eskoslovens 时间: 2012-8-26 17:13

liwenhui 发表于 2012-8-26 13:12
可以用随机搜索，只不过得到的解不能保证是最优解。
用模拟退火得到的结果也不一定是全局最优的，但结果 ...

额。。我们上次的题目是51个变量的问题。。结果没办法就用的随机搜索，但是随机搜索会有重复情况出现，。。这是个纠结的问题。。。多谢你详细的解答~。

作者: liwenhui 时间: 2012-8-26 17:34

eskoslovens 发表于 2012-8-26 17:13
额。。我们上次的题目是51个变量的问题。。结果没办法就用的随机搜索，但是随机搜索会有重复情况出现，。 ...

51个变量不算太多。
可以用SA方法。
我记得在我们论坛哪里看到过SA的现成的MATLAB程序，你自己找一下吧。
不同的问题往往需要不同的程序，不过有部分程序是通用型，只需要修改输入参数就可以得到结果，还有部分程序就算不能直接调用，但可以把它作为你自己程序的子程序。当然明白其原理才是最终重要的。

作者: eskoslovens 时间: 2012-8-28 09:01

liwenhui 发表于 2012-8-26 17:34
51个变量不算太多。
可以用SA方法。
我记得在我们论坛哪里看到过SA的现成的MATLAB程序，你自己找一下吧 ...

嗯~好的~大神啊

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