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

数学建模中惯用算法成都信息工程学院计算科学系胡建成jianchenghu@163.com-5-2010/10/第1页数学建模竞赛网上资源CUMCM网站:

MCM和ICM网站:

中国数学建模:

中科大建模网站:

MATLAB网站:

GOOGLE大学10/10/第2页数学建模竞赛中算法(1)93A非线性交调频率设计:拟合、规划93B足球队排名次:矩阵论、图论、层次分析法、整数规划94A逢山开路:图论、插值、动态规划94B锁具装箱问题:图论、组合数学95A飞行管理问题:非线性规划、线性规划95B天车与冶炼炉作业调度:非线性规划、动态规划、层次分析法、PETRI方法、图论方法、排队论方法96A最优打鱼策略：微分方程、积分、非线性规划10/10/第3页96B节水洗衣机：非线性规划97A零件参数设计：微积分、非线性规划、随机模拟97B截断切割：组合优化、几何变换、枚举、蒙特卡罗、递归、最短路98A投资收益与风险：线性规划、非线性规划98B灾情巡视：最小生成树、Hamilton圈、旅行商问题99A自动化车床：积分、概率分布、随机模拟、分布拟合度检验数学建模竞赛中算法(2)10/10/第4页99B钻井布局：几何变换、枚举、最大完全子图、混合整数规划00ADNA分类：神经网络、最小二乘拟合、统计分类00B管道订购：最短路、二次规划01A血管三维重建：数据挖掘、曲面重建与拟合01B公交车调度：非线性规划02A车灯光源优化设计：最优化02B彩票中数学：概率与优化数学建模竞赛中算法(3)10/10/第5页

MATLAB

Maple

Mathematica

Lindo

Lingo

SAS

SPSS

C&C++

Fortran

Pascal数学建模惯用软件10/10/第6页1.

蒙特卡罗方法(Monte-Carlo方法,MC)数学建模竞赛惯用算法(1)

该算法又称计算机随机性模拟方法，也称统计试验方法。MC方法是一个基于“随机数”计算方法，能够比较逼真地描述事物特点及物理试验过程，处理一些数值方法难以处理问题。MC方法雏型能够追溯到十九世纪后期蒲丰随机投针试验，即著名蒲丰问题。MC方法经过计算机仿真(模拟)处理问题，同时也能够经过模拟来检验自己模型正确性，是比赛中经常使用方法。10/10/第7页97年A题每个零件都有自己标定值，也都有自己容差等级，而求解最优组合方案将要面对着是一个极其复杂公式和108种容差选取方案，根本不可能去求解析解，那怎样去找到最优方案呢？随机性模拟搜索最优方案就是其中一个方法，在每个零件可行区间中按照正态分布随机选取一个标定值和选取一个容差值作为一个方案，然后经过蒙特卡罗算法仿真出大量方案，从中选取一个最正确。B题关于彩票第二问，要求设计一个更加好方案，首先方案优劣取决于很多复杂原因，一样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。数学建模竞赛惯用算法10/10/第8页98年美国赛A题

生物组织切片三维插值处理94年A题逢山开路

山体海拔高度插值计算数学建模竞赛惯用算法(2)2.数据拟合、参数预计、插值等数据处理算法比赛中通常会碰到大量数据需要处理，而处理数据关键就在于这些算法，通常使用MATLAB作为工具。与图形处理相关问题很多与拟合相关系。这类问题在MATLAB中有很多函数能够调用，只有熟悉MATLAB，这些方法才能用好。10/10/第9页98年B题用很多不等式完全能够把问题刻画清楚数学建模竞赛惯用算法(3)3.规划类问题算法这类问题主要有线性规划、整数规划、多元规划、二次规划等。竞赛中很多问题都和数学规划相关，能够说不少模型都能够归结为一组不等式作为约束条件、几个函数表示式作为目标函数问题，碰到这类问题，求解就是关键了。所以列举出规划后用Lindo、Lingo等软件来进行处理比较方便，所以还需要熟悉这两个软件。10/10/第10页98年B题、B题、95年锁具装箱等问题表达了图论问题主要性。数学建模竞赛惯用算法(4)4.

图论问题

