数学建模之智能计算

1、精选优质文档倾情为你奉上精选优质文档倾情为你奉上专心专注专业专心专注专业精选优质文档倾情为你奉上专心专注专业主要介绍几种典型的智能计算理论与方法. 1讲述基于热力学退火过程产生的模拟退火算法；2介绍一类从智能观点模拟生物智能的计算理论与方法遗传算法；3与4分别介绍模仿蚁群迁徙与觅食过程以及模拟鸟类群体行为而建立起来的蚁群算法和粒子群算法；5 元胞自动机的概念与算法，支持向量机等智能计算产生的背景优化问题的数学语言其中，为目标函数，为个约束条件（函数）。不难看出，优化问题是指在一定约束条件下，寻找一组参数使其最优性得到满足。根据目标与约束条件中变量是否满足线性、连续、目标函数的个数等，优化问题又

2、可以分为线性和非线性规划，或单目标规划与多目标规划等。线性规划中，当变量为整数或仅取0与1时，又得到整数规划或0-1整数规划。在一般情形下，非线性规划问题远远高于线性规划问题的求解难度。当考虑个目标函数时，上述优化问题可以描述为其中，为多目标变量。对于多目标优化问题而言，所包含的不同目标函数之间往往存在着目标不一致的地方，因此在求解过程中，很难满足同时达到最优的情形。根据变量的特性，优化问题又可以分为函数优化与组合优化两种，其中，优化对象约束在一定的区域时，呈现为函数优化问题，而优化对象为解空间中的离散状态时，则为组合优化问题。组合优化问题可以描述为：本节后面介绍的旅行商问题（TSP）、最大截

3、问题、0-1背包问题以及调度问题等都属于组合优化问题。最优化问题的求解可以分为经典优化算法与启发式优化算法。1947年。美国数学家Dantzig提出了求解线性规划问题的单纯性算法，随后，Kamaka提出多项式级的椭球算法与内点算法。对于非线性问题，人们从二次规划问题入手，建立了许多经典算法，如最速下降法、共轭梯度法、牛顿法与拟牛顿法等。经典算法的局限性：一般使用局部信息，如需要初始点以及导数等信息，从而使得经典算法容易陷入局部最优的陷阱，而导数等苛刻性质的需求则极大限制了算法的有效范围。智能计算的兴起：受到大自然运行规律的启发，上世纪50年代开始启发式算法得到广泛采用，尤其是启发式算法思想与人

4、工智能领域中的各种有关问题求解方法相结合，产生了许多智能型启发式搜索算法，其中，贪婪算法、局部搜索方法以及按概率选择成为最常见的启发式方法。一、模拟退火算法模拟退火算法属于一种典型的启发式算法Kirpatrick（1982）基本思想：观察到固体退火过程与离散系统中的组合优化问题的求解存在某种相似性，并将Metropolis准则引入到组和优化问题的求解中，建立了一种对Metropolis算法进行迭代的组合优化算法，由于该算法模拟固体退火原理，因此经常称之为“模拟退火算法”。1Metropolis准则Monte Carlo 方法 固体在指定温度下达到热平衡的过程可以通过Motel Carlo方法进

5、行仿真来实现，原理简单，算法易于编程实现问题：为了保证算法的精确性则必须进行大量采样，从而存在计算量巨大的问题。Metropolis准则，Metropolis 于1953年提出 思想: 借鉴Monte Carlo方法的思想,只对”重要贡献”的状态进行采样,目的: 减少运算量通过随机方式达到最优解，是一种随机接受准则，其方法可以描述如下（优异者一定接受，劣者按概率接受）：先给定以粒子相对位置表征的初始状态i，作为固体的当前状态，该状态的能量设为，然后利用摄动装置使随机选取的某个粒子的位移产生微小的变化，得到一个新的状态j,该状态的能量记为，如果，则该新状态就作为“重要”状态，如果，则考虑到热运动

6、的影响，该新状态是否“重要”需要设置一个概率数来进行判断，具体做法是设固体处于状态I与状态j的概率比值设为，r为一个小于1的数，用随机数产生器产生一个位于区间的随机数，若，则新状态仍然作为“重要”状态，否则舍去。若新状态是重要状态，就以j取代I成为当前状态，否则仍以I为当前状态，一直重复上述新状态的产生过程，当固体经过大量变换（或称为迁移）后，系统趋于能量较低的平衡状态。上述随机接受新状态的准则称之为Metropolis准则，相应的算法称之为Metropolis算法。由于采用随机方法，一般情况下Metropolis算法的运算量明显少于Mote Carlo方法的运算量。2 模拟退火算法(Simu

7、lated AnnealingSA) 1982年，Kirkpartrick提出将固体加温至充分高（能量达到最大），再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。统计力学的研究表明，当温度为T时，分子停留在状态满足Boltzmann概率分布，即其中为状态r的能量，为分子能量的一个随机变量，为概率分布的标准化因子：将优化问题类比成退火过程，当满足接受条件时，以概率为1的形式接受新解，否则，根据Boltzmann概率分布的形式接受劣解. 因此，不考虑标准化因子，粒子在温度T时趋于平衡的概率为，其中

