能力篇——信息搜索能力和信息整理能力

这里的能力主要包括搜索引擎的使用,文献数据库的使用,文献的管理

希望能借此机会将自己的搜索能力和技巧提升一个档次。这里主要是通过视频进行学习,视频资源网址如下:http://www.cnmooc.org/portal/course/27/1436.mooc

我的笔记如下:学习笔记

遗传算法

遗传算法(Genetic Algorithms,GA),是现代智能算法中的一种,也是用于求解优化问题的常用方法,它是一种基于自然选择原理和自然遗传机制的搜索算法。关于遗传算法网上的资料比较多,我推荐大家可以看看这几篇,就对遗传算法理解大概了。

如何通俗易懂地解释遗传算法?有什么例子?

遗传算法入门到掌握(一)

算法原理

我先画一下图帮助大家理解这个算法:

就是在所有的解中,将当先的解集向 最优解不断靠拢。

就是通过两个较好的解得到更好的解,集优。其实具体原理的理解就是如何实现上面所说的集优,这里的每个解相当于染色体,每个解可以转化成其他的表示方式,变成二进制或者用其他实数来表示,从而这个解就转变成一个可以知晓具体基因的染色体。这就是算法研究对象的转化,将解转化成一个可以知晓具体基因的染色体。这个过程叫作编码,这之后就是模拟自然选择,和自然遗传这两类实现基因优化的主要步骤。自然选择,在这里的实现主要就是对当前小解集,也就是当前群体,实现择优选择,就是依照适应函数(目标函数)计算出适应度,其中适应度较高的个体,繁殖下一代的数目较多。而适应度较小的个体,繁殖下一代的数目较少;甚至被淘汰。然后实现的是自然遗传也就是进行下一代的繁殖,也就是计算出更优秀的子代。主要这里分为交叉操作和变异操作。其中的变异操作是为了防止解集陷于局部最优解。然后就是不断不断筛选不断集优。从而满足终止条件。

算法的具体步骤:

这里用的是求解组合优化进行算法步骤的详细讲解,题目还是之前讲解退火算法的例子

1.编码策略:

实现转化,主要有两类,一类是实数编码,一类是二进制编码,二进制编码,就是用0,1表示,实数编码主要用[0,1]间的小数表示。从而为之后的交叉操作,变异操作做准备。对于这个问题,采用的只能是实数编码,因为这里的染色体也是就是解是组合数组,所以染色体采用的是用一组的小数表示,每个小数表示的一个基因,如果这里的解是就单是一个数字,则用二进制编码,其中的每一位二进制表示一个基因。

2.初始化种群:

主要就是尽量求出一个较好的初始解集,这个讲解用改良圈算法计算初始种群。改良圈算法是经典的近似算法。其实这里原理与退火算法中的新解产生是一样的。具体的解法之后补充。因为怕理解的不够详细误导大家,先留白,之后会好好研究。

3.确定目标函数

也就是求解适应度函数,这里的函数就是每个方案中飞机飞行的路长

4.交叉操作

就是产生优秀的子代的阶段。主要产生方式是单点交叉,还有其他的产生方式,单点交叉就是将一条链前t个基因与另外一条链的前t个基因交换从而得到两条新的。深层次的原理,应该就像显隐性基因一样,假设父母链为相对较好的Aa,那么他们产生的子链,刚回是将父母链中的A与a的基因分解开,则会产生AA与aa,这种情况,则就出现了更优解,一个多吸收了a,使另外的一个多得A,实现了集优,这个是个人猜想,大家有什么其他的想法可以在下面讨论。

5.变异操作

就是将基因进行随机调整,从而避免陷入局部最优解。

6.选择

就是依照上面的目标函数进行筛选。不断循环最终达到最优解。

代码工具:

1.软件:matlab

可以用网上别人编好的代码。这个还是比较多的。代入参数就能进行求值。

2.软件:matlab

可以利用matlab的工具箱,这个比较方便。

 

1)写函数文件保存到工程路径下。

2)>>optimtool%打开工具箱

