数学建模中的常用算法市公开课一等奖百校联赛特等奖课件.pptx
《数学建模中的常用算法市公开课一等奖百校联赛特等奖课件.pptx》由会员分享,可在线阅读,更多相关《数学建模中的常用算法市公开课一等奖百校联赛特等奖课件.pptx(110页珍藏版)》请在咨信网上搜索。
1、Algorithms in Mathematical ModelingGenetic Algorithm数学建模中惯用算法成都信息工程学院计算科学系胡建成-5-2010/10/第1页Algorithms in Mathematical ModelingGenetic Algorithm2数学建模竞赛网上资源数学建模竞赛网上资源CUMCM网站:http:/ MCM和ICM网站:http:/中国数学建模:http:/中科大建模网站:http:/MATLAB网站:http:/GOOGLE大学10/10/第2页Algorithms in Mathematical ModelingGenetic Alg
2、orithm3数学建模竞赛中算法数学建模竞赛中算法(1)93A 非线性交调频率设计非线性交调频率设计:拟合、规划拟合、规划93B 足球队排名次足球队排名次:矩阵论、图论、层次分析法、矩阵论、图论、层次分析法、整数规划整数规划94A 逢山开路逢山开路:图论、插值、动态规划图论、插值、动态规划94B 锁具装箱问题锁具装箱问题:图论、组合数学图论、组合数学95A 飞行管理问题飞行管理问题:非线性规划、线性规划非线性规划、线性规划95B 天车与冶炼炉作业调度天车与冶炼炉作业调度:非线性规划、动态规非线性规划、动态规划、层次分析法、划、层次分析法、PETRI方法、图论方法、排队论方方法、图论方法、排队论
3、方法法96A 最优打鱼策略最优打鱼策略:微分方程、积分、非线性规划微分方程、积分、非线性规划10/10/第3页Algorithms in Mathematical ModelingGenetic Algorithm496B 节水洗衣机节水洗衣机:非线性规划非线性规划97A 零件参数设计零件参数设计:微积分、非线性规划、随机模拟微积分、非线性规划、随机模拟97B 截断切割截断切割:组合优化、几何变换、枚举、蒙特卡组合优化、几何变换、枚举、蒙特卡罗、递归、最短路罗、递归、最短路98A 投资收益与风险投资收益与风险:线性规划、非线性规划线性规划、非线性规划98B 灾情巡视灾情巡视:最小生成树、最小生
4、成树、Hamilton圈、旅行商圈、旅行商问题问题99A 自动化车床自动化车床:积分、概率分布、随机模拟、分布积分、概率分布、随机模拟、分布拟合度检验拟合度检验数学建模竞赛中算法数学建模竞赛中算法(2)10/10/第4页Algorithms in Mathematical ModelingGenetic Algorithm599B 钻井布局钻井布局:几何变换、枚举、最大完全子图、几何变换、枚举、最大完全子图、混合整数规划混合整数规划00A DNA分类分类:神经网络、最小二乘拟合、统计分神经网络、最小二乘拟合、统计分类类00B 管道订购管道订购:最短路、二次规划最短路、二次规划01A 血管三维重
5、建血管三维重建:数据挖掘、曲面重建与拟合数据挖掘、曲面重建与拟合01B 公交车调度公交车调度:非线性规划非线性规划02A 车灯光源优化设计车灯光源优化设计:最优化最优化02B 彩票中数学彩票中数学:概率与优化概率与优化数学建模竞赛中算法数学建模竞赛中算法(3)10/10/第5页Algorithms in Mathematical ModelingGenetic Algorithm6 MATLABMapleMathematicaLindoLingo SASSPSSC&C+FortranPascal数学建模惯用软件数学建模惯用软件10/10/第6页Algorithms in Mathematica
6、l ModelingGenetic Algorithm71.蒙特卡罗方法(Monte-Carlo方法,MC)数学建模竞赛惯用算法数学建模竞赛惯用算法(1)该算法又称计算机随机性模拟方法计算机随机性模拟方法,也称统计试验统计试验方法方法。MC方法是一个基于“随机数”计算方法,能够比较逼真地描述事物特点及物理试验过程,处理一些数值方法难以处理问题。MC方法雏型能够追溯到十九世纪后期蒲丰随机投针试验,即著名蒲丰问题蒲丰问题。MC方法经过计算机仿真(模拟)处理问题,同时也能够经过模拟来检验自己模型正确性,是比赛中经常使用方法。10/10/第7页Algorithms in Mathematical Mo
7、delingGenetic Algorithm8o97年A题每个零件都有自己标定值,也都有自o己容差等级,而求解最优组合方案将要面对着是一o个极其复杂公式和108种容差选取方案,根本不可能去求o解析解,那怎样去找到最优方案呢?随机性模拟搜索最o优方案就是其中一个方法,在每个零件可行区间中按o照正态分布随机选取一个标定值和选取一个容差值作为o一个方案,然后经过蒙特卡罗算法仿真出大量方案,从o中选取一个最正确。oB题关于彩票第二问,要求设计一个更加好方o案,首先方案优劣取决于很多复杂原因,一样不可能o刻画出一个模型进行求解,只能靠随机仿真模拟。数学建模竞赛惯用算法数学建模竞赛惯用算法10/10/第
8、8页Algorithms in Mathematical ModelingGenetic Algorithm998 年美国赛年美国赛A 题题 生物组织切片三维插值处理生物组织切片三维插值处理94 年年A 题逢山开路题逢山开路 山体海拔高度插值计算山体海拔高度插值计算数学建模竞赛惯用算法数学建模竞赛惯用算法(2)2.数据拟合、参数预计、插值等数据处理算法比赛中通常会碰到大量数据需要处理,而处理数据关键就在于这些算法,通常使用MATLAB作为工具。与图形处理相关问题很多与拟合相关系。这类问题在MATLAB中有很多函数能够调用,只有熟悉MATLAB,这些方法才能用好。10/10/第9页Algorit
9、hms in Mathematical ModelingGenetic Algorithm1098年年B 题题 用很多不等式完全能够把问题刻画清楚用很多不等式完全能够把问题刻画清楚数学建模竞赛惯用算法数学建模竞赛惯用算法(3)3.规划类问题算法这类问题主要有线性规划、整数规划、多元规划、线性规划、整数规划、多元规划、二次规划二次规划等。竞赛中很多问题都和数学规划相关,能够说不少模型都能够归结为一组不等式作为约束条件、几个函数表示式作为目标函数问题,碰到这类问题,求解就是关键了。所以列举出规划后用Lindo、Lingo等软件来进行处理比较方便,所以还需要熟悉这两个软件。10/10/第10页Alg
10、orithms in Mathematical ModelingGenetic Algorithm11o98年B题、B题、95年锁具装箱等问题表达了图论问题主要性。数学建模竞赛惯用算法数学建模竞赛惯用算法(4)4.图论问题这类问题算法有很多,包含:Dijkstra、Floyd、Prim、Bellman-Ford,最大流,二分匹配,最大流,二分匹配等问题。10/10/第11页Algorithms in Mathematical ModelingGenetic Algorithm1292 年年B 题用分枝定界法题用分枝定界法97 年年B 题是经典动态规划问题题是经典动态规划问题98 年年B 题表达
11、了分治算法题表达了分治算法数学建模竞赛惯用算法数学建模竞赛惯用算法(5)5.计算机算法设计中问题计算机算法设计包含很多内容:动态规划、回溯搜动态规划、回溯搜索、分治算法、分枝定界索、分治算法、分枝定界等计算机算法.这方面问题和ACM程序设计竞赛中问题类似,可看一下与计算机算法相关书。10/10/第12页Algorithms in Mathematical ModelingGenetic Algorithm13o97年A题用模拟退火算法oB题用神经网络分类算法oB题这种难题也能够使用神经网络o美国89年A题也和BP算法相关系o美国B题伽马刀问题也是当前研究课题,当前算法最正确是遗传算法。数学建模
12、竞赛惯用算法数学建模竞赛惯用算法(6)6.最优化理论三大非经典算法:模拟退火法(SA)、神经网络(NN)、遗传算法(GA)近几年赛题越来越复杂,很多问题没有什么很好模型能够借鉴,于是这三类算法很多时候能够派上用场。10/10/第13页Algorithms in Mathematical ModelingGenetic Algorithm1497 年年A 题、题、99 年年B 题都能够题都能够用网格法搜索用网格法搜索数学建模竞赛惯用算法数学建模竞赛惯用算法(7)网格算法和穷举法一样,只是网格法是连续问题穷举。这类算法运算量较大。7.网格算法和穷举算法这种方法最好在运算速度较快计算机中进行,还有要
13、用高级语言来做,最好不要用MATLAB做网格,不然会算很久。10/10/第14页Algorithms in Mathematical ModelingGenetic Algorithm15很多问题都是实际来,数据能够是连续,而计算机只能处理离散数据,所以需要将连续问题进行将连续问题进行离散化处理后再用计算机求解离散化处理后再用计算机求解。比如差分代替微分、求和代替积分等思想都是把连续问题离散化惯用方法。数学建模竞赛惯用算法数学建模竞赛惯用算法(8)8.连续问题离散化方法10/10/第15页Algorithms in Mathematical ModelingGenetic Algorithm1
14、6数值分析研究各种求解数学问题数值计算方法求解数学问题数值计算方法,尤其是适合于计算机实现方法与算法。数学建模竞赛惯用算法数学建模竞赛惯用算法(9)9.数值分析方法它主要内容包含函数数值迫近、数值微分与数函数数值迫近、数值微分与数值积分、非线性方程数值解法、数值代数、常微分方值积分、非线性方程数值解法、数值代数、常微分方程数值解程数值解等。数值分析是计算数学一个主要分支,把理论与计算紧密结合,是当代科学计算基础。MATLAB等数学软件中已经有很多数值分析函数能够直接调用。10/10/第16页Algorithms in Mathematical ModelingGenetic Algorithm
15、17oA题中需要你会读BMP图象o98年美国A题需要你知道三维插值计算oB题要求更高,不但需要编程计算还要进行处理数学建模竞赛惯用算法数学建模竞赛惯用算法(10)10.图象处理算法赛题中有一类问题与图形相关,即使问题与图形无关,论文中也会需要图片来说明问题,这些图形怎样展示以及怎样处理就是需要处理问题,通常使用MATLAB进行处理。数模论文中也有很多图片需要展示,处理这类问题要熟悉MATLAB图形图像工具箱。10/10/第17页Algorithms in Mathematical ModelingGenetic Algorithm18三个孩子年纪三个孩子年纪(1)两个多年未见朋友相遇,聊了很多
16、事情。A:既然你是数学教授,那你帮我算这个题,今天是个特殊日子:我三个儿子都在今天庆贺生日!那么你能算出他们都有多大吗?B:好,但你得跟我讲讲他们情况。A:好,我给你一些提醒,他们三个年纪之积是36.B:很好,但我还需要更多提醒。10/10/第18页Algorithms in Mathematical ModelingGenetic Algorithm19三个孩子年纪三个孩子年纪(2)A:我大儿子眼睛是蓝色。B考虑了一下说,不过,我还有一点信息来处理你这个难题。B:哦,够了,B给出了正确答案,即三个小孩年纪。A:他们三个年纪之和等于那幢房子窗户个数。A指着对面一幢房子说。10/10/第19页A
17、lgorithms in Mathematical ModelingGenetic Algorithm20三个孩子年纪三个孩子年纪(3)依据对话信息,用搜索方法来解此问题。信息信息1:三个小孩年纪之积为三个小孩年纪之积为36只有以下8种可能,搜索范围降低至8种情况:o第一个小孩年纪36181299664o第二个小孩年纪12342633o第三个小孩年纪1111212310/10/第20页Algorithms in Mathematical ModelingGenetic Algorithm21三个孩子年纪三个孩子年纪(4)信息信息2:三个小孩年纪之和等于窗户数三个小孩年纪之和等于窗户数o第一个小
18、孩年纪36181299664o第二个小孩年纪12342633o第三个小孩年纪11112123窗户数窗户数:38 21 16 14 13 13 11 10假如窗户数为38、21、16、14、11、10即可得出答案B还需信息,即窗户数为13.则可能为(9、2、2)或(6、6、1)信息2:大儿子眼睛是蓝色得答案:(9、2、2)10/10/第21页Algorithms in Mathematical ModelingGenetic Algorithm22智能优化算法智能优化算法智能优化算法智能优化算法又称为当代启发式算法当代启发式算法,是一种含有全局优化性能、通用性强、且适合于并行处理算法。这种算法普
19、通含有严密理论依据,而不是单纯凭借教授经验,理论上能够在一定时间内找到最优解或近似最优解。10/10/第22页Algorithms in Mathematical ModelingGenetic Algorithm23惯用智能优化算法惯用智能优化算法遗传算法遗传算法GeneticAlgorithm,简称GA模拟退火算法模拟退火算法SimulatedAnnealing,简称SA禁忌搜索算法禁忌搜索算法TabuSearch,简称TS 10/10/第23页Algorithms in Mathematical ModelingGenetic Algorithm24智能优化算法特点智能优化算法特点它们共
20、同特点:都是从任一解出发,按照某种机制,以一定概率在整个求解空间中探索最优解。因为它们能够把搜索空间扩展到整个问题空间,因而含有全局优化性能。10/10/第24页Algorithms in Mathematical ModelingGenetic Algorithm25遗传算法遗传算法(Genetic Algorithm)进化算法(EvolutionaryAlgorithm)10/10/第25页Algorithms in Mathematical ModelingGenetic Algorithm26遗传算法遗传算法(GA)Darwin(1859):“物竟天择,适者生存物竟天择,适者生存”Jo
21、hnHolland(universityofMichigan,1975)Adaptation in Natural and Artificial System遗传算法作为一个有效工具,已广泛地应用于最优遗传算法作为一个有效工具,已广泛地应用于最优化问题求解之中化问题求解之中。遗传算法是一个基于自然群体遗传进化机制自适应遗传算法是一个基于自然群体遗传进化机制自适应全局优化概率搜索算法。全局优化概率搜索算法。它摒弃了传统搜索方式,模拟自然界生物进化过程,采取人工方式对目标空间进行随机化搜索。10/10/第26页Algorithms in Mathematical ModelingGenetic A
22、lgorithm27遗传算法模拟自然选择和自然遗传过程中发生繁殖、交叉和基因突变繁殖、交叉和基因突变现象,在每次迭代中都保留一组候选解,并按某种指标从解群中选取较优个体,利用遗传算子遗传算子(选择、交叉和变选择、交叉和变异异)对这些个体进行组合,产生新一代候选解群,重复此过程,直到满足某种收敛指标为止。遗传算法搜索机制遗传算法搜索机制10/10/第27页Algorithms in Mathematical ModelingGenetic Algorithm28局部局部局部局部全局全局全局全局遗传算法遗传算法(GA)10/10/第28页Algorithms in Mathematical Mod
23、elingGenetic Algorithm29We have a dream!We have a dream!I am at the I am at the toptopHeight is.Height is.I am not at the top.I am not at the top.My high is better!My high is better!I will continueI will continue遗传算法遗传算法(GA)GA-第0代10/10/第29页Algorithms in Mathematical ModelingGenetic Algorithm30Dead o
24、neDead oneNew oneNew one遗传算法遗传算法(GA)GA-第1代10/10/第30页Algorithms in Mathematical ModelingGenetic Algorithm31Not at the top,Not at the top,Come Up!Come Up!遗传算法遗传算法(GA)GA-第?代10/10/第31页Algorithms in Mathematical ModelingGenetic Algorithm32I am the I am the BESTBEST!遗传算法遗传算法(GA)GA-第N代10/10/第32页Algorithms
25、in Mathematical ModelingGenetic Algorithm33适者生存适者生存(SurvivaloftheFittest)GA主要采取进化规则是主要采取进化规则是“适者生存适者生存”很好解保留,较差解淘汰很好解保留,较差解淘汰遗传算法遗传算法(GA)10/10/第33页Algorithms in Mathematical ModelingGenetic Algorithm34生物进化与遗传算法对应关系生物进化与遗传算法对应关系生物进化生物进化遗传算法遗传算法适者生存适应函数值最大解被保留概率最大个体问题一个解染色体解编码基因编码元素群体被选定一组解种群依据适应函数选择一
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 建模 中的 常用 算法 公开 一等奖 联赛 特等奖 课件
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【w****g】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【w****g】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。