这类问题算法有很多，包含：Dijkstra、Floyd、Prim、Bellman-Ford，最大流，二分匹配等问题。10/10/第11页92年B题用分枝定界法97年B题是经典动态规划问题98年B题表达了分治算法数学建模竞赛惯用算法(5)5.计算机算法设计中问题

计算机算法设计包含很多内容：动态规划、回溯搜索、分治算法、分枝定界等计算机算法.

这方面问题和ACM程序设计竞赛中问题类似，可看一下与计算机算法相关书。10/10/第12页97年A题用模拟退火算法B题用神经网络分类算法B题这种难题也能够使用神经网络美国89年A题也和BP算法相关系美国B题伽马刀问题也是当前研究课题，当前算法最正确是遗传算法。数学建模竞赛惯用算法(6)6.最优化理论三大非经典算法:模拟退火法(SA)、神经网络(NN)、遗传算法(GA)近几年赛题越来越复杂，很多问题没有什么很好模型能够借鉴，于是这三类算法很多时候能够派上用场。10/10/第13页97年A题、99年B题都能够用网格法搜索数学建模竞赛惯用算法(7)网格算法和穷举法一样，只是网格法是连续问题穷举。这类算法运算量较大。7.网格算法和穷举算法这种方法最好在运算速度较快计算机中进行，还有要用高级语言来做，最好不要用MATLAB做网格，不然会算很久。10/10/第14页很多问题都是实际来，数据能够是连续，而计算机只能处理离散数据，所以需要将连续问题进行离散化处理后再用计算机求解。比如差分代替微分、求和代替积分等思想都是把连续问题离散化惯用方法。数学建模竞赛惯用算法(8)8.连续问题离散化方法10/10/第15页数值分析研究各种求解数学问题数值计算方法，尤其是适合于计算机实现方法与算法。数学建模竞赛惯用算法(9)9.数值分析方法它主要内容包含函数数值迫近、数值微分与数值积分、非线性方程数值解法、数值代数、常微分方程数值解等。数值分析是计算数学一个主要分支，把理论与计算紧密结合,是当代科学计算基础。MATLAB等数学软件中已经有很多数值分析函数能够直接调用。10/10/第16页A题中需要你会读BMP图象98年美国A题需要你知道三维插值计算B题要求更高，不但需要编程计算还要进行处理数学建模竞赛惯用算法(10)10.图象处理算法赛题中有一类问题与图形相关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形怎样展示以及怎样处理就是需要处理问题，通常使用MATLAB进行处理。数模论文中也有很多图片需要展示，处理这类问题要熟悉MATLAB图形图像工具箱。10/10/第17页三个孩子年纪(1)两个多年未见朋友相遇，聊了很多事情。…A：既然你是数学教授，那你帮我算这个题，今天是个特殊日子：我三个儿子都在今天庆贺生日！那么你能算出他们都有多大吗？B：好，但你得跟我讲讲他们情况。A：好，我给你一些提醒，他们三个年纪之积是36.B：很好，但我还需要更多提醒。10/10/第18页三个孩子年纪(2)A：我大儿子眼睛是蓝色。B考虑了一下说，不过，我还有一点信息来处理你这个难题。B：哦，够了，B给出了正确答案，即三个小孩年纪。A：他们三个年纪之和等于那幢房子窗户个数。A指着对面一幢房子说。10/10/第19页三个孩子年纪(3)依据对话信息，用搜索方法来解此问题。信息1:三个小孩年纪之积为36只有以下8种可能，搜索范围降低至8种情况:第一个小孩年纪36181299664第二个小孩年纪12342633第三个小孩年纪1111212310/10/第20页三个孩子年纪(4)信息2:三个小孩年纪之和等于窗户数第一个小孩年纪36181299664第二个小孩年纪12342633第三个小孩年纪11112123窗户数:3821161413131110假如窗户数为38、21、16、14、11、10即可得出答案B还需信息，即窗户数为13.则可能为(9、2、2)或(6、6、1)信息2:大儿子眼睛是蓝色得答案：(9、2、2)10/10/第21页智能优化算法

