1、现代优化算法 数学建模 数模课件现代优化算法什么是优化？就是从各种方案中选取一个最好的。从数学角度看，优化理论就是研究如何在状态空间中寻找到全局最优点。比如水泥混凝土的性能，涉及到水、沙、石子、水泥和其他掺杂物比例。学校课程表排课问题、售票员上岗问题、公司内部人员安排出效益等。降低成本、提高效益是问题的关键。一般的优化具有下面形式：minf(x1,x2,xn)s.t.g(x)0，xD其中x1,x2,xn（即问题的可行域，代表问题参数的选择范围），即minf(X)，其中X（矢量形式）。f(x)是决策问题的数学模型，也是决策问题的目标函数目标函数，g(x)0是决策问题的约束条件约束条件，D是决策问
2、题的定义域（可行域可行域）。问题归结为求极值。极值点非常多，需要找到全局最小点。注：注：求问题的最大和最小是同一个问题，算法完全一样。习惯上，将优化算法分为两类：局部优化算局部优化算法法和全局性优化算法全局性优化算法。前者可以称为经典优经典优化算法化算法，已经得到了人们广泛深入的研究。线性规划、整数规划、01规划、非线性规划、排队论、决策论。后者习惯上称为现代优化现代优化算法算法，是20世纪80年代兴起的新型全局性优化算法，主要包括禁忌搜索禁忌搜索、模拟退火模拟退火、遗传算法、神经网络等，其主要应用对象是优化问题中的难解问题难解问题，即NPhard问题 算法比喻 为了找出地球上最高的山，一群有
3、志气的兔子们开始想办法。方案一：兔子们吃了失忆药片，并被发射到太空，然后随机落到了地球上的某些地方。他们不知道自己的使命是什么。但是，如果你过几年就杀死一部分海拔低的兔子，多产的兔子们自己就会找到珠穆朗玛峰。遗传算法 方案二：兔子们朝着比现在高的地方跳去，它们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。其实，它们这种做法只是自己心理上认为找到了最高的山，并不能保证局部最优值就是全局最优值。局部搜索法 方案三：兔子们知道一个兔子的力量是渺小的。于是，它们互相转告着，哪里的山已经找过，并且找过的每一座山他们都留下一只兔子做记号。这样，它们制定了下一步去哪里寻找的策略。禁忌搜索法 方案四：
4、兔子们用酒将自己灌醉了。它们随机地跳了很长时间。在这期间，它们可能走向高处，也可能踏入平地。但是，随着时间的流逝，它们渐渐清醒了并朝最高方向跳去。模拟退火法 一一 遗传算法遗传算法遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。它最早由美国密执安大学的Holland教授提出，起源于60年代对自然和人工自适应系统的研究。70年代De.Jong 基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验。在一系列研究工作的基础上。80年代由Goldberg进行总结，形成了遗传算法的基本框架。一一 遗传算法遗传算法其主要特点是群体搜索策略和群体中个体之间的信
5、息交换，搜索不依赖于梯度信息。它的应用范围非常广泛，尤其适合于处理传统搜索方法难于解决的复杂和非线性问题，可广泛用于组合优化，机器学习，自适应控制，规划设计和人工生命等领域，从而确立了它在21世纪的智能计算技术中的关键地位。1 遗传算法的基本步骤 遗传算法流程图如下：集团中个体适应度的检测评估选择交叉变异图1 遗传算法的基本流程编码和初始集团生成一、编码一、编码 遗传算法主要是通过遗传操作对群体中具有某种结构形式的个体施加结重组处理，从而不断地搜索出群体中个体间结构相似性，由此可见，遗传算法不能直接处理问题空间参数，必须把它们转换成遗传空间的由基因按一定结构组成的染色体或个体。这一转换操作就叫
6、做编码。编码方法主要有：二进制编码，Gray编码，动态编码，实数编码，有序串编码，多参数编码，可变长编码等。（一）一维染色体编码（二值编码）所谓一维染色体编码是指搜索空间的参数转换到遗传空间过后，其相应的基因呈一维排列构成的染色体。具体地说，在遗传空间中，用以表示个体的字符集中的要素构成了字符串。如a,b,c,d或1,2,3,4。一维染色体编码中最常用的符号集是二进制符号0,1，基于此符号集的个体呈二值码串。二值编码的一般方法是：(1)根据所需要的精度确定参数的串长；(2)解码，由二值串转化成实数；例如：x=13,可被表示为01101。（二）多映射编码（多参数）在优化问题求解中常常会遇见多参数
7、优化问题。其基本思路是将每一个参数进行二值编码得到子串，每个子串对应各自的编码参数，然后将子串构成一个完整的染色体串。二、二、初始群体的生成初始群体的生成 遗传操作是对于多个体同时进行的。这众多的个体组成了群体。在遗传算法处理流程中，继编码设计后的任务是初始群体的设定，并以此为起点一代代进化直到按某种进化停止准则终止进化过程，由此得到最后一代（或群体）。其中需要考虑到两个因素：初始群体的设定；进化过程中各代（群体）的规模如何维持？它和交叉概率变异概率等参数一样，对于遗传算法效能的发挥是有影响的。初始群体的设定可采取如下策略：(1)根据问题固有的知识，设法确定最优解所占空间在整个问题空间中的分布
8、范围，然后，在此分布范围内设定初始群体。(2)先随机生成一定数目的个体，然后从中挑出最好的个体加到初始群体当中去。这种过程不断迭代，直到初始群体中个数达到了预先确定的规模。三、适应度函数三、适应度函数 适应度函数表明个体或解的优劣性。不同的问题，适应性函数的定义方式也不同。这一操作是借用了达尔文的自然选择原则，即个体适应度越高，其被选择的个体越多。遗传算法在进化搜索中基本上不用外部信息，仅用目标函数即适应度函数为依据。遗传函数的目标函数不受连续可微的约束且定义域可以为任意组合。对目标函数的唯一要求是，针对输入可计算出能加以比较的非负结果，这一特点使得遗传算法运用很广。在具体的应用中适应度函数的
9、设计要结合求解问题本身的要求而定，要强调的是，适应度函数评估是选择操作的依据，适应度函数的设计直接影响到遗传算法的性能。目标函数映射成适应度函数 在许多问题求解中，其目标函数是求取费用函数（代价函数）g（x）的最小值，而不是求效能函数或者利润函数的最大值。由于遗传算法中，适应度函数要比较排序并在此基础上计算选择概率，所以适应度函数的值要取正值。由此可见，在不少场合，将目标函数映射成最大值形式且函数值非负的适应度函数是很有必要的。在通常情况下，要把一个最小化函数转化为最大化问题，只需要简单的把费用函数乘以-1，即以下两种基本方法：（1）如目标函数为最大化问题：（2）如目标函数为最小化问题：但这对
10、遗传算法而言，这种方法还不足以保证在各种情况下的非负值。对此可以采用以下的方法进行转换：（3）其中 可以采用目前g(x)出现过的最大值或者当前群体当中出现过的最大值，但最好与群体无关。maxmax(),()()0,Cg xg xCf x当其他情况maxC()()Fit f xf x()()Fit f xf x 当求解问题的目标函数采用利润函数形式时，为了保证其非负性，可用如下变换式：（4）式中系数 可以式适合的输入值，或是当前一代或者前面几代中的g（x）的最小值，也可以是群体的方差。第三、四两种方法是对第一、二两种方法的改进，但有时存在界限值预先估计困难，不可能精确的问题，为此有下面两种改进的
11、方法：minmin,0()0,CCf xu(x)当u(x)+其他情况minC(5)若目标函数为最小问题:(6)若目标函数为最大问题：1()1()Fit f xcf x 0,()0cc f x1()1()Fit f xcf x 0,()0cc f x 四、遗传操作四、遗传操作 遗传操作是模拟生物基因遗传的操作。在遗传算法中，通过编码组成初始群体后，遗传操作的任务就是对群体的个体按照他们对环境适应的程度（适应度评估）施加一定的操作，从而实现优胜劣汰的进化过程，从优化搜索的角度而言，遗传操作可以使问题的解，一代又一代地优化，并逼近最优解。遗传算法的基本操作包括以下三个基本算子：选择，交叉,变异。（一
12、）选择（一）选择：选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。以下介绍目前几种常用的选择算子：（1）适应度比例方法(fitness proportional model)适应度比例方法是目前遗传算法中最基本也是最常用的选择方法，他也叫赌轮或蒙特卡罗（monte carlo）选择。该方法中各个个体的选择概率和其适应度成比例。其描述如下：设群体的大小为n，其中个体i的适应度值为 ,则i被选择的概率为 显然，概率 反映个体i的适应度在总和中所占的比例，个体的适应度越大，其被选择的概率就越高，反之亦
13、然，计算出群体中各个个体的选择概率后，就可以决定那些个体可以被选出。if1niijjpffip（2）最佳个体保存方法（elitise model）该方法的思想是把群体中适应度最高的个体不进行配对而直接复制到下一代中，此种选择操作又称复制（copy）。其定义如下：设到时刻t（第t代），群体A(t)中为最佳个体。又设A(t+1)为新一代群体，若A(t+1)中不存在，则把作为A(t+1)中的第n+1个个体（其中，n为群体大小）。此方法的优点是，进化过程中某一代的最优解可不被交叉和变异操作所破坏。这也隐含了一种危机，即局部最优个体的基因会急速增加而使进化有可能限于局部解，也就是说该方法全局搜索能力差，
14、它更适合单峰性质的搜索空间搜索，而不是多峰性质的空间搜索。所以此方法都与其他选择方法结合使用。*()a t*()a t*()a t（二）交叉（二）交叉：交换操作是遗传算法中最主要的遗传操作。在遗传算法中使用交叉算子来产生新的个体。对于占主流地位的二进制编码而言，各种交叉算子都包括两个基本容：1）从有选择操作形成的配对库（mating pool）中，对个体随机配对，并按预先设定的交叉概率来决定每对是否需要进行交叉操作；2）设定配对个体的交叉点（cross site），并对这些点前后的配对个体的部分结构（或基因）进行相互交换。基本交叉算子如下：单点交叉（one-point crossover），它
15、是指在个体编码串中只随机设置一个交叉点，然后在该点相互交换两个配对个体的部分染色体。双点交叉（twopoint crossover）是指在个体编码串中随机设置了二交叉点，然后再进行部分基因交换。双点交叉了的具体操作过程是：在相互配对的两个个体编码串中随机设置两个交叉点；交换两个个体在所设定的两个交叉点之间的部分染色体。（三）变异（三）变异：变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。同生物界一样，GA中变异发生的概率很低，通常取值在0.0010.01之间。遗传算法导入变异的目的有两个：一是使遗传算法具有局部的随机搜索能力。二是使遗传算法可维持群
16、体的多样性，以预防出现群体未成熟收敛现象。变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。就基因字符0,1的二进制码串而言，变异操作就是把某些基因座上的基因值取反，一般来说具有以下两个步骤：在群体中所有个体的码串范围内随机的确定基因座；以事先设定的变异概率来对这些基因座的基因值进行变异。1基本变异算子基本变异算子是指对群体中的个体码串随机挑选一个或者多个基因座，并对这些基因座的基因值做变动（以变异率做变动），0，1二进制码串中的基本变异操作如下：2逆转变异算子（inversion operator）逆转变异算子是变异算子的一种特殊形式。它的基本操作内容是，在个体码串中随机挑选
17、两个逆转点，然后将两个逆转点基因值以逆转概率逆向排序。0,1二值码串的逆转操作如下：mP11011110111010 变 异iP1000100110100101 01 逆 转2 遗传算法的模拟计算示例遗传算法的模拟计算示例 下面解释用遗传算法求函数 的最大值的一些重要步骤.这里只介绍第一代群体的生成过程与结果.(1)编码编码 由于在该例中 ,因此将变量 编码为5位长的二进制形式.如 可表示为 .(2)初始群体的生成初始群体的生成 随机产生初始群体的每个个体,群体的大小为4(如下表).2(),0,31f xx x0,31xx13x 01101个体号初始群体 的值适应度选择概率适应度期望值实际次数
18、配对 交叉位置新一代群体的值适应度101101131690.140.581240110012144211000245760.491.9721411001256253010008640.060.220441101127729410011193610.311.231341000016256适应度总和11701.004.0041754平均适应度2930.251.001439最大适应度5760.491.972729xx(3)适应度计算适应度计算 将每个个体 的函数值 作为该个体的适应度.如个体01101的适应度为 .(4)选择选择 计算每个个体的适应度所占的比例 ,并以此作为相应的选择概率.表的第5列
19、给出了每个个体的选择概率.由此概率可计算出每个个体选择的次数.也可采用轮盘赌方式来决定每个个体的选择份数.赌轮按每个个体适应度的比例分配,转动赌轮4次,就可决定各自的选择份数.如表中第7列.结果反映出,优秀个体2获得了最多的生存繁殖机会,最差个体3被淘汰.每次选择都对个体进行一次复制,由此得到的4份复制送到配对库,以备配对繁殖.x()f x2(13)13169fijff(5)交叉与变异交叉与变异 这里采用简单交叉操作:首先对配对库中的个体进行随机配对;其次,在配对个体中随机设定交叉处,配对个体彼此交换部分信息(如表).于是得到4个新个体,这4个新个体就形成了新一代群体.比较新旧群体,不难发现新
20、群体中个体适应度的平均值和最大值都有明显的提高.由此可见,新群体中的个体的确是朝着期望的方向进化了.一般而言,变异概率都取得很小.在这里取 由于群体中共有 位基因可以变异,这就意味着群体中通常没有一位基因可变异.20 0.0010.020.001,mp 二二 模拟退火算法模拟退火算法一、一、模拟退火算法简介 从物理学的有关知识知道，固体在恒定的温度下达到热平衡的过程可以用Monte Carlo方法进行模拟Monte Carlo方法的算法简单，但必须大量采样才能得到比较精确的结果因而计算量大。基于物理系统在自由状态下有向能量较低状态转移的趋势，而热运动又妨碍它准确落人最低状态的考虑,Metrop
21、olis于1953年提出对有重要贡献的状态进行采样，从而较快地达到比较理想的结果，其方法可以描述如下：先给定以粒子相对位置表征的初始状态 ，作为固体的当前状态，该状态的能量为 。然后用摄动装置使随机选取的某个粒子的位移产生一微小变化，得到一个新状态 ，新状态的能量是 。如果 ，则该新状态就可作为“重要”状态，如果 ，则考虑到热运动的影响，该新状态是否为“重要”状态需要根据固体处于该状态的概率来判断。设固体处于状态 与状态 的概率比值为r，r是一个小于1的数，用随机数产生器产生一个 区间的随机数 。若 ，则新状态作为重要状态，否则舍去。ijiEjEjiEEjiEEjir0,1 若新状态 是重要状
22、态,就 以取代 成为当前状态，否则仍以 为当前状态，再重复以上新状态的产生过程，在固体状态经过大量变换（常称之为迁移）后，系统趋于能量较低的平衡状态。上述接受新状态的准则称为Metropolis准则，相应的算法称为Metropolis算法。研究表明一般情况下 Metropolis算法计算量明显少于 Monte Carlo算法。通过对固体退火过程的研究可知，高温状态下的物质降温时其内能随之下降，如果降温过程充分缓慢，则在降温过程中物质体系始终处于平衡状态。从而降到某一低温时其内能可达最小，称这种降温为退火过程。模拟退火过程的寻优方法称为模拟退火（Simulated anneating，SA）算法
23、。jiji(1)模拟退火算法模拟退火算法（SA）设 为所有可能的组合状态，C：为非负目标函数，即 ，反映了取状态 为解的代价，则组合优化问题可以形式地描述为寻找 ，使 将状态 看成是某一物质体系的微观状态，而将 看成该物质体系在状态 下的能量，并用控制参数 表示为让温度 从一个足够高的值慢慢下降，对每一 用Metropolis采样法模拟该体系在此 下的热平衡状态，即对当前状态 做随机扰动以产生一个新的状态 ，计算增量：12,kSS SSSR 0iC S iS*SSiSSCSCSi min*iS iC SiSTTTTSS并以概率 接受 作为新的状态，当这样的随机扰动重复的次数足够多后，系统将达到
24、该温度下的平衡状态，且服从Boltzmann分布。这里b即为Boltzmann常数。上述Metropolis采样过程与退火过程可通过下列步骤来实现。expCbTS（2）退火过程实现算法（）退火过程实现算法（AP）1)任选一初始状态 作为初始解 ，并设初始温度为 ，令 ；2)令 ，以 和 调用Metropolis采样算法，然后返回到当前解 ；3)按一定的方式将 降温，即另令 4)检查退火过程是否结束，否则转到 2)；5)以当前解 作为最优解输出。0S 00SS0T0iiT TiSTiSST11,1;iiiT T TT i i iS（3）Metropolis采样算法（采样算法（M法）法）用AP算法
25、调用当前解 和 的过程如下：1)令 时的当前解为 ，而在温度 下进行以下步骤；2)按某一规定方式根据当前解 所处的状态 ，产生一个邻近子集 ，由 随机产生一个新的状态 以作为一个当前解的候选解，并计算 3)若 ，则接受 作为下一个当前解；若 ，则按概率 接受 作为下一个当前解；4)若 被接受，则令 。否则令 ；TS0k 0SST S kS N S k N S kS CC SC S k0C0CSexp/C bTS S1S kS1()S kS k 5)令 ，判断是否满足收敛准则，否则回到 2)；6)将当前解 返回调用它的AP算法。二、几种典型问题的模拟退火算法几种典型问题的模拟退火算法 模拟退火算
26、法是依据Metropolis准则接受新解，因此除接受优化解外，还在一个限定范围内接受劣解，这正是模拟退火算法与局部搜索算法的本质区别。由于开始时较大，可能接受一些较差的劣解。随着的减小，只能接受较好的可行解。最后在趋于0时，就只接受较优的可行解了，这就使模拟退火有可能从局部最优的“陷阱”中跳出来，从而求得整体最优解。研究表明，对大多数组合优化问题而言，模拟退火算法要优于局部搜索算法。下面仅对几个典型问题给出一个用迭代方法实现的算法描述，以揭示其建立数学模型和新解产生的基本求解方法。1k k S k1、货郎担问题（、货郎担问题（TSP）设有n个城市和距离矩阵D=，其中 表示城市 到城市 的距离，
27、则问题是要找遍访每个城市恰好一次的一条回路，且其路径长度为最短。求解的模拟退火算法描述如下：（1）解空间 解空间 可表为 的所有循环排列的集合，即 其中每一个循环排列表示遍访n个城市的一条回路，初始解可选为 。ijdijdijS1,2,n 的循环排列，为nkkkkkSnn21,|,1211,2,n （2）目标函数 此时目标函数即为访问所有城市的路径长度或代价函数的极小值，即 其中 。而一次迭代步骤由下列三步构成。(3)新解的产生 新解可通过分别或交替使用以下两种方法来产生。1)2变换法 任选序号 。交换 与 之间的访问顺序，此时新路径为（不妨设 ）：（*）nikkniidkkf111,min1
28、1nkk,u vvuuv11111 v vvuunukkkkkkk k 2)3变换法 任选序号 和 ，将 和 之间的路径插到 之后访问，对应的新路径为（设 ）：（*）在实际中经常将上述两种方法综合交替使用。（4）代价函数差 相应于新解（*）和（*）式的代价函数的差分别满足：（）,u vwwvuu v w 1111uvwwnuvkkkk kkkk11111111uvu vi iuuv viinnk kk kkkk kkkk ki ui ufdddddd 和 特别地，当问题对称即距离矩阵D=为对称矩阵时，（）式可简化为：（5）接受准则 根据以上的分析，即可写出相应的算法。111111uvw uv
29、wuuv vw wkkk kk kkkk kk kfdddddd ijd 1111uvu vuuv vkkk kkkk kfdddd 否则f/T),exp(0f,0p2、最大截问题（、最大截问题（MCP）给定带权图 ，权矩阵为 。要将 划分为子集 和 ，使 中所有顶点分属 和 的边的权之和最大。模拟退火算法描述为：（1）解空间 解空间可表示为集 的所有划分为两个子集 和 的分划 的集合，即 其中分划 （；），表示顶点 的初始解选为 ，。,GV E ijWwVV0V0V1V1VV0V1V的一个分划和划分为为将10|VVVS ij1,2,in0,1j ijvV 0i1,2,in（2）目标函数 直接
30、取分划所得到的截量 其中 ，需求其最大值。（3）新解 任选一顶点 ，将其从目前子集移到另一子集中去，即 。（4）目标函数差 根据目标函数与产生新解的方法可知，相应于新解的目标函数差为（5）接受准则 由于MCP为最大优化问题，所以接受准则为：,uvfw uv 1uu u V uvuvvuvufww 否则,/exp0,1TffP3、0/1背包问题（背包问题（ZKP）给定一个可装质量M的背包及n件物品，物品 的质量和价值分别为 和 ，。要选若干件物品装入背包，使其价值之和最大。模拟退火算法可描述如下：（1）解空间 0/1背包问题是一个有约束的优化问题，因此，限定解空间为所有可行解的集合，即（2）目标
31、函数 求下列函数的最大值：s.t.iiwic 1,0,|,1121innnxMxwxwxxxSnnnxcxcxcxxxf221121,1,0,11innxMxwxw（3）新解的产生 随机选取物品 ，若 不在背包中，则将其直接装入背包，或同时从背包中随机取出另一件物品 ；若 已在背包中，则将其取出，并同时随机装入另一物品 ，即 ，且（或）。（4）背包价值差与质量差价值差：质量差：iijij1iixx 1,jjxx i j 装入取出而，将物品取出装入而，将物品直接装入将物品jiccjiccicfijjii,装入取出而，将物品取出装入而，将物品直接装入，将物品jiwwjiwwiwmijjii（5）接
32、受准则 4、独立集问题（、独立集问题（ISP）设图 ，要找 的最大独立集 ，使 且对任意的 时，必有 。模拟退火算法的求解形式为：0,1,0exp/,mmMPmmMff T 其他,G VE12,nVv vvV1V1VV1,u v V,u vE（1）解空间 取 为 的幂集 ，即 的所有子集的集合 。注意到解空间中可能含有不可行解，即可能存在 的子集 但并非独立集，初始解为 。如此构造解空间可以使得产生新解的方法简便，同时使算法可以从一个局部最优的可行解变为不可行解，以增大逃脱局部最优“陷阱”的概率。（2）目标函数 为“惩罚”可能出现的不可行解，将目标函数选为 其中 ，是大于1的惩罚因子，用于“惩罚”在 中存在的边。VS2VV1V112|VSV VVV*VS1V11f VVE1,|,Euv uv VuvE 1V（3）新解的产生 通过任选顶点 ，当 时将其移出 。而当 时将其移入 ，即 其中 为集 的特征函数，定义为（4）目标函数差 设 表示图 的邻接矩阵，表示顶点 与 邻接，则伴随新解的目标函数差为：（5）接受准则 uV1u V1V1uV1V uxuxVV111 1Vx u1V1110,()1,vuVx uuV ijAaGjviv1ija 11,1,111VuaVuafVvuvVvuv否则,/exp0,1TffP
