建模中近似计算与智能算法课件

建模中的近似计算与智能算法建模中的近似计算与智能算法2017年年08月月13日日主要内容主要内容1、函数拟合中的近似、函数拟合中的近似2、非线性优化中的近似、非线性优化中的近似3、智能算法近似求解复杂数学模型、智能算法近似求解复杂数学模型4、遗传算法、遗传算法1、函数拟合中的近似、函数拟合中的近似给定观测向量 x=a1,a2,.,an,y=b1,b2,.,bn,如何拟合出y关于x的函数表达式？假设通过Matlab软件，得到拟合关系 y=f(x)那么该拟合的误差是多少？一方面，可以通过一方面，可以通过Matlab拟合结果中自带的显拟合结果中自带的显示参数来说明拟合效果；示参数来说明拟合效果；另一方面，可以通过将观测值的散点图与拟合另一方面，可以通过将观测值的散点图与拟合函数的图像，绘画在同一坐标系下，肉眼分辨函数的图像，绘画在同一坐标系下，肉眼分辨拟合误差。拟合误差。前者抽象前者抽象后者直观后者直观一个简单的一元一一个简单的一元一次多项式拟合次多项式拟合观测值的散点图与观测值的散点图与拟合函数偏差图拟合函数偏差图2、非线性优化中的近似、非线性优化中的近似目标函数目标函数:max y=x1-x2+x1x32约束条件约束条件:2x1+x20;x1-3x20;1x32.这是目标函数非线性的优化模型，如何求近似这是目标函数非线性的优化模型，如何求近似最优解？最优解？利用非线性优化方法计算，自然是可行的。但是，这里我讲另外一种计算思路（将非线性转化为线性模型求解）。因为1x32，所以可将其取值范围100等分，步长为0.01，那么原非线性优化模型就转化成99个线性优化问题的求解：目标函数：max y=(1+x32）x1-x2 约束条件：2x1+x20;x1-3x20；其中，x3=1.01,1.02,1.03,.,1.99.目标函数：目标函数：max y=(1+x32）x1-x2约束条件：约束条件：2x1+x20;x1-3x20；其中，其中，x3=1.01,1.02,1.03,.,1.99.-问题：这问题：这99个线性优化模型求得的最优解，是个线性优化模型求得的最优解，是否与原非线性优化模型求得的最优解相同？否与原非线性优化模型求得的最优解相同？答：一般而言，它们不是完全等同的，只是一答：一般而言，它们不是完全等同的，只是一种近似求解策略。但是，如果种近似求解策略。但是，如果x3的精度保留两的精度保留两位数的话，此时结果可以认为是相同的。位数的话，此时结果可以认为是相同的。一般地，把非线性优化模型转化为N个线性优化问题的思想，称为“带参数穷举策略”的线性优化处理方法。显然，这种思想，不仅仅局限于穷举一个变量（x3），可以根据非线性优化模型的难易程度，灵活选择一个或多个变量进行穷举。近几年，全国大学生数学建模竞赛的题目中，或多或少都涉及到这种“带参数穷举策略”的处理技巧。比如，2014年的折叠椅设计问题；2015年的出租车打的软件开发等。3、智能算法近似求解复杂数学、智能算法近似求解复杂数学模型模型在工程实践中，经常会接触到一些比较“新颖”的算法，比如局部搜索，模拟退火，遗传算法，禁忌搜索等。这些算法都有一些共同的特性（比如模拟自然过程），通称为“智能算法”。它们在解决一些复杂的工程问题时大有用武之地。为了找出地球上最高的山，一群有志气为了找出地球上最高的山，一群有志气的兔子们开始想办法。的兔子们开始想办法。（1）兔子朝着比现在高的地方跳去。）兔子朝着比现在高的地方跳去。他们找到了不远处的最高山峰。但是这他们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是局部座山不一定是珠穆朗玛峰。这就是局部搜索，它不能保证局部最优值就是全局搜索，它不能保证局部最优值就是全局最优值。最优值。下面通过形象比喻，简单介绍常见的智下面通过形象比喻，简单介绍常见的智能算法：能算法：（2）兔子喝醉了。他随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，他渐渐清醒了，并朝最高方向跳去。这就是模拟退火。（3）兔子们吃了失忆药片，并被发射到太空，然后随机落到了地球上的某些地方。他们不知道自己的使命是什么。但是，如果你过几年就杀死一部分海拔低的兔子，多产的兔子们自己就会找到珠穆朗玛峰。这就是遗传算法。（4）兔子们知道一个兔的力量是渺小的。他们互相转告着，哪里的山已经找过，并且找过的每一座山他们都留下一只兔子做记号。他们制定了下一步去哪里寻找的策略。这就是禁忌搜索。4、遗传算法、遗传算法遗传算法是由美国的J.Holland教授于1975年在他的专著自然界和人工系统的适应性中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。标准遗传算法的组成：（1）编码（产生初始种群）（2）适应度函数（3）遗传算子（选择、交叉、变异）（4）运行参数编码编码遗传算法是通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。标准遗传算法使用二进制串进行编码。几个术语几个术语基因型：基因型：101基因基因表现型：表现型：5解码解码编码编码初始种群初始种群标准遗传算法采用随机方法生成若干个个体的集合，该集合称为初始种群。初始种群中个体的数量称为种群规模。初始种群一般通过Matlab软件中的随机函数产生。适应度函数适应度函数遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。选择算子选择算子遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。标准遗传算法中选择算子采用轮盘赌选择方法。轮盘赌选择方法轮盘赌选择方法轮盘赌选择又称比例选择算子，它的基本思想是：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n，个体i 的适应度为 Fi，则个体i 被选中遗传到下一代群体的概率为：轮盘赌选择方法的实现步骤轮盘赌选择方法的实现步骤（1）计算群体中所有个体的适应度函数值（需计算群体中所有个体的适应度函数值（需要解码）；要解码）；（2）利用比例选择算子的公式，计算每个个体利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；被选中遗传到下一代群体的概率；（3）模拟赌盘操作（即生成模拟赌盘操作（即生成0到到1之间的随机数之间的随机数与每个个体遗传到下一代群体的概率进行匹配）与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。来确定各个个体是否遗传到下一代群体中。交叉算子交叉算子所谓交叉运算，是指对两个相互配对的染色体依据交叉概率 Pc 按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。标准遗传算法中交叉算子采用单点交叉算子。单点交叉单点交叉交叉前：交叉前：00000|01000011100|000101交叉后：交叉后：00000|00010111100|010000变异算子变异算子所谓变异运算，是指依据变异概率 Pm 将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。标准遗传算法中变异算子采用基本位变异算子。基本位变异算子的执行过程基本位变异算子的执行过程 变异前：变异前：0000010000变异后：变异后：1000010000运行参数运行参数（1）M ：种群规模种群规模 （2）T ：遗传运算的终止进化代数遗传运算的终止进化代数 （3）Pc ：交叉概率交叉概率 （4）Pm：变异概率变异概率遗传算法的流程图遗传算法的流程图产生初始群体产生初始群体是否满足停止准则是否满足停止准则是是输出结果并结束输出结果并结束计算个体适应度值计算个体适应度值比例选择运算比例选择运算单点交叉运算单点交叉运算基本位变异运算基本位变异运算否否产生新一代群体产生新一代群体执行执行M/2M/2次次示例示例目标函数目标函数:max y=x12+x22约束条件约束条件:x1 的取值范围为的取值范围为0,1,2,3,4,5,6,7 x2 的取值范围为的取值范围为0,1,2,3,4,5,6,7遗传算法编程讲解遗传算法编程讲解遗传算法程序源代码遗传算法程序源代码结束语结束语近年来，全国大学生数学建模竞赛的题目越来越开放，所建立的模型基本无法精确求解，因此数学模型近似求解技巧愈发重要。本报告叙述比较简洁，从“函数拟合中的近似”，“非线性优化中的近似”，“智能算法近似求解复杂数学模型”和“遗传算法”四个方面介绍了近似求解复杂模型的思想。实际上，这远远是不够的。现代近似计算是一门科学，也是热门研究领域之一。特别地，结合了高性能计算机的近似计算方法设计越来越受到科研和工程技术人员的高度重视。有兴趣的同学，可以到网上买一些近似计算方法的书籍来系统学习一下，进一步提高近似计算的能力。讲座结束，谢谢大家！讲座结束，谢谢大家！