9月12日参加了为期三天的数学建模比赛,总想写点什么纪念大学第一次通宵。虽然结果似乎有点崩,但是感觉非常有意思~就记录一下这三天我的酱油经历~

第一天

我们的进度其实在第一天是蛮快的,很快确定了题目,以及方法,第一天蛮成功的。

上午~~确定题目

9月12日上午7点我早早到了队友借的会议室里,刷着各个出题页面等着题目,大概7点45分左右就拿到了题目。A题是嫦娥三号软着陆问题,B题是一个奇葩桌子的设计问题。

乍一看B题不仅题目短,附件也少,看起来非常友好的样子。但是仔细看看题目,他需要画好多动态图,我们三个人没有一个会画的,而且似乎受力分析也是十分的困难,看上去有种无从下手的感觉。反观A题,虽然附件很多,但是起码还有点思路,知道怎么算一些东西,所以只过了一个小时我们就决定了要做A题。

这个时候一上午已经这样过去了,既然决定了题目,那么我们就开始了工作。首先去了图书馆,把各种A,B分区都逛了一遍,借了13本书,虽然最后都没怎么看,但是心里总归有一种安定感。_(:3」∠)_把书搬回微电子学院,然后下午就开始了各种学习。看到了好多对于月球软着陆的动力下降段,也就是主减速段的轨迹优化的论文,有打靶法,蚁群算法,遗传算法,直接数学计算法等等各种方法。这个题目最大的好处就是第一问有好多论文可以用来参考,不至于完全没有思路。

下午~~主减速段轨迹优化算法敲定

最终我们觉得用蚁群算法是比较轻松的方法其实是个深坑,首先是因为有一篇讲用蚁群算法解决月球软着陆轨迹优化的论文写的挺清楚的,然后就是蚁群算法是一个仿真算法嘛,不用什么厉害的数学姿势,写起来也会轻松一点。于是我来负责蚁群算法的实现,队友开始继续往下做。于是我就陷入蚁群算法的坑中不能自拔了。

首先我们需要解决的是一个多元连续函数最优化的问题,蚁群算法处理连续的问题,首先需要把问题离散化,本身设了推力大小,推力方向角,和时间三个变量,把一个连续的过程离散化为10个阶段后,推力大小,推力方向角分别被离散化为10个变量。然后蚁群算法处理十进制的问题还需要逐位处理,于是三个不知道函数关系的连续变量,要使用蚁群算法解决,就要变成大概60多个决策变量。

一个下午大概就是在找现成的算法,然后自己做些改动,熟悉了蚁群算法的基本知识。但是也没有太大的进展,主要是这个算法中的信息素更新啊,局部信息素更新啊,这些东西也不是很好理解,还是花了一些时间的。

晚上~~战蚁群

这个时候队友已经积累了很多姿势,对于避障也有了认识,开始往下做,我还卡在蚁群。不得不说这个matlab语言是有点难用,代码感觉好丑陋。虽然画图很方便,但是总感觉有点点别扭,似乎哪里不太对。点乘与乘傻傻分不清楚,也是因为这些原因的共同作用导致我第一天可以称得上是毫无输出,完全就是坑队友。

这时候蚁群算法的雏形已经打出来了,只是只能解决变量无界限的问题,肯定对我们的这次要求是不符合的,考虑了一晚上应该如何让算法可以设置变量的界限,最终还是在回寝室的路上,被队友提醒才想到,可以用线性放缩的方式把没有约束的变量放缩到变量的约束界限之中,瞬间感觉前途光明。

第二天

第二天是印象中很模糊的一天,做了些啥有点记不清楚了,但是似乎主题还是在战蚁群,似乎是崩掉的一天。

上午~~奖惩分明战蚁群

本着不能坑队友的心态,我又是7点到了微电子,然后开始战蚁群,首先把昨晚的放缩先用上,解决了变量的上下界问题,然后就遇到了新的问题,不知道应该如何把动力学公式的约束条件加入到蚁群算法中,论文也没给出他的方式。最终是搞明白可以用罚函数的方式,把约束写进评价函数中作为一部分影响评价的因素进行考虑。其实想想这样子一点都不严谨,从评价函数来看,就算评价函数达到最大值,也不代表是最优解,当然只是个三天的比赛,就别想太多了。

下午~~强人所难战蚁群

下午基本来说,所有的实现都已经完成了,到了收获的季节。但是很悲剧,事实证明结果根本不可能收敛。想想也是,一共1000只蚂蚁,让人家探索这么多可能性,简直就是强蚂蚁所难。但是当时我并没有察觉出是变量太多的原因导致不能收敛,我一直在怀疑是我的动力学方程的约束写错了,于是一遍一遍地推导,自然是徒劳无功的。一个下午就费在这里了。

晚上~~另辟蹊径战蚁群

不收敛,意味着每次运行,结果都是不一样的,而且基本来说会相差很远。但是不收敛并不是算法的问题,而是迭代次数太少,蚂蚁太少。但是时间上,如果提高迭代次数,或者说蚂蚁数,那么会有非常可怕的提高。所以这算法写是写出来了,但是毫无意义,因为没有时间迭代那么多次。

