建模中的近似计算与智能算法.pptVIP

适应度函数 遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。 选择算子 遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。标准遗传算法中选择算子采用轮盘赌选择方法。 轮盘赌选择方法 轮盘赌选择又称比例选择算子，它的基本思想是：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n ，个体i 的适应度为 Fi，则个体i 被选中遗传到下一代群体的概率为： 轮盘赌选择方法的实现步骤 （1） 计算群体中所有个体的适应度函数值（需要解码）； （2） 利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率； （3） 模拟赌盘操作（即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。 交叉算子 所谓交叉运算，是指对两个相互配对的染色体依据交叉概率 Pc 按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。 标准遗传算法中交叉算子采用单点交叉算子。 建模中的近似计算与智能算法 昆明理工大学理学院 昆明理工大学数据科学研究中心 李金海 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）兔子朝着比现在高的地方跳去。他们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是局部有哪些信誉好的足球投注网站，它不能保证局部最优值就是全局最