数学建模（二）：优化

目录

👉🏻历史回顾👈🏻

✨前言

🔍一、什么是启发式算法？

📚二、简单的优化问题

📓三、启发式算法

💡四、粒子群算法

🗝️五、代码实现

🔍六、代码讲解与分析

🎈写在最后

👉🏻历史回顾👈🏻

✨前言

     在数学建模比赛中，优化的问题是再常见不过了，关于一些常见的有约束条件的函数寻优，我们可以用lingo就可以解决，但是对于一些复杂的并且无约束条件的寻优，我们常常无法入手，这个时候启发式算法就是我们求解该类优化问题的一大法宝。

    关于智能优化算法有很多，遗传算法、例子群算法、模拟退火....，这里我们就先学习掌握“粒子群算法”即可！

数学建模专栏：数学建模从0到1

🔍一、什么是启发式算法？

启发式算法百度百科上的定义：一个基于直观或经验构造的算法，在可接受的花费下给出待解决优化问题的一个可行解。

1）什么是可接受的花费？

计算时间和空间能接受（求解一个问题要几万年 or 一万台电脑）

2）什么是优化问题？

指在一定约束条件下,求解一个目标函数的最大值(或最小值)问题。

(注：实际上和我们之前学过的规划问题的定义一样，称呼不同而已 )

3）什么是可行解？

得到的结果能用于工程实践（不一定非要是最优解）

📚二、简单的优化问题

编辑

如上图所示，我们在f(x)这个函数中要寻找一个最大值点，因为f(x)是一个组合函数，也就是不规则的函数，我们如果要在图中找出这个最大值点，我们最好的方法就是对[a,b]进行分割，比如说分割步长为0.01的然后跑一个循环求出x分别为（a）,(a+0.01).....（b）中对应的最大的y，这种方法是最容易想到的办法，但是存在一定的局限性，得出来的解很有可能是局部最优解，为什么这么说呢?

举一个例子：

1）a=1；b=10；

2）按照步长为0.01将[a,b]划分成1000份

3）然后求出当x=2.01是对应的y最大，这个时候我们就会认为f(2.01)是全局最优解

4）事实上，如果x=2.015对应的才是实际的最大值，但是我们再枚举的过程中并不能计算精度为0.001时的值，就很难得到最优解，这个时候我们就可以使用启发式搜索方法！

📓三、启发式算法

按照预定的策略实行搜索，在搜索过程中获取的中间信息不用来改进策略，称为盲目搜索；

反之如果利用了中间信息来改进搜索策略则称为启发式搜索。

例如：蒙特卡罗模拟用来求解优化问题就是盲目搜索，

还有大家熟悉的枚举法也是盲目搜索。

• 关于“启发式”，可以简单总结为下面两点：

（1）任何有助于找到问题的最优解，但不能保证找到最优解的方法均是启发式方法；

（2）有助于加速求解过程和找到较优解的方法是启发式方法。

💡四、粒子群算法

编辑

1995年，美国学者Kennedy和Eberhart共同提出了粒子群算法，其基本思想源于对鸟类群体行为进行建模与仿真的研究结果的启发。

核心思想：是利用群体中的个体对信息的共享使整个群体的运动在问题求解空间中产生从无序到有序的演化过程，从而获得问题的可行解。

🗝️五、代码实现

编辑

我们就拿这个题目来举例子 ，求函数f(t,s)的极小值，这道题目的原解法是利用单纯形搜索法实现，那么我们这里用粒子群算法来实现一下，代码如下所示：

1）SOA.m文件

%function [x,minf] = minPS(f,x0,delta,gama,sita,var,eps)
clc;clear
x0=[-2 6];
delta=[0.2 0.2];
gama=1.4;
sita=0.2;
format long;
    eps = 1.0e-6;
k = 0;
n = 2;%length(var);
while 1
    y = x0;
    %yf = Funval(f, var,y);
    yf=fun(y);
    for i=1:n
        tmpy = zeros(size(y));
        tmpy(i) = delta(i);
       % tmpf = Funval(f, var,y+tmpy);
          tmpf =fun(y+tmpy);
        if tmpf < yf
            y = y + tmpy;
        else
           % tmpf = Funval(f, var,y-tmpy);
             tmpf =fun(y-tmpy);
            if tmpf < yf
                y = y - tmpy;
            end
        end
    end
    x1 = y;
  %  fx1 = Funval(f, var,x1);
     fx1 =fun(x1);
    if fx1 < yf
        y = x1 + gama*(x1 - x0);
    else
        tol = norm(delta);
        if tol<eps
            x = x0;
            break;
        else
            if x1~=x0
                y = x1;
            else
                y = x1;
                delta = sita*delta;
            end
        end
    end
    x0 = x1;
end
%minf = Funval(f,var,x);
minf=fun(x);
format short;

2）Sphere.m文件

function y=Sphere(x)
%y=-(3*x(1)^2+x(2)^2-2*x(1)*x(2)+4*x(1)+3*x(2));
 y=3*x(1)^2+x(2)^2-x(1)*x(2)+3*x(2)-5;

3）运行结果

编辑 编辑

4）答案验证

编辑

答案正确√

🔍六、代码讲解与分析

关于粒子群算法的各个步骤原理，我这边不做过多赘述，下面我来教大家如何应用并解决问题。

（1）这个Sphere.m文件存储的是我们需要求最小值的函数表达式，里面一共有两个变量，存在x矩阵里了，分别是x(1)，x(2)，分别对应着我们题目中的t和s，如果一个函数表达式中有n个变量，那么我们分别用x(1).....x(n)去替代即可

编辑

（2）这个SOA.m文件存储的是粒子群算法的核心实现代码，我们主要需要注意的就是m这个变量的值，是由Sphere.m文件中函数表示中的变量的个数决定的，例如这道题目的变量是t,s，那么这个时候m的值就是2

编辑

🎈写在最后

数模之路漫漫远兮，以上均为博主个人理解，如有错误，欢迎指正，您的三连就是对俺最大的肯定！

编辑