智能优化算法又称为当代启发式算法，是一种含有全局优化性能、通用性强、且适合于并行处理算法。这种算法普通含有严密理论依据,而不是单纯凭借教授经验，理论上能够在一定时间内找到最优解或近似最优解。10/10/第22页惯用智能优化算法

遗传算法

GeneticAlgorithm，简称GA模拟退火算法SimulatedAnnealing，简称SA禁忌搜索算法TabuSearch，简称TS……10/10/第23页智能优化算法特点它们共同特点：都是从任一解出发，按照某种机制，以一定概率在整个求解空间中探索最优解。因为它们能够把搜索空间扩展到整个问题空间，因而含有全局优化性能。10/10/第24页遗传算法(GeneticAlgorithm)进化算法(EvolutionaryAlgorithm)10/10/第25页遗传算法(GA)Darwin(1859):“物竟天择，适者生存”JohnHolland(universityofMichigan,1975)

《AdaptationinNaturalandArtificialSystem》遗传算法作为一个有效工具，已广泛地应用于最优化问题求解之中。遗传算法是一个基于自然群体遗传进化机制自适应全局优化概率搜索算法。它摒弃了传统搜索方式，模拟自然界生物进化过程，采取人工方式对目标空间进行随机化搜索。10/10/第26页遗传算法模拟自然选择和自然遗传过程中发生繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代候选解群，重复此过程，直到满足某种收敛指标为止。遗传算法搜索机制10/10/第27页局部全局遗传算法(GA)10/10/第28页Wehaveadream!!IamatthetopHeightis...Iamnotatthetop.Myhighisbetter!Iwillcontinue遗传算法(GA)GA-----第0代10/10/第29页DeadoneNewone遗传算法(GA)GA----第1代10/10/第30页Notatthetop,ComeUp!!!遗传算法(GA)GA----第?代10/10/第31页IamtheBEST!!!遗传算法(GA)GA----第N代10/10/第32页适者生存(SurvivaloftheFittest)GA主要采取进化规则是“适者生存”很好解保留，较差解淘汰遗传算法(GA)10/10/第33页生物进化与遗传算法对应关系生物进化遗传算法适者生存适应函数值最大解被保留概率最大个体问题一个解染色体解编码基因编码元素群体被选定一组解种群依据适应函数选择一组解交叉以一定方式由双亲产生后代过程变异编码一些分量发生改变过程环境适应函数10/10/第34页遗传算法基本操作选择(selection):

依据各个个体适应值，按照一定规则或方法，从第t代群体P(t)中选择出一些优良个体遗传到下一代群体P(t+1)中。交叉(crossover):

将群体P(t)内各个个体随机搭配成对，对每一个个体，以某个概率Pc

(称为交叉概率，crossvoerrate)交换它们之间部分染色体。变异(mutation):

对群体P(t)中每一个个体，以某一概率Pm(称为变异概率，mutationrate)改变某一个或一些基因座上基因值为其它等位基因。10/10/第35页怎样设计遗传算法怎样进行编码？怎样产生初始种群？怎样定义适应函数？怎样进行遗传操作(复制、交叉、变异)？怎样产生下一代种群？怎样定义停顿准则？10/10/第36页编码(Coding)表现型空间编码(Coding)解码(Decoding)基因型空间={0,1}L011101001010001001100100101001000110/10/第37页选择(Selection)选择(复制)操作把当前种群染色体按与适应值成正百分比概率复制到新种群中

主要思想:适应值较高染色体体有较大选择(复制)机会实现1：”轮盘赌”选择(Roulettewheelselection)将种群中全部染色体适应值相加求总和，染色体适应值按其百分比转化为选择概率Ps产生一个在0与总和之间随机数m从种群中编号为1染色体开始，将其适应值与后续染色体适应值相加，直到累加和等于或大于m10/10/第38页选择(Selection)设种群规模为Nxi是i为种群中第i个染色体AC1/6=17%3/6=50%B2/6=33%fitness(A)=3fitness(B)=1fitness(C)=2染色体xi被选概率10/10/第39页选择(Selection)染色体适应值和所占百分比轮盘赌选择10/10/第40页选择(Selection)随机数23491338627所选号码262514所选染色体110000001111000011000111010010染色体编号123456染色体011101100000100100100110000011适应度81525128被选概率0.160.30.040.10.240.16适应度累计8

