分类目录归档:数学

美赛终于结束了

今年美赛分为两个批次,wk1,、2,第一周放出了A、D、E三个题,我们选择的是wk2,哎。

早上五点多就醒了,看到发题了赶紧打卡看题。初看B题,心里就否定了大半,B题有很多关于流体力学的内容,如何设计沙雕的形状和含水量,使得沙雕在海潮的冲击下坚持的时间最久,我已经三年没有碰过物理了。C题还是一个数据问题,分析电商购买评论打分数据,为卖家谋取最大利益,这种题类型还算中规中矩,我也比较熟悉,但是里面通篇几个问题都涉及到分析评论的语义,需要一些NLP知识,而我们三个人没有一个学过NLP的,所以C题也很快排除掉了。
剩下的F题是一个非常广泛的问题,我们需要先预测气候难民的数目和文化丧失的风险,然后设计政策,分析政策,这题太发散了,令我感觉就是:没有建模的门槛,建模的程度下限低,上限高。如果做得好,能设计出非常棒的模型,但是不会建模的话,也不太影响做题。

第一天的一上午我们三个分别看了三个题,研究C题思路,队友分别研究B、F。选题的过程非常艰难,我们本来打算12点之前选好题,然而12点过去了,我们还没有确定。

中午的时候我和一个队友大概的意向是F题,另一个队友的大概意向是B题。B题算是中规中矩的题,只要把核心的物理模型搭建出来,整个论文就稳在一个水平线上了,但问题就在于我们都3年没学过物理了。我考虑了一下,下午又花了大半的时间去研究流体力学、边坡稳定性这些物理问题,然而基础太过薄弱,费劲脑汁研究了一下午都没有研究出来,已经下午五点了。另外一个一直想选择B题的队友也没有弄通核心物理方法。我们很无奈,只能选择下限低上限高的F题来做了。

晚上又看了看F题,感觉已经凉凉了。我们花了一整天的时间来选题,而F题又是胡扯题,我们还是不太擅长胡扯的,当时大家都有点泄气,第二天也没有什么战斗意志,我感觉大家似乎都已经放弃了。
其实也是因为不在一起做题的原因,大家都被困在家里,很容易受到家里的各种干扰,而且不能很好的交流,有种一个人做题的感觉,这很容易让人产生放弃感。

第二天我们没做题,大概是都已经战略性放弃这次坑爹的赛题了。晚上十点的时候,队友在群里说再坚持一下吧,胡编乱遭交上去一个论文就行了。

于是我们最后两天就开始了胡编乱造的过程

首先是预测难民数目,难民的数目没有明确的统计,没法用传统的方法来预测,看到有人说时间序列,其实不靠谱,难民数目和海平面上升趋势以及人口都有很大的关系,仅仅用时间序列根据目前的难民数目来预测实在是不靠谱。不过我也没想到什么好的思路,我在网上找了一些数据,胡乱预测了一下,大概思路是这样的:先预测出未来海平面的上升趋势、未来人口增长趋势,然后根据人口地理分布算出低海平面人口,根据2000年到现在海平面已经上涨的高度带来的影响评估未来海平面上涨的影响。
后面就开始胡扯了,队友有AHP何信息论分析的文化丧失的风险和不同政策可能造成的信息loss,这里的信息可以看成文化。然后我们胡扯了点政策,论述了一下我们政策的好坏,最后我画了图拍了版就交上去了。

虽然这次很失败,但好歹我觉得,我画的图还是很好看的。比国赛的时候的图好看多了,这也算是一个进吧。虽然我们第一天一整天都在选题,第二天没做题但是这次比赛感觉倒还是比较轻松的。没有太大压力,可能是因为语文建模的缘故吧,我以前每次建模都要写代码最少200行,国赛的时候甚至最后交的代码都有三十多页,每次工作量都很大,反而这次我倒是只写了很少的代码,大部分的时间都在做图和排版、写文稿。
这次的图画的相较于国赛真的是有质的提升。

充分意识到自己很菜,还要继续努力学习。

初次使用MATLAB写遗传算法(2011B)

虽然之前已经接触过遗传算法了,但这还是第一次 真刀真枪的在MATLAB上面写,记录一下,以供参考

总的来说遗传算法是一个基于随机过程的算法,其目标是为了max或min一个目标函数的值,求解的过程不是严格的推导,而是类似于随机产生个体,筛选最优解,不断的迭代,以此达到求解最优值。下面对其思想和理论做一些我个人的理解

遗传算法是为了求解目标函数的最优值(max=f(x1,x2,…xn)),而目标函数的最优值通过参数x1 x2…xn控制,那么我们把x1 x2 … xn等每个参数都表示为一个基因,如此一来,我们就有了n个基因构成一组解,我们把这n个基因构成的一组解称为染色体,而许多染色体组成了种群,下面梳理一下:

  • 基因——参数
  • 染色体——解
  • 种群——一系列解

