数学建模中的常用算法市公开课一等奖百校联赛特等奖课件.pptx

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 Algorithm3数学建模竞赛中算法数学建模竞赛中算法(1)93A 非线性交调频率设计非线性交调频率设计:拟合、规划拟合、规划93B 足球队排名次足球队排名次:矩阵论、图论、层次分析法、矩阵论、图论、层次分析法、整数规划整数规划94A 逢山开路逢山开路:图论、插值、动态规划图论、插值、动态规划94B 锁具装箱问题锁具装箱问题:图论、组合数学图论、组合数学95A 飞行管理问题飞行管理问题:非线性规划、线性规划非线性规划、线性规划95B 天车与冶炼炉作业调度天车与冶炼炉作业调度:非线性规划、动态规非线性规划、动态规划、层次分析法、划、层次分析法、PETRI方法、图论方法、排队论方方法、图论方法、排队论方法法96A 最优打鱼策略最优打鱼策略：微分方程、积分、非线性规划微分方程、积分、非线性规划10/10/第3页Algorithms in Mathematical ModelingGenetic Algorithm496B 节水洗衣机节水洗衣机：非线性规划非线性规划97A 零件参数设计零件参数设计：微积分、非线性规划、随机模拟微积分、非线性规划、随机模拟97B 截断切割截断切割：组合优化、几何变换、枚举、蒙特卡组合优化、几何变换、枚举、蒙特卡罗、递归、最短路罗、递归、最短路98A 投资收益与风险投资收益与风险：线性规划、非线性规划线性规划、非线性规划98B 灾情巡视灾情巡视：最小生成树、最小生成树、Hamilton圈、旅行商圈、旅行商问题问题99A 自动化车床自动化车床：积分、概率分布、随机模拟、分布积分、概率分布、随机模拟、分布拟合度检验拟合度检验数学建模竞赛中算法数学建模竞赛中算法(2)10/10/第4页Algorithms in Mathematical ModelingGenetic Algorithm599B 钻井布局钻井布局：几何变换、枚举、最大完全子图、几何变换、枚举、最大完全子图、混合整数规划混合整数规划00A DNA分类分类：神经网络、最小二乘拟合、统计分神经网络、最小二乘拟合、统计分类类00B 管道订购管道订购：最短路、二次规划最短路、二次规划01A 血管三维重建血管三维重建：数据挖掘、曲面重建与拟合数据挖掘、曲面重建与拟合01B 公交车调度公交车调度：非线性规划非线性规划02A 车灯光源优化设计车灯光源优化设计：最优化最优化02B 彩票中数学彩票中数学：概率与优化概率与优化数学建模竞赛中算法数学建模竞赛中算法(3)10/10/第5页Algorithms in Mathematical ModelingGenetic Algorithm6 MATLABMapleMathematicaLindoLingo SASSPSSC&C+FortranPascal数学建模惯用软件数学建模惯用软件10/10/第6页Algorithms in Mathematical ModelingGenetic Algorithm71.蒙特卡罗方法(Monte-Carlo方法,MC)数学建模竞赛惯用算法数学建模竞赛惯用算法(1)该算法又称计算机随机性模拟方法计算机随机性模拟方法，也称统计试验统计试验方法方法。MC方法是一个基于“随机数”计算方法，能够比较逼真地描述事物特点及物理试验过程，处理一些数值方法难以处理问题。MC方法雏型能够追溯到十九世纪后期蒲丰随机投针试验，即著名蒲丰问题蒲丰问题。MC方法经过计算机仿真(模拟)处理问题，同时也能够经过模拟来检验自己模型正确性，是比赛中经常使用方法。10/10/第7页Algorithms in Mathematical ModelingGenetic Algorithm8o97年A题每个零件都有自己标定值，也都有自o己容差等级，而求解最优组合方案将要面对着是一o个极其复杂公式和108种容差选取方案，根本不可能去求o解析解，那怎样去找到最优方案呢？随机性模拟搜索最o优方案就是其中一个方法，在每个零件可行区间中按o照正态分布随机选取一个标定值和选取一个容差值作为o一个方案，然后经过蒙特卡罗算法仿真出大量方案，从o中选取一个最正确。oB题关于彩票第二问，要求设计一个更加好方o案，首先方案优劣取决于很多复杂原因，一样不可能o刻画出一个模型进行求解，只能靠随机仿真模拟。数学建模竞赛惯用算法数学建模竞赛惯用算法10/10/第8页Algorithms in Mathematical ModelingGenetic Algorithm998 年美国赛年美国赛A 题题 生物组织切片三维插值处理生物组织切片三维插值处理94 年年A 题逢山开路题逢山开路 山体海拔高度插值计算山体海拔高度插值计算数学建模竞赛惯用算法数学建模竞赛惯用算法(2)2.数据拟合、参数预计、插值等数据处理算法比赛中通常会碰到大量数据需要处理，而处理数据关键就在于这些算法，通常使用MATLAB作为工具。与图形处理相关问题很多与拟合相关系。这类问题在MATLAB中有很多函数能够调用，只有熟悉MATLAB，这些方法才能用好。10/10/第9页Algorithms in Mathematical ModelingGenetic Algorithm1098年年B 题题 用很多不等式完全能够把问题刻画清楚用很多不等式完全能够把问题刻画清楚数学建模竞赛惯用算法数学建模竞赛惯用算法(3)3.规划类问题算法这类问题主要有线性规划、整数规划、多元规划、线性规划、整数规划、多元规划、二次规划二次规划等。竞赛中很多问题都和数学规划相关，能够说不少模型都能够归结为一组不等式作为约束条件、几个函数表示式作为目标函数问题，碰到这类问题，求解就是关键了。所以列举出规划后用Lindo、Lingo等软件来进行处理比较方便，所以还需要熟悉这两个软件。10/10/第10页Algorithms 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 题表达了分治算法题表达了分治算法数学建模竞赛惯用算法数学建模竞赛惯用算法(5)5.计算机算法设计中问题计算机算法设计包含很多内容：动态规划、回溯搜动态规划、回溯搜索、分治算法、分枝定界索、分治算法、分枝定界等计算机算法.这方面问题和ACM程序设计竞赛中问题类似，可看一下与计算机算法相关书。10/10/第12页Algorithms in Mathematical ModelingGenetic Algorithm13o97年A题用模拟退火算法oB题用神经网络分类算法oB题这种难题也能够使用神经网络o美国89年A题也和BP算法相关系o美国B题伽马刀问题也是当前研究课题，当前算法最正确是遗传算法。数学建模竞赛惯用算法数学建模竞赛惯用算法(6)6.最优化理论三大非经典算法:模拟退火法(SA)、神经网络(NN)、遗传算法(GA)近几年赛题越来越复杂，很多问题没有什么很好模型能够借鉴，于是这三类算法很多时候能够派上用场。10/10/第13页Algorithms in Mathematical ModelingGenetic Algorithm1497 年年A 题、题、99 年年B 题都能够题都能够用网格法搜索用网格法搜索数学建模竞赛惯用算法数学建模竞赛惯用算法(7)网格算法和穷举法一样，只是网格法是连续问题穷举。这类算法运算量较大。7.网格算法和穷举算法这种方法最好在运算速度较快计算机中进行，还有要用高级语言来做，最好不要用MATLAB做网格，不然会算很久。10/10/第14页Algorithms in Mathematical ModelingGenetic Algorithm15很多问题都是实际来，数据能够是连续，而计算机只能处理离散数据，所以需要将连续问题进行将连续问题进行离散化处理后再用计算机求解离散化处理后再用计算机求解。比如差分代替微分、求和代替积分等思想都是把连续问题离散化惯用方法。数学建模竞赛惯用算法数学建模竞赛惯用算法(8)8.连续问题离散化方法10/10/第15页Algorithms in Mathematical ModelingGenetic Algorithm16数值分析研究各种求解数学问题数值计算方法求解数学问题数值计算方法，尤其是适合于计算机实现方法与算法。数学建模竞赛惯用算法数学建模竞赛惯用算法(9)9.数值分析方法它主要内容包含函数数值迫近、数值微分与数函数数值迫近、数值微分与数值积分、非线性方程数值解法、数值代数、常微分方值积分、非线性方程数值解法、数值代数、常微分方程数值解程数值解等。数值分析是计算数学一个主要分支，把理论与计算紧密结合,是当代科学计算基础。MATLAB等数学软件中已经有很多数值分析函数能够直接调用。10/10/第16页Algorithms in Mathematical ModelingGenetic Algorithm17oA题中需要你会读BMP图象o98年美国A题需要你知道三维插值计算oB题要求更高，不但需要编程计算还要进行处理数学建模竞赛惯用算法数学建模竞赛惯用算法(10)10.图象处理算法赛题中有一类问题与图形相关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形怎样展示以及怎样处理就是需要处理问题，通常使用MATLAB进行处理。数模论文中也有很多图片需要展示，处理这类问题要熟悉MATLAB图形图像工具箱。10/10/第17页Algorithms in Mathematical ModelingGenetic Algorithm18三个孩子年纪三个孩子年纪(1)两个多年未见朋友相遇，聊了很多事情。A：既然你是数学教授，那你帮我算这个题，今天是个特殊日子：我三个儿子都在今天庆贺生日！那么你能算出他们都有多大吗？B：好，但你得跟我讲讲他们情况。A：好，我给你一些提醒，他们三个年纪之积是36.B：很好，但我还需要更多提醒。10/10/第18页Algorithms in Mathematical ModelingGenetic Algorithm19三个孩子年纪三个孩子年纪(2)A：我大儿子眼睛是蓝色。B考虑了一下说，不过，我还有一点信息来处理你这个难题。B：哦，够了，B给出了正确答案，即三个小孩年纪。A：他们三个年纪之和等于那幢房子窗户个数。A指着对面一幢房子说。10/10/第19页Algorithms in Mathematical ModelingGenetic Algorithm20三个孩子年纪三个孩子年纪(3)依据对话信息，用搜索方法来解此问题。信息信息1:三个小孩年纪之积为三个小孩年纪之积为36只有以下8种可能，搜索范围降低至8种情况:o第一个小孩年纪36181299664o第二个小孩年纪12342633o第三个小孩年纪1111212310/10/第20页Algorithms in Mathematical ModelingGenetic Algorithm21三个孩子年纪三个孩子年纪(4)信息信息2:三个小孩年纪之和等于窗户数三个小孩年纪之和等于窗户数o第一个小孩年纪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智能优化算法智能优化算法智能优化算法智能优化算法又称为当代启发式算法当代启发式算法，是一种含有全局优化性能、通用性强、且适合于并行处理算法。这种算法普通含有严密理论依据,而不是单纯凭借教授经验，理论上能够在一定时间内找到最优解或近似最优解。10/10/第22页Algorithms in Mathematical ModelingGenetic Algorithm23惯用智能优化算法惯用智能优化算法遗传算法遗传算法GeneticAlgorithm，简称GA模拟退火算法模拟退火算法SimulatedAnnealing，简称SA禁忌搜索算法禁忌搜索算法TabuSearch，简称TS 10/10/第23页Algorithms in Mathematical ModelingGenetic Algorithm24智能优化算法特点智能优化算法特点它们共同特点：都是从任一解出发，按照某种机制，以一定概率在整个求解空间中探索最优解。因为它们能够把搜索空间扩展到整个问题空间，因而含有全局优化性能。10/10/第24页Algorithms in Mathematical ModelingGenetic Algorithm25遗传算法遗传算法(Genetic Algorithm)进化算法(EvolutionaryAlgorithm)10/10/第25页Algorithms in Mathematical ModelingGenetic Algorithm26遗传算法遗传算法(GA)Darwin(1859):“物竟天择，适者生存物竟天择，适者生存”JohnHolland(universityofMichigan,1975)Adaptation in Natural and Artificial System遗传算法作为一个有效工具，已广泛地应用于最优遗传算法作为一个有效工具，已广泛地应用于最优化问题求解之中化问题求解之中。遗传算法是一个基于自然群体遗传进化机制自适应遗传算法是一个基于自然群体遗传进化机制自适应全局优化概率搜索算法。全局优化概率搜索算法。它摒弃了传统搜索方式，模拟自然界生物进化过程，采取人工方式对目标空间进行随机化搜索。10/10/第26页Algorithms in Mathematical ModelingGenetic Algorithm27遗传算法模拟自然选择和自然遗传过程中发生繁殖、交叉和基因突变繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优个体，利用遗传算子遗传算子(选择、交叉和变选择、交叉和变异异)对这些个体进行组合，产生新一代候选解群，重复此过程，直到满足某种收敛指标为止。遗传算法搜索机制遗传算法搜索机制10/10/第27页Algorithms in Mathematical ModelingGenetic Algorithm28局部局部局部局部全局全局全局全局遗传算法遗传算法(GA)10/10/第28页Algorithms in Mathematical ModelingGenetic 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 oneDead 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 in Mathematical ModelingGenetic Algorithm33适者生存适者生存(SurvivaloftheFittest)GA主要采取进化规则是主要采取进化规则是“适者生存适者生存”很好解保留，较差解淘汰很好解保留，较差解淘汰遗传算法遗传算法(GA)10/10/第33页Algorithms in Mathematical ModelingGenetic Algorithm34生物进化与遗传算法对应关系生物进化与遗传算法对应关系生物进化生物进化遗传算法遗传算法适者生存适应函数值最大解被保留概率最大个体问题一个解染色体解编码基因编码元素群体被选定一组解种群依据适应函数选择一组解交叉以一定方式由双亲产生后代过程变异编码一些分量发生改变过程环境适应函数10/10/第34页Algorithms in Mathematical ModelingGenetic Algorithm35遗传算法基本操作遗传算法基本操作选择选择(selection):依据各个个体适应值，按照一定规则或方法，从第t代群体P(t)中选择出一些优良个体遗传到下一代群体P(t+1)中。交叉交叉(crossover):将群体P(t)内各个个体随机搭配成对，对每一个个体，以某个概率Pc(称为交叉概率，crossvoerrate)交换它们之间部分染色体。变异变异(mutation):对群体P(t)中每一个个体，以某一概率Pm(称为变异概率，mutationrate)改变某一个或一些基因座上基因值为其它等位基因。10/10/第35页Algorithms in Mathematical ModelingGenetic Algorithm36怎样设计遗传算法怎样设计遗传算法怎样进行编码？怎样进行编码？怎样产生初始种群？怎样产生初始种群？怎样定义适应函数？怎样定义适应函数？怎样进行遗传操作怎样进行遗传操作(复制、交叉、变异复制、交叉、变异)？怎样产生下一代种群？怎样产生下一代种群？怎样定义停顿准则怎样定义停顿准则？10/10/第36页Algorithms in Mathematical ModelingGenetic Algorithm37编码编码(Coding)表现型空间编码(Coding)解码(Decoding)基因型空间=0,1L011101001010001001100100101001000110/10/第37页Algorithms in Mathematical ModelingGenetic Algorithm38选择选择(Selection)选择选择(复制复制)操作把当前种群染色体按与适应值成正百分操作把当前种群染色体按与适应值成正百分比概率复制到新种群中比概率复制到新种群中 主要思想主要思想:适应值较高染色体体有较大选择适应值较高染色体体有较大选择(复制复制)机会机会实现实现1：”轮盘赌轮盘赌”选择选择(Roulette wheel selection)将种群中全部染色体适应值相加求总和，染色体适应值将种群中全部染色体适应值相加求总和，染色体适应值按其百分比转化为选择概率按其百分比转化为选择概率Ps产生一个在产生一个在0与总和之间随机数与总和之间随机数m从种群中编号为从种群中编号为1染色体开始，将其适应值与后续染色染色体开始，将其适应值与后续染色体适应值相加，直到累加和等于或大于体适应值相加，直到累加和等于或大于m10/10/第38页Algorithms in Mathematical ModelingGenetic Algorithm39选择选择(Selection)设种群规模为Nxi是i为种群中第i个染色体AC1/6=17%3/6=50%B2/6=33%fitness(A)=3fitness(B)=1fitness(C)=2染色体xi被选概率10/10/第39页Algorithms in Mathematical ModelingGenetic Algorithm40选择选择(Selection)染色体适应值和所占百分比染色体适应值和所占百分比轮盘赌选择10/10/第40页Algorithms in Mathematical ModelingGenetic Algorithm41选择选择(Selection)随机数23491338627所选号码262514所选染色体110000001111000011000111010010染色体编号123456染色体011101100000100100100110000011适应度81525128被选概率0.160.30.040.10.240.16适应度累计82325304250染色体被选概率被选染色体10/10/第41页Algorithms in Mathematical ModelingGenetic Algorithm42选择选择(Selection)轮轮盘盘上上片片分分配配给给群群体体染染色色体体，使使得得每每一一个个片片大大小小与与对对于于染染色色体体适适应值成百分比应值成百分比从从群群体体中中选选择择一一个个染染色色体体可可视视为为旋旋转转一一个个轮轮盘盘，当当轮轮盘盘停停顿顿时时，指针所指片对于染色体就时要选染色体。指针所指片对于染色体就时要选染色体。模拟模拟“轮盘赌轮盘赌”算法算法：(1)r=random(0,1)，s=0，i=0；(2)假如假如sr，则转，则转(4)；(3)s=s+p(xi)，i=i+1,转转(2)(4)xi即为被选中染色体，输出即为被选中染色体，输出I(5)结束结束10/10/第42页Algorithms in Mathematical ModelingGenetic Algorithm43选择选择(Selection)其它选择法其它选择法：随机遍历抽样随机遍历抽样(Stochastic universal sampling)局部选择局部选择(Local selection)截断选择截断选择(Truncation selection)竞标赛选择竞标赛选择(Tournament selection)特点特点：选择操作得到新群体称为交配池，交配池是当前代和下一代之间中间群体，其规模为初始群体规模。选择操作作用效果是提升了群体平均适应值(低适应值个体趋于淘汰，高适应值个体趋于选择)，但这也损失了群体多样性多样性。选择操作没有产生新个体，群体中最好个体适应值不会改变。10/10/第43页Algorithms in Mathematical ModelingGenetic Algorithm44交叉交叉(crossover,Recombination)遗传交叉(杂交、交配、有性重组)操作发生在两个染色体之间，由两个被称之为双亲父代染色体，经杂交以后，产生两个含有双亲部分基因新染色体，从而检测搜索空间中新点。选择(复制)操作每次作用在一个染色体上，而交叉操作每次作用在从交配池中随机选取两个个体上(交叉概率Pc)。交叉产生两个子染色体，他们与其父代不一样，且彼此不一样,每个子染色体都带有双亲染色体遗传基因。10/10/第44页Algorithms in Mathematical ModelingGenetic Algorithm45单点交叉单点交叉(1-point crossover)在双亲父代染色体中随机产生一个交叉点位置在双亲父代染色体中随机产生一个交叉点位置在交叉点位置分离双亲染色体在交叉点位置分离双亲染色体交换交叉点位置右边基因码产生两个子代染色体交换交叉点位置右边基因码产生两个子代染色体交叉概率交叉概率Pc 普通范围为普通范围为(60%,90%)，平均约，平均约80%1 11 11 11 11 11 11 11 1父代父代父代父代1 11 11 11 10 00 00 00 00 00 00 00 00 00 00 00 0子代子代子代子代1 11 11 11 10 00 00 00 00 00 00 00 00 00 00 00 01 11 11 11 11 11 11 11 1交叉点位置交叉点位置交叉点位置交叉点位置10/10/第45页Algorithms in Mathematical ModelingGenetic Algorithm46交叉交叉(crossover,Recombination)单点交叉操作能够产生与父代染色体完全不一样子代染色体；它不会改变父代染色体中相同基因。但当双亲染色体相同时，交叉操作是不起作用。假如交叉概率Pc50%,则交配池中50%染色体(二分之一染色体)将进行交叉操作，余下50%染色体进行选择(复制)操作。GA利用选择和交叉操作能够产生含有更高平均适应值和更加好染色体群体10/10/第46页Algorithms in Mathematical ModelingGenetic Algorithm47变异变异(Mutation)以变异概率Pm改变染色体某一个基因,当以二进制编码时，变异基因由0变成1，或者由1变成0。变异概率Pm 普通介于1/种群规模与1/染色体长度之间，平均约1-2%1 11 10 01 10 01 10 00 0父代父代父代父代0 01 10 01 10 01 10 01 1子代子代子代子代变异基因变异基因变异基因变异基因变异基因变异基因变异基因变异基因10/10/第47页Algorithms in Mathematical ModelingGenetic Algorithm48变异变异(Mutation)比起选择和交叉操作，变异操作是GA中次要操作，但它在恢复群体中失去多样性多样性方面含有潜在作用。在GA执行开始阶段，染色体中一个特定位上值1可能与好性能紧密联络，即搜索空间中一些初始染色体在那个位上值1可能一致产生高适应值。因为越高适应值与染色体中那个位上值1相联系，选择操作就越会使群体遗传多样性损失。等抵达一定程度时，值0会从整个群体中那个位上消失，然而全局最优解可能在染色体中那个位上为0。假如搜索范围缩小到实际包含全局最优解那部分搜索空间，在那个位上值0就可能恰好是抵达全局最优解所需要。10/10/第48页Algorithms in Mathematical ModelingGenetic Algorithm49适应函数适应函数(Fitness Function)GA在搜索中不依靠外部信息，仅以适应函数为依据，利用群体中每个染色体(个体)适应值来进行搜索。以染色体适应值大小来确定该染色体被遗传到下一代群体中概率。染色体适应值越大，该染色体被遗传到下一代概率也越大；反之，染色体适应值越小，该染色体被遗传到下一代概率也越小。所以适应函数选取至关主要，直接影响到GA收敛速度以及能否找到最优解。群体中每个染色体都需要计算适应值适应函数普通由目标函数变换而成10/10/第49页Algorithms in Mathematical ModelingGenetic Algorithm50适应函数适应函数(Fitness Function)适应函数常见形式：适应函数常见形式：直接将目标函数转化为适应函数直接将目标函数转化为适应函数若目标函数为最大化问题：Fitness(f(x)=f(x)若目标函数为最小化问题：Fitness(f(x)=-f(x)缺点:(1)可能不满足轮盘赌选择中概率非负要求(2)一些代求解函数值分布上相差很大，由此得到评价适应值可能不利于表达群体评价性能，影响算法性能。10/10/第50页Algorithms in Mathematical ModelingGenetic Algorithm51适应函数适应函数(Fitness Function)界限结构法界限结构法 目标函数为最大化问题其中Cmin为f(x)最小预计值 目标函数为最小化问题其中Cmaxn为f(x)最大预计值10/10/第51页Algorithms in Mathematical ModelingGenetic Algorithm52停顿准则停顿准则(Termination Criteria)种群中个体最大适应值超出预设定值种群中个体平均适应值超出预设定值种群中个体进化代数超出预设定值10/10/第52页Algorithms in Mathematical ModelingGenetic Algorithm53基本步骤基本步骤(Step by Step)(1)随机产生初始种群;(2)计算种群体中每个个体适应度值,判断是否满足停顿条件，若不满足，则转第(3)步,不然转第(6)步;(3)按由个体适应值所决定某个规则选择将进入下一代个体;(4)按交叉概率Pc进行交叉操作,生产新个体;(5)按变异概率Pm进行变异操作,生产新个体;(6)输出种群中适应度值最优染色体作为问题满意解或最优解。10/10/第53页Algorithms in Mathematical ModelingGenetic Algorithm54流程图流程图(Flow Chart)10/10/第54页Algorithms in Mathematical ModelingGenetic Algorithm55基本遗传算法基本遗传算法基本遗传算法（SimpleGeneticAlgorithms,简称SGA）是一个统一最基本遗传算法，它只使用选择、交叉、变异这三种基本遗传算子，其遗传进化操作过程简单，轻易了解，是其它一些遗传算法雏形和基础，它不但给各种遗传算法提供了一个基本框架，同时也含有一定应用价值。10/10/第55页Algorithms in Mathematical ModelingGenetic Algorithm56SGA伪码描述伪码描述ProcedureGeneticAlgorithmbeginbegint=0;初始化 P(t);计算 P(t)适应值;while(不满足停顿准则)do begin t=t+1;从P(t-1)中选择 P(t);%selection 重组 P(t);%crossover and mutation 计算 P(t)适应值;end end10/10/第56页Algorithms in Mathematical ModelingGenetic Algorithm57遗传算法应用遗传算法应用函数优化函数优化函数优化是遗传算法经典应用领域，也是对遗传算法进行性能测试评价惯用算例。对于一些非线性、多模型、多目标函数优化问题，用其它优化方法较难求解，而遗传算法却能够方便地得到很好结果。遗传算法提供了一个求解复杂系统优化问题通用框架，它不依赖于问题详细领域，对问题种类有很强鲁棒性，所以广泛应用于很多学科。下面列举一些遗传算法主要应用领域。10/10/第57页Algorithms in Mathematical ModelingGenetic Algorithm58遗传算法应用遗传算法应用组合优化组合优化遗传算法是寻求组合优化问题满意解最正确工具之一，实践证实，遗传算法对于组合优化问题中NP完全问题非常有效。比如，遗传算法已经在求解旅行商问题(Traveling Salesman Problem,TSP)、背包问题(Knapsack Problem)、装箱问题(Bin Packing Problem)等方面得到成功应用。生产调度问题生产调度问题生产调度问题在很多情况下所建立起来数学模型难以准确求解，即使经过一些简化之后能够进行求解也会因简化得太多而使求解结果与实际相差太远。现在遗传算法已经成为处理复杂调度问题有效工具。10/10/第58页Algorithms in Mathematical ModelingGenetic Algorithm59遗传算法应用遗传算法应用自动控制自动控制遗传算法已经在自动控制领域中得到了很好应用，比如基于遗传算法含糊控制器优化设计、基于遗传算法参数辨识、基于遗传算法含糊控制规则学习、利用遗传算法进行人工神经网络结构优化设计和权值学习等。机器人智能控制机器人智能控制机器人是一类复杂难以准确建模人工系统，而遗传算法起源就来自于对人工自适应系统研究，所以机器人智能控制自然成为遗传算法一个主要应用领域。10/10/第59页Algorithms in Mathematical ModelingGenetic Algorithm60遗传算法应用遗传算法应用图象处理和模式识别图象处理和模式识别图像处理和模式识别是计算机视觉中一个主要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可防止地存在一些误差，这些误差会影响图像处理效果。怎样使这些误差最小是使计算机视觉到达实用化主要要求，遗传算法在这些图像处理中优化计算方面得到了很好应用。人工生命人工生命人工生命是用计算机、机械等人工媒体模拟或结构出含有自然生物系统特有行为人造系统。自组织能力和自学习能力是人工生命两大主要特征。人工生命与遗传算法有着亲密关系，基于遗传算法进化模型是研究人工生命现象主要理论基础。10/10/第60页Algorithms in Mathematical ModelingGenetic Algorithm61遗传算法应用遗传算法应用遗传程序设计遗传程序设计Koza发展了遗传程序设计概念，他使用了以LISP语言所表示编码方法，基于对一个树形结构所进行遗传操作来自动生成计算机程序。机器学习机器学习 基于遗传算法机器学习，在很多领域中都得到了应用。比如基于遗传算法机器学习可用来调整人工神经网络连接权，也能够用于人工神经网络网络结构优化设计。分类器系统在多机器人路径规划系统中得到了成功应用。10/10/第61页Algorithms in Mathematical ModelingGenetic Algorithm62SGA实例实例1：函数最值：函数最值SGA参数:编码方式:二进制码 e.g.00000e.g.000000;0;01101 01101 13;1111113;111113131种群规模:4随机初始群体“转盘赌”选择一点杂交,二进制变异 求函数f(x)=x2最大值，x为自然数且0 x31.o手工方式完成演示SGA过程10/10/第62页Algorithms in Mathematical ModelingGenetic Algorithm63SGA实例实例1 max x2 :选择操作选择操作10/10/第63页Algorithms in Mathematical ModelingGenetic Algorithm64SGA实例实例1 max x2 :交叉操作交叉操作10/10/第64页Algorithms in Mathematical ModelingGenetic Algorithm65SGA实例实例1 max x2 :变异操作变异操作10/10/第65页Algorithms in Mathematical ModelingGenetic Al