23

253042

50染色体被选概率被选染色体10/10/第41页选择(Selection)轮盘上片分配给群体染色体，使得每一个片大小与对于染色体适应值成百分比从群体中选择一个染色体可视为旋转一个轮盘，当轮盘停顿时，指针所指片对于染色体就时要选染色体。模拟“轮盘赌”算法：r=random(0,1)，s=0，i=0；假如s≥r，则转(4)；s=s+p(xi)，i=i+1,转(2)xi即为被选中染色体，输出I结束10/10/第42页选择(Selection)其它选择法：随机遍历抽样(Stochasticuniversalsampling)局部选择(Localselection)截断选择(Truncationselection)竞标赛选择(Tournamentselection)特点：选择操作得到新群体称为交配池，交配池是当前代和下一代之间中间群体，其规模为初始群体规模。选择操作作用效果是提升了群体平均适应值(低适应值个体趋于淘汰，高适应值个体趋于选择)，但这也损失了群体多样性。选择操作没有产生新个体，群体中最好个体适应值不会改变。10/10/第43页交叉(crossover,Recombination)遗传交叉(杂交、交配、有性重组)操作发生在两个染色体之间，由两个被称之为双亲父代染色体，经杂交以后，产生两个含有双亲部分基因新染色体，从而检测搜索空间中新点。选择(复制)操作每次作用在一个染色体上，而交叉操作每次作用在从交配池中随机选取两个个体上(交叉概率Pc)。交叉产生两个子染色体，他们与其父代不一样，且彼此不一样,每个子染色体都带有双亲染色体遗传基因。10/10/第44页单点交叉(1-pointcrossover)在双亲父代染色体中随机产生一个交叉点位置在交叉点位置分离双亲染色体交换交叉点位置右边基因码产生两个子代染色体交叉概率Pc

普通范围为(60%,90%)，平均约80%11111111父代1111000000000000子代111100000000000011111111交叉点位置10/10/第45页交叉(crossover,Recombination)单点交叉操作能够产生与父代染色体完全不一样子代染色体；它不会改变父代染色体中相同基因。但当双亲染色体相同时，交叉操作是不起作用。假如交叉概率Pc

＝50%,则交配池中50%染色体(二分之一染色体)将进行交叉操作，余下50%染色体进行选择(复制)操作。GA利用选择和交叉操作能够产生含有更高平均适应值和更加好染色体群体10/10/第46页变异(Mutation)以变异概率Pm改变染色体某一个基因,当以二进制编码时，变异基因由0变成1，或者由1变成0。变异概率Pm普通介于1/种群规模与1/染色体长度之间，平均约1-2%11010100父代01010101子代变异基因变异基因10/10/第47页变异(Mutation)比起选择和交叉操作，变异操作是GA中次要操作，但它在恢复群体中失去多样性方面含有潜在作用。

在GA执行开始阶段，染色体中一个特定位上值1可能与好性能紧密联络，即搜索空间中一些初始染色体在那个位上值1可能一致产生高适应值。因为越高适应值与染色体中那个位上值1相联系，选择操作就越会使群体遗传多样性损失。等抵达一定程度时，值0会从整个群体中那个位上消失，然而全局最优解可能在染色体中那个位上为0。假如搜索范围缩小到实际包含全局最优解那部分搜索空间，在那个位上值0就可能恰好是抵达全局最优解所需要。10/10/第48页适应函数(FitnessFunction)GA在搜索中不依靠外部信息，仅以适应函数为依据，利用群体中每个染色体(个体)适应值来进行搜索。以染色体适应值大小来确定该染色体被遗传到下一代群体中概率。染色体适应值越大，该染色体被遗传到下一代概率也越大；反之，染色体适应值越小，该染色体被遗传到下一代概率也越小。所以适应函数选取至关主要，直接影响到GA收敛速度以及能否找到最优解。群体中每个染色体都需要计算适应值适应函数普通由目标函数变换而成10/10/第49页适应函数(FitnessFunction)适应函数常见形式：直接将目标函数转化为适应函数若目标函数为最大化问题：

Fitness(f(x))=f(x)若目标函数为最小化问题：