所以,我们的目标就是,找到一个最优的染色体,那么如何找到这个最优的染色体呢?下面就讲解一下流程

1.首先,我们初始化一组解,这最开始的一组解可以随机的生成

2.然后我们计算这一组解的适应度,适应度其实就是我们要max或min的函数转换成的,一般来说,一个染色体的适应度越高,那么他存活的几率最高,所以,如果我们的目标是max f(x1 … xn) 那么可以直接用目标函数求出的解作为适应度,如果目标是min的话,用其倒数。

3.筛选,找到适应度后,从这一代的种群里面筛选,采用随机的方法,把适应度不太好的解都随机地筛掉,选取出适应度比较好的解

4.杂交,随机的选择染色体进行杂交,杂交是如何来理解的呢,可以类似的理解为,参数的随机组合,比如说现在有一个染色体x1 x2 x3… xn=a1 a2 a3 … an 另外有一个染色体是b1 b2 b3 … bn 那么这两条染色体进行杂交,产生的结果可能是两个染色体的随机组合,a1 a2 b3 b4 ……,会有什么作用呢?这就要想一下遗传算法的总过程了,遗传算法会筛选出优秀的解,那么这些优秀的解里面的参数可能就是一些比较优秀的参数,这样让他们直接互换,互相杂交,就可能会把两个解的优秀基因融合在一起,这样就生成了一个更优的个体,这个更优的染色体就更可能被遗传下去,如此反复迭代,最终生成一个接近于最优的染色体。

5.变异,变异是随机的使解里面的基因产生变化,这样就可以产生新的基因以供筛选

6.如果迭代到一定代数,或达到一个比较稳定的值(连续n带没有发生变化),那么可以结束遗传算法,并从最后一代里面选取最优染色体作为整个算法最终的解。如果没有达到这个值,那么就把筛选、杂交、变异产生的新的一组解作为新的一代,然后返回第2步,对着新的一代重新进行筛选、杂交、变异,如此反复;

这就是遗传算法的大致过程了,上面也掺杂了很多个人的理解,下面解释一下贯穿整个算法的问题——如何用基因表示参数,用染色体表示解,答案就是编码

编码——把一组解编制为一串特色的编码,方式有很多。较为常用的是二进制编码、实数编码、符号编码,以二进制编码为例,我们知道一组解是由参数组成的,那么参数应该有对应的取值范围和取值粒度,我们把这些参数离散化,比如说x1取值范围是0-1,精确到小数点后3位,那么离散化之后x1的取值就是0、0.001、0.002、0.003、……0.999、1.0,一共有1001个可能的取值,那么我们用一个10位的二进制串表示这1001个可能的取值,00000000对应0 00000001对应0.001、0000000010对应0.002、……

解码——编码的逆过程

杂交和变异都在这些被编码过后的串上面进行,生成新一代的种群后,在进行下一次评估的时候,把种群里面的基因解码为参数,然后计算适应度

筛选也有多种筛选方法,通常来说,各个方法基本都是筛选出适应度较大的解,可以通过随机选择个体比较、直接排序筛选、轮盘筛选等方法

杂交也有很多不同的方法,不过大同小异,基本上都是选择染色体上面的区间,两个染色体交换区间里面的内容

变异也有很大不同的方法,某个基因的某个位置变异、局部顺序颠倒等,变异的目的是为了基因的多样性,所以选择如何变异影响不大,主要是变异的概率,如果变异概率太高,那么优良基因很可能会遭到破坏,如果变异概率过低,种群多样性下降太快,要选取一个合适的值,一般可以取0.001·0.2

下面以2011B实操一下:

待补充……

数学建模培训第一天——2016国赛B题

培训第一天,来新校区上课挺不方便的,在路上的时间就得一小时,不过还好,上午一直在讨论2016数模B题,倒也没困,中午在图书馆写ACM,感觉挺好的,就是没开空调有点热。

先占个坑,晚上回去补充今天讨论的结果,下午再讨论一下,看几篇参考论文

记录一个简单否定的问题

从一个简单的问题记录命题的否定

命题的否定其实是对命题结果的真值进行取翻,一般流传的”只改结论”描述的并不全面

eg.“小李和小王学习努力”的否定。如果只改结论很容易就变成”小李和小王学习不努力”,但是显然这个题应该是”小李学习不努力或小王学习不努力”

怎么搞得?

假设P:小李学习努力 Q:小王学习努力

则原命题是P^Q

则命题的否定应该是-(P^Q)  ps:真值取反

即(-P v-Q)

 

 

也可以从量词的角度,设Q(x):x学习努力,论域是小李和小王

原命题就是V x Q(x)

这个命题的否定即为-VxQ(x)=Ex-Q(x)即存在一个x学习不努力,即小李或小王学习不努力。