3)选择算法ga Genetic-Algorithms选择输入 变量个数(Number of variables) 和 自变量定义域(Bounds) 的值,点击 Start,遗传算法就跑起来了。最终在输出框中可以看到函数的(近似)最小值,和达到这一程度的迭代次数(Current iteration)和最终自变量的值(Final point)

具体的教程大家去查看。特别推崇第三种方法,当然还是用1stOpt的。

3.软件:1stOpt

用这个做一下知乎上第二个回答的

求解函数 f(x) = x + 10*sin(5*x) + 7*cos(4*x) 在区间[0,9]的最大值。

Parameter x[0,9];
MinFunction -x-10*sin(5*x)-7*cos(4*x);

哈哈,爽死了。

====== 结果 ======

迭代数: 477
计算用时(时:分:秒:毫秒): 00:00:00:110
计算中止原因: 达到收敛判定标准
优化算法: 遗传算法
函数表达式: -x-10*sin(5*x)-7*cos(4*x)
目标函数值(最小): -24.8553625162905
x: 7.8567

====== 计算结束 ======

哈哈,这玩意真带劲!!!

 

 

 

 

 

 

 

1stOpt

1stOpt(First Optimization)一套数学优化分析综合工具软件包。在非线性回归曲线拟合,非线性复杂工程模型参数估算求解等领域傲视群雄,首屈一指,居世界领先地位。除去简单易用的界面,其计算核心是基于七维高科有限公司科研人员数十年的革命性研究成果【通用全局优化算法】(Universal Global Optimization – UGO),该算法之最大特点是克服了当今世界上在优化计算领域中使用迭代法必须给出合适初始值的难题,即用户勿需给出参数初始值,而由1stOpt随机给出,通过其独特的全局优化算法,最终找出最优解。以非线性回归为例,目前世界上在该领域最有名的软件工具包诸如OriginPro,Matlab,SAS,SPSS,DataFit,GraphPad,TableCurve2D,TableCurve3D等,均需用户提供适当的参数初始值以便计算能够收敛并找到最优解。如果设定的参数初始值不当则计算难以收敛,其结果是无法求得正确结果。而在实际应用当中,对大多数用户来说,给出(猜出)恰当的初始值是件相当困难的事,特别是在参数量较多的情况下,更无异于是场噩梦。而1stOpt凭借其超强的寻优,容错能力,在大多数情况下(大于90%),从任一随机初始值开始,都能求得正确结果。
这是在百度百科上的说明,大家想详细了解可以去看一下。
关于软件的下载,这个需要大家自己去查找了,毕竟大家搞建模,搜东西的能力应该还是杠杠的,哈哈。

 

1stOpt的教程,里面有不少案例大家可以参照练习,如果有空。我个人觉得还是解题驱动学习比较方便,因为这些东西在平时不是常用的,容易忘记,所以当你需要时,再去学习我觉得还是挺省时的做法。

教程学习

用例一(麦夸特法)这里的function表示的最小二乘中的基础表达式

 
a,b,c; 
Variable t,l; 
Function 
l=c/tan(arcsin(cos(a*pi/180)*cos((t-(120-b)/15-12)*15*pi/180)*cos(10.9813*p
i/180)+sin(a*pi/180)*sin(pi/180*10.9813))); 
Data; 
14.7 1.149625826 
14.75 1.182198976 
14.8 1.215296955 
14.85 1.249051052 
14.9 1.28319534 
14.95 1.317993149 
15 1.353364049 
15.05 1.389387091 
15.1 1.426152856 
15.15 1.463399853 
15.2 1.501481622 
15.25 1.540231817 
15.3 1.579853316 
15.35 1.620144515 
15.4 1.661270613 
15.45 1.703290633 
15.5 1.74620591 
15.55 1.790050915 
15.6 1.835014272 
15.65 1.880875001 
15.7 1.927918447
 用例二(遗传算法)似乎必须要写x的范围,对于实际问题可以先推测一个大概
这里的MinFunction 表示的目标表达式。
Parameter x[0,9];
MinFunction -x-10*sin(5*x)-7*cos(4*x);

2015国赛A题(2)

今天学习的论文为:太阳影子定位优秀论文(2)