Fitness(f(x))=-f(x)缺点:(1)可能不满足轮盘赌选择中概率非负要求

(2)一些代求解函数值分布上相差很大，由此得到评价适应值可能不利于表达群体评价性能，影响算法性能。10/10/第50页适应函数(FitnessFunction)界限结构法

目标函数为最大化问题其中Cmin为f(x)最小预计值目标函数为最小化问题其中Cmaxn为f(x)最大预计值10/10/第51页停顿准则(TerminationCriteria)种群中个体最大适应值超出预设定值种群中个体平均适应值超出预设定值种群中个体进化代数超出预设定值10/10/第52页基本步骤(StepbyStep)(1)随机产生初始种群;(2)计算种群体中每个个体适应度值,判断是否满足停顿条件，若不满足，则转第(3)步,不然转第(6)步;(3)按由个体适应值所决定某个规则选择将进入下一代个体;(4)按交叉概率Pc进行交叉操作,生产新个体;(5)按变异概率Pm进行变异操作,生产新个体;(6)输出种群中适应度值最优染色体作为问题满意解或最优解。10/10/第53页流程图(FlowChart)10/10/第54页基本遗传算法基本遗传算法（SimpleGeneticAlgorithms,简称SGA）是一个统一最基本遗传算法，它只使用选择、交叉、变异这三种基本遗传算子，其遗传进化操作过程简单，轻易了解，是其它一些遗传算法雏形和基础，它不但给各种遗传算法提供了一个基本框架，同时也含有一定应用价值。10/10/第55页SGA伪码描述ProcedureGeneticAlgorithm

begint=0;初始化P(t);计算P(t)适应值;while(不满足停顿准则)dobegint=t+1;从P(t-1)中选择P(t);%selection重组P(t);%crossoverandmutation计算P(t)适应值;end

end10/10/第56页遗传算法应用函数优化

函数优化是遗传算法经典应用领域，也是对遗传算法进行性能测试评价惯用算例。对于一些非线性、多模型、多目标函数优化问题，用其它优化方法较难求解，而遗传算法却能够方便地得到很好结果。遗传算法提供了一个求解复杂系统优化问题通用框架，它不依赖于问题详细领域，对问题种类有很强鲁棒性，所以广泛应用于很多学科。下面列举一些遗传算法主要应用领域。10/10/第57页遗传算法应用组合优化

遗传算法是寻求组合优化问题满意解最正确工具之一，实践证实，遗传算法对于组合优化问题中NP完全问题非常有效。比如，遗传算法已经在求解旅行商问题(TravelingSalesmanProblem,TSP)、背包问题(KnapsackProblem)、装箱问题(BinPackingProblem)等方面得到成功应用。生产调度问题

生产调度问题在很多情况下所建立起来数学模型难以准确求解，即使经过一些简化之后能够进行求解也会因简化得太多而使求解结果与实际相差太远。现在遗传算法已经成为处理复杂调度问题有效工具。10/10/第58页遗传算法应用自动控制

遗传算法已经在自动控制领域中得到了很好应用，比如基于遗传算法含糊控制器优化设计、基于遗传算法参数辨识、基于遗传算法含糊控制规则学习、利用遗传算法进行人工神经网络结构优化设计和权值学习等。机器人智能控制

机器人是一类复杂难以准确建模人工系统，而遗传算法起源就来自于对人工自适应系统研究，所以机器人智能控制自然成为遗传算法一个主要应用领域。

10/10/第59页遗传算法应用图象处理和模式识别

图像处理和模式识别是计算机视觉中一个主要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可防止地存在一些误差，这些误差会影响图像处理效果。怎样使这些误差最小是使计算机视觉到达实用化主要要求，遗传算法在这些图像处理中优化计算方面得到了很好应用。人工生命

人工生命是用计算机、机械等人工媒体模拟或结构出含有自然生物系统特有行为人造系统。自组织能力和自学习能力是人工生命两大主要特征。人工生命与遗传算法有着亲密关系，基于遗传算法进化模型是研究人工生命现象主要理论基础。10/10/第60页遗传算法应用遗传程序设计

Koza发展了遗传程序设计概念，他使用了以LISP语言所表示编码方法，基于对一个树形结构所进行遗传操作来自动生成计算机程序。

