【文章内容全部来自bilibili：https://www.bilibili.com/video/BV1Kb41167QZ】
数学建模的13种常用的方法
一、层次分析法（AHP）
1.起源：

美国运筹学家在上世纪70年代初，为美国国防部研究“根据各个工业部门对国家福利的贡献大小而进行电力分配”课题是，应用网络系统理论和多目标综合评价方法，提出的一种层次权重决策分析方法。

2.特点：

在对复杂的决策问题的本质、影响因素及其内在关系等进行深入分析的基础上，利用较小的定量信息使决策的思维过程数学化，从而为多目标、多准则或无结构性的复杂问题提供简便的决策方法。

3.定位：

是对难以完全定量的复杂系统做出决策的模型和方法。

4.原理：

层次分析法根据问题的性质和要达到的总目标，将问题分解为不同的组成因素，按照因素间的相互关联影响以及隶属关系将因素按不同层次聚集组合，形成一个多层次的分析结构模型，从而最终使问题归结为最底层相对于最高层的相对重要权值的确定或相对优劣的排定。

5.步骤：

1.建立层次结构模型。

2.构造判断（成对比较）矩阵

3.层次单排序及其一致性检验

4.层次总排序及其一致性检验

6.例子1：




7.例子2：





案例代码：

disp(‘请输入判断矩阵A(n阶)’);

A=input(‘A=’);

[n,n]=size(A);

x=ones(n,100);

y=ones(n,100);

m=zeros(1,100);

m(1)=max(x(:,1));

y(:,1)=x(:,1);

x(:,2)=Ay(:,1);

m(2)=max(x(:,2));

y(:,2)=x(:,2)/m(2);

p=0.0001;i=2;k=abs(m(2)-m(1));

while  k>p

i=i+1;

x(:,i)=Ay(:,i-1);

m(i)=max(x(:,i));

y(:,i)=x(:,i)/m(i);

k=abs(m(i)-m(i-1));

end

a=sum(y(:,i));

w=y(:,i)/a;

t=m(i);

disp(w);

%以下是一致性检验

CI=(t-n)/(n-1);RI=[0 0 0.52 0.89 1.12 1.26 1.36 1.41 1.46 1.49 1.52 1.54 1.56 1.58 1.59];

CR=CI/RI(n);

if CR<0.10

disp(‘此矩阵的一致性可以接受!’);

disp(‘CI=’);disp(CI);

disp(‘CR=’);disp(CR);

end
二、多属性决策











灰色预测

平面分离法求解带有偏好的动态多目标优化问题

I.介绍

动态多目标进化算法

DMOP：决策问题的目标函数不仅与决策变量有关，并且还会随着时间(环境)的变化而变化。因此该决策问题的最优解可能也会随时间(环境)的变化而变化。

常用求解方法：

(1)、EA算法：DNSGAII、DCOEA等

(2)、hyper-heuristics（超启发式）

超启发式的主要目标：组合不同的启发式算法，称为低级启发式算法(LLHs)，为产生更好的解。

基于选择的超启发式算法可以分为两个阶段：启发式选择和移动接受，

前者定义在当前时间段应用哪个LLH来解决问题，

后者设置接受或拒绝由所选LLH获得的解的标准。

(3)记忆、预测等

II.基于偏好的动态多目标进化算法

1）DSNGA-II，DNSGA-II考虑由DM先验定义的一组偏好，为每个当前候选解计算单个目标函数的归一化伪权重。然后，选择具有最接近归一化值的。

2）InDM2(基于偏好点),交互式DMOEA，允许DM在过程中设置参考点。一旦检测到问题变化或者参考点变化，当前种群的子集就会被随机产生的解所替代。

3）通过2）的两种可以解决偏好问题的结合InDM2的算法：WASF-GA和 RNSGA-II。

动态超启发式算法

低级启发式算法的复杂性没有限制，所以特定问题的启发式(problem-specific)和元启发式算法(meta-heuristics)可以作为超启发式(hyper-heuristic)的LLHs(low-level heuristics)

求解动态问题(DOPs)的启发式算法：AHC、HH、HMHH

求解DMOP的算法：DPEM-HH

相关参数



III.平面分离算法

平面分离法是一种在求解动态问题的优化算法中引入偏好的方法。