这篇论文内容简明,思路清晰。这篇论文主要用到的方法是麦夸特法,实现的参数拟合,论文整体的解题思路,是根据物理公式建立影子长度得模型,主要利用太阳高度角,经纬度,日期,时间,杆长,时角这些因素建立的,也就得到了,第一问,然后对问题二,三,四的处理,就是将第一问得到的等式,相关参数设为未知,根据麦夸特法,得到各类参数,其中问题四是matlab自己得到数据的。另外在这篇论文中发现了一个求解非线性优化问题的大利器,1stOpt,这个用了一下感觉,贼爽,不需要去找matlab的代码,开心。

继续阅读2015国赛A题(2)

2015国赛A题(1)

这是今天参考学习的论文:太阳影子定位优秀论文(1)

刚刚研究的一篇再后来研究时,发现好像存在一些问题,大家慢慢看看。这次的研究会包含一些算法的研究,可以看数模算法那一章的模拟退火算法

这次的问题主要包含4问,介于今天只对前两问看看,现在就先写这两问的思路和感悟

建模的前提假设都依据论文中的提及的,考虑的因素也是文中所述。

建模的背景,其实是建模的第一个难关,在拿到竞赛题到竞赛结束这几天,需要对一个你不曾接触过领域的核心,有基础认识,才能在短时间内进行建模。在本文中,需要了解的天文地理方面术语有太阳赤纬,地理纬度,太阳高度角,时角,地方时,北京时间。

查了不少资料对它们的理解还是有些模棱两可。本来想将我的理解告诉大家的,不过考虑可能会误人子弟,在这种正经事上还是不瞎bb了。大家自己查看,其实概念有些不清在接下来思路的理解上也没有什么问题。

第一问:

需要处理的问题:在给定经纬度,日期,杆子高度等情况下描述出杆子影子的变化曲线

解决思路:如下图就是求出L的变化曲线,而h是已知一根3m的直杆

问题的关键就是求解出H角的高度,H角就是太阳高度角,如何求解H角的求解公式,可以通过公式查找 (由于还未掌握其中的公式编译器所以无奈截图)

其中的一些其他变量可以对照符号说明和下面的图了解

其中变量大部分是需要求解得,

1.是时角,是由地方时 t 决定的而地方时可以通过来计算其中的T表示的是120度的北京时间,这里是我唯一之前知道的地理知识(欲哭无泪)。(从这个式子我们也可以推知的意义,是直射点与测试地点的偏移角度)

2.是赤纬,是与天数N有关的,这里的N是从1月1号开始计算的。

3.是纬度,而是经度,(这里就出问题了文中对H求了一下反函数就就将经纬调换了,不知道是谁的问题)通过下面的表述这里是纬度

最终结果,并没有代入这样比较清爽,当是我觉得两类都应该写下防止到时候找不到

在有了如上的公式准备之后就能求解出第一问,再利用matlab进行图像描绘。为了能够真实的实现,我把matlab的代码敲下来了,为了以后编程需要。

function T1(a,b,n,h1,t)
%a 纬度 b 经度 n天数 h1杆高度 t北京时间
%求出太阳高度角并画出影子的长度
d=2*pi*(n-1)/365;
c=0.0069180.399912*cos(d)+0.070257*sin(d)...
 -0.006758*cos(2*d)+0.000907*sin(2*d)...
 -0.002697*cos(3*d)+0.00148*sin(3*d);
t1=abs(b-120)/15+t;
t2=(t1-12)*15/180*pi;
h=asin(sin(a/180*pi)*sin(c)+cos(a/180*pi)*cos(c)*cos(t2));
h2=h1/tan(h)
plot(t,h2);
%figure(2);plot(t,180/pi*h);

end

思考:这一题所用到的东西,基本上还是别人已经写好的数学模型也就是那些物理公式,我们在最开始时,就要能够不断的搜集与赛题相关的知识,这个阶段其实也是弄清楚背景知识的阶段。这是个很重要的阶段,也为接下来建立自己的模型打好基础

第二问:

问题是根据影子在地上的坐标变化,确定直杆所处的经纬度。就是建立基于影子坐反求地点模型。