机器学习

基于遗传算法机器学习，在很多领域中都得到了应用。比如基于遗传算法机器学习可用来调整人工神经网络连接权，也能够用于人工神经网络网络结构优化设计。分类器系统在多机器人路径规划系统中得到了成功应用。10/10/第61页SGA实例1：函数最值SGA参数:编码方式:二进制码

e.g.000000;01101

13;1111131种群规模:4随机初始群体“转盘赌”选择一点杂交,二进制变异求函数f(x)=x2最大值，x为自然数且0≤x≤31.手工方式完成演示SGA过程10/10/第62页SGA实例1maxx2:选择操作10/10/第63页SGA实例1maxx2:交叉操作10/10/第64页SGA实例1maxx2:变异操作10/10/第65页SGA实例2:连续函数最值求以下函数最大值：10/10/第66页SGA实例2:编码高精度

编码[x,y]

{0,1}L

必须可逆(一个表现型对应一个基因型)

解码算子：:{0,1}L

[x,y]

染色体长度L决定可行解最大精度长染色体(慢进化)

实数问题：变量z为实数，怎样把{a1,…,aL}

{0,1}Lz∈[x,y]10/10/第67页SGA实例2:编码设定求解准确到6位小数，因区间长度位2-(-1)=3,则需将区间分为3X106等份。因2097152＝221<3X106≤222＝4194304。故编码二进制串长L=22。将一个二进制串(b21b20…b0)转化为10进制数：e.g.<0000000000000000000000>-1;<1111111111111111111111>2<1110000000111111000101>1.6278881.627888=-1+3x(1110000000111111000101)2

/(222-1)=-1+3x3674053/(222-1)10/10/第68页SGA实例2:初始化种群、适应函数随机初始化种群适应函数本实例目标函数在定义域内均大于0，且是求函数最大值，故直接引用目标函数作为适应函数：f(s)=f(x)其中二进制串s对于变量x值。e.g.s1=<0000001110000000010000>x1=-0.958973

适应值:f(s1)=f(x1)=1.078878

s2=<1110000000111111000101>x2=1.627888

适应值:f(s2)=f(x2)=3.25065010/10/第69页SGA实例2:遗传操作选择操作(“轮盘赌”选择)交叉操作(单点交叉)

交叉前(父):

s1=<00000|01110000000010000>s2=<11100|00000111111000101>

交叉后(子):

s’1=<00000|

00000111111000101>s’2=<11100|

01110000000010000>

适应值:f(s’1)=f(-0.998113)=1.940865f(s’2)=f(1.666028)=3.459245

s’2适应值比其双亲个体适应值高。10/10/第70页SGA实例2:遗传操作变异操作

变异前(父):

s2=<1110000000111111000101>

变异后(子):

s’2=<1110100000111111000101>

适应值

f(s’2)=f(1.721638)=0.917743比f(s2)小

变异前(父):

s2=<1110000000111111000101>

变异后(子):

s”2=<1110000001111111000101>

适应值

f(s”2)=f(1.630818)=3.343555比f(s2)大变异操作有”扰动”作用，同时含有增加种群多样性效果。10/10/第71页SGA实例2:模拟结果遗传算法参数:

种群规模:50染色体长度:L=22最大进化代数:150交叉概率:Pc=0.25变异概率:Pm=0.01

10/10/第72页SGA实例2:模拟结果(最正确个体进化情况)世代数染色体编码变量x适应值141117344054718915010001110000101100011110000011011000101001111011010101110011100111111101010111111010011111100001101111011001111110100100010001100111110001101101000110011110100110110001011001111110100111111001100111111010011111100110011111.8316241.8424161.8548601.8475361.8532901.8484431.8486991.8508971.8505491.8505493.5348063.7903623.8332863.8420043.8434023.8462323.8471553.8501623.8502743.85027410/10/第73页最优化问题(OptimizationProblem)最优化问题:组合优化问题(CombinatorialOptimizationProblem):最优化问题中解空间X或S由离散集合组成。其中很多问题是NP完全(NondeterministicPolynomialCompleteness)问题.10/10/第74页最优化问题算法传统优化方法(局部优化方法)