每个目标的最小值和最大值偏好

平面为每个维度拓展的大小

每个平面获得参考点的集合，L中的点用于将种群P分割成在目标搜索空间内形成一组平面S的子种群。

定义了每个平面中可对种群做出贡献的最大解集百分比。

是DMOEA实施的精英启发式，用于为新种群选择解。



平面分离法的特点

1)PS是一种灵活且通用的偏好插入方法，可用于替代或补充DMOEA的精英启发式。

2)关注ROI的同时能保持POF中解之间的多样性，以使算法能够快速适应变化。

3)它适用于DMOEA流程的任何部分。唯一的要求是必须在合并父母与子代种群之间的集的过程中应用它。

4) PS将种群分成多个平面后，每个平面都是独立工作的。

5)然后，DMOEA根据其选择过程生成一个与ROI最接近的个体的新种群。


原因：

1）每一代都激活PS，允许优化算法在PS内探索，找到最优解

2）C，贡献给新解集的最大百分比

PS应用

DNSGAII-A （随机解替代部分） DNSGAII-A-PS

DNSGAII-B   （部分变异）

DNSGAII-AB （部分替代，其余变异） DNSGAII-AB-PS

GDE3  (增加响应和检测)àDGDE3(随机解替代部分) DGDE3-PS

基于偏好的启发式算法 作为 超启发式算法

用上面的三个带有PS的算法作为LLHs,本文提出DHH-PS超启发式算法。



DHH-PS框架

使用CF(choice function)作为启发方式，CF使用性能指标来评估每个LLH的结果，选择CF值最大的启发式。




显示了DHH-PS用来评估启发式h的选择函数(CF)

两阶段排序方案，根据一组性能指标来比较h

自上次DHH-PS选择h以来经过的世代数。

平衡两个函数的作用





计算CF和评价算法性能的指标

ROI中非支配解比例



变量空间世代距离



反世代距离



超体积比



IV.实验设置 主要参数

DM1: Wf1=[0.1,0.4],FDA1,FDA3,dMOP3 Wf2=[0.3,0.7],dMOP1,dMOP2,Wf2=[0.65,1.0]

DM2:Wf1=[0.6,0.9],FDA1,FDA3,dMOP3 Wf2=[0.05,0.3],dMOP1,dMOP2,Wf2=[0.1,0.65]\

            |PS| = 3

             R={0%,15%,30%}

             C = {80%,15%,3%,2%}  %贡献比

                          

            

实验结果



将种群划分为平面允许单独管理每个子集中的解，例如，将非支配排序和拥挤距离方法应用到一个平面中，与其他平面分离。通过这种方式，我们赋予DNSGA-II-PS将来自每个平面的非支配且分布良好的解添加到种群中的能力，促进了收敛到ROI和解之间的多样性。



超启发式可能带来的一个弱点是，当使用性能较低的LLH时，其结果的质量会下降

V.总结

提出了一种新的基于参考点的方法，将偏好融入到DMOEA中，

1)  该方法可以求解具有DM给定偏好的DMOPS。

2）四个新的基于偏好的DMOEA：DNSGA-II的两个版本，即DNSGA-II-A-PS和DNSGA-II-AB-PS， DGDE3-PS，以及基于参考点的NSGA-II的动态版本(DRNSGA-II)。

3）提出了一种新的超启发式算法，称为带平面分离的动态超启发式算法(DHH-PS)， 采用基于偏好的DMOEA作为底层启发式算法来求解带偏好的DMOPs。

如果有一种LLH表现得非常好，那么当单独应用时，它可能会工作得更好

	

