数学建模常用算法.ppt

《数学建模常用算法.ppt》由会员分享，可在线阅读，更多相关《数学建模常用算法.ppt（110页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Algorithms in Mathematical ModelingGenetic Algorithm1Algorithms in Mathematical ModelingGenetic Algorithm数学建模中的常用算法Algorithms in Mathematical ModelingGenetic Algorithm22022/11/13数学建模竞赛网上资源数学建模竞赛网上资源CUMCM网站:http:/ MCM和ICM网站:http:/中国数学建模:http:/中科大建模网站:http:/MATLAB网站:http:/GOOGLE大学Algorithms in Mathema

2、tical ModelingGenetic Algorithm32022/11/13数学建模竞赛中的算法数学建模竞赛中的算法(1)93A 非线性交调的频率设计非线性交调的频率设计:拟合、规划拟合、规划93B 足球队排名次足球队排名次:矩阵论、图论、层次分析法、矩阵论、图论、层次分析法、整数规划整数规划94A 逢山开路逢山开路:图论、插值、动态规划图论、插值、动态规划94B 锁具装箱问题锁具装箱问题:图论、组合数学图论、组合数学95A 飞行管理问题飞行管理问题:非线性规划、线性规划非线性规划、线性规划95B 天车与冶炼炉的作业调度天车与冶炼炉的作业调度:非线性规划、动态非线性规划、动态规划、层次

3、分析法、规划、层次分析法、PETRI方法、图论方法、排队论方法、图论方法、排队论方法方法96A 最优捕鱼策略最优捕鱼策略：微分方程、积分、非线性规划微分方程、积分、非线性规划Algorithms in Mathematical ModelingGenetic Algorithm42022/11/1396B 节水洗衣机节水洗衣机：非线性规划非线性规划97A 零件参数设计零件参数设计：微积分、非线性规划、随机模拟微积分、非线性规划、随机模拟97B 截断切割截断切割：组合优化、几何变换、枚举、蒙特卡组合优化、几何变换、枚举、蒙特卡罗、递归、最短路罗、递归、最短路98A 投资收益与风险投资收益与风险：

4、线性规划、非线性规划线性规划、非线性规划98B 灾情巡视灾情巡视：最小生成树、最小生成树、Hamilton圈、旅行商圈、旅行商问题问题99A 自动化车床自动化车床：积分、概率分布、随机模拟、分布积分、概率分布、随机模拟、分布拟合度检验拟合度检验数学建模竞赛中的算法数学建模竞赛中的算法(2)Algorithms in Mathematical ModelingGenetic Algorithm52022/11/1399B 钻井布局钻井布局：几何变换、枚举、最大完全子图、几何变换、枚举、最大完全子图、混合整数规划混合整数规划00A DNA分类分类：神经网络、最小二乘拟合、统计分神经网络、最小二乘拟

5、合、统计分类类00B 管道订购管道订购：最短路、二次规划最短路、二次规划01A 血管的三维重建血管的三维重建：数据挖掘、曲面重建与拟合数据挖掘、曲面重建与拟合01B 公交车调度公交车调度：非线性规划非线性规划02A 车灯光源优化设计车灯光源优化设计：最优化最优化02B 彩票中的数学彩票中的数学：概率与优化概率与优化数学建模竞赛中的算法数学建模竞赛中的算法(3)Algorithms in Mathematical ModelingGenetic Algorithm62022/11/13 MATLAB Maple Mathematica Lindo Lingo SAS SPSS C&C+Fortr

6、an Pascal数学建模常用软件数学建模常用软件Algorithms in Mathematical ModelingGenetic Algorithm72022/11/131.蒙特卡罗方法(Monte-Carlo方法,MC)数学建模竞赛常用算法数学建模竞赛常用算法(1)该算法又称计算机随机性模拟方法计算机随机性模拟方法，也称统计试验统计试验方法方法。MC方法是一种基于“随机数”的计算方法，能够比较逼真地描述事物的特点及物理实验过程，解决一些数值方法难以解决的问题。MC方法的雏型可以追溯到十九世纪后期的蒲丰随机投针试验，即著名的蒲丰问题蒲丰问题。MC方法通过计算机仿真(模拟)解决问题，同时也

