《数学建模现代优化算法》由会员分享，可在线阅读，更多相关《数学建模现代优化算法（51页珍藏版）》请在金锄头文库上搜索。
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 遗传算法的基本步骤,遗传算法流程图如下：,一、编码遗传算法主要是通过遗传操作对群体中具有某种结构形式的个体施加结重组处理，从而不断地搜索出群体中个体间结构相似性，由此可见，遗传算法不能直接处理问题空间参数，必须把它们转换成遗传空间的由基因按一定结构组成的染色体或个体。这一转换操作就叫做编码。编码方法主要有：二进制编码，Gray编码，动态编码，实数编码，有序串编码，多参数编码，可变长编码等。,（一）一维染色体编码（二值编码）所谓一维染色体编码是指搜索空间的参数转换到遗传空
6、间过后，其相应的基因呈一维排列构成的染色体。具体地说，在遗传空间中，用以表示个体的字符集中的要素构成了字符串。如a,b,c,d或1,2,3,4。一维染色体编码中最常用的符号集是二进制符号0,1，基于此符号集的个体呈二值码串。二值编码的一般方法是：(1)根据所需要的精度确定参数的串长；(2)解码，由二值串转化成实数；例如：x=13,可被表示为01101。,（二）多映射编码（多参数）在优化问题求解中常常会遇见多参数优化问题。其基本思路是将每一个参数进行二值编码得到子串，每个子串对应各自的编码参数，然后将子串构成一个完整的染色体串。,二、 初始群体的生成遗传操作是对于多个体同时进行的。这众多的个体组
7、成了群体。在遗传算法处理流程中，继编码设计后的任务是初始群体的设定，并以此为起点一代代进化直到按某种进化停止准则终止进化过程，由此得到最后一代（或群体）。其中需要考虑到两个因素：初始群体的设定；进化过程中各代（群体）的规模如何维持？它和交叉概率变异概率等参数一样，对于遗传算法效能的发挥是有影响的。初始群体的设定可采取如下策略：(1) 根据问题固有的知识，设法确定最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。(2) 先随机生成一定数目的个体，然后从中挑出最好的个体加到初始群体当中去。这种过程不断迭代，直到初始群体中个数达到了预先确定的规模。,三、适应度函数 适应度函
8、数表明个体或解的优劣性。不同的问题，适应性函数的定义方式也不同。这一操作是借用了达尔文的自然选择原则，即个体适应度越高，其被选择的个体越多。遗传算法在进化搜索中基本上不用外部信息，仅用目标函数即适应度函数为依据。遗传函数的目标函数不受连续可微的约束且定义域可以为任意组合。对目标函数的唯一要求是，针对输入可计算出能加以比较的非负结果，这一特点使得遗传算法运用很广。在具体的应用中适应度函数的设计要结合求解问题本身的要求而定，要强调的是，适应度函数评估是选择操作的依据，适应度函数的设计直接影响到遗传算法的性能。,目标函数映射成适应度函数在许多问题求解中，其目标函数是求取费用函数（代价函数）g（x）的
9、最小值，而不是求效能函数或者利润函数的最大值。由于遗传算法中，适应度函数要比较排序并在此基础上计算选择概率，所以适应度函数的值要取正值。由此可见，在不少场合，将目标函数映射成最大值形式且函数值非负的适应度函数是很有必要的。在通常情况下，要把一个最小化函数转化为最大化问题，只需要简单的把费用函数乘以-1，即以下两种基本方法：,（1）如目标函数为最大化问题： （2）如目标函数为最小化问题：但这对遗传算法而言，这种方法还不足以保证在各种情况下的非负值。对此可以采用以下的方法进行转换： （3） 其中 可以采用目前g(x)出现过的最大值或者当前群体当中出现过的最大值，但最好与群体无关。,当求解问题的目标
10、函数采用利润函数形式时，为了保证其非负性，可用如下变换式：（4） 式中系数 可以式适合的输入值，或是当前一代或者前面几代中的g（x）的最小值，也可以是群体的方差。 第三、四两种方法是对第一、二两种方法的改进，但有时存在界限值预先估计困难，不可能精确的问题，为此有下面两种改进的方法：,(5) 若目标函数为最小问题:(6) 若目标函数为最大问题：,四、遗传操作遗传操作是模拟生物基因遗传的操作。在遗传算法中，通过编码组成初始群体后，遗传操作的任务就是对群体的个体按照他们对环境适应的程度（适应度评估）施加一定的操作，从而实现优胜劣汰的进化过程，从优化搜索的角度而言，遗传操作可以使问题的解，一代又一代地
11、优化，并逼近最优解。遗传算法的基本操作包括以下三个基本算子：选择，交叉,变异。,（一）选择：选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。以下介绍目前几种常用的选择算子： （1）适应度比例方法(fitness proportional model)适应度比例方法是目前遗传算法中最基本也是最常用的选择方法，他也叫赌轮或蒙特卡罗（monte carlo）选择。该方法中各个个体的选择概率和其适应度成比例。其描述如下：,设群体的大小为n，其中个体i的适应度值为 ,则i被选择的概率为显然，概率 反映个体
12、i的适应度在总和中所占的比例，个体的适应度越大，其被选择的概率就越高，反之亦然，计算出群体中各个个体的选择概率后，就可以决定那些个体可以被选出。,（2）最佳个体保存方法（elitise model）该方法的思想是把群体中适应度最高的个体不进行配对而直接复制到下一代中，此种选择操作又称复制（copy）。其定义如下：设到时刻t（第t代），群体A(t)中 为最佳个体。又设A(t+1)为新一代群体，若A(t+1)中不存在 ，则把 作为A(t+1)中的第n+1个个体（其中，n为群体大小）。此方法的优点是，进化过程中某一代的最优解可不被交叉和变异操作所破坏。这也隐含了一种危机，即局部最优个体的基因会急速增
13、加而使进化有可能限于局部解，也就是说该方法全局搜索能力差，它更适合单峰性质的搜索空间搜索，而不是多峰性质的空间搜索。所以此方法都与其他选择方法结合使用。,（二）交叉：交换操作是遗传算法中最主要的遗传操作。在遗传算法中使用交叉算子来产生新的个体。 对于占主流地位的二进制编码而言，各种交叉算子都包括两个基本容：1）从有选择操作形成的配对库（mating pool）中，对个体随机配对，并按预先设定的交叉概率来决定每对是否需要进行交叉操作；2）设定配对个体的交叉点（cross site），并对这些点前后的配对个体的部分结构（或基因）进行相互交换。,基本交叉算子如下：单点交叉（one-point cro
14、ssover），它是指在个体编码串中只随机设置一个交叉点，然后在该点相互交换两个配对个体的部分染色体。双点交叉（twopoint crossover）是指在个体编码串中随机设置了二交叉点，然后再进行部分基因交换。双点交叉了的具体操作过程是：在相互配对的两个个体编码串中随机设置两个交叉点；交换两个个体在所设定的两个交叉点之间的部分染色体。,（三）变异：变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。同生物界一样，GA中变异发生的概率很低，通常取值在0.0010.01之间。遗传算法导入变异的目的有两个：一是使遗传算法具有局部的随机搜索能力。二是使遗传算
15、法可维持群体的多样性，以预防出现群体未成熟收敛现象。变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。就基因字符0,1的二进制码串而言，变异操作就是把某些基因座上的基因值取反，一般来说具有以下两个步骤：在群体中所有个体的码串范围内随机的确定基因座；以事先设定的变异概率来对这些基因座的基因值进行变异。,1基本变异算子基本变异算子是指对群体中的个体码串随机挑选一个或者多个基因座，并对这些基因座的基因值做变动（以变异率 做变动），0，1二进制码串中的基本变异操作如下：2逆转变异算子（inversion operator）逆转变异算子是变异算子的一种特殊形式。它的基本操作内容是，在个体
16、码串中随机挑选两个逆转点，然后将两个逆转点基因值以逆转概率 逆向排序。0,1二值码串的逆转操作如下：,2 遗传算法的模拟计算示例,下面解释用遗传算法求函数 的最大值的一些重要步骤.这里只介绍第一代群体的生成过程与结果. (1)编码 由于在该例中 ,因此将变量 编码为5位长的二进制形式.如 可表示为 . (2)初始群体的生成随机产生初始群体的每个个体,群体的大小为4(如下表).,(3)适应度计算将每个个体 的函数值 作为该个体的适应度.如个体01101的适应度为 . (4)选择计算每个个体的适应度所占的比例 ,并以此作为相应的选择概率.表的第5列给出了每个个体的选择概率.由此概率可计算出每个个体选择的次数.也可采用轮盘赌方式来决定每个个体的选择份数.赌轮按每个个体适应度的比例分配,转动赌轮4次,就可决定各自的选择份数.如表中第7列.结果反映出,优秀个体2获得了最多的生存繁殖机会,最差个体3被淘汰.每次选择都对个体进行一次复制,由此得到的4份复制送到配对库,以备配对繁殖.,