建模思路:这里引入了太阳方位角(关于太阳方位角这应不算基本知识储备,因为其他论文中没有出现过应该是他们在建模时查看到的相关论文的论文成果,是踩别人肩膀上的值得我们学习)。论文中还用到了很多技巧,比如其中的数据处理,利用相对运动的原理,简化模型。另外这里还用到了退火算法,今天查了不少资料,不过在论文中的应用,还不明确有些无法理解。等之后将退火算法研究再透彻些,写完算法章中的退火算法再细讲。

继续阅读2015国赛A题(1)

麦夸特法

Levenberg-Marquardt(LM)算法是一种迭代技术,其定位表示为非线性函数的平方和的函数的最小值。它已经成为非线性最小二乘问题的标准技术,可以被认为是最快下降与高斯牛顿法的组合。主要就是用来求解非线性最小二乘问题。

在了解麦夸特法的过程中,发现还有一些与它相关的其他算法,为了说明我画了下图进行说明算法间的关系

这些算法都在求解非线性问题的优化中常用的算法。

牛顿法,一般用在解决非线性中的求零点和求极值,(求极值其实也是优化问题,求出最为合适的解),并且适用的范围是在变量较少的情况下。为了解决高维非线方程中的最小二乘问题,在牛顿法的基础进行了修改,有了高斯牛顿法,但是却有缺陷,另外梯度下降法在用在这里的最小二乘法也有自己的缺陷。为此,就有了在高斯牛顿法的基础上修改的麦夸特法。下面关于具体原理,我会一一说明。

算法原理

非线性问题的处理思路都是将非线性的转化成线性的,主要有两类算法,一类是搜索算法,一类是这里的迭代算法。(算法的分类是有些模糊的,这个大家不必在意)另外关于各类概念的说明,防止大家搞得太乱,我会详细说明的。

大家可以先看一下一些博客:

谈谈自己对线性最小二乘和非线性最小二乘之间关系的理解~

Jacobian矩阵和Hessian矩阵

最小二乘法:一般是在进行数据拟合,对结果进行评估的一种方式,一般是通过将测量值与实际值作差求平方再求和。

雅克比矩阵(Jacobian矩阵):类似于多元函数的一阶导组成的矩阵。

海森矩阵(Hessian矩阵) :类似于多元函数的二阶导组成的矩阵。

 

先看一下

1.牛顿法

主要用于解决的问题有低维非线性函数的求零点和求极值的问题。

1.求零点

主要是先将目标函数在某一可可微点处x0进行一阶泰勒展开,忽略高阶,令展开式=0,求解出x1,此时得到的x1并不是目标函数的零点,但是确实一个比x0更加接近零点的点,因此就不免想到多次迭代从而达到零点处。

2.求极值点

求目标函数的极值点,其实就是对目标函数的一阶导求零点。这里可以通过对目标函数的二阶泰勒展开式求值,来实现原理同上,不断迭代从而找到满足条件的点。

Jacobian矩阵和Hessian矩阵中有关于牛顿法更为详细的说明。

2.高斯牛顿法

高斯牛顿法正是用于解决非线性最小二乘问题,达到数据拟合、参数估计和函数估计的目的。

主要的在牛顿的法上的改变是将迭代公式,也就是求解下个点的公式的处理,由于在高维的情况下,迭代公式中的海森矩阵是极其复杂的,因此高斯牛顿法中舍弃黑森矩阵的二阶偏导数,将海森矩阵用雅克比矩阵进行表示。

具体的表达式可以看

Gauss-Newton算法学习

【math】梯度下降法(梯度下降法,牛顿法,高斯牛顿法,Levenberg-Marquardt算法)

高斯牛顿法

3.麦夸特法

麦夸特法又称为阻尼因子法,是在高斯牛顿法的基础上进行的,对迭代式的调整,主要就是添加了阻尼因子,从而对高斯牛顿法进行完善。

Levenberg-Marquardt方法的好处在于可以调节:

如果下降太快,使用较小的λ,使之更接近高斯牛顿法

如果下降太慢,使用较大的λ,使之更接近梯度下降法

这里有一篇英文的文档是对麦夸特法的具体阐述,有能力的可以看看

麦夸特法.pdf

以上是对原理的大概讲解

