数学建模之智能计算

主要介绍几种典型的智能计算理论与方法.1讲述基于热力学退火过程产生的模拟退火算法；2介绍一类从智能观点模拟生物智能的计算理论与方法—遗传算法；3与§4分别介绍模仿蚁群迁徙与觅食过程以及模拟鸟类群体行为而建立起来的蚁群算法和粒子群算法；5元胞自动机的概念与算法，支持向量机等智能计算产生的背景优化问题的数学语言max()..{|()0,1,2,,}ifxstXSXgXin其中，()fX为目标函数，()igX为n个约束条件（函数）。不难看出，优化问题是指在一定约束条件下，寻找一组参数使其最优性得到满足。根据目标与约束条件中变量是否满足线性、连续、目标函数的个数等，优化问题又可以分为线性和非线性规划，或单目标规划与多目标规划等。线性规划中，当变量为整数或仅取0与1时，又得到整数规划或0-1整数规划。在一般情形下，非线性规划问题远远高于线性规划问题的求解难度。当考虑(1)kk个目标函数时，上述优化问题可以描述为12max(),()((),(),,())..{|()0,1,2,,}TkiFXFXfXfXfXstXSXgXin其中，()FX为多目标变量。对于多目标优化问题而言，所包含的不同目标函数之间往往存在着目标不一致的地方，因此在求解过程中，很难满足同时达到最优的情形。根据变量的特性，优化问题又可以分为函数优化与组合优化两种，其中，优化对象约束在一定的区域时，呈现为函数优化问题，而优化对象为解空间中的离散状态时，则为组合优化问题。组合优化问题可以描述为：12max(){,,,}iinCssSsss本节后面介绍的旅行商问题（TSP）、最大截问题、0-1背包问题以及调度问题等都属于组合优化问题。最优化问题的求解可以分为经典优化算法与启发式优化算法。1947年。美国数学家Dantzig提出了求解线性规划问题的单纯性算法，随后，Kamaka提出多项式级的椭球算法与内点算法。对于非线性问题，人们从二次规划问题入手，建立了许多经典算法，如最速下降法、共轭梯度法、牛顿法与拟牛顿法等。经典算法的局限性：一般使用局部信息，如需要初始点以及导数等信息，从而使得经典算法容易陷入局部最优的陷阱，而导数等苛刻性质的需求则极大限制了算法的有效范围。智能计算的兴起：受到大自然运行规律的启发，上世纪50年代开始启发式算法得到广泛采用，尤其是启发式算法思想与人工智能领域中的各种有关问题求解方法相结合，产生了许多智能型启发式搜索算法，其中，贪婪算法、局部搜索方法以及按概率选择成为最常见的启发式方法。一、模拟退火算法模拟退火算法属于一种典型的启发式算法Kirpatrick（1982）基本思想：观察到固体退火过程与离散系统中的组合优化问题的求解存在某种相似性，并将Metropolis准则引入到组和优化问题的求解中，建立了一种对Metropolis算法进行迭代的组合优化算法，由于该算法模拟固体退火原理，因此经常称之为“模拟退火算法”。1．Metropolis准则MonteCarlo方法固体在指定温度下达到热平衡的过程可以通过MotelCarlo方法进行仿真来实现，原理简单，算法易于编程实现问题：为了保证算法的精确性则必须进行大量采样，从而存在计算量巨大的问题。Metropolis准则，Metropolis于1953年提出思想:借鉴MonteCarlo方法的思想,只对”重要贡献”的状态进行采样,目的:减少运算量通过随机方式达到最优解，是一种随机接受准则，其方法可以描述如下（优异者一定接受，劣者按概率接受）：先给定以粒子相对位置表征的初始状态i，作为固体的当前状态，该状态的能量设为iE，然后利用摄动装置使随机选取的某个粒子的位移产生微小的变化，得到一个新的状态j,该状态的能量记为jE，如果jiEE，则该新状态就作为“重要”状态，如果jiEE，则考虑到热运动的影响，该新状态是否“重要”需要设置一个概率数来进行判断，具体做法是设固体处于状态I与状态j的概率比值设为r，r为一个小于1的数，用随机数产生器产生一个位于[0,1)区间的随机数，若r，则新状态j仍然作为“重要”状态，否则舍去。若新状态j是重要状态，就以j取代I成为当前状态，否则仍以I为当前状态，一直重复上述新状态的产生过程，当固体经过大量变换（或称为迁移）后，系统趋于能量较低的平衡状态。上述随机接受新状态的准则称之为Metropolis准则，相应的算法称之为Metropolis算法。由于采用随机方法，一般情况下Metropolis算法的运算量明显少于MoteCarlo方法的运算量。2模拟退火算法(SimulatedAnnealing—SA)1982年，Kirkpartrick提出将固体加温至充分高（能量达到最大），再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。统计力学的研究表明，当温度为T时，分子停留在状态r满足Boltzmann概率分布，即1(){()}exp{}()ErPEErZTbT其中()Er为状态r的能量，E为分子能量的一个随机变量，()ZT为概率分布的标准化因子：()()exp{}sDEsZTbT将优化问题类比成退火过程，当满足接受条件时，以概率为1的形式接受新解，否则，根据Boltzmann概率分布的形式接受劣解.因此，不考虑标准化因子，粒子在温度T时趋于平衡的概率为exp{}EbT，其中E为温度T时的内能，ΔE为其改变量，b为Boltzmann常数.将固体退火的思想引入到组合优化问题的求解中，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(CoolingSchedule)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。上述模拟退火过程可以通过下列算法来实现.(1)初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)，每个T值的迭代次数L(2)对k=1，……，L做第(3)至第（6）步：(3)产生新解S′(4)计算增量(')()TCSCS，其中C(S)为评价函数(5)若0T则以概率为1的形式接受S′作为新的当前解，否则计算概率exp{}EbT，并按照接照Metropolis准则将S′作为新的当前解.(6)如果满足终止条件则输出当前解作为最优解，结束程序.终止条件通常取为连续若干个新解都没有被接受时终止算法.(7)T逐渐减少，且T-0，然后转第2步.算法中新解的产生和接受可分为如下四个步骤：第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。第二步是计算与新解所对应的目标函数差。目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。第三步判断新解是否被接受判断的依据是一个接受准则,最常用的接受准则是Metropo1is准则:若Δt′0则接受S′作为新的当前解S，否则以概率exp(-Δt′/T)接受S作为新的当前解S。第四步当新解被确定接受时，用新解代替当前解这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。模拟退火算法评价:模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。模拟退火算法的应用很广泛，可以求解NP完全问题。模拟退火算法的数学理论支持从数学的角度来看，可以通过马尔科夫（Markov）过程来描述模拟退火算法：在给定领域结构后，模拟退火过程是一个从一个状态到另一个状态不断的随机游动，具体地说，当温度t为确定值后，两个状态的转移概率（transitionprobability）定义为1,()(),()1()(),ijijNijililkkigyAtjiptgtAtji其中，N表示状态集合中状态的个数，()ijgt称为从i到j的产生概率，表示在状态i时，j状态被选取的概率。当j为i的邻域时，如果采用等概率选取方法，则j被选中的概率为1|()|(),()0,()ijNeigtjNeijNei其中(),|()|NeiNei分别表示i的邻域以及邻域所含元素的个数，()ijAt为接受概率，()ijAt表示从状态i产生状态j后，接受状态j的概率，在模拟退火算法中，接受概率值为1,()()()exp(/),()()ijijfifjAtftfifj()(()),()(())ijNNijNNGtgtAtAt和()(())ijNNPtpt分别称之为产生矩阵、接受矩阵和一步转移概率矩阵。模拟退火算法的难点:参数难以控制，其主要问题有以下三点：(1)温度T的初始值设置问题.温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响.实际应用过程中，初始温度一般需要依据实验结果进行若干次调整.(2)退火速度问题.模拟退火算法的全局搜索性能也与退火速度密切相关.一般来说，同一温度下的“充分”搜索(退火)是相当必要的，但这需要计算时间.实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件.(3)温度管理问题.温度管理问题也是模拟退火算法难以处理的问题之一,降温方式对算法影响最大，如果降温过快，可能丢失最优值点；如果降温速度太慢，算法的收敛速度又会受到较大的影响，收敛速度大大降低.实际应用中，由于必须考虑计算复杂度的切实可行性等问题，常采用如下所示的降温方式：(1)(),1,1tttTtTt.另外，为了便于操作，也常采用下面两种取法：（1）经典退火方式降温公式为0()ln(1)TTtt，特点是温度下降较慢，因此，算法的收敛速度也很慢；（2）快速退火方式降温公式为0()1TTtt；这种退火方式的特点是在高温区退火速度较快、在低温区退火速度逐渐变慢，降温速度减弱，这符合在热力学分子运动理论中，在高温时某粒子所具有较低能量的概率比在低温时小得多的规律.因此，寻优的重点应该放在低温区，式中用以改善退火曲线的形态.上述算法可以通过程序的方式来描述，具体过程为：SA_AlgorithmProcedureSA-Algorithm(00,iT);/*0iS为任一初始状态，0T为初始控制参数*/begin(1)0;*;0iiSSCCk/*简记(),*iiCCSC为当前代价值*/（2）repeat(2.1)repeat(2.1.1)()jSGenerateS(2.1.2)if*jCCthenjSSelseifAccept(,)jsthenjSSendifendig(2.1.3)until内循环结束；(2.2)1();1kiTUpdateTkk(3)UntilkTend.在上述算法中，（1）为初始化，（2.1.1）的Generate(S)表示从S的邻域中随机产生下一个状态0jS，若*jCC，则接受j为新的当前状态；否则仅以一定的概率接受j为新的状态，这也是Accept(j,s0函数的功能。Accept函数的常见形式为functionAccept(j,s)begi