共轭梯度法、牛顿法、单纯形方法等特点:

1)依赖于初始条件。2)与求解空间有紧密关系，促使较快地收敛到局部解，但同时对解域有约束，如连续性或可微性。利用这些约束，收敛快。3)有些方法，如Davison-Fletcher-Powell直接依赖于最少一阶导数；共轭梯度法隐含地依赖于梯度。10/10/第75页最优化问题算法全局优化方法

下降轨线法、Monte-Carlo随机试验法、模拟退火法、GA等特点：1)不依赖于初始条件；2)不与求解空间有紧密关系,对解域无可微或连续要求;轻易实现，求解稳健。3)但收敛速度慢,能取得全局最优;适合于求解空间不知情况。4)GA可应用于大规模、多峰多态函数、含离散变量等全局优化问题;求解速度和质量远超出常规方法。10/10/第76页无约束最优化问题GA编码：X=(x1,x2,…,xn)各个变量能够按二进制编码方法分别编码。对于变量xi上、下限约束li≤xi≤

ui(i=1,2,…,n)，依据解精度要求(有效位数)求得各个变量X=(x1,x2,…,xn)二进制码位数(m1,m2,…,mn)(确定方法类似于SGA实例2)，所以将n个二进制位串次序连接起来，组成一个个体染色体编码，编码总位数m＝m1+m2+…+mn。无约束最优化问题:10/10/第77页无约束最优化问题GA解码：解码时仍按各个变量编码次序分别实现常规二进制编码解码方法。二进制遗传编码示意图以下：10/10/第78页约束最优化问题常规解法：(1)把约束问题转化为无约束问题，在用无约束问题方法求解，如罚函数法(2)改进无约束问题方法，再用于约束问题，如梯度投影法、广义简约梯度法约束最优化问题:10/10/第79页约束最优化问题遗传算法求解关键:约束条件处理等式约束能够包含到适应函数，仅考虑不等式约束。假设按无约束问题那样求解，在搜索过程中计算目标函数值，并检验是否有约束违反。假如没有违反，则表明是可行解，就依据目标函数指定一适应值；不然，就是不可行解，因而没有适应值(适应值为0)。这么处理实际不可行，因为找到一个可行解几乎与找到最优解一样困难。10/10/第80页普通解法：经过引入罚函数，从不可行解中得到一些信息。将罚函数包含到适应函数中。关键是怎样设计罚函数；不一样问题需要设计不一样罚函数；对普通约束处理，通常很困难。约束最优化问题10/10/第81页组合最优化问题经典问题：巡回旅行商问题(TravelingSalesmanProblem)作业调度问题(JobShopSchedulingProblem)背包问题(KnapsackProblem)图着色问题………很多组合最优化问题是NP难问题或NP完全问题10/10/第82页巡回旅行商问题(TSP)TSP，也称货郎担问题，是一个NP完全问题。TSP描述：图论:设图G=(V,E),其中V是顶点集，E是边集。设C=(cij)是与E相联络距离矩阵。寻找一条经过全部顶点且每个顶点只经过一次最短距离回路(Hamilton回路)。实际应用中，C也可解释为费用或旅行时间矩阵。实际:一位推销员从自己所在城市出发，必须遍访全部城市之后又回到原来城市，求使其旅行费用最少路径。10/10/第83页巡回旅行商问题(TSP)中国货郎担问题:城市数:40城市编号1,2,…,40寻找一条最短路径10/10/第84页TSP复杂性搜索空间庞大TSP包括求多个变量函数最小值，求解很困难。其可能路径条数伴随城市数目n成指数增加，如，5个城市对应12条路径；10个城市对应181440条路径；100个城市对应4.6663X10155条路径。如此庞大搜索空间，常规解法和计算工具都碰到计算上困难。只能寻找近似解法，如神经网络方法、模拟退火法、遗传算法等。10/10/第85页TSP编码:路径表示染色体表示成全部城市一个排列，若有n个城市，一条可能路径编码为长度为n整数向量(i1,i2,…,in),其中ik表示第ik个城市。比如:路径编码向量(517894623)直接表示一条旅行旅程(5->1->7->8->9->4->6->2->3)。此向量是1到n一个排列，即从1到n每个整数在这个向量中恰好出现一次,不能有重复。这么，基本遗传算法基因操作生成个体不能满足这一约束条件，需寻求其它遗传操作。10/10/第86页TSP交叉需其它方式交叉(重组)操作,如部分匹配交叉(PartiallyMatchedCrossover,PMX)、次序交叉(OrderedCrossover,OX)、循环交叉(CycleCrossover,CX)、边重组(EdgeRecombination)。12345543211232154345普通交叉操作会产生不适当解，如10/10/第87页TSP交叉1:部分匹配交叉(PMX)双亲P1,P2随机选取两个交叉点，得到一个匹配段,依据交叉点中间段给出映射关系。123456789937826514xxx4567xxxxx8265xxP1P2映射关系：48、52、75c1c2交换两个交叉点之间编码,(X表示未定码)10/10/第88页TSP交叉1:部分匹配交叉(PMX)子个体C1，C2分别从其父个体中继承未映射城市码12345678993782651493x45671x1x38265x9P1P2c1c2映射关系：48、52、75932456718173826549c1c2