接下来就是代码工具:

代码工具:

麦夸特法:
  1. %% 函数功能:利用Levenberg_Marquardt算法求解无约束的非线性最小二乘问题
  2. function [x_curr, iter] = Levenberg_Marquardt(Diff, f, var, x0, lamda, beita, eps)
  3.     % 相关参数
  4.     max_iter    = 100;
  5.     flag        = 1;
  6.     x_curr      = x0;
  7.     for iter = 1 : max_iter
  8.         if flag
  9.             J   = double(subs(jacobian(Diff, var), var, x_curr));      % 雅可比矩阵
  10.             H   = transpose(J) * J;                                    % 赫森矩阵
  11.             if iter == 1
  12.                 f_curr = double(subs(f, var, x_curr));
  13.             end
  14.         end
  15.         % 计算新Hessen矩阵
  16.         H_new = H + (lamda * eye(2, 2));
  17.         % 计算步长d
  18.         diff = double(subs(Diff, var, x_curr));
  19.         d    = inv(H_new) * (J’ * diff);
  20.         % 更新参数
  21.         x_new = x_curr – d;
  22.         % 计算新函数值
  23.         f_new = double(subs(f, var, x_new));
  24.         if f_new < f_curr
  25.             % 收敛条件(左侧分支)
  26.             x_curr = x_new;
  27.             if (norm(d) < eps)
  28.                 disp(‘收敛条件1’)
  29.                 break;
  30.             end
  31.             f_curr = f_new;
  32.             flag = 1;
  33.             lamda = lamda / beita;
  34.         else
  35.             % 收敛条件(右侧分支)
  36.             if (norm(d) < eps)
  37.                 disp(‘收敛条件2’)
  38.                 break;
  39.             end
  40.             flag = 0;
  41.             lamda = lamda * beita;
  42.         end
  43.     end
  44. end

其他的代码以后再积累补充

 

接下来就是最关键的部分了

算法的应用

 

 

模拟退火算法

对于退火算法,查了不少资料,大概清楚了基本原理,并带有例题进行讲解

模拟退火算法,是现代优化算法的一种,主要是用于解决组合优化问题,求解出全局最优解,就是求解在众多解中能满足目标函数式的解。

算法基本原理:

大家可以先看一下如下的两个博客

 

1.大白话解析模拟退火算法

2.模拟退火算法

这里他们从爬山算法开始介绍,写出爬山算法的局限性,只能查找到局部最优,然后再拓展到退火算法,引出在进行选择时,可以按照一定概率选择有潜在价值的不是局部最优的选择。另外他们的伪代码中都有一个问题Y(i+1)=Y(i);也就是状态跳转的语句有问题。

3.模拟退火算法中的退火策略研究

这篇论文是讲解退火算法中关于T=T*a也就是a的变化率的探讨,可以让大家更加了解退火算法的含义

 

以飞机侦察目标地最终返回的旅行商问题,退火算法只要分为以下几步

问题描述:我方的一架飞机从基地起飞,要侦察附近区域的100个目标地,并返回到基地,不考虑在目标地上的侦察时间,求解出飞机花费的最少时间,并且确定侦察路线。

1.解空间的确立

在固定起点终点,也就是基地的基础上,确定飞行方案,这里的100!种选择,这也是解空间

2.确立初始解

也就是从哪个点入手,开始进行退火操作,这里可以用蒙特卡洛法确立合适的初始解,关于蒙特卡洛法会在影子技术结束后补充学习

3.构造目标函数

就是表示出侦察路线的总长度

4.迭代

也就是在这是对方案不断进行选择,和对选择方法进行适当修正

4.1 新解产生

就是在当前方案的情况下,进行一些微调整,产生出一个新的解,也就是一个马尔代夫过程,马尔代夫过程是现在这个状态完全依赖于前一个状态,和之前的起始状态,或其他状态无关

4.2  比较这两个方案

作差,或依据做的微调简化处理进行作差

4.3  接受准则

就是做出选择,如果新的方案用时更少,就选择新的方案 如果不是就需要进行潜能的判断,潜能这个词是我自己编的,哈哈,具体的判断方法就是将           exp(-f/T)与[0,1]间的随机数比较大于等于时接受