8、E为温度T时的内能，E为其改变量，为Boltzmann常数.将固体退火的思想引入到组合优化问题的求解中，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解计算目标函数差接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子t、每个t值时的迭代次数L和停止条件S。 上述模拟退火过程可以通过下列算法来实现.(1) 初始化：初始温度T(充分大)，

9、初始解状态S(是算法迭代的起点)， 每个T值的迭代次数L(2) 对k=1，L做第(3)至第（6）步：(3) 产生新解S(4) 计算增量，其中C(S)为评价函数(5) 若则以概率为1的形式接受S作为新的当前解，否则计算概率，并按照接照Metropolis准则将S作为新的当前解.(6) 如果满足终止条件则输出当前解作为最优解，结束程序.终止条件通常取为连续若干个新解都没有被接受时终止算法.(7) T逐渐减少，且T-0，然后转第2步.算法中新解的产生和接受可分为如下四个步骤：第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换

10、即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。第二步是计算与新解所对应的目标函数差。目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。第三步 判断新解是否被接受判断的依据是一个接受准则,最常用的接受准则是Metropo1is准则: 若t0则接受S作为新的当前解S，否则以概率exp(-t/T)接受S作为新的当前解S。第四步 当新解被确定接受时，用新解代替当前解这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目

11、标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。模拟退火算法评价:模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。模拟退火算法的应用很广泛，可以求解NP完全问题。模拟退火算法的数学理论支持从数学的角度来看，可以通过马尔科夫（Markov）过程来描述模拟退火算法：在给定领域结构后，模拟退火过程是一个从一个状态到另一个状态不断的随机游动，具体地说，当温度为确定值后，两个状态

12、的转移概率（transition probability）定义为其中，N表示状态集合中状态的个数， 称为从到的产生概率，表示在状态时，状态被选取的概率。当为的邻域时，如果采用等概率选取方法，则被选中的概率为其中分别表示的邻域以及邻域所含元素的个数，为接受概率，表示从状态产生状态后，接受状态的概率，在模拟退火算法中，接受概率值为 和分别称之为产生矩阵、接受矩阵和一步转移概率矩阵。模拟退火算法的难点: 参数难以控制，其主要问题有以下三点： (1) 温度T的初始值设置问题. 温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计

13、算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响.实际应用过程中，初始温度一般需要依据实验结果进行若干次调整.(2) 退火速度问题. 模拟退火算法的全局搜索性能也与退火速度密切相关.一般来说，同一温度下的“充分”搜索(退火)是相当必要的，但这需要计算时间.实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件. (3) 温度管理问题. 温度管理问题也是模拟退火算法难以处理的问题之一,降温方式对算法影响最大，如果降温过快，可能丢失最优值点；如果降温速度太慢，算法的收敛速度又会受到较大的影响，收敛速度大大降低.实际应用中，由于必须考虑计算复杂度的切实可行性等问题，常采用如下所示的降

