数学建模中的常用算法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Algorithms in,Mathematical Modeling,Genetic Algorithm,*,*,数学建模中的常用算法,成都信息工程学院,计算科学系,胡建成,jianchenghu,200,9,-,5,-,20,数学建模竞赛网上资源,CUMCM,网站,:,MCM,和,ICM,网站,:,,中国数学建模,:,中科大建模网站,:,,MATLAB,网站,:,GOOGLE,大学,6/26/2026,数学建模竞赛中的算法,(1),93A,非线性交调的频率设计,:,拟合、规划,93B,足球队排名次,:,矩阵论、图论、层次分析法、整数规划,94A,逢山开路,:,图论、插值、动态规划,94B,锁具装箱问题,:,图论、组合数学,95A,飞行管理问题,:,非线性规划、线性规划,95B,天车与冶炼炉的作业调度,:,非线性规划、动态规划、层次分析法、,PETRI,方法、图论方法、排队论方法,96A,最优捕鱼策略,：,微分方程、积分、非线性规划,6/26/2026,96B,节水洗衣机,：,非线性规划,97A,零件参数设计,：,微积分、非线性规划、随机模拟,97B,截断切割,：,组合优化、几何变换、枚举、蒙特卡罗、递归、最短路,98A,投资收益与风险,：,线性规划、非线性规划,98B,灾情巡视,：,最小生成树、Hamilton,圈、旅行商问题,99A,自动化车床,：,积分、概率分布、随机模拟、分布拟合度检验,数学建模竞赛中的算法,(2),6/26/2026,99B,钻井布局,：,几何变换、枚举、最大完全子图、混合整数规划,00A DNA,分类,：,神经网络、最小二乘拟合、统计分类,00B,管道订购,：,最短路、二次规划,01A,血管的三维重建,：,数据挖掘、曲面重建与拟合,01B,公交车调度,：,非线性规划,02A,车灯光源优化设计,：,最优化,02B,彩票中的数学,：,概率与优化,数学建模竞赛中的算法,(3),6/26/2026,MATLAB,Maple,Mathematica,Lindo,Lingo,SAS,SPSS,C&C+,Fortran,Pascal,数学建模常用软件,6/26/2026,1.,蒙特卡罗方法,(Monte-Carlo,方法,MC),数学建模竞赛常用算法,(1),该算法又称,计算机随机性模拟方法,，也称,统计试验,方法,。,MC,方法是一种基于,“,随机数,”,的计算方法，能够,比较逼真地描述事物的特点及物理实验过程，解决一些,数值方法难以解决的问题。,MC,方法的雏型可以追溯到十九世纪后期的蒲丰随机,投针试验，即著名的,蒲丰问题,。,MC,方法通过计算机仿,真,(,模拟,),解决问题，同时也可以通过模拟来检验自己,模型的正确性，是比赛中经常使用的方法。,6/26/2026,97,年的,A,题,每个零件都有自己的标定值，也都有自,己的容差等级，而求解最优的组合方案将要面对着的是一,个极其复杂的公式和,108,种容差选取方案，根本不可能去求,解析解，那如何去找到最优的方案呢？随机性模拟搜索最,优方案就是其中的一种方法，在每个零件可行的区间中按,照正态分布随机的选取一个标定值和选取一个容差值作为,一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从,中选取一个最佳的。,02,年的,B,题,关于彩票第二问，要求设计一种更好的方,案，首先方案的优劣取决于很多复杂的因素，同样不可能,刻画出一个模型进行求解，只能靠随机仿真模拟。,数学建模竞赛常用算法,6/26/2026,98,年美国赛,A,题,生物组织切片的三维插值处理,94,年,A,题逢山开路,山体海拔高度的插值计算,数学建模竞赛常用算法,(2),2.,数据拟合、参数估计、插值等数据处理算法,比赛中通常会遇到大量的数据需要处理，而处理数,据的关键就在于这些算法，通常使用,MATLAB,作为工,具。与图形处理有关的问题很多与拟合有关系。,此类问题在,MATLAB,中有很多函数可以调用，只有熟,悉,MATLAB,，这些方法才能用好。,6/26/2026,98,年,B,题,用很多不等式完全可以把问题刻画清楚,数学建模竞赛常用算法,(3),3.,规划类问题算法,此类问题主要有,线性规划、整数规划、多元规划、二次规划,等。竞赛中很多问题都和数学规划有关，可以,说不少的模型都可以归结为一组不等式作为约束条件、,几个函数表达式作为目标函数的问题，遇到这类问题，,求解就是关键了。,因此列举出规划后用,Lindo,、,Lingo,等软件来进行解决,比较方便，所以还需要熟悉这两个软件。,6/26/2026,98,年,B,题、,00,年,B,题、,95,年锁具装箱,等问题体现了,图论问题,的重要性。,数学建模竞赛常用算法,(4),4.,图论问题,这类问题算法有很多，包括：,Dijkstra,、,Floyd,、,Prim,、,Bellman-Ford,，最大流，二分匹配,等问题。,6/26/2026,92,年B,题用分枝定界法,97,年,B,题是典型的动态规划问题,98,年,B,题体现了分治算法,数学建模竞赛常用算法,(5),5.,计算机算法设计中的问题,计算机算法设计包括很多内容：,动态规划、回溯搜,索、分治算法、分枝定界,等计算机算法,.,这方面问题和,ACM,程序设计竞赛中的问题类似，,可看一下与计算机算法有关的书。,6/26/2026,97,年,A,题用模拟退火算法,00,年,B,题用神经网络分类算法,01,年,B,题这种难题也可以使用神经网络,美国,89,年,A,题也和,BP,算法,有关系,美国,03,年,B,题,伽马刀问题也是目前研究的课题，目前,算法最佳的是遗传算法,。,数学建模竞赛常用算法,(6),6.,最优化理论的三大非经典算法,:,模拟退火法,(SA),、神经网络,(NN),、遗传算法,(GA),近几年的赛题越来越复杂，很多问题没有什么很好的,模型可以借鉴，于是这三类算法很多时候可以派上用场。,6/26/2026,97,年,A,题、,99,年,B,题都可以,用网格法搜索,数学建模竞赛常用算法,(7),网格算法和穷举法一样，只是网格法是连续问题的穷,举。此类算法运算量较大。,7.,网格算法和穷举算法,这种方法最好在运算速度较快的计算机中进行，还有,要用高级语言来做，最好不要用,MATLAB,做网格，否则,会算很久的。,6/26/2026,很多问题都是实际来的，数据可以是连续的，而计,算机只能处理离散的数据，因此需要,将连续问题进行,离散化处理后再用计算机求解,。比如差分代替微分、,求和代替积分等思想都是把连续问题离散化的常用方,法。,数学建模竞赛常用算法,(8),8.,连续问题离散化的方法,6/26/2026,数值分析研究各种,求解数学问题的数值计算方法,，,特别是适合于计算机实现方法与算法。,数学建模竞赛常用算法,(9),9.,数值分析方法,它的主要内容包括,函数的数值逼近、数值微分与数,值积分、非线性方程的数值解法、数值代数、常微分方,程数值解,等。数值分析是计算数学的一个重要分支，把,理论与计算紧密结合,是现代科学计算的基础。,MATLAB,等数学软件中已经有很多数值分析的函,数可以直接调用。,6/26/2026,01,年,A,题中需要你会读,BMP,图象,98,年美国,A,题需要你知道三维插值计算,03,年,B,题要求更高，不但需要编程计算还要进行处理,数学建模竞赛常用算法,(10),10.,图象处理算法,赛题中有一类问题与图形有关，即使问题与图形无,关，论文中也会需要图片来说明问题，这些图形如何展,示以及如何处理就是需要解决的问题，通常使用,MATLAB,进行处理。,数模论文中也有很多图片需要展示，解决这类问题,要熟悉,MATLAB,图形图像工具箱。,6/26/2026,三个孩子的年龄,(1),两个多年未见的朋友相遇，聊了很多事情。A,：,既然你是数学教授，那你帮我算这个题，今天是,个特殊日子：我三个儿子都在今天庆祝生日！那么你,能算出他们都有多大吗？,B,：好，但你得跟我讲讲他们的情况。,A,：好的，我给你一些提示，他们三个年龄之积是,36.,B,：很好，但我还需要更多提示。,6/26/2026,三个孩子的年龄,(2),A,：我的大儿子的眼睛是蓝色的。,B,考虑了一下说，,但是，我还有一点信息来解决你的这,个难题。,B,：哦，够了，,B,给出了正确的答案，即三个小孩的年龄。,A,：他们三个年龄之和等于那幢房子的窗户个数。,A,指着对面的一幢房子说。,6/26/2026,三个孩子的年龄,(3),根据对话信息，用,搜索,的方法来解此问题。,信息,1:,三个小孩年龄之积为,36,只有以下,8,种可能，搜索范围减少至,8,种情况,:,第一个小孩年龄,36 18 12 9 9 6 6 4,第二个小孩年龄,1 2 3 4 2 6 3 3,第三个小孩年龄,1 1 1 1 2 1 2 3,6/26/2026,三个孩子的年龄,(4),信息,2:,三个小孩年龄之和等于窗户数,第一个小孩年龄,36 18 12 9 9 6 6 4,第二个小孩年龄,1 2 3 4 2 6 3 3,第三个小孩年龄,1 1 1 1 2 1 2 3,窗户数,:,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),6/26/2026,智能优化算法,智能优化算法,又称为,现代启发式算法,，是一,种具有全局优化性能、通用性强、且适合于并行,处理的算法。这种算法一般具有严密的理论依据,而不是单纯凭借专家经验，理论上可以在一定的,时间内找到最优解或近似最优解。,6/26/2026,常用的智能优化算法,遗传算法,Genetic Algorithm,，简称,GA,模拟退火算法,Simulated Annealing,简称,SA,禁忌搜索算法,Tabu,Search,，简称,TS,6/26/2026,智能优化算法的特点,它们的共同特点：都是从任一解出发，按照,某种机制，以一定的概率在整个求解空间中探索,最优解。由于它们可以把搜索空间扩展到整个问,题空间，因而具有,全局优化性能,。,6/26/2026,遗传算法,(Genetic Algorithm),进化算法,(,Evolutionary Algorithm,),6/26/2026,遗传算法,(GA),Darwin,(1859):“,物竟天择，适者生存,”,John Holland(university of Michigan,1975),Adaptation in Natural and Artificial System,遗传算法作为一种有效的工具，已广泛地应用于最优化问题求解之中,。,遗传算法是一种基于自然群体遗传进化机制的自适应全局优化概率搜索算法。,它摒弃了传统的搜索方式，模拟自然界生物进化过程，采用人工的方式对目标空间进行随机化搜索。,6/26/2026,遗传算法模拟自然选择和自然遗传过程中发生,的,繁殖、交叉和基因突变,现象，在每次迭代中,都保留一组候选解，并按某种指标从解群中选,取较优的个体，利用,遗传算子,(,选择、交叉和变,异,),对这些个体进行组合，产生新一代的候选解,群，重复此过程，直到满足某种收敛指标为止。,遗传算法的搜索机制,6/26/2026,局部,全局,遗传算法,(GA),6/26/2026,We have a dream!,I am at the top,Height is.,I am not at the top.,My high is better!,I will continue,遗传算法,(GA),GA-,第,0,代,6/26/2026,Dead one,New one,遗传算法,(GA),GA-,第,1,代,6/26/2026,Not at the top,Come Up!,遗传算法,(GA),GA-,第,?,代,6/26/2026,I am the,BEST,!,遗传算法,(GA),GA第,N,代,6/26/2026,适者生存,(,Survival of the Fittest,),GA,主要采用的进化规则是“,适者生存,”,较好的解保留，较差的解淘汰,遗传算法,(GA),6/26/2026,生物进化与遗传算法对应关系,生物进化,遗传算法,适者生存,适应函数值最大的解被保留的概率最大,个体,问题的一个解,染色体,解的编码,基因,编码的元素,群体,被选定的一组解,种群,根据适应函数选择的一组解,交叉,以一定的方式由双亲产生后代的过程,变异,编码的某些分量发生变化的过程,环境,适应函数,6/26/2026,遗传算法的基本操作,选择,(selection),:,根据各个个体的适应值，按照一定的规则或方法，从第,t,代群体,P(t),中选择出一些优良的个体遗传到下一代群体,P,(,t,+1),中。,交叉,(crossover),:,将群体,P(t),内的各个个体随机搭配成对，对每一个个体，以某个概率,P,c,(,称为交叉概率，,crossvoer rate),交换它们之间的部分染色体。,变异,(mutation),:,对群体,P(t),中的每一个个体，以某一概率,P,m,(,称为变异概率，,mutation rate),改变某一个或一些基因座上基因值为其它的等位基因。,6/26/2026,如何设计遗传算法,如何进行编码？,如何产生初始种群？,如何定义适应函数？,如何进行遗传操作,(,复制、交叉、变异,),？,如何产生下一代种群？,如何定义停止准则,？,6/26/2026,编码,(Coding),表现型空间,编码,(Coding),解码,(Decoding),基因型空间,=0,1,L,011101001,010001001,10010010,10010001,6/26/2026,选择,(Selection),选择,(,复制,),操作把当前种群的染色体按与适应值成正比例的概率复制到新的种群中,主要思想,:,适应值较高的染色体体有较大的选择,(,复制,),机会,实现,1,：,”,轮盘赌,”,选择,(Roulette wheel selection),将种群中所有染色体的适应值相加求总和，染色体适应值按其比例转化为选择概率,Ps,产生一个在,0,与总和之间的的随机数,m,从种群中编号为,1,的染色体开始，将其适应值与后续染色体的适应值相加，直到累加和等于或大于,m,6/26/2026,选择,(Selection),设种群的规模为,N,x,i,是,i,为种群中第,i,个染色体,A,C,1/6=,17%,3/6=,50%,B,2/6=,33%,fitness(A)=3,fitness(B)=1,fitness(C)=2,染色体,x,i,被选概率,6/26/2026,选择,(Selection),染色体的适应值和所占的比例,轮盘赌选择,6/26/2026,选择,(Selection),随机数,23,49,13,38,6,27,所,选号码,2,6,2,5,1,4,所选染色体,11000,00011,11000,01100,01110,10010,染色体编号,1,2,3,4,5,6,染色体,01110,11000,00100,10010,01100,00011,适应度,8,15,2,5,12,8,被选,概率,0.16,0.3,0.04,0.1,0.24,0.16,适应度累计,8,23,25,30,42,50,染色体被选的概率,被选,的染色体,6/26/2026,选择,(Selection),轮盘上的片分配给群体的染色体，使得每一个片的大小与对于染色体的适应值成比例,从群体中选择一个染色体可视为旋转一个轮盘，当轮盘停止时，指针所指的片对于的染色体就时要选的染色体。,模拟“轮盘赌”算法,：,r=random(0,1),，,s=0,，,i=0,；,如果,sr,，,则转,(4),；,s=s+p(x,i,),，,i=i+1,转,(2),xi,即为被选中的染色体，输出,I,结束,6/26/2026,选择,(Selection),其他选择法,：,随机遍历抽样,(Stochastic universal sampling),局部选择,(Local selection),截断选择,(Truncation selection),竞标赛选择,(Tournament selection),特点,：,选择操作得到的新的群体称为交配池，交配池是当前代和下一代之间的中间群体，其规模为初始群体规模。选择操作的作用效果是提高了群体的平均适应值,(,低适应值个体趋于淘汰，高适应值个体趋于选择,),，但这也损失了群体的,多样性,。选择操作没有产生新的个体，群体中最好个体的适应值不会改变。,6/26/2026,交叉,(crossover,Recombination),遗传交叉,(,杂交、交配、有性重组,),操作发生在两个染色体之间，由两个被称之为双亲的父代染色体，经杂交以后，产生两个具有双亲的部分基因的新的染色体，从而检测搜索空间中新的点。,选择,(,复制,),操作每次作用在一个染色体上，而交叉操作每次作用在从交配池中随机选取的两个个体上,(,交叉概率,P,c,),。,交叉产生两个子染色体，他们与其父代不同，且彼此不同,每个子染色体都带有双亲染色体的遗传基因。,6/26/2026,单点交叉,(1-point crossover),在双亲的父代染色体中随机产生一个交叉点位置,在交叉点位置分离双亲染色体,互换交叉点位置右边的基因码产生两个子代染色体,交叉概率,P,c,一般范围为,(6,0%,9,0%,),，平均约,80%,1,1,1,1,1,1,1,1,父代,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,子代,1,1,1,1,0,0,0,00,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,交叉点位置,6/26/2026,交叉,(crossover,Recombination),单点交叉操作可以产生与父代染色体完全不同的子代染色体；它不会改变父代染色体中相同的基因。但当双亲染色体相同时，交叉操作是不起作用的。,假如交叉概率,P,c,50%,则交配池中,50%,的染色体,(,一半染色体,),将进行交叉操作，余下的,50%,的染色体进行选择,(,复制,),操作。,GA,利用,选择和交叉操作,可以产生具有,更高平均适应值和更好染色体的群体,6/26/2026,变异,(Mutation),以变异概率,P,m,改变,染色体的某一个基因,当以二进制编码时，变异的基因由,0,变成,1,，或者由,1,变成,0,。,变异概率,P,m,一般介于,1/,种群规模与,1/,染色体长度之间，平均约,1-2%,1,1,0,1,0,1,0,0,父代,0,1,0,1,0,1,0,1,子代,变异基因,变异基因,6/26/2026,变异,(Mutation),比起选择和交叉操作，,变异操作,是,GA,中的次要操作，但它在恢复群体中失去的,多样性,方面具有潜在的作用。,在,GA,执行的开始阶段，染色体中一个特定位上的值,1,可能与好的性,能紧密联系，即搜索空间中某些初始染色体在那个位上的值,1,可能一,致产生高的适应值。因为越高的适应值与染色体中那个位上的值,1,相联,系，选择操作就越会使群体的遗传多样性损失。,等到达一定程度时，值,0,会从整个群体中那个位上消失，然而全局最,优解可能在染色体中那个位上为,0,。如果搜索范围缩小到实际包含全局,最优解的那部分搜索空间，在那个位上的值,0,就可能正好是到达全局最,优解所需要的。,6/26/2026,适应函数,(Fitness Function),GA,在搜索中不依靠外部信息，仅以,适应函数,为依据，利用群体中每个染色体,(,个体,),的适应值来进行搜索。,以染色体适应值的大小来确定该染色体被遗传到下一代群体中的概率,。染色体适应值越大，该染色体被遗传到下一代的概率也越大；反之，染色体的适应值越小，该染色体被遗传到下一代的概率也越小。因此适应函数的选取至关重要，直接影响到,GA,的收敛速度以及能否找到最优解。,群体中的每个染色体都需要计算适应值,适应函数一般由,目标函数,变换而成,6/26/2026,适应函数,(Fitness Function),适应函数常见形式：,直接将目标函数转化为适应函数,若目标函数为最大化问题：,Fitness(f(x)=f(x),若目标函数为最小化问题：,Fitness(f(x)=-f(x),缺点,:,(1),可能不满足轮盘赌选择中概率非负的要求,(2),某些代求解的函数值分布上相差很大，由此得到的评价适应值可能不利于体现群体的评价性能，影响算法的性能。,6/26/2026,适应函数,(Fitness Function),界限构造法,目标函数为最大化问题,其中,C,min,为,f(x,),的最小估计值,目标函数为最小化问题,其中,C,maxn,为,f(x,),的最大估计值,6/26/2026,停止准则,(,Termination,Criteria),种群中个体的,最大适应值,超过预设定值,种群中个体的,平均适应值,超过预设定值,种群中个体的,进化代数,超过预设定值,6/26/2026,基本步骤,(Step by Step),(1),随机产生,初始种群,;,(2),计算种群体中每个个体的,适应度值,判断是否满足停止条件，若不满足，则转第,(3),步,否则转第,(6),步,;,(3),按由个体适应值所决定的某个规则,选择,将进入下一代的个体,;,(4),按交叉概率,P,c,进行,交叉操作,生产新的个体,;,(5),按变异概率,P,m,进行,变异操作,生产新的个体,;,(6),输出种群中适应度值最优的染色体作为问题的,满意解或最优解,。,6/26/2026,流程图,(Flow Chart),6/26/2026,基本遗传算法,基本遗传算法,（,Simple Genetic Algorithms,简称,SGA,）,是一种统一的最基本的遗传算法，它只,使用,选择、交叉、变异,这三种基本遗传算子，其遗传,进化操作过程简单，容易理解，是其他一些遗传算法,的雏形和基础，它不仅给各种遗传算法提供了一个基,本框架，同时也具有一定的应用价值。,6/26/2026,SGA,伪码描述,Procedure Genetic Algorithm,begin,t=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,end,6/26/2026,遗传算法的应用,函数优化,函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能测试评价的常用算例。对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，而遗传算法却可以方便地得到较好的结果。,遗传算法提供了一种求解复杂系统优化问题的通用框,架，它不依赖于问题的具体领域，对问题的种类有很,强的鲁棒性，所以广泛应用于很多学科。下面列举一,些遗传算法的主要应用领域。,6/26/2026,遗传算法的应用,组合优化,遗传算法是寻求组合优化问题满意解的最佳工具之一，实践证明，遗传算法对于组合优化问题中的,NP,完全问题非常有效。例如，遗传算法已经在求解旅行商问题,(Traveling Salesman Problem,TSP),、背包问题,(Knapsack Problem),、装箱问题,(Bin Packing Problem),等方面得到成功的应用。,生产调度问题,生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解也会因简化得太多而使求解结果与实际相差太远。现在遗传算法已经成为解决复杂调度问题的有效工具。,6/26/2026,遗传算法的应用,自动控制,遗传算法已经在自动控制领域中得到了很好的应用，例如基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权值学习等。,机器人智能控制,机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于对人工自适应系统的研究，所以机器人智能控制自然成为遗传算法的一个重要应用领域。,6/26/2026,遗传算法的应用,图象处理和模式识别,图像处理和模式识别是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地存在一些误差，这些误差会影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求，遗传算法在这些图像处理中的优化计算方面得到了很好的应用。,人工生命,人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。自组织能力和自学习能力是人工生命的两大重要特征。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要理论基础。,6/26/2026,遗传算法的应用,遗传程序设计,Koza,发展了遗传程序设计的概念，他使用了以,LISP,语言所表示的编码方法，基于对一种树形结构所进行的遗传操作来自动生成计算机程序。,机器学习,基于遗传算法的机器学习，在很多领域中都得到了应用。例如基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可以用于人工神经网络的网络结构优化设计。分类器系统在多机器人路径规划系统中得到了成功的应用。,6/26/2026,SGA,实例,1,：函数最值,SGA,参数,:,编码方式,:,二进制码,e.g.00000,0;,01101,13;11111,31,种群规模,:4,随机初始群体,“,转盘赌”选择,一点杂交,二进制变异,求函数,f(x,)=x,2,的最大值，,x,为自然数且,0 x31.,手工方式完成演示,SGA,过程,6/26/2026,SGA,实例,1 max x,2,:,选择操作,6/26/2026,SGA,实例,1 max x,2,:,交叉操作,6/26/2026,SGA,实例,1 max x,2,:,变异操作,6/26/2026,SGA,实例,2:,连续函数最值,求下列函数的最大值,：,6/26/2026,SGA,实例,2:,编码,高精度,编码,x,y,0,1,L,必须可逆,(,一个表现型对应一个基因型,),解码算子,：,:,0,1,L,x,y,染色体长度,L,决定可行解的最大精度,长染色体,(,慢进化,),实数问题,：,变量,z,为实数，如何把,a,1,a,L,0,1,L,zx,y,6/26/2026,SGA,实例,2:,编码,设定求解精确到,6,位小数，因区间长度位,2-(-1)=3,则需将区,间分为,3X10,6,等份。因,2097152,2,21,3X10,6,2,22,4194304,。故编码的二进制串长,L=22,。,将一个二进制串,(b21b20b0),转化为,10,进制数：,e.g.,-1;,2,1.627 888,1.627888=-1+3x(1110000000111111000101),2,/(2,22,-1),=-1+3x3674053/(222-1),6/26/2026,SGA,实例,2:,初始化种群、适应函数,随机初始化种群,适应函数,本实例目标函数在定义域内均大于,0,，,且是求函数最大值，故直接引用目标函数作为适应函数：,f(s)=f(x),其中二进制串,s,对于变量,x,的值。,e.g.,s,1,=,x,1,=-0.958 973,适应值,:f(s,1,)=f(,x,1,)=1.078 878,s,2,=,x,2,=,1.627 888,适应值,:f(s,2,)=f(,x,2,)=3.250 650,6/26/2026,SGA,实例,2:,遗传操作,选择操作,(“,轮盘赌”选择,),交叉操作,(,单点交叉,),交叉前,(,父,):,s,1,=,s,2,=,交叉后,(,子,):,s,1,=,s,2,=,适应值,:,f(s,1,)=f(-0.998 113)=1.940 865,f(s,2,)=f(1.666 028)=3.459 245,s,2,的适应值比其双亲个体的适应值高。,6/26/2026,SGA,实例,2:,遗传操作,变异操作,变异前,(,父,):,s,2,=,变异后,(,子,),:,s,2,=,适应值,f(s,2,)=f(1.721 638)=0.917 743,比,f(s,2,),小,变异前,(,父,),:,s,2,=,变异后,子,),:,s”,2,=,适应值,f(s”,2,)=f(1.630 818)=3.343 555,比,f(s,2,),大,变异操作有”,扰动,”作用，同时具有增加种群多,样性的效果。,6/26/2026,SGA,实例,2:,模拟结果,遗传算法的参数,:,种群规模,:50,染色体长度,:L=22,最大进化代数,:150,交叉概率,:P,c,=0.25,变异概率,:P,m,=0.01,6/26/2026,SGA,实例,2:,模拟结果,(,最佳个体进化情况,),世代数,染色体编码,变量,x,适应值,1,4,11,17,34,40,54,71,89,150,1000111000010110001111,0000011011000101001111,0110101011100111001111,1110101011111101001111,1100001101111011001111,1101001000100011001111,1000110110100011001111,0100110110001011001111,1101001111110011001111,1101001111110011001111,1.831 624,1.842 416,1.854 860,1.847 536,1.853 290,1.848 443,1.848 699,1.850 897,1.850 549,1.850 549,3.534 806,3.790 362,3.833 286,3.842 004,3.843 402,3.846 232,3.847 155,3.850 162,3.850 274,3.850 274,6/26/2026,最优化问题,(Optimization Problem),最优化问题,:,组合优化问题,(Combinatorial Optimization Problem):,最优化问题中的解空间,X,或,S,由离散集合构成。其中很,多问题是,NP,完全,(Nondeterministic Polynomial,Completeness),问题,.,6/26/2026,最优化问题算法,传统的优化方法,(,局部优化方法,),共轭梯度法、牛顿法、单纯形方法,等,特点,:,1),依赖于初始条件。,2),与求解空间有紧密关系，促使较快地收敛到局部 解，但同时对 解域有约束，如连续性或可微性。利用这些约束，收敛快。,3),有些方法，如,Davison-Fletcher-Powell,直接依赖于至少一阶导数；共轭梯度法隐含地依赖于梯度。,6/26/2026,最优化问题算法,全局优化方法,下降轨线法、,Monte-Carlo,随机试验法、模拟退火法、,GA,等,特点：,1),不依赖于初始条件；,2),不与求解空间有紧密关系,对解域无可微或连续的要求,;,容易实现，求解稳健3),但收敛速度慢,能获得全局最优,;,适合于求解空间不知的情况。,4)GA,可应用于大规模、多峰多态函数、含离散变量等全局优化问题,;,求解速度和质量远超过常规方法。,6/26/2026,无约束最优化问题,GA,编码,：,X=(x,1,x,2,x,n,),的各个变量可以按二进制编码方法分别编码。,对于变量,x,i,的上、下限约束,l,i,x,i,u,i,(i=1,2,n),，依据解,的精度要求,(,有效位数,),求得各个变量,X=(x,1,x,2,x,n,),的二进制,码位数,(m,1,m,2,m,n,),(,确定方法类似于,SGA,实例,2),，因此将,n,个二进制位串顺序连接起来，构成一个个体的染色体编码，编,码的总位数,m,m,1,+m,2,+m,n,。,无约束最优化问题,:,6/26/2026,无约束最优化问题,GA,解码,：,解码时仍按各个变量的编码顺序分别实现常规的二进制编码,解码方法。,二进制遗传编码示意图如下：,6/26/2026,约束最优化问题,常规解法,：,(1),把约束问题转化为无约束问题，在用无约束问题方法求解，如罚函数法,(2),改进无约束问题的方法，再用于约束问题，如梯度投影法、广义简约梯度法,约束最优化问题,:,6/26/2026,约束最优化问题,遗传算法求解关键,:,约束条件的处理,等式约束可以包含到适应函数，仅考虑不等式,约束。,假设按无约束问题那样求解，在搜索过程中计算目标函,数值，并检查是否有约束违反。如果没有违反，则表明是,可行解，就根据目标函数指定一适应值；否则，就是不可,行解，因而没有适应值,(,适应值为,0),。这样的处理实际不可,行，因为找到一个可行解几乎与找到最优解一样困难。,6/26/2026,一般解法,：,通过引入罚函数，从不可行解中得到一些信,息。将罚函数包含到适应函数中。,关键是如何设计罚函数；,不同问题需要设计不同的罚函数；,对一般的约束处理，通常很困难。,约束最优化问题,6/26/2026,组合最优化问题,典型问题：,巡回旅行商问题,(Traveling Salesman Problem),作业调度问题Job Shop Scheduling Problem),背包问题,(Knapsack Problem),图着色问题,很多组合最优化问题是,NP,难问题,或,NP,完全问题,6/26/2026,巡回旅行商问题,(TSP),TSP,，也称货郎担问题，是一个,NP,完全问题。,TSP,描述：,图论,:,设图,G=(V,E),其中,V,是顶点集，,E,是边集。设,C=(,c,ij,),是与,E,相联系的距离矩阵。寻找一条通过所有顶点且每个顶点只通过一次的最短距离回路,(Hamilton,回路,),。实际应用中，,C,也可解释为费用或旅行时间矩阵。,实际,:,一位推销员从自己所在城市出发，必须遍访所有城市之后又回到原来的城市，求使其旅行费用最少的路径。,6/26/2026,巡回旅行商问题,(TSP),中国货郎担问题,:,城市数,:40,城市编号,1,2,40,寻找一条最短路径,6/26/2026,TSP,复杂性,搜索空间庞大,TSP,涉及求多个变量的函数的最小值，求解很困难。,其可能的路径条数随着城市数目,n,成指数增长，如，,5,个城市对应,12,条路径；,10,个城市对应,181 440,条,路径；,100,个城市对应,4.6663,X,10,155,条路径。如此,庞大的搜索空间，常规解法和计算工具都遇到计算上,的困难。只能寻找近似解法，如神经网络方法、模拟,退火法、遗传算法等。,6/26/2026,TSP,编码,:,路径表示,染色体表示成所有城市的一个排列，若有,n,个城市，一,条可能路径编码为长度为,n,的整数向量,(i,1,i,2,i,n,),其中,i,k,表示第,i,k,个城市。,例如,:,路径编码向量,(5 1 7 8 9 4 6 2 3),直接表示一条,旅行路程,(5-1-7-8-9-4-6-2-3),。,此向量是,1,到,n,的一个排列，即从,1,到,n,的每个整数在这,个向量中正好出现一次,不能有重复。这样，基本遗传,算法的基因操作生成的个体不能满足这一约束条件，需,寻求其他遗传操作。,6/26/2026,TSP,交叉,需其他方式的交叉,(,重组,),操