再依据映射关系，对以上未定码，使用最初双亲码，得到子个体对应码。映射关系存在传递关系，则选择未定码交换。10/10/第89页TSP交叉2:次序交叉(OX)双亲P1,P2随机选取两个交叉点123456789937826514P1P2xxx4567xxxxx8265xxc1c2

两个交叉点间中间段保留不变

子个体C1未定码确实定需要父个体P2未选定城市码，子个体C2未定码确实定需要父个体P1未选定城市码。10/10/第90页TSP交叉2:次序交叉(OX)记取父个体P2从第二个交叉点开始城市码排列次序，当抵达表尾时，返回表头继续统计，直到第二个交叉点。937826514P2xxx4567xxc1382456719c1347826591c2

得到父个体P2排列次序1-4-9-3-7-8-2-6-5,并将C1已经有城市码4,5,6,7从中去掉，得到排列次序1-9-3-8-2，再将此顺序复制到C1，复制点也是从第二个交叉点开始，得到C1。同理C2，10/10/第91页TSP交叉3:循环交叉(CX)CX操作中子个体中城市码次序依据任一父个体产生确定循环编码复制循环编码到子个体10/10/第92页TSP变异InsertMutation随机选取个体中两个编码，然后把第二个编码放在第一个编码之后，其它编码顺次调整位置。

Swapmutation随机选取个体中两个编码，然后交换它们位置。10/10/第93页TSP变异Inversionmutation随机选取个体中一段编码，然后颠倒这段编码次序。

Scramblemutation随机选取个体上一段编码,然后打乱这段编码次序。选取编码不一定是邻接编码10/10/第94页TSPGA过程从N个随机起点开始产生N条路径，N为种群规模;利用最优方法搜索每条路径局部最优解;选择交叉对使在平均性能之上个体得到更多子代;交叉和变异;搜索每条路径得到其极小解，假如不收敛，则回到第3步；不然，停顿。10/10/第95页GAMATLAB实现软件平台(SoftwarePlatforms):MATLAB7.xGeneticAlgorithmandDirectSearchToolbox

2.0.1

MATLAB6.x(or7.x)+GAOTGAOT:GeneticAlgorithmOptimizationToolbox美国NorthCarolinaStateUniversity开发MATLAB6.x(or7.x)+GEATbxGEATbx:GeneticandEvolutionaryAlgorithmToolbox英国TheUniversityofSheffield开发《MATLAB遗传算法工具箱及应用》(雷英杰等,西安电子科技大学出版社,)基于此工具箱

10/10/第96页GAOT工具箱关键函数：[pop]=initializega(num,bounds,eevalFN,eevalOps,options)------初始种群生成函数【输出参数】pop-----生成初始种群【输入参数】num-----种群中个体数目bounds-----代表变量上下界矩阵eevalFN-----适应度函数eevalOps-----传递给适应度函数参数options-----选择编码形式(浮点编码或是二进制编码)与精度，如[typeprec]，type-----为1时选择浮点编码，不然为二进制编码prec-----变量进行二进制编码时指定精度，默认