7、可以通过模拟来检验自己模型的正确性，是比赛中经常使用的方法。Algorithms in Mathematical ModelingGenetic Algorithm82022/11/1397年的年的A题题 每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和108种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢？随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。02年的年的B题题 关于彩票第二问，要

8、求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。数学建模竞赛常用算法数学建模竞赛常用算法Algorithms in Mathematical ModelingGenetic Algorithm92022/11/1398 年美国赛年美国赛A 题题 生物组织切片的三维插值处理生物组织切片的三维插值处理94 年年A 题逢山开路题逢山开路 山体海拔高度的插值计算山体海拔高度的插值计算数学建模竞赛常用算法数学建模竞赛常用算法(2)2.数据拟合、参数估计、插值等数据处理算法 比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，

9、通常使用MATLAB 作为工具。与图形处理有关的问题很多与拟合有关系。此类问题在MATLAB中有很多函数可以调用，只有熟悉MATLAB，这些方法才能用好。Algorithms in Mathematical ModelingGenetic Algorithm102022/11/1398年年B 题题 用很多不等式完全可以把问题刻画清楚用很多不等式完全可以把问题刻画清楚数学建模竞赛常用算法数学建模竞赛常用算法(3)3.规划类问题算法 此类问题主要有线性规划、整数规划、多元规划、线性规划、整数规划、多元规划、二次规划二次规划等。竞赛中很多问题都和数学规划有关，可以说不少的模型都可以归结为一组不等式作

10、为约束条件、几个函数表达式作为目标函数的问题，遇到这类问题，求解就是关键了。因此列举出规划后用Lindo、Lingo 等软件来进行解决比较方便，所以还需要熟悉这两个软件。Algorithms in Mathematical ModelingGenetic Algorithm112022/11/1398 年年B 题、题、00年年B 题、题、95 年锁具装箱年锁具装箱等问题体现了等问题体现了图论问题图论问题的重要性。的重要性。数学建模竞赛常用算法数学建模竞赛常用算法(4)4.图论问题 这类问题算法有很多，包括：Dijkstra、Floyd、Prim、Bellman-Ford，最大流，二分匹配，最大

11、流，二分匹配等问题。Algorithms in Mathematical ModelingGenetic Algorithm122022/11/1392 年年B 题用分枝定界法题用分枝定界法97 年年B 题是典型的动态规划问题题是典型的动态规划问题98 年年B 题体现了分治算法题体现了分治算法数学建模竞赛常用算法数学建模竞赛常用算法(5)5.计算机算法设计中的问题 计算机算法设计包括很多内容：动态规划、回溯搜动态规划、回溯搜索、分治算法、分枝定界索、分治算法、分枝定界等计算机算法.这方面问题和ACM 程序设计竞赛中的问题类似，可看一下与计算机算法有关的书。Algorithms in Mathe

12、matical ModelingGenetic Algorithm132022/11/1397年年A 题用模拟退火算法题用模拟退火算法00年年B 题用神经网络分类算法题用神经网络分类算法01年年B 题这种难题也可以使用神经网络题这种难题也可以使用神经网络美国美国89年年A 题也和题也和BP 算法算法有关系美国美国03年年B 题题伽马刀问题也是目前研究的课题，目前算法最佳的是遗传算法算法最佳的是遗传算法。数学建模竞赛常用算法数学建模竞赛常用算法(6)6.最优化理论的三大非经典算法:模拟退火法(SA)、神经网络(NN)、遗传算法(GA)近几年的赛题越来越复杂，很多问题没有什么很好的模型可以借鉴，于

