编程讨论第一贴：讨论97年A题的编程方法

路过 · 发表于 2003-6-30 04:09:07

dcyu算说到点子上去了，我不喜欢退火算法，就是因为参数没有选取规则。我没经验，不知道怎么取才好，结果退火算法的效果反而很差。

shihong8488 · 发表于 2003-6-30 06:07:23

我去年训练时做的一个题目灾情巡视问题（也不知是哪年的拉），用的就是SA算法，当初想到这样做也是偶然，我们图书馆好象有个《C语言实用编程》就有介绍。
当时，提出这个算法，同学们都吃了一惊，都没听说过。和我们练相同题目的计算机同学都用基本算法做的（大二下学期，他们都学了数据结构），也没听说过。

后来，在用google搜索，网上以有人参考我说的书，用SA算法做了一遍。

这次，我的一个朋友做毕设也用了这个算法……

这次比赛如果有类似题目，但愿还能用上，不过一般出现过的，以后不太可能再出现。

我去年就没遇上（去年做的是车灯，就因为迭代精度不够而与全国奖无缘，ft）.

路过 · 发表于 2003-6-30 06:34:03

so pity...

宇游游 · 发表于 2003-6-30 06:57:02

有时候就差那么一点点...
没关系,再来!

dcyu · 发表于 2003-6-30 09:35:41

好。能有这么多人来讨论。

其实模拟退火算法是一种寻找最优化解的一种算法，可以这样描述这种算法，有一个跳蚤在群峰中找寻最高的山峰，但是当它登上一个山峰的时候，并不一定说明它就找到了最高峰，但是对于我们来说，我们就要安排这只跳蚤来进行搜寻工作，找寻的山峰值与7个变量相关，还有不同容差等级这个离散的变量，因此目标函数是极为复杂的，所以跳蚤根本不可能知道其他地方还会不会有山峰存在，但是对于跳蚤而言，他知道的是每一次它到达的山的海拔，于是跳蚤准备采用这样一种方法，名曰：模拟退火法。以一定的概率向剃度方向跳去，而且选择另一剩余的概率向反方向跳去，这种概率的函数就是Bolzmann函数，保证了不会永远向更高的地方前进，它会选择下山的方式来寻找新的山峰，以保证去遍历所有可能的取值，因此最高的山峰就有可能在跳蚤的不断努力下被找到。这种方法是非常好的。但是有一个问题就是Bolzmann函数需要一些参数和跳蚤起跳的步长，步长过小，跳蚤可能会跳很久还没有出结果，甚至陷入局部最高点的境地，过大的话，可能会错过最优点，因此跳蚤自己都不知道怎样才能去安排自己的行进方式。所以我们就更加为难了，对于我们要做的就是只能去尝试，就是多放一些跳蚤，设置不同大小的跳蚤，大步长的跳蚤和小步长的跳蚤，观察跳蚤的尝试跳的结果，只需要在一定时间内观察就可以了，选择一个最好的跳蚤作为你实验的基础，然后进行模拟退火算法的实验。最后就会到达你想要的结果。对于一些优秀论文来说，一般都是说“我们取...为参数值”，事实上他们是已经进行过实验后才这样说的，所以并不表明他们选择参数有什么更高的预见性，只是他们更擅长与做数学实验而已。

shihong8488 · 发表于 2003-7-1 00:28:46

To 路过 &宇游游:
Thx.我会努力的,以后大家一起交流,争取搞个好成绩,呵呵……

To dcyu:

我也见过类似的解释方法,很形象……

Hughie · 发表于 2003-7-3 01:16:52

这道题的模拟退火算法实现,可以看看论文下载区6-26号上传的文章,效果还不错
不过既然matlab可以做的很好,为什么不用呢?

风之泪~ · 发表于 2003-7-3 06:06:58

大体看了看程序，好象写的很泛。

zcphil · 发表于 2003-8-20 04:51:50

你运行过了吗？好像要运行几个小时才有结果。
我觉得这个题最好用模拟退火法。

Haomiao · 发表于 2003-8-21 04:06:59

程序好像不对……

		自动登录	找回密码
密码			注-册-帐-号