11.1.3  多目标优化
前面介绍的最优化方法只有一个目标函数，是单目标最优化方法。但是，在许多实际工程问题中，往往希望多个指标都达到最优值，所以就有多个目标函数，这种问题称为多目标最优化问题。
多目标规划有许多解法，下面列出常用的几种。
(1)化多为少法：将多目标问题化成只有1个或2个目标的问题，然后用简单的决策方法求解。最常用的是线性加权和法。
(2)分层序列法：将所有的目标按其重要程度依次排序，先求出第1个(最重要的)目标的最优解，然后在保证前一个目标最优解的前提下依次求下一个目标的最优解，一直求到最后一个目标为止。
(3)直接求非劣解法：先求出一组非劣解，然后按事先确定好的评价标准从中找出一个满意的解。
(4)目标规划法：当所有的目标函数和约束条件都是线性时，可以采用目标规划法，它是20世纪60年代初由查纳斯和库珀提出来的。此方法对每一个目标函数都事前给定一个期望值，然后在满足约束条件集合的情况下，找出使目标函数离期望值最近的解。
(5)多属性效用法(MAUM)：各个目标分别用各自的效用函数表示，然后构成多目标综合效用函数，以此来评价各个可行方案的优劣。
(6)层次分析法：由T.沙基于1980年提出来。这种方法是通过对目标、约束条件、方案等的主观判断，对各种方案加以综合权衡比较，然后评定优劣。
(7)重排次序法：把原来不好比较的非劣解，通过其他办法排出优劣次序。此外，还有多目标群决策和多目标模糊决策等方法。
针对多目标优化问题，MATLAB提供了fgoalattain和fminimax 函数用来进行求解。篇幅有限，这里仅举例说明fgoalattain函数的用法，fminimax函数的用法读者可自行查阅帮助文档。
【例11-7】  某工厂因生产需要欲采购一种原材料，市场上这种原材料有两个等级，甲级单价2元/千克，乙级单价1元/千克。要求所花总费用不超过200元，购得原材料总量不少于100千克，其中甲级原材料不少于50千克，问如何确定最好的采购方案。
设x1、x2分别为采购甲级和乙级原材料的数量(千克)，要求总采购费用尽量少，总采购重量尽量多，采购甲级原材料尽量多。
首先需要编写目标函数的M文件myfun4.m，返回目标计算值。具体代码如下：
function f=myfun4(x)
f(1)=2*x(1)+ x(2);
f(2)=-x(1)- x(2);
f(3)=-x(1);
给定目标，权重按目标比例确定，给出初始值。具体代码如下：
>> goal=[200 -100 -50];       %  要达到的目标
>> weight=[2040 -100 -50];   %  各个目标的权重
>> x0=[55 55];                  %  搜索的初始值
%  约束条件
>> A=[2 1;-1 -1;-1 0];
>> b=[200 -100 -50];
>> lb=zeros(2,1);
%  调用fgoalattain函数进行多目标优化
>> [x,fval,attainfactor,exitflag] =...
fgoalattain(@myfun4,x0,goal,weight,A,b,[],[],lb,[])
经过计算，MATLAB输出计算结果为：
x =
    50    50
fval =
   150  -100   -50
attainfactor =
  3.4101e-010
exitflag =
     4
所以，对于给定的权重比例，最好的采购方案是采购甲级原材料和乙级原材料各50千克。此时采购总费用为150元，总重量为100千克，甲级原材料总重量为50千克。

	

决策树的目标是从一组样本数据中，根据不同的特征和属性，建立一颗树形的分类结构。对于一个特定的问题，决策树的选择可能有很多种，从中选择最优的决策树是一个NP问题，在实际中我们通常会采用启发式学习的方法去构建一颗满足启发式条件的决策树。

常用的决策树算法有ID3、C4.5、CART，下面对这三种算法进行讲述：

ID3--最大信息增益

对于样本集合D，类别数为K，数据集D的经验熵表示为

                                                                                                                   (1)

其中是样本集合中属于第类的样本子集，表示子集的元素个数，表示样本集合的元素个数。

某个特征对于数据集的经验条件熵为：

                                                     (2)

其中，表示中特征取第个值的样本子集，表示中属于第类的样本子集。

于是信息增益可以表示为二者之差，可得：

                                                                                                              (3)

下面我们使用一个列子来说明一下计算过程。

假设有5个人与一个女孩相亲，女孩根据下面的条件进行判断见不见，年龄有两个属性（老，年轻），长相三个属性（帅，一般，丑），工资有三个属性（高，中等，低），会不会写代码有两个属性（会，不会），最终结果如下表：

5个候选相亲对象的属性及女孩意愿
	
 
			
年龄(age)
			
长相(appearance)
			
工资(salary)
			
写代码(programming)
			
类别
		
A
			
老
			
帅
			