13、是这三类算法很多时候可以派上用场。Algorithms in Mathematical ModelingGenetic Algorithm142022/11/1397 年年A 题、题、99 年年B 题都可以题都可以用网格法搜索用网格法搜索数学建模竞赛常用算法数学建模竞赛常用算法(7)网格算法和穷举法一样，只是网格法是连续问题的穷举。此类算法运算量较大。7.网格算法和穷举算法 这种方法最好在运算速度较快的计算机中进行，还有要用高级语言来做，最好不要用MATLAB 做网格，否则会算很久的。Algorithms in Mathematical ModelingGenetic Algorithm152

14、022/11/13 很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的数据，因此需要将连续问题进行将连续问题进行离散化处理后再用计算机求解离散化处理后再用计算机求解。比如差分代替微分、求和代替积分等思想都是把连续问题离散化的常用方法。数学建模竞赛常用算法数学建模竞赛常用算法(8)8.连续问题离散化的方法Algorithms in Mathematical ModelingGenetic Algorithm162022/11/13 数值分析研究各种求解数学问题的数值计算方法求解数学问题的数值计算方法，特别是适合于计算机实现方法与算法。数学建模竞赛常用算法数学建模竞赛常用算法(9)9.

15、数值分析方法 它的主要内容包括函数的数值逼近、数值微分与数函数的数值逼近、数值微分与数值积分、非线性方程的数值解法、数值代数、常微分方值积分、非线性方程的数值解法、数值代数、常微分方程数值解程数值解等。数值分析是计算数学的一个重要分支，把理论与计算紧密结合,是现代科学计算的基础。MATLAB等数学软件中已经有很多数值分析的函数可以直接调用。Algorithms in Mathematical ModelingGenetic Algorithm172022/11/1301年年A 题中需要你会读题中需要你会读BMP 图象图象98年美国年美国A 题需要你知道三维插值计算题需要你知道三维插值计算03年

16、年B 题要求更高，不但需要编程计算还要进行处理题要求更高，不但需要编程计算还要进行处理数学建模竞赛常用算法数学建模竞赛常用算法(10)10.图象处理算法 赛题中有一类问题与图形有关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用MATLAB进行处理。数模论文中也有很多图片需要展示，解决这类问题要熟悉MATLAB图形图像工具箱。Algorithms in Mathematical ModelingGenetic Algorithm182022/11/13三个孩子的年龄三个孩子的年龄(1)两个多年未见的朋友相遇，聊了很多事情。A：既然你是

17、数学教授，那你帮我算这个题，今天是个特殊日子：我三个儿子都在今天庆祝生日！那么你能算出他们都有多大吗？B：好，但你得跟我讲讲他们的情况。A：好的，我给你一些提示，他们三个年龄之积是36.B：很好，但我还需要更多提示。Algorithms in Mathematical ModelingGenetic Algorithm192022/11/13三个孩子的年龄三个孩子的年龄(2)A：我的大儿子的眼睛是蓝色的。B考虑了一下说，但是，我还有一点信息来解决你的这个难题。B：哦，够了，B给出了正确的答案，即三个小孩的年龄。A：他们三个年龄之和等于那幢房子的窗户个数。A指着对面的一幢房子说。Algorith

18、ms in Mathematical ModelingGenetic Algorithm202022/11/13三个孩子的年龄三个孩子的年龄(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 3Algorithms in Mathematical ModelingGenetic Algorithm212022/11/13三个孩子的年龄三个孩子的年龄(4)信息信息2:三个小

19、孩年龄之和等于窗户数三个小孩年龄之和等于窗户数第一个小孩年龄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)Algorithms in Mathematical ModelingGenetic Algorithm222022/11/13智能优化算法智能优化算法 智能优化算法智能优化算法又

20、称为现代启发式算法现代启发式算法，是一种具有全局优化性能、通用性强、且适合于并行处理的算法。这种算法一般具有严密的理论依据,而不是单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。Algorithms in Mathematical ModelingGenetic Algorithm232022/11/13常用的智能优化算法常用的智能优化算法 遗传算法遗传算法 Genetic Algorithm，简称GA 模拟退火算法模拟退火算法 Simulated Annealing，简称SA 禁忌搜索算法禁忌搜索算法 Tabu Search，简称TS Algorithms in Mathe