于是,我们就只能考虑简化模型,降低决策变量的个数。首先是假设云推力,结果还是不理想,最后连方向角和时间的关系也假设成线性,倒是取得了勉强可以用的结果,而代价是胡乱假设,毫无依据。

最后我们得到了一张轨迹图,就是这样。

轨迹图
主减速段轨迹

第三天

到了第三天,基本也就到了该写论文/*弃疗*/的阶段了。因为我整个三天唯一一点贡献就是一个勉强能用的蚁群算法,还不带推广价值,只能解决主减速段的问题,所以实在是有点对不起队友。而队友确实十分给力,他们做的是有模有样,要是我可以写出比较完美的蚁群算法,想必这一次我们应该会有不错的收获/*奖项*/,但是确实十分苦恼,到最后也没有写出一个靠谱的算法,导致后面的对于其他阶段的计算也是没有办法进行下去,有点忧伤。

这一天我们是通宵在赶论文,三个人都是从八点集合,一直写到第二天的七点中,除了吃饭,就是在不断地计算,写论文。而且我在这个时候真是有点着急,一直担心论文写不完,所以一直在催促队友,先放弃手头的计算,全力写论文。这种着急也是有原因的,在学院里赶DeadLine赶多了也赶出经验了,很多时候我们都是喜欢对进度抱有盲目的乐观,认为一切都来得及,就比如说两天后要交的暑假大作业/*_(:3」∠)_*/,但是其实时间已经不容许你在做过多的幻想和优化了。我觉得有一个漂亮的论文在这个时候才是最有用的。但是队友也是个强迫症/*ORZ*/,最后还是非常钟情于计算,我们也是在各种强行假设的前提下完成了所有问题,有点醉了。

这次参加这个比赛收获挺多的,认识了两个非常靠谱的队友,学习了新姿势,掌握了新技巧。不过很遗憾的是我坑了队友,花了两天实现一个算法,还是实现的不完美,存在很多问题,而且在拿到队友的需求的时候总觉得这个要求是没有办法实现的,现在想想,有些时候是自己考虑的太少,一些明明可以实现可以优化的地方,没有做出来,自己也是有点愧疚- -在以后估计很难有这种机会了,三个人能够为了一个共同的目标,一起疲劳作战三天,一起讨论,一起计算,一起写论文,真是一个非常让人难忘的经历。感觉拿出三天来参加这样一个比赛,挺值得的,除了价钱坑了一点。那么就是这样~

本来还想对队友说一声抱歉的,但是估计队友也都看不到,那就默默放在心里吧Orz

后续 2014-11-14

=-=最后的结果还是有点出人意料的,竟然得了上海赛区的一等奖!有点难以置信,看标准的解法的时候似乎有很多的因素都没有考虑进去,又多考虑了不少不需要考虑的因素。由此看来可能评定奖项的时候没有完全按照那个来判吧~我们组的主要亮点是在避障阶段吧,之后又去看了一遍提交的论文,感觉刘做的确实非常有道理,而且图文并茂,估计能得奖就是因为这个。

最后,还是很纠结为何我的蚁群算法不能收敛,直到现在我还是一直在改进那部分的代码,还是得不到一个收敛的解,问题已经简化地有些扭曲变形了,还是不收敛。曾经试着让代码跑了两次平均时长为20小时左右的测试,最后两次的结果也是有差距。感觉这是算法上的事情了,希望能有标准论文用到这种方法,然后能看看到底十进制蚁群算法应该怎么写。

一直在想,要是当初能写出来这个算法,是不是就国奖了~这么一想,锅似乎更大了。

后续的后续 2014-11-23

=-=最后的最后,去中国大学生在线找了几篇官方发的文章,就在这里。。。。确实不是我想找茬,但是有的组也太tricky了。

本来是想去找找跟自己用相同算法的得奖文章,看看他们的代码是怎么实现的,毕竟自己在这个算法上花了三天的时间还是不能收敛,心中对这算法的正确性充满了疑惑。后来找到了跟我们方法类似的队伍,他们用的是模拟退火算法,跟我们一样都是属于仿真算法。

结果去看他们的源码,真是令人气愤

嗯,模拟退火是用Java写的,一开始就有点疑惑了。比赛只有三天,却选择用Java来实现算法,好吧可能他们组负责算法的也是跟我一样,不太会MatLab这些语言。但是看源码,感觉相当无奈。

嗯,模拟退火算法写了450行左右,虽然长,不过有注释,虽然注释在我这边是乱码,估计又是Mac的编码问题,硬着头皮读下去。说实话,真是读不懂,看别人的代码简直就是煎熬。后来打算先看Main函数,后来发现了,令我感到智商被碾压的事实。

嗯,估计很多人都会想到了,输出大法好。他们组首先定义了很多常量数组,这些常量数组里,有一个是乱序的。然后Main函数的作用,就是把那个乱序的数组Sort一下,然后挨个输出已定义好的数组,这简直是我见过的最Tricky的Cheating方式。

然后这篇文章成为了优秀论文,放在了网上供下载。

感觉不做化简,降低变量个数,直接仿真的算法,在这道题目上想得到一个收敛的结果,根本是不太可能的。原本以为会在优秀论文里得到一个靠谱的实现,结果得到的。。。。

如果你想自己看看,他们Tricky的实现方式,请联系我。。

评论