4.4  降温

因为每一次都是越接近最优值的,所以对于T需要改变进行降温从而更加稳定不会再那么轻易选择那些看不清的潜能了,具体的降温就是将T=a*T,a一般都是在0.95左右

5.结束

迭代的终止条件就是温度降到终止温度了,其最终结果就是为最优解

这就是退火算法的具体步骤。下面有关于这个飞机侦察的这个题目的具体代码,可以参考。还有一篇不错的博客如果还不是很清楚,可以看看   手把手教会你模拟退火算法

 

要想真正灵活的掌握这个算法,还需要多多练习,之后有机会也想真正把握它的精髓。

路线模型的代码
clc,clear
sj0=load('sj.txt');%加载100个目标数据,数据按照表格中的位置保存在纯文本文件sj.txt中‘
x=sj0(:,[1:2:8]);x=x(:);
y=sj0(:,[2:2:8]);y=y(:);
sj=[x y];d1=[70,40];
sj=[d1;sj;d1];sj=sj*pi/180;%角度化成弧度
d=zeros(102);%距离矩阵d初始化
for i=1:101
 for j=i+1:102
 d(i,j)=6370*acos(cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*cos(sj(j,2))+sin(sj(i,2))*sin(sj(j,2)));
 end
end
d=d+d';
path=[];longth=inf;%巡航路径及长度初始化
rand('state',sum(clock));

for j=1:1000%求较好的初始解(蒙特卡洛)
 path0=[1 1 + randperm(100),102];temp=0;
 for i =1:101
 temp =temp+d(path0(i),path0(i+1));
 end
 if temp<long
 path=path0;long=temp;
 end
end

e=0.1^30;L=20000;at=0.999;t=1;
for k=1:L%退火过程
 c=2+floor(100*rand(1,2));%产生新解
 c=sort(c);c1=c(1);c2-c(2);
 %计算代价函数值的增量
 df=d(path(c1-1),path(c2))+d(path(c1),path(c2+1))-d(path(c1-1),path(c1))-d(path(c2),path(c2+1));
 if df<0
 %接受准则
 path=[path(1:c1-1),path(c2:-1:c1),path(c2+1:102)];long=long+df;
 elseif exp(-df/T)>=rand
 path=[path(1:c1-1),path(c2:-1:c1),path(c2+1:102)];long=long+df;
 end
 T=T*at;
 if T<e
 break;
 end
end

path,long%long输出巡航路径及路径长度
xx=sj(path,1);yy=sj(path,2);
plot(xx,yy,'-*')%画出巡航路径
模型数据

sj.txt

对于文中存在疑问的,或有什么问题,博主很希望能够相互交流

数模算法

是数模学习的另外一个模块

主要是对论文用到的算法进行详细讲解,主要讲解从算法原理,算法步骤,代码工具,及算法应用这几步。算法应用在建模算法中,是最为关键的部分,如何灵活的应用各类算法是重中之重,这才是算法学习的关键处,之前的原理的讲解就是希望能对算法有深入的理解,从而更加灵活的应用算法,对于算法的应用的主要还是回归论文中,所以这部分内容不会写在这里,会标明是具体的那篇论文。

算法名称                                              涉及论文

1.模拟退火算法                                 2015国赛A题(1)

2.麦夸特算法                                     2015国赛A题(2)

数模历程

  对于数模的学习主要围绕两个比赛:全国大学生数学建模(CUMCM)和美国大学生数学建模竞赛(MCM/ICM),主要的学习方法就是借助比赛中的优秀论文进行学习,分析。望能学习处理问题的相关思路和数学方法。会将将论文进行专题性质的探讨以及优秀论文中出现的一些算法进行详尽研究。

  数学建模,一直觉得是很神奇的,让我们更加理性的,真实的看待这个世界。每个建立的模型,都相当于一个黑盒子,它是由各类数学方法,思想构建的,当你输入相关的因素或将它置于一个适合它的环境,它给你,你之前看不到的,或是不久的未来。仿佛创造出一个新的工具,可以看清未来的一角。(我不管我就喜欢瞎bb)

     得儿,驾