21、matical ModelingGenetic Algorithm242022/11/13智能优化算法的特点智能优化算法的特点 它们的共同特点：都是从任一解出发，按照某种机制，以一定的概率在整个求解空间中探索最优解。由于它们可以把搜索空间扩展到整个问题空间，因而具有全局优化性能。Algorithms in Mathematical ModelingGenetic Algorithm252022/11/13遗传算法遗传算法(Genetic Algorithm)进化算法(Evolutionary Algorithm)Algorithms in Mathematical ModelingGeneti

22、c Algorithm262022/11/13遗传算法遗传算法(GA)Darwin(1859):“物竟天择，适者生存物竟天择，适者生存”John Holland(university of Michigan,1975)Adaptation in Natural and Artificial System遗传算法作为一种有效的工具，已广泛地应用于最遗传算法作为一种有效的工具，已广泛地应用于最优化问题求解之中优化问题求解之中。遗传算法是一种基于自然群体遗传进化机制的自适遗传算法是一种基于自然群体遗传进化机制的自适应全局优化概率搜索算法。应全局优化概率搜索算法。它摒弃了传统的搜索方式，模拟自然界生物

23、进化过程，采用人工的方式对目标空间进行随机化搜索。Algorithms in Mathematical ModelingGenetic Algorithm272022/11/13 遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子遗传算子(选择、交叉和变选择、交叉和变异异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。遗传算法的搜索机制遗传算法的搜索机制Algorithms in Mathematical ModelingGenetic Algo

24、rithm282022/11/13局部局部局部局部全局全局全局全局遗传算法遗传算法(GA)Algorithms in Mathematical ModelingGenetic Algorithm292022/11/13We 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遗传算

25、法遗传算法(GA)GA-第0代Algorithms in Mathematical ModelingGenetic Algorithm302022/11/13Dead oneDead oneNew oneNew one遗传算法遗传算法(GA)GA-第1代Algorithms in Mathematical ModelingGenetic Algorithm312022/11/13Not at the top,Not at the top,Come Up!Come Up!遗传算法遗传算法(GA)GA-第?代Algorithms in Mathematical ModelingGenetic Al

26、gorithm322022/11/13I am the I am the BESTBEST!遗传算法遗传算法(GA)GA-第N代Algorithms in Mathematical ModelingGenetic Algorithm332022/11/13适者生存适者生存(Survival of the Fittest)GA主要采用的进化规则是主要采用的进化规则是“适者生存适者生存”较好的解保留，较差的解淘汰较好的解保留，较差的解淘汰遗传算法遗传算法(GA)Algorithms in Mathematical ModelingGenetic Algorithm342022/11/13生物进化与

27、遗传算法对应关系生物进化与遗传算法对应关系生物进化生物进化遗传算法遗传算法适者生存适应函数值最大的解被保留的概率最大个体问题的一个解染色体解的编码基因编码的元素群体被选定的一组解种群根据适应函数选择的一组解交叉以一定的方式由双亲产生后代的过程变异编码的某些分量发生变化的过程环境适应函数Algorithms in Mathematical ModelingGenetic Algorithm352022/11/13遗传算法的基本操作遗传算法的基本操作选择选择(selection):根据各个个体的适应值，按照一定的规则或方法，从第t代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t+1)中。

28、交叉交叉(crossover):将群体P(t)内的各个个体随机搭配成对，对每一个个体，以某个概率Pc(称为交叉概率，crossvoer rate)交换它们之间的部分染色体。变异变异(mutation):对群体P(t)中的每一个个体，以某一概率Pm(称为变异概率，mutation rate)改变某一个或一些基因座上基因值为其它的等位基因。Algorithms in Mathematical ModelingGenetic Algorithm362022/11/13如何设计遗传算法如何设计遗传算法如何进行编码？如何进行编码？如何产生初始种群？如何产生初始种群？如何定义适应函数？如何定义适应函数？如

