数学建模中的常用算法市公开课获奖课件省名师优质课赛课一等奖课件.ppt

数学建模中惯用算法成都信息工程学院计算科学系胡建成-5-201/11010/6/数学建模竞赛网上资源数学建模竞赛网上资源CUMCM网站:http:/ MCM和ICM网站:http:/中国数学建模:http:/中科大建模网站:http:/MATLAB网站:http:/GOOGLE大学2/11010/6/数学建模竞赛中算法数学建模竞赛中算法(1)93A 非线性交调频率设计非线性交调频率设计:拟合、规划拟合、规划93B 足球队排名次足球队排名次:矩阵论、图论、层次分析法、矩阵论、图论、层次分析法、整数规划整数规划94A 逢山开路逢山开路:图论、插值、动态规划图论、插值、动态规划94B 锁具装箱问题锁具装箱问题:图论、组合数学图论、组合数学95A 飞行管理问题飞行管理问题:非线性规划、线性规划非线性规划、线性规划95B 天车与冶炼炉作业调度天车与冶炼炉作业调度:非线性规划、动态规非线性规划、动态规划、层次分析法、划、层次分析法、PETRI方法、图论方法、排队论方方法、图论方法、排队论方法法96A 最优打鱼策略最优打鱼策略：微分方程、积分、非线性规划微分方程、积分、非线性规划3/11010/6/96B 节水洗衣机节水洗衣机：非线性规划非线性规划97A 零件参数设计零件参数设计：微积分、非线性规划、随机模拟微积分、非线性规划、随机模拟97B 截断切割截断切割：组合优化、几何变换、枚举、蒙特卡组合优化、几何变换、枚举、蒙特卡罗、递归、最短路罗、递归、最短路98A 投资收益与风险投资收益与风险：线性规划、非线性规划线性规划、非线性规划98B 灾情巡视灾情巡视：最小生成树、最小生成树、Hamilton圈、旅行商圈、旅行商问题问题99A 自动化车床自动化车床：积分、概率分布、随机模拟、分布积分、概率分布、随机模拟、分布拟合度检验拟合度检验数学建模竞赛中算法数学建模竞赛中算法(2)4/11010/6/99B 钻井布局钻井布局：几何变换、枚举、最大完全子图、几何变换、枚举、最大完全子图、混合整数规划混合整数规划00A DNA分类分类：神经网络、最小二乘拟合、统计分神经网络、最小二乘拟合、统计分类类00B 管道订购管道订购：最短路、二次规划最短路、二次规划01A 血管三维重建血管三维重建：数据挖掘、曲面重建与拟合数据挖掘、曲面重建与拟合01B 公交车调度公交车调度：非线性规划非线性规划02A 车灯光源优化设计车灯光源优化设计：最优化最优化02B 彩票中数学彩票中数学：概率与优化概率与优化数学建模竞赛中算法数学建模竞赛中算法(3)5/11010/6/MATLABMapleMathematicaLindoLingo SASSPSSC&C+FortranPascal数学建模惯用软件数学建模惯用软件6/11010/6/1.蒙特卡罗方法(Monte-Carlo方法,MC)数学建模竞赛惯用算法数学建模竞赛惯用算法(1)该算法又称计算机随机性模拟方法计算机随机性模拟方法，也称统计试验统计试验方法方法。MC方法是一个基于“随机数”计算方法，能够比较逼真地描述事物特点及物理试验过程，处理一些数值方法难以处理问题。MC方法雏型能够追溯到十九世纪后期蒲丰随机投针试验，即著名蒲丰问题蒲丰问题。MC方法经过计算机仿真(模拟)处理问题，同时也能够经过模拟来检验自己模型正确性，是比赛中经常使用方法。7/11010/6/o97年A题每个零件都有自己标定值，也都有自o己容差等级，而求解最优组合方案将要面对着是一o个极其复杂公式和108种容差选取方案，根本不可能去求o解析解，那怎样去找到最优方案呢？随机性模拟搜索最o优方案就是其中一个方法，在每个零件可行区间中按o照正态分布随机选取一个标定值和选取一个容差值作为o一个方案，然后经过蒙特卡罗算法仿真出大量方案，从o中选取一个最正确。oB题关于彩票第二问，要求设计一个更加好方o案，首先方案优劣取决于很多复杂原因，一样不可能o刻画出一个模型进行求解，只能靠随机仿真模拟。数学建模竞赛惯用算法数学建模竞赛惯用算法8/11010/6/98 年美国赛年美国赛A 题题 生物组织切片三维插值处理生物组织切片三维插值处理94 年年A 题逢山开路题逢山开路 山体海拔高度插值计算山体海拔高度插值计算数学建模竞赛惯用算法数学建模竞赛惯用算法(2)2.数据拟合、参数预计、插值等数据处理算法比赛中通常会碰到大量数据需要处理，而处理数据关键就在于这些算法，通常使用MATLAB作为工具。与图形处理相关问题很多与拟合相关系。这类问题在MATLAB中有很多函数能够调用，只有熟悉MATLAB，这些方法才能用好。9/11010/6/98年年B 题题 用很多不等式完全能够把问题刻画清楚用很多不等式完全能够把问题刻画清楚数学建模竞赛惯用算法数学建模竞赛惯用算法(3)3.规划类问题算法这类问题主要有线性规划、整数规划、多元规划、线性规划、整数规划、多元规划、二次规划二次规划等。竞赛中很多问题都和数学规划相关，能够说不少模型都能够归结为一组不等式作为约束条件、几个函数表示式作为目标函数问题，碰到这类问题，求解就是关键了。所以列举出规划后用Lindo、Lingo等软件来进行处理比较方便，所以还需要熟悉这两个软件。10/11010/6/o98年B题、B题、95年锁具装箱等问题表达了图论问题主要性。数学建模竞赛惯用算法数学建模竞赛惯用算法(4)4.图论问题这类问题算法有很多，包含：Dijkstra、Floyd、Prim、Bellman-Ford，最大流，二分匹配，最大流，二分匹配等问题。11/11010/6/92 年年B 题用分枝定界法题用分枝定界法97 年年B 题是经典动态规划问题题是经典动态规划问题98 年年B 题表达了分治算法题表达了分治算法数学建模竞赛惯用算法数学建模竞赛惯用算法(5)5.计算机算法设计中问题计算机算法设计包含很多内容：动态规划、回溯搜动态规划、回溯搜索、分治算法、分枝定界索、分治算法、分枝定界等计算机算法.这方面问题和ACM程序设计竞赛中问题类似，可看一下与计算机算法相关书。12/11010/6/o97年A题用模拟退火算法oB题用神经网络分类算法oB题这种难题也能够使用神经网络o美国89年A题也和BP算法相关系o美国B题伽马刀问题也是当前研究课题，当前算法最正确是遗传算法。数学建模竞赛惯用算法数学建模竞赛惯用算法(6)6.最优化理论三大非经典算法:模拟退火法(SA)、神经网络(NN)、遗传算法(GA)近几年赛题越来越复杂，很多问题没有什么很好模型能够借鉴，于是这三类算法很多时候能够派上用场。13/11010/6/97 年年A 题、题、99 年年B 题都能够题都能够用网格法搜索用网格法搜索数学建模竞赛惯用算法数学建模竞赛惯用算法(7)网格算法和穷举法一样，只是网格法是连续问题穷举。这类算法运算量较大。7.网格算法和穷举算法这种方法最好在运算速度较快计算机中进行，还有要用高级语言来做，最好不要用MATLAB做网格，不然会算很久。14/11010/6/很多问题都是实际来，数据能够是连续，而计算机只能处理离散数据，所以需要将连续问题进行将连续问题进行离散化处理后再用计算机求解离散化处理后再用计算机求解。比如差分代替微分、求和代替积分等思想都是把连续问题离散化惯用方法。数学建模竞赛惯用算法数学建模竞赛惯用算法(8)8.连续问题离散化方法15/11010/6/数值分析研究各种求解数学问题数值计算方法求解数学问题数值计算方法，尤其是适合于计算机实现方法与算法。数学建模竞赛惯用算法数学建模竞赛惯用算法(9)9.数值分析方法它主要内容包含函数数值迫近、数值微分与数函数数值迫近、数值微分与数值积分、非线性方程数值解法、数值代数、常微分方值积分、非线性方程数值解法、数值代数、常微分方程数值解程数值解等。数值分析是计算数学一个主要分支，把理论与计算紧密结合,是当代科学计算基础。MATLAB等数学软件中已经有很多数值分析函数能够直接调用。16/11010/6/oA题中需要你会读BMP图象o98年美国A题需要你知道三维插值计算oB题要求更高，不但需要编程计算还要进行处理数学建模竞赛惯用算法数学建模竞赛惯用算法(10)10.图象处理算法赛题中有一类问题与图形相关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形怎样展示以及怎样处理就是需要处理问题，通常使用MATLAB进行处理。数模论文中也有很多图片需要展示，处理这类问题要熟悉MATLAB图形图像工具箱。17/11010/6/三个孩子年纪三个孩子年纪(1)两个多年未见朋友相遇，聊了很多事情。A：既然你是数学教授，那你帮我算这个题，今天是个特殊日子：我三个儿子都在今天庆贺生日！那么你能算出他们都有多大吗？B：好，但你得跟我讲讲他们情况。A：好，我给你一些提醒，他们三个年纪之积是36.B：很好，但我还需要更多提醒。18/11010/6/三个孩子年纪三个孩子年纪(2)A：我大儿子眼睛是蓝色。B考虑了一下说，不过，我还有一点信息来处理你这个难题。B：哦，够了，B给出了正确答案，即三个小孩年纪。A：他们三个年纪之和等于那幢房子窗户个数。A指着对面一幢房子说。19/11010/6/三个孩子年纪三个孩子年纪(3)依据对话信息，用搜索方法来解此问题。信息信息1:三个小孩年纪之积为三个小孩年纪之积为36只有以下8种可能，搜索范围降低至8种情况:o第一个小孩年纪36181299664o第二个小孩年纪12342633o第三个小孩年纪1111212320/11010/6/三个孩子年纪三个孩子年纪(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)21/11010/6/智能优化算法智能优化算法智能优化算法智能优化算法又称为当代启发式算法当代启发式算法，是一种含有全局优化性能、通用性强、且适合于并行处理算法。这种算法普通含有严密理论依据,而不是单纯凭借教授经验，理论上能够在一定时间内找到最优解或近似最优解。22/11010/6/惯用智能优化算法惯用智能优化算法遗传算法遗传算法GeneticAlgorithm，简称GA模拟退火算法模拟退火算法SimulatedAnnealing，简称SA禁忌搜索算法禁忌搜索算法TabuSearch，简称TS 23/11010/6/智能优化算法特点智能优化算法特点它们共同特点：都是从任一解出发，按照某种机制，以一定概率在整个求解空间中探索最优解。因为它们能够把搜索空间扩展到整个问题空间，因而含有全局优化性能。24/11010/6/遗传算法遗传算法(Genetic Algorithm)进化算法(EvolutionaryAlgorithm)25/11010/6/遗传算法遗传算法(GA)Darwin(1859):“物竟天择，适者生存物竟天择，适者生存”JohnHolland(universityofMichigan,1975)Adaptation in Natural and Artificial System遗传算法作为一个有效工具，已广泛地应用于最优遗传算法作为一个有效工具，已广泛地应用于最优化问题求解之中化问题求解之中。遗传算法是一个基于自然群体遗传进化机制自适应遗传算法是一个基于自然群体遗传进化机制自适应全局优化概率搜索算法。全局优化概率搜索算法。它摒弃了传统搜索方式，模拟自然界生物进化过程，采取人工方式对目标空间进行随机化搜索。26/11010/6/遗传算法模拟自然选择和自然遗传过程中发生繁殖、交叉和基因突变繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优个体，利用遗传算子遗传算子(选择、交叉和变选择、交叉和变异异)对这些个体进行组合，产生新一代候选解群，重复此过程，直到满足某种收敛指标为止。遗传算法搜索机制遗传算法搜索机制27/11010/6/局部局部局部局部全局全局全局全局遗传算法遗传算法(GA)28/11010/6/We 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代29/11010/6/Dead oneDead oneNew oneNew one遗传算法遗传算法(GA)GA-第1代30/11010/6/Not at the top,Not at the topCome Up!Come Up!遗传算法遗传算法(GA)GA-第?代31/11010/6/I am the I am the BESTBEST!遗传算法遗传算法(GA)GA-第N代32/11010/6/适者生存适者生存(SurvivaloftheFittest)GA主要采取进化规则是主要采取进化规则是“适者生存适者生存”很好解保留，较差解淘汰很好解保留，较差解淘汰遗传算法遗传算法(GA)33/11010/6/生物进化与遗传算法对应关系生物进化与遗传算法对应关系生物进化生物进化遗传算法遗传算法适者生存适应函数值最大解被保留概率最大个体问题一个解染色体解编码基因编码元素群体被选定一组解种群依据适应函数选择一组解交叉以一定方式由双亲产生后代过程变异编码一些分量发生改变过程环境适应函数34/11010/6/遗传算法基本操作遗传算法基本操作选择选择(selection):依据各个个体适应值，按照一定规则或方法，从第t代群体P(t)中选择出一些优良个体遗传到下一代群体P(t+1)中。交叉交叉(crossover):将群体P(t)内各个个体随机搭配成对，对每一个个体，以某个概率Pc(称为交叉概率，crossvoerrate)交换它们之间部分染色体。变异变异(mutation):对群体P(t)中每一个个体，以某一概率Pm(称为变异概率，mutationrate)改变某一个或一些基因座上基因值为其它等位基因。35/11010/6/怎样设计遗传算法怎样设计遗传算法怎样进行编码？怎样进行编码？怎样产生初始种群？怎样产生初始种群？怎样定义适应函数？怎样定义适应函数？怎样进行遗传操作怎样进行遗传操作(复制、交叉、变异复制、交叉、变异)？怎样产生下一代种群？怎样产生下一代种群？怎样定义停顿准则怎样定义停顿准则？36/11010/6/编码编码(Coding)表现型空间编码(Coding)解码(Decoding)基因型空间=0,1L011101001010001001100100101001000137/11010/6/选择选择(Selection)选择选择(复制复制)操作把当前种群染色体按与适应值成正百分操作把当前种群染色体按与适应值成正百分比概率复制到新种群中比概率复制到新种群中 主要思想主要思想:适应值较高染色体体有较大选择适应值较高染色体体有较大选择(复制复制)机会机会实现实现1：”轮盘赌轮盘赌”选择选择(Roulette wheel selection)将种群中全部染色体适应值相加求总和，染色体适应值将种群中全部染色体适应值相加求总和，染色体适应值按其百分比转化为选择概率按其百分比转化为选择概率Ps产生一个在产生一个在0与总和之间随机数与总和之间随机数m从种群中编号为从种群中编号为1染色体开始，将其适应值与后续染色染色体开始，将其适应值与后续染色体适应值相加，直到累加和等于或大于体适应值相加，直到累加和等于或大于m38/11010/6/选择选择(Selection)设种群规模为Nxi是i为种群中第i个染色体AC1/6=17%3/6=50%B2/6=33%fitness(A)=3fitness(B)=1fitness(C)=2染色体xi被选概率39/11010/6/选择选择(Selection)染色体适应值和所占百分比染色体适应值和所占百分比轮盘赌选择40/11010/6/选择选择(Selection)随机数23491338627所选号码262514所选染色体110000001111000011000111010010染色体编号123456染色体011101100000100100100110000011适应度81525128被选概率0.160.30.040.10.240.16适应度累计82325304250染色体被选概率被选染色体41/11010/6/选择选择(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)结束结束42/11010/6/选择选择(Selection)其它选择法其它选择法：随机遍历抽样随机遍历抽样(Stochastic universal sampling)局部选择局部选择(Local selection)截断选择截断选择(Truncation selection)竞标赛选择竞标赛选择(Tournament selection)特点特点：选择操作得到新群体称为交配池，交配池是当前代和下一代之间中间群体，其规模为初始群体规模。选择操作作用效果是提升了群体平均适应值(低适应值个体趋于淘汰，高适应值个体趋于选择)，但这也损失了群体多样性多样性。选择操作没有产生新个体，群体中最好个体适应值不会改变。43/11010/6/交叉交叉(crossover,Recombination)遗传交叉(杂交、交配、有性重组)操作发生在两个染色体之间，由两个被称之为双亲父代染色体，经杂交以后，产生两个含有双亲部分基因新染色体，从而检测搜索空间中新点。选择(复制)操作每次作用在一个染色体上，而交叉操作每次作用在从交配池中随机选取两个个体上(交叉概率Pc)。交叉产生两个子染色体，他们与其父代不一样，且彼此不一样,每个子染色体都带有双亲染色体遗传基因。44/11010/6/单点交叉单点交叉(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交叉点位置交叉点位置交叉点位置交叉点位置45/11010/6/交叉交叉(crossover,Recombination)单点交叉操作能够产生与父代染色体完全不一样子代染色体；它不会改变父代染色体中相同基因。但当双亲染色体相同时，交叉操作是不起作用。假如交叉概率Pc 50%,则交配池中50%染色体(二分之一染色体)将进行交叉操作，余下50%染色体进行选择(复制)操作。GA利用选择和交叉操作能够产生含有更高平均适应值和更加好染色体群体46/11010/6/变异变异(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子代子代子代子代变异基因变异基因变异基因变异基因变异基因变异基因变异基因变异基因47/11010/6/变异变异(Mutation)比起选择和交叉操作，变异操作是GA中次要操作，但它在恢复群体中失去多样性多样性方面含有潜在作用。在GA执行开始阶段，染色体中一个特定位上值1可能与好性能紧密联络，即搜索空间中一些初始染色体在那个位上值1可能一致产生高适应值。因为越高适应值与染色体中那个位上值1相联系，选择操作就越会使群体遗传多样性损失。等抵达一定程度时，值0会从整个群体中那个位上消失，然而全局最优解可能在染色体中那个位上为0。假如搜索范围缩小到实际包含全局最优解那部分搜索空间，在那个位上值0就可能恰好是抵达全局最优解所需要。48/11010/6/适应函数适应函数(Fitness Function)GA在搜索中不依靠外部信息，仅以适应函数为依据，利用群体中每个染色体(个体)适应值来进行搜索。以染色体适应值大小来确定该染色体被遗传到下一代群体中概率。染色体适应值越大，该染色体被遗传到下一代概率也越大；反之，染色体适应值越小，该染色体被遗传到下一代概率也越小。所以适应函数选取至关主要，直接影响到GA收敛速度以及能否找到最优解。群体中每个染色体都需要计算适应值适应函数普通由目标函数变换而成49/11010/6/适应函数适应函数(Fitness Function)适应函数常见形式：适应函数常见形式：直接将目标函数转化为适应函数直接将目标函数转化为适应函数若目标函数为最大化问题：Fitness(f(x)=f(x)若目标函数为最小化问题：Fitness(f(x)=-f(x)缺点:(1)可能不满足轮盘赌选择中概率非负要求(2)一些代求解函数值分布上相差很大，由此得到评价适应值可能不利于表达群体评价性能，影响算法性能。50/11010/6/适应函数适应函数(Fitness Function)界限结构法界限结构法 目标函数为最大化问题其中Cmin为f(x)最小预计值 目标函数为最小化问题其中Cmaxn为f(x)最大预计值51/11010/6/停顿准则停顿准则(Termination Criteria)种群中个体最大适应值超出预设定值种群中个体平均适应值超出预设定值种群中个体进化代数超出预设定值52/11010/6/基本步骤基本步骤(Step by Step)(1)随机产生初始种群;(2)计算种群体中每个个体适应度值,判断是否满足停顿条件，若不满足，则转第(3)步,不然转第(6)步;(3)按由个体适应值所决定某个规则选择将进入下一代个体;(4)按交叉概率Pc进行交叉操作,生产新个体;(5)按变异概率Pm进行变异操作,生产新个体;(6)输出种群中适应度值最优染色体作为问题满意解或最优解。53/11010/6/流程图流程图(Flow Chart)54/11010/6/基本遗传算法基本遗传算法基本遗传算法（SimpleGeneticAlgorithms,简称SGA）是一个统一最基本遗传算法，它只使用选择、交叉、变异这三种基本遗传算子，其遗传进化操作过程简单，轻易了解，是其它一些遗传算法雏形和基础，它不但给各种遗传算法提供了一个基本框架，同时也含有一定应用价值。55/11010/6/SGA伪码描述伪码描述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 end56/11010/6/遗传算法应用遗传算法应用函数优化函数优化函数优化是遗传算法经典应用领域，也是对遗传算法进行性能测试评价惯用算例。对于一些非线性、多模型、多目标函数优化问题，用其它优化方法较难求解，而遗传算法却能够方便地得到很好结果。遗传算法提供了一个求解复杂系统优化问题通用框架，它不依赖于问题详细领域，对问题种类有很强鲁棒性，所以广泛应用于很多学科。下面列举一些遗传算法主要应用领域。57/11010/6/遗传算法应用遗传算法应用组合优化组合优化遗传算法是寻求组合优化问题满意解最正确工具之一，实践证实，遗传算法对于组合优化问题中NP完全问题非常有效。比如，遗传算法已经在求解旅行商问题(Traveling Salesman Problem,TSP)、背包问题(Knapsack Problem)、装箱问题(Bin Packing Problem)等方面得到成功应用。生产调度问题生产调度问题生产调度问题在很多情况下所建立起来数学模型难以准确求解，即使经过一些简化之后能够进行求解也会因简化得太多而使求解结果与实际相差太远。现在遗传算法已经成为处理复杂调度问题有效工具。58/11010/6/遗传算法应用遗传算法应用自动控制自动控制遗传算法已经在自动控制领域中得到了很好应用，比如基于遗传算法含糊控制器优化设计、基于遗传算法参数辨识、基于遗传算法含糊控制规则学习、利用遗传算法进行人工神经网络结构优化设计和权值学习等。机器人智能控制机器人智能控制机器人是一类复杂难以准确建模人工系统，而遗传算法起源就来自于对人工自适应系统研究，所以机器人智能控制自然成为遗传算法一个主要应用领域。59/11010/6/遗传算法应用遗传算法应用图象处理和模式识别图象处理和模式识别图像处理和模式识别是计算机视觉中一个主要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可防止地存在一些误差，这些误差会影响图像处理效果。怎样使这些误差最小是使计算机视觉到达实用化主要要求，遗传算法在这些图像处理中优化计算方面得到了很好应用。人工生命人工生命人工生命是用计算机、机械等人工媒体模拟或结构出含有自然生物系统特有行为人造系统。自组织能力和自学习能力是人工生命两大主要特征。人工生命与遗传算法有着亲密关系，基于遗传算法进化模型是研究人工生命现象主要理论基础。60/11010/6/遗传算法应用遗传算法应用遗传程序设计遗传程序设计Koza发展了遗传程序设计概念，他使用了以LISP语言所表示编码方法，基于对一个树形结构所进行遗传操作来自动生成计算机程序。机器学习机器学习 基于遗传算法机器学习，在很多领域中都得到了应用。比如基于遗传算法机器学习可用来调整人工神经网络连接权，也能够用于人工神经网络网络结构优化设计。分类器系统在多机器人路径规划系统中得到了成功应用。61/11010/6/SGA实例实例1：函数最值：函数最值SGA参数:编码方式:二进制码 e.g.00000e.g.000000;0;01101 01101 13;1111113;111113131种群规模:4随机初始群体“转盘赌”选择一点杂交,二进制变异 求函数f(x)=x2最大值，x为自然数且0 x31.o手工方式完成演示SGA过程62/11010/6/SGA实例实例1 max x2 :选择操作选择操作63/11010/6/SGA实例实例1 max x2 :交叉操作交叉操作64/11010/6/SGA实例实例1 max x2 :变异操作变异操作65/11010/6/SGA实例实例2:连续函数最值连续函数最值求以下函数最大值：66/11010/6/SGA实例实例2:编码编码高精度高精度编码 x,y 0,1L 必须可逆(一个表现型对应一个基因型)解码算子解码算子：:0,1L x,y 染色体长度染色体长度L决定可行解最大精度决定可行解最大精度长染色体长染色体(慢进化慢进化)实数问题：变量z为实数，怎样把a1,aL 0,1Lzx,y67/11010/6/SGA实例实例2:编码编码设定求解准确到设定求解准确到6位小数，因区间长度位位小数，因区间长度位2-(-1)=3,则需将区则需将区间分为间分为3X106等份。因等份。因 2097152221 3X1062224194304。故编码二进制串长。故编码二进制串长L=22。将一个二进制串将一个二进制串(b21b20b0)转化为转化为10进制数：进制数：e.g.-1;2 1.627 888 1.627888=-1+3x(1110000000111111000101)2/(222-1)=-1+3x3674053/(222-1)68/11010/6/SGA实例实例2:初始化种群适应函数初始化种群、适应函数随机初始化种群随机初始化种群适应函数适应函数本实例目标函数在定义域内均大于0，且是求函数最大值，故直接引用目标函数作为适应函数：f(s)=f(x)其中二进制串s对于变量x值。e.g.s1=x1=-0.958973适应值适应值:f(s1)=f(x1)=1.078878s2=x2=1.627888适应值适应值:f(s2)=f(x2)=3.25065069/11010/6/SGA实例实例2:遗传操作遗传操作选择操作(“轮盘赌”选择)交叉操作(单点交叉)交叉前交叉前(父父):s1=s2=交叉后交叉后(子子):s1=s2=适应值适应值:f(s1)=f(-0.998113)=1.940865f(s2)=f(1.666028)=3.459245s2适应值比其双亲个体适应值高。70/11010/6/SGA实例实例2:遗传操作遗传操作变异操作变异前变异前(父父):s2=变异后变异后(子子):s2=适应值适应值 f(s2)=f(1.721638)=0.917743比f(s2)小变异前变异前(父父):s2=变异后变异后(子子):s”2=适应值适应值f(s”2)=f(1.630818)=3.343555比f(s2)大变异操作有变异操作有”扰动扰动”作用，同时含有增加种群作用，同时含有增加种群多多样性效果。样性效果。71/11010/6/SGA实例实例2:模拟结果模拟结果遗传算法参数:种群规模种群规模:50 染色体长度染色体长度:L=22 最大进化代数最大进化代数:150 交叉概率交叉概率:Pc=0.25 变异概率变异概率:Pm=0.0172/11010/6/SGA实例实例2:模拟结果模拟结果(最正确个体进化情况最正确个体进化情况最正确个体进化情况最正确个体进化情况)世代数染色体编码变量x适应值141117344054718915010001110000101100011110000011011000101001111011010101110011100111111101010111111010011111100001101111011001111110100100010001100111110001101101000110011110100110110001011001111110100111111001100111111010011111100110011111.8316241.8424161.8548601.8475361.8532901.8484431.8486991.8508971.8505491.8505493.5348063.7903623.8332863.8420043.8434023.8462323.8471553.8501623.8502743.85027473/11010/6/最优化问题最优化问题(Optimization Problem)最优化问题最优化问题:组合优化问题组合优化问题(Combinatorial Optimization Problem):最优化问题中解空间X或S由离散集合组成。其中很多问题是NP完全(Nondeterministic Polynomial Completeness)问题.74/11010/6/最优化问题算法最优化问题算法传统优化方法传统优化方法(局部优化方法局部优化方法)共轭梯度法、牛顿法、单纯形方法共轭梯度法、牛顿法、单纯形方法等特点:1)依赖于初始条件。2)与求解空间有紧密关系，促使较快地收敛到局部解，但同时对解域有约束，如连续性或可微性。利用这些约束，收敛快。3)有些方法，如Davison-Fletcher-Powell直接依赖于最少一阶导数；共轭梯度法隐含地依赖于梯度。75/11010/6/最优化问题算法最优化问题算法全局优化方法 下降轨线法、下降轨线法、Monte-CarloMonte-Carlo随机试验法、模拟退随机试验法、模拟退火法、火法、GAGA等等特点：1)不依赖于初始条件；2)不与求解空间有紧密关系,对解域无可微或连续要求;轻易实现，求解稳健。3)但收敛速度慢,能取得全局最优;适合于求解空间不知情况。4)GA可应用于大规模、多峰多态函数、含离散变量等全局优化问题;求解速度和质量远超出常规方法。76/11010/6/无约束最优化问题无约束最优化问题GA编码编码：X=(x1,x2,xn)各个变量能够按二进制编码方法分别编码。对于变量xi上、下限约束lixiui(i=1,2,n)，依据解精度要求(有效位数)求得各个变量X=(x1,x2,xn)二进制码位数(m1,m2,mn)(确定方法类似于SGA实例2)，所以将n个二进制位串次序连接起来，组成一个个体染色体编码，编码总位数mm1+m2+mn。无约束最优化问题:77/11010/6/无约束最优化问题无约束最优化问题GA解码解码：解码时仍按各个变量编码次序分别实现常规二进制编码解码方法。二进制遗传编码示意图以下：78/11010/6/约束最优化问题约束最优化问题常规解法常规解法：(1)把约束问题转化为无约束问题，在用无约束问题方法求解，如罚函数法(2)改进无约束问题方法，再用于约束问题，如梯度投影法、广义简约梯度法约束最优化问题:79/11010/6/约束最优化问题约束最优化问题遗传算法求解关键:约束条件处理等式约束能够包含到适应函数，仅考虑不等式约束。假设按无约束问题那样求解，在搜索过程中计算目标函数值，并检验是否有约束违反。假如没有违反，则表明是可行解，就依据目标函数指定一适应值；不然，就是不可行解，因而没有适应值(适应值为0)。这么处理实际不可行，因为找到一个可行解几乎与找到最优解一样困难。80/11010/6/普通解法普通解法：经过引入罚函数，从不可行解中得到一些信息。将罚函数包含到适应函数中。o关键是怎样设计罚函数；关键是怎样设计罚函数；o不一样问题需要设计不一样罚函数；不一样问题需要设计不一样罚函数；o对普通约束处理，通常很困难。对普通约束处理，通常很困难。约束最优化问题约束最优化问题81/11010/6/组合最优化问题组合最优化问题经典问题：经典问题：巡回旅行商问题巡回旅行商问题(Traveling Salesman Problem)作业调度问题作业调度问题(Job Shop Scheduling Problem)背包问题背包问题(Knapsack Problem)图着色问题图着色问题 很多组合最优化问题是很多组合最优化问题是NPNP难问题难问题或或NPNP完全问题完全问题82/11010/6/巡回旅行商问题巡回旅行商问题(TSP)TSP，也称货郎担问题，是一个NP完全问题。TSP描述：图论图论:设图设图G=(V,E),其中其中V是顶点集，是顶点集，E是边集。设是边集。设C=(cij)是与是与E相联络距离矩阵。寻找一条经过全部相联络距离矩阵。寻找一条经过全部顶点且每个顶点只经过一次最短距离回路顶点且每个顶点只经过一次最短距离回路(Hamilton回路回路)。实际应用中，。实际应用中，C也可解释为费用或旅行时间也可解释为费用或旅行时间矩阵。矩阵。实际实际:一位推销员从自己所在城市出发，必须遍访全一位推销员从自己所在城市出发，必须遍访全部城市之后又回到原来城