高
			
不会
			
不见
		
B
			
年轻
			
一般
			
中等
			
会
			
见
		
C
			
年轻
			
丑
			
高
			
不会
			
不见
		
D
			
年轻
			
一般
			
高
			
会
			
见
		
E
			
年轻
			
一般
			
低
			
不会
			
不见
		
在这个问题中，

                                                                    

 

根据式(2)可以计算出4个分支节点的信息熵为：

                                                                

                                                                                   

                                           

                                                                           

                                                   

                                                                           

                                                             

                                                                                                  

根据式(3)可计算出各个特征的信息增益为：

                                                                 

                                                            

显然，写代码（programming）的信息增益最大，所有的样本根据此特征可以直接分到叶节点（即见或者不见），完成决策树生长。实际应用中决策树往往需要多个特征才能构建完成，需要在经验熵非0的类别中欧继续生长。

C4.5--最大信息增益比

特征A对于数据集D的信息增益比定义为：

                                                                                                                                             (4)

其中，

                                                                                                                              (5)

为数据集D关于A的取值熵。上面的例子，我们根据(5)求出数据集关于每个特征的取值熵：

                                                             

                                                 

                                                     

                                                       

根据式(4)计算各个特征的信息增益比为：

                                                     

                                                    

信息增益比中‘’写代码‘’仍然是最大的，但通过信息增益比，特征“年龄”对应的指标上升了，而特征“长相”和特征“工资”却下降了。

CART--最大基尼指数（Gini）

Gini描述的数据的纯度，与信息熵含义类似。

                                                                                                              (6)

CART在每一次迭代中选择基尼指数最小的特征及其对应的切分点进行分类。但与ID3,C4.5不同的是，CART是一颗二叉树，采用二元切割法，每一步将数据按特征A的取值切成两份，分别进入左右子树。特征A的Gini指数定义为：

                                                                                                      (7)

对于上面的例子，应用CART分类准则，根据式(7)计算各个Gini指数为：

                                                    

                       

                                     

                                         

                                                                      

在“年龄”“长相”“工资”“写代码”四个特征中，我们可以很快的发现“写代码”的Gini指数最小为0，因此选择特征“写代码”作为最优特征，“写代码”=“yes”为最优切分点。根据切分点，从根节点会直接产生两个叶节点，基尼指数为0，完成决策树生长。

总结

根据上面的例子我们发现三者直接的差异。

首先，ID3采用信息增益作为评价标准，除了“写代码”这一特征外，会倾向于取值较多的特征。因为，信息增益反映的是给定条件以后不确定性减少的程度，特征取值越多就意味着确定性更高，也就是条件熵越小，信息增益越大。这在实际应用中是一个缺陷。比如我们引入特征“DNA”，每个人的DNA都是不同的，如果ID3按照“DNA”特征进行划分一定是最优的，但这种分类的泛化能力是非常差的。因此C4.5实际上式对ID3进行优化，通过引入信息增益比，一定程度上对取值多特征进行惩罚，避免ID3出现过拟合的特性，提升决策树的泛化能力。

其次，从样本类型的角度，ID3只能处理离散型变量，而C4.5和CART都可以处理连续型变量。C4.5处理连续变量时，通过对数据排序之后找到类别不同的分割线作为切分点，根据切分点把连续属性转换为布尔型，从而将连续型变量转换多个取值区间的离散型变量。而对CART，由于其构建时每次都会对特征进行二值划分，因此可以很好的适用于连续型变量。

从应用角度，ID3和C4.5只能用于分类任务，而CART（Classification and Regression Tree）从名字就可以看出其不仅可以用于分类，还能用于回归任务。

此外，从实现细节、优化过程等角度，这三种决策树还有些不同，比如，ID3对样本特征缺失值比较敏感，而C4.5和CART可以对缺失值进行不同方式的处理。ID3和C4.5可以在每个节点上产生多叉分支，而每个特征在层级之间不会复用，而CART每个节点只会产生两个分支，因此最后会形成一颗二叉树，且每个特征可以被重复使用；ID3和C4.5通过剪枝来权衡树的准确性和泛化能力，而CART直接利用全部数据发现所有可能的树结构进行对比。

参考：《百面机器学习算法工程师》