14、温方式： .另外，为了便于操作，也常采用下面两种取法：（1）经典退火方式 降温公式为，特点是温度下降较慢，因此，算法的收敛速度也很慢；（2） 快速退火方式 降温公式为 ；这种退火方式的特点是在高温区退火速度较快、在低温区退火速度逐渐变慢，降温速度减弱，这符合在热力学分子运动理论中，在高温时某粒子所具有较低能量的概率比在低温时小得多的规律.因此，寻优的重点应该放在低温区，式中用以改善退火曲线的形态.上述算法可以通过程序的方式来描述，具体过程为：SA_AlgorithmProcedure SA-Algorithm();/* 为任一初始状态，为初始控制参数*/begin (1) /*简记为当前代价值

15、*/（2）repeat(2.1) repeat(2.1.1) (2.1.2) if then else if Accept then end if endig(2.1.3) until 内循环结束；(2.2) (3) Until end.在上述算法中，（1）为初始化，（2.1.1）的Generate(S)表示从S 的邻域中随机产生下一个状态，若，则接受j为新的当前状态；否则仅以一定的概率接受j为新的状态，这也是Accept(j,s0函数的功能。Accept函数的常见形式为function Accept(j,s)begin ;if exp()Random(0,1)/*b为Boltzmann常数*

16、/then Accepttrieelse Acceptfalseendifend.(2.1.3) 中的内循环结束条件是指在每一温度下迭代多次以达到平衡状态，而（2.2）中的Update() 函数则表示温度每次下降的速度。由此可知，SA算法有三个重要函数：生成函数generate，接受函数Accept和温度控制函数Update.在算法实现过程中，伪温度函数和内循环次数的选择直接决定了模拟退火算法的收敛速度。在组合优化算法问题的模拟退火算法求解过程中，一般取其中n为问题的规模，为关于的多项式函数；，如；迭代终止参数取值范围一般为，当时迭代结束。3 模拟退火算法的典型应用 模拟退火算法引入Metro

17、polis准则接受新解，因此，除了接收到较理想的解外，同时也有可能在一定范围内接受劣解。这是具有随机特色的模拟退火算法与局部搜索等确定性算法的区别。由于开始时温度取值较大，存在接受劣解的可能；随着T值不断变小，可行解越来越接近最优解，当T 值趋近于0时，逐步接近最优解，从而有可能避免局部搜索算法陷入局部最优的“陷阱”，得到整体最优解。实际例子表明，对于大多数组合优化问题而言，模拟退火算法要优于局部搜索算法。 利用模拟退火算法求解应用问题的数学模型由：解空间、目标函数、新解的产生、代价函数差以及接受准则等五个方面组成。 问题 1旅行商问题(Travelling Salesman Problem，

18、简记为TSP) TSP问题描述如下：设有n个城市，用数码1,n代表.城市和城市之间的距离为TSP问题是要找遍访每个域市恰好一次的一条回路，且其路径总长度为最短. 求解TSP的模拟退火算法模型可描述如下：（1）解空间 解空间S是遍访每个城市恰好一次的所有回路，是1，n的所有循环排列的集合，即为的排列.表示在第I次访问第j个城市，并记以及初始解可选为(1，n) .（2）目标函数目标函数即为访问所有城市的路径总长度或称为代价函数的最小值，即求 (1)其中. (1)的求解通过迭代来完成,每一次迭代,需要完成下面三个任务:(3) 产生新解新解一般按照某种规则对序号实现变换得到,下面介绍分别或交替采用的三

19、种变换过程. = 1 * GB3 2变换法随机生成两个序号,交换上述序号之间的访问顺序,此时新路径变为 （2） = 2 * GB3 3变换法随机生成三个序号,将之间的序号插入到序号之后再来访问,对应的新路径为 （3） = 3 * GB3 逆转中间或者逆转两端变换法随机产生两个序号，若，则对应新的路径为 （4）如果是,则对应的新路径为 （5）也可以采用其他的变换方法，有些变换有独特的优越性，有时也将它们交替使用，得到一种更好方法. (4) 代价函数差 设将路径变为新路径，则代价函数差为 （6）例如，相应于（2）的代价函数差为 （7）特别地，当问题具有对称性时，对应矩阵为对称矩阵，此时，（7）可以

20、简化为（5）接受准则 （8）为简单计，讨论二维平面上的TSP问题，其距离矩阵满足对称性以及三角不等式： 当退火过程完成以后，由变量形参p输出的数值即为近似最短路经，而f 为对应的最短路长度。 下面用一个实例说明模拟退火算法求解TSP问题的有效性.例1 随机产生一个包含30座城市的TSP问题其示意图如下：图1 TSP问题示意图求解本问题的模拟退火算法模型可描述如下：解空间：解空间是遍访每个点恰好一次的所有路径，解可以表示为 ，是的一个排列，其中为起始城市，表明从出发，依次经过点，再返回.初始解可选为；目标函数：访问所有城市的路径总长度；我们要求的最优路径为目标函数为最小值时对应的路径. 新路径的

21、产生：随机产生1和之间的两相异数和，不妨假设，则将原路径:变为新路径：.上述变换方法就是将和对应的两个垃圾站点在路径序列中交换位置，称为2-opt映射. 根据上述描述，模拟退火算法求解该TSP问题的流程框图如下：图2 TSP模拟退火算法流程图通过采用Matlab编程求解，迭代效果见图3.图3 算法迭代过程由图3 可以看出，仅仅经过10次左右迭代便得到了问题的解，该解即使不是全局最优解，也应该是最接近最优解的近似解.问题2最大截问题(Max Cut Problem ，简计为MCP) 给定带权图，其中为顶点集，E 为边界集，权矩阵为。最大截问题要求将V 划分为子集，使E 中所有顶点分属和的边的权之

22、和最大。 问题3 0-1背包问题（Zero One Knapsack Problem），简记为ZOKP） 0-1背包问题是一个有约束的优化问题，问题定义如下：有n个物品，其重量分别为W=w1, w1, w3, . wn，其价值分别为V=c1, c2, c3, . cn。现在要将这N个物品放入允许的最大重量为w的包中，问怎样选择物品能使包中的物品总价值最大。 0-1背包问题采用模拟退火算法求解描述如下：解空间0-1背包问题作为有约束的优化问题，其解空间可以限定为所有可行解的集合，即 （9）其中表示物品被装入背包，初始解选为.目标函数求下列函数的最大值 （10）（3）新解的产生随机选取物品，若不在

23、背包中，则将其直接装入背包，或同时从背包中随机取出另一物品；若已在背包中，则将其取出，并同时随机装入另一物品，即 且（或） （11）背包的价值差于重量差根据产生新解的三种可能，相应的背包价值差为 （12）而对应背包的重量差为 （13）反映了当前重量的增量变化情况.接受准则 （14）问题4 调度问题（Scheduling Problem，简记为SCP） 设完成个相互独立的任务所需的时间分别为，这些任务可以由m台机器，且每台机器每一个时间段内只能承接一项任务。假设m台机器同时开工，要求寻找一个分配方案，使完成任务的时间最短。 二、遗传算法遗传算法（Genertic Algorithm,GA）是一类

24、模拟达尔文生物进化论的自然选择和遗传学机理的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。它最初由美国Michigan大学J.Holland教授于1975年提出来，颇有影响的专著Adaptation in Natural and Artificial Systems出版后，GA这个名称逐渐为人所知，J.Holland教授所提出的GA通常为标准遗传算法（SGA）. 遗传算法的特点一个例子：求解非线性方程根的牛顿迭代法描述为给定初始解（猜测）；对于，实施直到 中止算法特点：（1）初始解只有一个，有可能得不到需要的根；（2）要求函数具有导函数且导函数值不能为0。遗传算法与上述求解过程相同的是

25、迭代部分，但不同之处在于：遗传算法的工作过程是模仿生物的进化过程。因此，首先需要确定一种编码方法，使得你的问题中的任何一个潜在的可行解都能表示为一个“数字”染色体。然后创建一个由随机的染色体组成的初始群体（不是一个单一的初始值，每个染色体代表一种不同的选择）；在一段时间内，通过适应度函数给每个个体一个数值评价，淘汰适应度低的个体（该过程称之为选择），经过复制、交叉、变异等遗传操作的个体集合形成一个新的种群，对这个种群进行下一轮进化，从而达到最优化的目的，这便是遗传算法的基本原理。因此，遗传算法的具有如下典型特征：（1）与自然界相似，遗传算法对求解问题的本身一无所知， 对搜索空间没有任何要求（如

26、函数可导、光滑性、连通性等），只以决策编码变量作为运算对象并对算法所产生的染色体进行评价，可用于求解无数值概念或很难有数值概念的优化问题，应用范围广泛； （2） 搜索过程不直接作用到变量上，直接对参数集进行编码操作，操作对象可以是集合、序列、矩阵、树、图、链和表等；（3）搜索过程是一组解迭代到另一组解，采用同时处理群体中多个个体的方法，因此，算法具有并行特性；（4）遗传算法利用概率转移规则，可以在一个具有不确定性的空间寻优，与一般的随机性优化方法相比，它不是从一点出发按照一条固定路线寻优，而是在整个可行解空间同时搜索， 可以有效避免陷入局部极值点，具有全局最有特性；（5）遗传算法有很强的容错能

27、力。由于遗传算法初始解是一个种群，通过选择、交叉、变异等操作能够迅速排除与最优解相差较大的劣解。三、遗传算法的应用由于遗传算法的整体搜索策略和优化搜索方法在计算是不依赖于梯度信息或其它辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于许多科学，下面我们将介绍遗传算法的一些主要应用领域：1、 函数优化。函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例，许多人构造出了各种各样复杂形式的测试函数：连续函数和离散函数、凸函数和凹函数、低维函数和高维函数、单

28、峰函数和多峰函数等。对于一些非线性、多模型、多目标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方便的得到较好的结果。2、 组合优化随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算上用枚举法很难求出最优解。对这类复杂的问题，人们已经意识到应把主要精力放在寻求满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的NP问题非常有效。例如遗传算法已经在求解旅行商问题、 背包问题、装箱问题、图形划分问题等方面得到成功的应用。此外，GA也在生产调度问题、自动控制、机器人学、图象处理、人工生命、遗传编码和机器学习等方面获得了广泛的运用。遗传算法

29、基本原理遗传算法工作过程：模仿生物的进化过程首先需要确定一种编码方法，使得所讨论的问题中的任何一个潜在的可行解都能表示为一个“数字”染色体. 然后创建一个由随机的染色体组成的初始群体（不是一个单一的初始值，每个染色体代表一种不同的选择）；在一段时间内，通过适应度函数给每个个体一个数值评价，淘汰适应度低的个体（该过程称之为选择），经过复制、交叉、变异等遗传操作的个体集合形成一个新的种群，对这个种群进行下一轮进化，从而达到最优化的目的。实施步骤：（1）通过随机方式产生问题的初始种群；（2）将问题编码为染色体，即将优化变量对应到生物中的个体，一般用字符串表示为：，该字符串称之为编码.（从生物学的角度

30、来看，编码相当于遗传物质的选择，每一个字符串与一个染色体对应.为了便于在计算机进行表示和处理，在遗传算法设计中，最为常见的方式为0/1二进制编码体制）. 例如：以8座城市的TSP问题为例，此时，TSP问题中的两个路径与编码分别为周游路线 二进制编码3 4 0 7 2 5 1 6 011 100 000 111 010 101 001 1102 5 0 3 6 1 4 7 010 101 000 011 110 001 100 111（3）为了衡量每一个个体的优劣，我们通过定义适应度对其进行评价，对每一个个体计算适应度，实现个体的“优胜劣汰”.与生物一代一代进化类似，遗传算法的运算过程本质上为利

31、用迭代产生种群的过程.例如，设第代种群为，则通过遗传和进化操作后，得到第代种群，该种群由多个更优异的个体组成.该个体不断重复，按照选择、交叉与变异以及“优胜劣汰”规则产生新的个体.遗传算法流程图 开始 1 初始种群（随机产生，记为，并对其编码） 2 个体评价与种群进化 种群 个体适应度检测与评价 选择 交叉 变异 新种群 3 停止检验（是否满足停止条件） 若不满足停止条件，转移到第2步 若满足停止条件，解码染色体，输出问题的解 新概念：初始种群、编码、个体适应度、选择、交叉、变异、解码、染色体的定义。 定义1（编码） 把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的方法称之为编码

32、.在基本的遗传算法中，采用固定的二进制符号串来表示群体中元素的个数，其等位基因由二值符号集0，1组成.定义2（遗传编码）将变量转换成有限长字符串，称为的一个遗传编码（或染色体编码），记为，L称为编码长度，而称为的解码，记为.定义3（适应值函数与适应度）考虑优化问题 （2.2.1）若函数与函数有相同的全局极大值，且满足则称是问题（2.2.1）的适应值函数.显然存在无穷多种适应度函数，例如，设为满足的常数，则是一种适应度函数对于每一个适应值函数，定义，称之为个体的适应度.在遗传算法中，适应度是描述个体性能的主要指标. 根据适应度的大小，对个体实行优胜劣汰，遗传算法只依靠适应度指导搜索过程，因此它的

33、好坏直接决定了遗传算法的性能. 适应度作为驱动遗传算法的动力，在遗传过程中具有重要意义. 遗传算法中目标函数的使用通过适应度来体现，因此，需要将目标函数以某种形式进行转换. 根据定义3将目标函数转换成适应度函数必须遵循下面几条原则：（1）非负性：适应度非负；（2）一致性：优化过程中目标函数的变化方向与群体进化过程中适应度函数变化方向一致；（3）计算量小；（4）通用性强.适应度进行转换.假设目标函数为最大值问题，否则，对于最小值问题可以进行如下转换：其中，为转换后的适应度，为充分大的常数，保证，为最小值问题的适应度.为了保证适应度不出现负值，对于有可能产生负值的最大值问题，可采用下面的形式进行转

34、换其中，为转换后的适应度，为充分小的常数，只要满足即可，为最大值问题的适应度.现在再来讨论适应度函数的几种尺度变换方法.线性变换假设原适应度函数为，变换后的适应度函数为，则线性变换可以表示为其系数的确定 需要满足下列条件：（1）原适应度平均值要等于定标后的适应度平均值，以保证适应度为平均值的个体在下一代的期望复制数为1，即（2） 变换后适应度最大值应等于元适应度平均值的指定倍数，以控制适应度最大的个体在下一代的复制数.幂函数变换上式中幂指数与所求的优化问题相关，需要具体问题具体分析.指数变换上述变换的思想来自于模拟退火过程，其中系数决定了复制的强制性，其值越小，复制的强制性越趋向于那些具有最大

35、适应度的个体.定义4（选择算子）根据每一个个体的适应度，按照一定的规则或方法，从代种群中选择出优秀的个体.选择算子是一种按照“优胜劣汰”的自然法则.模拟自然选择的操作.定义5（交叉算子）将从群体中选出的每一对母体，按照交叉概率交换它们之间的部分基因.交叉算子是一种模仿有性繁殖的基因重组操作.定义6（变异算子）对种群的每一个个体，按照变异概率改变某一个或某一些基因上的基因值为其它的等位基因.变异算子是一种模拟基因突变的遗传操作.遗传算法流程图 开始 1 初始种群（随机产生，记为，并对其编码） 2 个体评价与种群进化 种群 个体适应度检测与评价 选择 交叉 变异 新种群 3 停止检验（是否满足停止

36、条件） 若不满足停止条件，转移到第2步 若满足停止条件，解码染色体，输出问题的解 在上述算法中，第一步初始化种群要求确定出种群规模N、交叉概率、变异概率以及终止进化的准则等，而初始种群一般采用服从均匀分布的随机数得到. 在种群进化过程中，选择一个偶数以及对母体，对所选择的对母体，按照概率进行交叉，形成M个中间体，然后对M个中间个体按照概率进行变异，形成M个候选体.为了在候选体中选择出下一代新中群，从M个候选体中依照适应度选择出N个个体组成新一代种群.直到选择出来的新种群符合终止准则时停止，一般情况下，完成一个遗传算法大约需要迭代50到500次. 遗传算法的实施一、编码编码是可行解到遗传空间解的

37、一中表示方法. 编码需要建立可行解空间和遗传空间的对应，为了不产生歧义，这种对应最好是一一的，同时为了计算简便，编码应尽量简明.编码是遗传算法设计中首先需要解决的问题，在遗传算法中起到重要的作用，这种作用主要表现在：（1）它不仅决定个体染色体的排列形式（从而决定选择、交叉及变异等操作的运行方式），而且决定了个体从搜索空间的基因型到解空间的表现时的解码方法（从而获得基于遗传算法的解的理解）；（2）它决定了遗传算法进化运算的效率（编码方法的好坏直接决定了交叉与变异等遗传操作的计算效率和执行难度，一个差的编码方法可能导致无效解的出现）；（3）它决定了问题求解的精度（一个好的编码方法首先应该具有保持解

38、空间拓扑连续性的特点）下面对编码方法进行具体讨论.一个好的编码方法首先需要具备下列性质：完备性： 问题中所有的候选解都能够作为遗传算法空间中的染色体来体现.健全性： 遗传算法空间中的染色体能够对应所有问题中的候选解。常见编码方案.二进制编码方法二进制编码（binary encoding）是以二进制字符0与1为等位基因的定长字符串编码，是当今数字计算机普遍采用的数字表示方法. 二进制编码字符串的长度与所求解问题的精度要求有关,设，给定编码精度，取满足的最小整数，指定对应关系则任何长的0,1字符串唯一对应一个实数，定义为现在令，对于任意长度为L 的字符串A，设指定其解码为上式给出了所对应的唯一实数

39、.二进制编码的特点通用、简明、易于各种进化操作等优点，与十进制以及英文字母相比，在执行交叉和变异操作时具有更多的变化。缺点：二进制编码不等同的实数可以对应同一定长二进制表示，并且有可能破坏可行解空间的拓扑连续性：两个在解空间上非常接近的点在编码后可以相隔非常远，例如，在0到8的整数集中，7与8是最邻近的，而其4位二进制编码分别为0111与1111，它们在汉明（Hamming）距离（不同数值的位数个数）下是最大的.因此，有必要研究保持拓扑连续性质的新的编码方法.(2)格雷码（Gray Coding）编码方法格雷码是为了弥补二进制码不能保持可行解空间的连续性而提出的，因此，格雷码在连续的两个相邻整

40、数之间所对应的编码值之间仅仅只有一个码位不相同，其余码位完全相同.例如，0到15之间的二进制码和相应的格雷码可以表示为表2的形式.表2 四位格雷码十进制整数标准二进制码格雷码十进制整数标准二进制码格雷码012345670000000100100011010001010011011100000001001100100110011101010100891011121314151000100110101011110011011110111111001101111111101010101110011000 利用二进制编码和灰度编码还可以得到性质更好的编码方法。如实数编码（又称浮点数编码），即对任何，或

41、直接取染色体编码.或取一个同胚映射，其中表示的第个分量.除了上述实数编码外，人们还提出了可分解/可拼接编码、可拼接/可分解编码以及符号编码等.二、选择算子选择操作从染色体中选择某些染色体用于创建下一代个体的基因库（新的候选解），有时，某些选出的染色体不作任何修改直接进入下一代作为种子（精英），但是更为常见的是，某些被挑选出来的染色体作为父代.通过交叉、变异等过程产生子代. 因此，如何挑选父代非常重要，它对遗传算法收敛性有很大的影响. 直观上看，适应度较大（优良）的个体应该有较大生存机会，而适应度较小（劣质）的个体生存机会也相对变小，标准遗传算法采用的轮盘赌选择技术采用的便是上述思想.选择算子要

42、求被选择的个体应该是被选择的种群中的一部分，只要所有个体的适应度不完全相同（非其次种群），除选择后个体与原种群的数目存在差异外，选择算子的作用应该有可能增加种群中最优个体（即具有最高适应度的个体）的数目.选择算子的取法.(i) 比例型选择法首先讨论一种基于比例方法的选择算子轮盘赌选择法.设表示种群中第个染色体的适应度值，为种群总的适应度之和，则第个染色体产生后代的能力定义为其适应度在总的适应度中所占的比重，在具体的实施过程中，个体适应度按比例转化为选中概率，为了选择交配个体，需要进行多轮（设轮）选择，此时将轮盘分为个扇区，每一轮产生一个0，1上服从均匀分布的随机数，将该随机数作为选择指针，指针

43、停止在哪个扇区，该扇区代表的个体即被选中.轮盘赌方法过程简单、易于操作，但是，该方法存在明显的缺点.由于轮盘赌方法采用产生随机数来完成，而遗传算法中种群比较小时，分配给个体的数目可能远低于应有的值，更坏的情形是，轮盘赌方法可能将所有的最优染色体丢掉，为了克服简单轮盘赌方法的缺陷，人们提出了多种轮盘赌方法的改进方案.下面介绍一般的比例选择方法.例2（比例选择）给定种群，以概率(2)独立、重复地从中选择M个个体组成： (2)其中表示在中重复的次数，是定义在实数域上满足的严格单调递增函数.在上式中，一个常见的比例选择算子是整体退火选择算子，此时，以及其中称之为退火温度.另一个常见的比例选择算子是乘幂

44、适应值选择算子，此时尺度以及 （3）例3（杰出者选择） 杰出者选择是以概率为1的形式强制性选择种群中适应度最高的个体，其概率分布为 （4）在遗传算法中，上述选择的实施过程为：首先根据父代种群执行繁殖操作，生成中间种群，然后从中间种群中选择（例如以比例选择）个个体，从中选择一个最优个体共同组成新一代种群，上述过程可以通过下面的数学表达式进行描述： （5）其中是比例算子，是杰出者选择算子，是繁殖算子，是复制算子，是扩展算子，定义为.例4（期望生存数选择）该选择基于对当前群体中每个个体在下一代中的期望生存数作个体选择，具体方法是：（a）计算种群中各个体在下一代种群中的期望生存数：令在下一代的期望生存

45、数取为的整数部分.（b）根据上述计算值选择出个个体（即如果，则选择次）.（c）用其它方法选择出剩下的个个体.(ii) 排序法排序选择的思想是对个体适应度作降序排列并分别指定其序号，则被选中某个个个体的概率随的增大而不断递减，递减的速度视问题的需要而定，如果强烈要求优先选择适应度高的个体，则概率函数可以设置为关于变量的急剧递减函数.目前比较常见的概率函数主要有关于的线性递减函数以及关于的指数函数等.在排序型选择算子中，还有一类锦标赛选择算子也经常被采用，其思想是：首先在种群中随机选出个个体，然后将适应度最高的个体加入新种群，上述过程不断重复，直至加入的个体数目达到新种群要求的数目.任何被选中的个

46、体不从原种群中移走，因此，有可能重复多次选中同一个个体.锦标赛选择法易于实现，它不需要任何预处理技术.三、繁殖算子繁殖算子是遗传算法中所选出的母体生成子代的操作，繁殖算子模拟生物种群的演化过程，在遗传算法中，选择算子负责挑选出优良的母体，而繁殖算子则根据挑选出来的母体培育出更加优良的下一代，从而通过不断的迭代实施选择算子与繁殖算子操作，最终收敛到最优值.为了从理论上描述繁殖算子，我们先讨论满意集的概念.定义10（满意集）如果对于任意子集以及，适应度函数都有，则子集称之为满意集.根据满意度的概念，满意集中的每一个个体的适应度均高于它之外的任何个体的适应度，因此，问题的全局最优解集一定是一个满意集

47、.另外，根据满意集的概念不难推出，全局最优解集是所有满意解集的交集，是最小的满意解集合.按照繁殖算子的定义，不难看出，当繁殖算子作用到种群上时，产生新的种群，而新种群中可能存在比旧种群中更满意的个体，这是保证生物不断进化的最低要求.四、变异算子模仿生物遗传和进化过程中的变异环节，在遗传算法中也引入变异算子来产生新的个体.变异运算从直观上来看就是将个体染色体编码串中的某些基因座上的基因值用该基因座的其它等位基因来替换，从而形成一个新的个体. 在遗传算法中使用变异算子有两个主要目的：改善遗传算法的局部搜索能力；维持群体的多样性，防止出现早熟现象.性质：（a）如果当前种群含有满意个体，则变异后的种群

48、也应该含满意个体；（b）如果当前种群不含满意个体，则变异后的种群有可能含满意个体.下面讨论变异算子的几种典型形式.定义13（点变异） 点变异是指以某一概率独立地改变个体中等位基因值的进化操作，以二进制编码为例. 设，第位的变异概率为，定义 （8）即改变的概率为，不改变的概率为.特别地，下面的讨论中假设为一个常数值，记为，于是对个体有上式中为汉明（Hamming）距离，表示个体与含不同基因位的个数.对应于点变异，下面引入均匀变异的概念.定义14（均匀变异） 均匀变异要求对不同的等位基因，产生均匀分布的随机数，以某一较小概率来替代个体编码串各个基因座上的原有基因值.上面描述的两种变异方式强调在搜索

49、空间自由移动，从而增加种群的多样性.下面讨论两种加强局部搜索能力的变异方式.例15（正态变异） 正态变异用于实数编码，是用服从正态分布的随机数代替原有基因的变换，即.当较小时，正态变异用于局部搜索比较有效.定义16（非一致变异）非一致变异是另一种强调局部化操作的变异方式.设是遗传算法在代产生的个体，则非一致变异作用到所产生的变异个体定义为 （9）其中，是取0，1的随机数，为服从均匀分布的随机数，随着变大，单调递减趋近于0.例如，可以定义为 （10）其中为0，1内服从均匀分布的随机数，是最大进化代数（迭代次数），是可调参数，它决定了随机扰动对进化代数的依赖程度.在初始界阶段，代数较小，非一致变异

50、实施均匀随机搜索，而当代数变大，尤其是当接近时，非一致变异执行局部搜索. 五、交叉算子交叉操作是指对于两个相互配对的染色体按照某种方式相互交换其中的部分基因，从而形成新的个体.交叉运算是遗传算法区别于其它进化算法的一个重要特征，它在遗传算法中起着非常重要的作用，是产生新个体的主要方法.首先我们讨论一种最简单的交叉算子单点交叉.单点交叉的基本操作是：等概率地指定一个基因值作为交叉点，再把母体对中两个个体从交叉点分为前、后两部分，以某个确定概率交换两个个体的后半部分，得到两个新个体，取第一个个体为杂交结果.例如，取，设，交叉点位置为，则对母体实施交叉操作后变为.相应于单点交叉，可以类似定义多点交叉

51、的概念.多点交叉的基本操作是：首先在母体对的基因串中随机设置多个交叉点，然后按照一定的概率在交叉点所分割的基因段中进行交换.例如，两点杂交是将母体的基因串分成三部分，交换中间部分，即为交叉结果.单点交叉与多点杂交的重要特点是：若邻接基因座之间的关系能够提供较好的个体形状和较高的个体适应度的话，则这种单点交叉操作破坏这种个体形状和降低个体适应度的可能性最小.除了上面描述的单点与多点交叉操作外，常见的还有均匀交叉、算术交叉、部分匹配交叉、顺序交叉、循环交叉以及缩小代理交叉等.六、进化技巧遗传算法中进化技巧对算法有重要影响，这些技巧体现在算法的每一步中，主要包括：编码、初始种群、适应值函数、复制、交

52、叉、变异以及终止进化代数的执行技巧以及上述每一步运算过程中参数的设计等.实例：下面以含8座城市的TSP问题为例，讨论相关的遗传算法步骤：此时，TSP问题中的两个路径与编码分别为周游路线 二进制编码3 4 0 7 2 5 1 6 011 100 000 111 010 101 001 1102 5 0 3 6 1 4 7 010 101 000 011 110 001 100 111如果在第四个城市之后设立一个杂交点（用一个x表示）父辈1 011 100 000 111x 010 101 001 110父辈2 010 101 000 011x 110 001 100 111则杂交后有子辈1 01

53、1 100 000 111 110 101 001 110子辈2 010 101 000 011 010 001 100 111解码后分别为3，4，0，7，6，1，4，72，5，0，3，2，5，1，6两个后代均包含重复的后代，这不是有效的路径需要继续杂交.变异 变异时先从群体中随机选择一个个体，对于选中的个体以一定的概率随机改变串结构数据中某个串的值.遵循生物学的规律，GA 中发生变异的概率很低，通常在0.0010.01之间，例如，TSP问题中，将3 4 0 7 2 5 1 6 011 100 000 111 010 101 001 110变异为6 1 5 2 7 0 4 3 110 001

54、101 010 111 000 100 011即倒序运算而TSP问题完整示例表示如下：考虑8个城市0，1，2，3，4，5，6，7，一个旅行路线51032647可以简单的表示成（），遗传算法步骤为随机初始化种群 ，计算种群中个体的适应度while（不满足中止条件） for (k=0;kN;k+=2)/设N为偶数随机从产生两个父体交叉后产生两个后代将这两个后代加入中间群体去对中间群体中的每个个体进行变异操作从和进行选择操作得到N个体并加入到新群体中去计算中每个个体的适应度t+其中，交叉与变异非常重要，其方法也多种多样，如交叉算子（OX算子）通过在一个亲体中选择一个子序列旅行并保持另一个亲体中的城市

55、相对次序从而构造出后代.例如，两个亲体设为将按照下面的方式产生后代.首先，切割点之间的部分保持在新的个体中为了得到，移走中已在中的城市得到 21706该序列顺次放入中得到，相似地得到另一个后代为变异算子（倒序算子）在染色体上随机选取两点，将两点间的子串翻转，例如，原个体：随机选择两点：倒序后的个体：选择算子在求解TSP问题中常采用锦标赛选择算子，即随机在群体中选择个个体进行比较，适应度最好的个体将被选择复制到下一代，参数常称之为竞赛规模，常取遗传算法缺陷：基本遗传算法可以求解一些规模较小的优化问题，但是，对于规模较大或有一定难度的NP完全优化问题，使用遗传算法可能变得比较困难.因此，众多学者对

56、遗传算法进行了深入的研究，提出了多种改进方案.下面的例子将遗传算法与贪婪算法结合求解组合优化问题。（ZOKP 的混合遗传算法，问题描述见前述）求解ZOKP的贪婪算法（Greedy algorithm）常采用下面的启发式策略：首先将物品按照价值密度从大到小进行排列，依次将物品装入背包，直到背包容量达到最大为止。采取该贪婪策略可以求得ZOKP 的近似较好解，但是有可能得不到最优解。采用标准遗传算法求解，当问题规模不大时，可以求出近似最优或最优解，但当问题规模变得较大时，由于标准遗传算法在较大的搜索空间中搜索能力较差，从而很难得到该质量的解，因此，为了提高标准遗传算法的搜索能力，将求解背包问题的贪婪

57、算法溶入到遗传算法中，得到一种混合遗传算法，其思想描述为：（） 编码格式： 采用0-1字符串进行编码，一个字符串代表一种编码策略，例如，个体与装包策略的关系为：分别对应于将第件物品不装入（或者装入）袋中；（）混合繁殖算子：对于选取的选择算子S,交叉算子C和变异算子M,引进背包问题已有的贪婪算法以改进繁殖算子，具体做法是：首先引进贪婪变换，对于任意的，其中由下列贪婪算法得到：贪婪算法：第一步（排序）：对所有的物品，物品按照价值密度从大到小进行排列，形成队列；第二步（赋值）：. ；. 计算；.如果，则将第号物品装入袋中，即，赋值并回到. 否则转下一步. 该贪婪变换把任意一个个体变换成可行解，此时，

58、我们把贪婪变换与所选定的交叉与变异算子分别作复合运算，从而形成新的混合交叉与混合遗传算子：（1）（）适应度度量：按照上面描述的编码格式、混合的交叉与变异算子以及适应度度量，即可建立一种求解背包问题的混合遗传算法。例如，考虑由件物品组成的背包问题，其中物品价值、容积和背包容量分别为分别采用贪婪算法、标准的遗传算法（含比例选择、单点交叉和点变异）和上述构造混合遗传算法进行求解，其中运行参数取为第一组：；第二组：其中分别代表种群规模和终止进化代数，各算法独立运行000次，然后对结果进行统计，其统计结果如表4所示，而最好结果如表5 所示。表4 求背包问题的贪婪算法、标准遗传算法与混合遗传算法的比较（次

59、实验）算法及参数结果超过贪婪算法的解的次数结果超过贪婪算法解时的进化代数最好求解结果（总价值总重量）标准遗传算法混合遗传算法标准遗传算法混合遗传算法贪婪算法表5标准遗传算法、混合遗传算法与贪婪算法求解个物品背包问题的最好解比较算法个体求解结果（总价值总重量）标准遗传算法1110003077/999混合遗传算法1110003103/999贪婪算法1110013036/999从表4与表5不难看出，由于将求解背包问题的贪婪算法溶入遗传算法得涉及中，无论是解的质量还是在求解速度方面，混合遗传算法比标准遗传算法和贪婪算法都有显著改进。（英文版 ） easily blame, to prevent the

60、 broken window effect. Supervise the leading cadres to play an exemplary role, take the lead in the strict implementation of the and , lead to safeguard the solemnity and authority of the party discipline, ensure that the party discipline and the laws and regulations for implementation in place. Thr