29、何进行遗传操作如何进行遗传操作(复制、交叉、变异复制、交叉、变异)？如何产生下一代种群？如何产生下一代种群？如何定义停止准则如何定义停止准则？Algorithms in Mathematical ModelingGenetic Algorithm372022/11/13编码编码(Coding)表现型空间编码(Coding)解码(Decoding)基因型空间=0,1L0111010010100010011001001010010001Algorithms in Mathematical ModelingGenetic Algorithm382022/11/13选择选择(Selection)选择选

30、择(复制复制)操作把当前种群的染色体按与适应值成正比操作把当前种群的染色体按与适应值成正比例的概率复制到新的种群中例的概率复制到新的种群中 主要思想主要思想:适应值较高的染色体体有较大的选择适应值较高的染色体体有较大的选择(复制复制)机会机会实现实现1：”轮盘赌轮盘赌”选择选择(Roulette wheel selection)将种群中所有染色体的适应值相加求总和，染色体适应将种群中所有染色体的适应值相加求总和，染色体适应值按其比例转化为选择概率值按其比例转化为选择概率Ps产生一个在产生一个在0与总和之间的的随机数与总和之间的的随机数m从种群中编号为从种群中编号为1的染色体开始，将其适应值与后

31、续染的染色体开始，将其适应值与后续染色体的适应值相加，直到累加和等于或大于色体的适应值相加，直到累加和等于或大于mAlgorithms in Mathematical ModelingGenetic Algorithm392022/11/13选择选择(Selection)设种群的规模为Nxi是i为种群中第i个染色体AC1/6=17%3/6=50%B2/6=33%fitness(A)=3fitness(B)=1fitness(C)=2染色体xi被选概率Algorithms in Mathematical ModelingGenetic Algorithm402022/11/13选择选择(Sele

32、ction)染色体的适应值和所占的比例染色体的适应值和所占的比例轮盘赌选择Algorithms in Mathematical ModelingGenetic Algorithm412022/11/13选择选择(Selection)随机数234913 386 27所选号码 26 2 51 4所选染色体110000001111000011000111010010染色体编号 1 2 3 4 5 6染色体011101100000100100100110000011适应度 8 152 5 128被选概率0.160.30.040.10.240.16适应度累计 8 23 25 30 42 50染色体被选的

33、概率被选的染色体Algorithms in Mathematical ModelingGenetic Algorithm422022/11/13选择选择(Selection)轮轮盘盘上上的的片片分分配配给给群群体体的的染染色色体体，使使得得每每一一个个片片的的大大小小与与对对于于染染色体的适应值成比例色体的适应值成比例从从群群体体中中选选择择一一个个染染色色体体可可视视为为旋旋转转一一个个轮轮盘盘，当当轮轮盘盘停停止止时时，指针所指的片对于的染色体就时要选的染色体。指针所指的片对于的染色体就时要选的染色体。模拟模拟“轮盘赌轮盘赌”算法算法：(1)r=random(0,1)，s=0，i=0；(2

34、)如果如果sr，则转，则转(4)；(3)s=s+p(xi)，i=i+1,转转(2)(4)xi即为被选中的染色体，输出即为被选中的染色体，输出I(5)结束结束Algorithms in Mathematical ModelingGenetic Algorithm432022/11/13选择选择(Selection)其他选择法其他选择法：随机遍历抽样随机遍历抽样(Stochastic universal sampling)局部选择局部选择(Local selection)截断选择截断选择(Truncation selection)竞标赛选择竞标赛选择(Tournament selection)特点

35、特点：选择操作得到的新的群体称为交配池，交配池是当前代和下一代之间的中间群体，其规模为初始群体规模。选择操作的作用效果是提高了群体的平均适应值(低适应值个体趋于淘汰，高适应值个体趋于选择)，但这也损失了群体的多样性多样性。选择操作没有产生新的个体，群体中最好个体的适应值不会改变。Algorithms in Mathematical ModelingGenetic Algorithm442022/11/13交叉交叉(crossover,Recombination)遗传交叉(杂交、交配、有性重组)操作发生在两个染色体之间，由两个被称之为双亲的父代染色体，经杂交以后，产生两个具有双亲的部分基因的新的

