实习小记

这个暑假基本上都花在我们DI的L3必修实习上了,只回家了两个星期多一点的时间,不过这个实习还是比较有趣而且有用的~~~

我是去南特做的实习,是关于SAT和WalkSAT的。SAT就是那个著名的NPC的可满足性问题,而WalkSAT是一个专门解SAT的Solver,用的是局部搜索的方法。我之前用过不少局部搜索的东西(比如说做优美树的时候),所以还是对这个题目比较感兴趣的。这次实习主要就是研究WalkSAT的各种参数对程序的性能有什么影响,这个也是局部搜索的老问题了,总是会遇到local minima出不来,所以就要各种各样的机制来逃出去,这样少不免就要牵涉到很多很多的参数之类的东西,而且这些参数对性能的影响非常大,每次写局部搜索的时候不仅要选取适当的heuristique,还要慢慢给参数调优,其实是相当麻烦的。我选这个实习也就是为了学学别人是怎么样解决参数调优的这个问题的,虽然不能直接应用,但是稍微借鉴一下经验估计也是没问题的~~~

这个实习的encardant有两个,一个女的一个男的。女encardant(以下简称CT)是在南特的,见得比较多,也基本上是她指导各种东西的;男的encardrant(以下简称FS)是在昂热的,所以见得比较少,对我这个实习的指导工作也比较少而且抽象。他们人都很好,很热情,在实习中也给了我很多很有用的建议和意见。

我是6月1号就去南特的。一开始情况相当困难,中午到的时候,住的地方没有人办公,都出去吃饭了,我却拉着一大堆行李没饭吃。然后等啊等,终于有人办公了,但是又遇上各种问题,于是就只能先去找CT报到,看看能不能说有些手续可以帮忙搞一下。然后经过各种非常复杂的手续之后,终于住进了CiteU。大学里边实习生的手续倒是很简单,或者说就是已经搞定了,拿了个badge就好了。实习工资不多,但是房租学校给,所以其实也还好,然后房间相当大,比ENS的大多了。

CT有一个博士生,叫Marie,也是女的,也是很好人,经常拉我去参加各种实验室的人一起去玩的活动,虽然显然我不一定很有兴趣,然后在实习里边也帮了不少各种事情,比如说revise报告之类的。

这个实习中我做的事情其实主要就是找WalkSAT的最好的参数组合。显然这些参数组合也是因实例而不同的,比如说随机的实例跟来自planning问题的实例,本来性质就不同,然后最优的参数组合也是不同的,我做的其实就是弄个算法,找到对不同的实例的最好的参数组合。基本上这些算法都需要解决实例,但是对比较小的实例得到的参数组合对比较大的实例也是有参考意义的,所以其实这样做还是reasonable的。

然后为了测量性能,我们就需要弄一个benchmark,但是因为有这么多种性质不同的实例,针对不同种类的实例,最优的参数组合也不同,所以如果要很好衡量一个参数组合的话,最好还是抽取一些有代表性的实例,然后用这些实例做benchmark。我的另一个工作就是想办法弄一个方法来将一堆实例好好分类,然后选出一些有代表性的实例。CT给的方法是选取一些statistic characteristic,然后算出来之后做一个k-means clustering,根据结果来分类然后选取有代表性的实例。

于是我就写了一个很简单的程序来算statistic characteristic,虽然很简单但是为了优化还是花了不少的功夫的。现在那东西就躺在我在ENS的网站上,其实估计也没啥用。这个东西的另一个功能就是自动做clustering,其实就是把别人某个开源的implementation稍稍改了一下然后而已,不是很复杂。

然后用这个工具我分析了SAT Competition 2007的所有实例,结果很悲剧,clustering做出来的结果跟实例的性质关系不是很大,所以那个有代表性的benchmark就浮云了。于是接下来找参数组合就只能随便做了。

找参数组合的算法,FS提议说用一个叫Revac的东西,但是那玩意儿要用matlab,然后我完全不懂……所以我就看了原始的论文,自己写了一个简化版本,基本上也是很简单的,几百行的样子。运行还是可以的,但是就是慢。

然后看着这个实习的主要内容做得差不多了,CT就给了我一篇Sermerjian和Monasson的文章,是用统计物理的方法来研究random SAT实例的。然后CT就让我去验证一下这个paper的一些结论。然后我做了一些,然后其实也有一两个发现。基本上做完这个就做完实习了。

然后就是写报告和弄presentation。报告花了我两个星期的时间。那个时间学校放假,然后我就躲在寝室里边有心情就写两段,断断续续的竟然也在两个星期内写完了。最后各种更改(我的法语还是一如既往地很多bug……)之后最终是36页。那个时间真是非常累啊……

其实南特风景很好,但是我因为实习很忙,其实基本上就没啥时间出去透气,当然我很宅这也是一个非常重要的因素。平时做饭因为只有一个人做,所以做的东西也很简单,天天不是煮意粉就是煮面,大部分时间外加煎猪排或者碎肉牛排,蔬菜大部分时间都是番茄,因为做起来容易。有时候也会去买点好吃的,不过不多,而且集中在实习最后很有空的时间。在实习的时间里边也没有做很多比较有建设性的东西,一方面是因为忙,另一方面是因为在松鼠会的工作遇到了一些很令人沮丧和状况。唯一有点创造性的东西就是那个水滴游戏的解程序,而且直到现在因为情况没怎么改变,所以暂时也没什么热情去写文章。

那个优美树的东西,我也去问了CT,从Constraint Programming的角度CT也给了不少的建议,虽然我觉得都是比较靠近于通用问题的思路,对于这种特殊性比较强的问题这种方法可能不是太好,不过还是可以考虑一下的。

然后前几天刚刚弄完presentation。本来我一开始做presentation的时候不知道需要多少时间,然后就随便做了做,看看要多少时间去讲,结果计时是差不多半个小时。但是CT给ENS这边的负责人发了信来问,结果发现一个人只有20分钟的时间,于是我就杯具了……最后做的时候只好一味地省略很多东西,然后才勉强在20分钟里边讲完。

其实这次实习收获还是很大的,虽然这个的性质基本上也就是implementation – observation,不是什么很有创造性的工作,不过起码也是有用的,而且也是很锻炼的。要说一开始的目的,其实也没有达到,因为本质上我现在用的方法也是差不多的,如果假定参数之间的相关性不高的话。不过也学了不少关于SAT的东西,还是很有趣的~~~

Advertisements

3 thoughts on “实习小记

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s