36、染色体，从而检测搜索空间中新的点。选择(复制)操作每次作用在一个染色体上，而交叉操作每次作用在从交配池中随机选取的两个个体上(交叉概率Pc)。交叉产生两个子染色体，他们与其父代不同，且彼此不同,每个子染色体都带有双亲染色体的遗传基因。Algorithms in Mathematical ModelingGenetic Algorithm452022/11/13单点交叉单点交叉(1-point crossover)在双亲的父代染色体中随机产生一个交叉点位置在双亲的父代染色体中随机产生一个交叉点位置在交叉点位置分离双亲染色体在交叉点位置分离双亲染色体互换交叉点位置右边的基因码产生两个子代染色体互换

37、交叉点位置右边的基因码产生两个子代染色体交叉概率交叉概率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交叉点位置交叉点位置交叉点位置交叉点位置Algorithms in Mathematical ModelingGenetic Algorithm462022/

38、11/13交叉交叉(crossover,Recombination)单点交叉操作可以产生与父代染色体完全不同的子代染色体；它不会改变父代染色体中相同的基因。但当双亲染色体相同时，交叉操作是不起作用的。假如交叉概率Pc 50%,则交配池中50%的染色体(一半染色体)将进行交叉操作，余下的50%的染色体进行选择(复制)操作。GA利用选择和交叉操作可以产生具有更高平均适应值和更好染色体的群体Algorithms in Mathematical ModelingGenetic Algorithm472022/11/13变异变异(Mutation)以变异概率Pm改变染色体的某一个基因,当以二进制编码时，

39、变异的基因由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子代子代子代子代变异基因变异基因变异基因变异基因变异基因变异基因变异基因变异基因Algorithms in Mathematical ModelingGenetic Algorithm482022/11/13变异变异(Mutation)比起选择和交叉操作，变异操作是GA中的次要操作，但它在恢复群体中失去的多样性多样性方面具有潜在的作用。在GA执行的开始阶段，染色体中一个特定位上

40、的值1可能与好的性能紧密联系，即搜索空间中某些初始染色体在那个位上的值1可能一致产生高的适应值。因为越高的适应值与染色体中那个位上的值1相联系，选择操作就越会使群体的遗传多样性损失。等到达一定程度时，值0会从整个群体中那个位上消失，然而全局最优解可能在染色体中那个位上为0。如果搜索范围缩小到实际包含全局最优解的那部分搜索空间，在那个位上的值0就可能正好是到达全局最优解所需要的。Algorithms in Mathematical ModelingGenetic Algorithm492022/11/13适应函数适应函数(Fitness Function)GA在搜索中不依靠外部信息，仅以适应函数

41、为依据，利用群体中每个染色体(个体)的适应值来进行搜索。以染色体适应值的大小来确定该染色体被遗传到下一代群体中的概率。染色体适应值越大，该染色体被遗传到下一代的概率也越大；反之，染色体的适应值越小，该染色体被遗传到下一代的概率也越小。因此适应函数的选取至关重要，直接影响到GA的收敛速度以及能否找到最优解。群体中的每个染色体都需要计算适应值适应函数一般由目标函数变换而成Algorithms in Mathematical ModelingGenetic Algorithm502022/11/13适应函数适应函数(Fitness Function)适应函数常见形式：适应函数常见形式：直接将目标函数

42、转化为适应函数直接将目标函数转化为适应函数若目标函数为最大化问题：Fitness(f(x)=f(x)若目标函数为最小化问题：Fitness(f(x)=-f(x)缺点:(1)可能不满足轮盘赌选择中概率非负的要求(2)某些代求解的函数值分布上相差很大，由此得到的评价适应值可能不利于体现群体的评价性能，影响算法的性能。Algorithms in Mathematical ModelingGenetic Algorithm512022/11/13适应函数适应函数(Fitness Function)界限构造法界限构造法 目标函数为最大化问题其中Cmin为f(x)的最小估计值目标函数为最小化问题其中Cma

43、xn为f(x)的最大估计值Algorithms in Mathematical ModelingGenetic Algorithm522022/11/13停止准则停止准则(Termination Criteria)种群中个体的最大适应值超过预设定值种群中个体的平均适应值超过预设定值种群中个体的进化代数超过预设定值Algorithms in Mathematical ModelingGenetic Algorithm532022/11/13基本步骤基本步骤(Step by Step)(1)随机产生初始种群;(2)计算种群体中每个个体的适应度值,判断是否满足停止条件，若不满足，则转第(3)步,否则

44、转第(6)步;(3)按由个体适应值所决定的某个规则选择将进入下一代的个体;(4)按交叉概率Pc进行交叉操作,生产新的个体;(5)按变异概率Pm进行变异操作,生产新的个体;(6)输出种群中适应度值最优的染色体作为问题的满意解或最优解。Algorithms in Mathematical ModelingGenetic Algorithm542022/11/13流程图流程图(Flow Chart)Algorithms in Mathematical ModelingGenetic Algorithm552022/11/13基本遗传算法基本遗传算法基本遗传算法（Simple Genetic Algo

45、rithms,简称SGA）是一种统一的最基本的遗传算法，它只使用选择、交叉、变异这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。Algorithms in Mathematical ModelingGenetic Algorithm562022/11/13SGA伪码描述伪码描述Procedure Genetic Algorithm beginbegint=0;初始化 P(t);计算 P(t)的适应值;while(不满足停止准则)do begin t=t+1;从P(t-1)中选择 P(t);%

46、selection 重组 P(t);%crossover and mutation 计算 P(t)的适应值;end endAlgorithms in Mathematical ModelingGenetic Algorithm572022/11/13遗传算法的应用遗传算法的应用函数优化函数优化 函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能测试评价的常用算例。对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，而遗传算法却可以方便地得到较好的结果。遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很

47、多学科。下面列举一些遗传算法的主要应用领域。Algorithms in Mathematical ModelingGenetic Algorithm582022/11/13遗传算法的应用遗传算法的应用组合优化组合优化 遗传算法是寻求组合优化问题满意解的最佳工具之一，实践证明，遗传算法对于组合优化问题中的NP完全问题非常有效。例如，遗传算法已经在求解旅行商问题(Traveling Salesman Problem,TSP)、背包问题(Knapsack Problem)、装箱问题(Bin Packing Problem)等方面得到成功的应用。生产调度问题生产调度问题 生产调度问题在很多情况下所建立

48、起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解也会因简化得太多而使求解结果与实际相差太远。现在遗传算法已经成为解决复杂调度问题的有效工具。Algorithms in Mathematical ModelingGenetic Algorithm592022/11/13遗传算法的应用遗传算法的应用自动控制自动控制 遗传算法已经在自动控制领域中得到了很好的应用，例如基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权值学习等。机器人智能控制机器人智能控制 机器人是一类复杂的难以精确建模的人工系统，而

49、遗传算法的起源就来自于对人工自适应系统的研究，所以机器人智能控制自然成为遗传算法的一个重要应用领域。Algorithms in Mathematical ModelingGenetic Algorithm602022/11/13遗传算法的应用遗传算法的应用图象处理和模式识别图象处理和模式识别 图像处理和模式识别是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地存在一些误差，这些误差会影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求，遗传算法在这些图像处理中的优化计算方面得到了很好的应用。人工生命人工生命 人工生命是用计算机、机械等

50、人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。自组织能力和自学习能力是人工生命的两大重要特征。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要理论基础。Algorithms in Mathematical ModelingGenetic Algorithm612022/11/13遗传算法的应用遗传算法的应用遗传程序设计遗传程序设计 Koza发展了遗传程序设计的概念，他使用了以LISP语言所表示的编码方法，基于对一种树形结构所进行的遗传操作来自动生成计算机程序。机器学习机器学习 基于遗传算法的机器学习，在很多领域中都得到了应用。例如基于遗传算法的机器学