智能优化搜索算法

模拟退火算法模拟退火（SimulatedAnnealing，简称SA）是一种通用概率算法，用来在一个大的搜寻空间内找寻命题的最优解。1、固体退火原理：将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-ΔE/(kT)，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。2、用固体退火模拟组合优化问题：将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法——由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。3、退火过程：冷却进度表(CoolingSchedule)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。4、模拟退火算法的模型模拟退火算法可以分解为解空间、目标函数和初始解三部分。(1)初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)，每个T值的迭代次数L(2)对k=1，……，L做第(3)至第6步：(3)产生新解S′(4)计算增量Δt′=C(S′)-C(S)，其中C(S)为评价函数(5)若Δt′0则接受S′作为新的当前解，否则以概率exp(-Δt′/T)接受S′作为新的当前解.(6)如果满足终止条件则输出当前解作为最优解，结束程序。终止条件常取为连续若干个新解都没有被接受时终止算法。(7)T逐渐减少，且T-0，然后转第2步。（降温）5、模拟退火算法新解的产生和接受：（1）由一个产生函数从当前解产生一个位于解空间的新解：为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。（2）计算与新解所对应的目标函数差：因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。（3）判断新解是否被接受：判断的依据是一个接受准则，最常用的接受准则是Metropo1is准则:若Δt′0则接受S′作为新的当前解S，否则以概率exp(-Δt′/T)接受S′作为新的当前解S。（4）当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。6、算法的特点模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。7、简单应用作为模拟退火算法应用，讨论货郎担问题(TravellingSalesmanProblem，简记为TSP)：设有n个城市，用数码1,…,n代表。城市i和城市j之间的距离为d(i，j)i,j=1,…,n．TSP问题是要找遍访每个域市恰好一次的一条回路，且其路径总长度为最短.。求解TSP的模拟退火算法模型可描述如下：解空间解空间S是遍访每个城市恰好一次的所有回路，是{1，……，n}的所有循环排列的集合，S中的成员记为(w1,w2,……，wn)，并记wn+1=w1。初始解可选为(1，……，n)目标函数此时的目标函数即为访问所有城市的路径总长度或称为代价函数：我们要求此代价函数的最小值。新解的产生随机产生1和n之间的两相异数k和m，若k(w1,w2,…，wk,wk+1,…，wm,…，wn)变为：(w1,w2,…，wm,wm-1,…，wk+1,wk,…，wn).如果是km，则将(w1,w2,…，wk,wk+1,…，wm,…，wn)变为：(wm,wm-1,…，w1,wm+1,…，wk-1,wn,wn-1,…，wk).上述变换方法可简单说成是“逆转中间或者逆转两端”。也可以采用其他的变换方法，有些变换有独特的优越性，有时也将它们交替使用，得到一种更好方法。代价函数差设将(w1,w2,……，wn)变换为(u1,u2,……，un),则代价函数差为：根据上述分析，可写出用模拟退火算法求解TSP问题的伪程序：ProcedureTSPSA:begininit-of-T;{T为初始温度}S={1，……，n};{S为初始值}termination=false;whiletermination=falsebeginfori=1toLdobegingenerate(S′formS);{从当前回路S产生新回路S′}Δt:=f(S′))-f(S);{f(S)为路径总长}IF(Δt0)OR(EXP(-Δt/T)Random-of-[0,1])S=S′;IFthe-halt-condition-is-TRUETHENtermination=true;End;T_lower;End;End模拟退火算法的应用很广泛，可以较高的效率求解最大截问题(MaxCutProblem)、0-1背包问题(ZeroOneKnapsackProblem)、图着色问题(GraphColouringProblem)、调度问题(SchedulingProblem)等等。8、参数控制问题模拟退火算法的应用很广泛，可以求解NP完全问题，但其参数难以控制，其主要问题有以下三点：(1)温度T的初始值设置问题。温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始温度一般需要依据实验结果进行若干次调整。(2)退火速度问题。模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说，同一温度下的“充分”搜索(退火)是相当必要的，但这需要计算时间。实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。(3)温度管理问题。温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中，由于必须考虑计算复杂度的切实可行性等问题，常采用如下所示的降温方式：T(t+1)＝k×T(t)式中k为正的略小于1.00的常数，t为降温的次数。禁忌算法禁忌搜索算法（TabuSearch或TabooSearch，简称TS算法）是一种全局性邻域搜索算法，模拟人类具有记忆功能的寻优特征。TS算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。1、基本思想考虑最优化问题，对于X中每一个解x，定义一个邻域N(x)，禁忌搜索算法首先确定一个初始可行解x，初始可行解x可以从一个启发式算法获得或者在可行解集合X中任意选择，确定完初始可行解后，定义可行解x的邻域移动集s(x)，然后从邻域移动中挑选一个能改进当前解x的移动，s(x)，再从新解x’开始，重复搜索。2、算法流程给定一个当前解（初始解）和一种邻域，然后在当前解的邻域中确定若干候选解；若最佳候选解对应的目标值优于“bestsofar”状态，则忽视其禁忌特性，用其替代当前解和“bestsofar”状态，并将相应的对象加入禁忌表，同时修改禁忌表中各对象的任期；若不存在上述候选解，则选择在候选解中选择非禁忌的最佳状态为新的当前解，而无视它与当前解的优劣，同时将相应的对象加入禁忌表，并修改禁忌表中各对象的任期；如此重复上述迭代搜索过程，直至满足停止准则。（1）给定算法参数，随机产生初始解x，置禁忌表为空。（2）判断算法终止条件是否满足？若是，则结束算法并输出优化结果；否则，继续以下步骤。（3）利用当前解中的邻域函数产生其所有（或若干）邻域解，并从中确定若干候选解。（4）对候选解判断藐视准则是否满足？若成立，则用满足藐视准则的最佳状态y替代x成为新的当前解，即x=y，并用与y对应的禁忌对象替换最早进入禁忌表的禁忌对象，同时用y替换“bestsofar”状态，然后转步骤6；否则，继续以下步骤。（5）判断候选解对应的各对象的禁忌属性，选择候选解集中非禁忌对象对应的最佳状态为新的当前解，同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象元素。（6）转步骤（2）。3、算法特点新解不是在当前解的邻域中随机产生，而或是优于“bestsofar”的解，或是非禁忌的最佳解，因此选取优良解的概率远远大于其他解。由于TS算法具有灵活的记忆功能和藐视准则，并且在搜索过程中可以接受劣解，所以具有较强的“爬山”能力，搜索时能够跳出局部最优解，转向解空间的其他区域，从而增强获得更好的全局最优解的概率，所以TS算法是一种局部搜索能力很强的全局迭代寻优算法。4、组合策略(1)邻域移动:是从一个解产生另一个解的途径。它是保证产生好的解和算法搜索速度的最重要因素之一。通过移动，目标函数值将产生变化，移动前后的目标函数值之差，称之为移动值。如果移动值是非负的，则称此移动为改进移动;否则称作非改进移动。最好的移动不一定是改进移动，也可能是非改进移动，这一点就保证搜索陷入局部最优时，禁忌搜索算法能自动把它跳出局部最优。(2)禁忌表:不允许恢复即被禁止的性质称作Tabu。禁忌表的主要目的是阻止搜索过程中出现循环和避免陷入局部最优，它通常记录前若干次的移动，禁止这些移动在近期内返回。在迭代固定次数后，禁忌表释放这些移动，重新参加运算，因此它是一个循环表，每迭代一次，将最近的一次移动放在禁忌表的末端，而它的最早的一个移动就从禁忌表中释放出来。禁忌表记载移动的方式主要有三种:*记录目标值；*移动前的状态；*移禁忌搜索算法.(3)选择策略:即择优规则，是对当前的邻域移动选择一个移动而采用的准则。当前采用最广泛的两类策略是最好解优先策略(Bestlmprovedstrategy)和第一个改进解优先策略(FirstImProvedstrategy)。最好改进解优先策略就是对当前邻域中选择移动值最好的移动产生的解，作为下一次迭代的开始。而第一个改进解优先策略是搜索邻域移动时选择第一改进当前解的邻域移动产生的解作为下一次迭代的开始。(4)破禁策略:常指渴望水平(Aspiration)函数选择，当一个禁忌移动在随后T次的迭代内再度出现时，如果它能把搜索带到一个从未搜索过的区域，则应该接受该移动即破禁，不受禁忌表的限制。(5)停止规则:一种是把最大迭代数作为停止算法的标准，而不以局优为停止规则;另一种是在给定数目的迭代内所发现的最好解无法改进或无法离开它时，算法停止。(6)长期表:短期记忆用来避免最近所作的一些移动被重复，但是在很多的情况下短期记忆并不足以把算法搜索带到能够改进解的区域。因此在实际应用中常常短期记忆与长期记忆相结合使用，以保持局部的强化和全局多样化之间的平衡，即在加强与好解有关性质的同时还能把搜索带到未搜索过的区域。一种通过惩罚的形式，即用一些评价函数来惩罚在过去的搜索中用得最多或最少的那些选择，并用一些启发方法来产生新的初始点。另一种形式采用频率矩阵，使用两种长期记忆，一种是基于最小频率的长期记忆，另一种是基于最大频率的长期记忆。遗传算法遗传算法（GeneticAlgorithm，简称GA）是建立在自然选择和群体遗传学基础上，通过自然选择、杂交和变异实现随机化搜索的方法。1、基本思想从任意初始种群出发，通过随机选择（使种群中的优秀个体有更多的机会传给下一代）、杂交（体现自然界中种群内个体之间的信息交换）和变异（在种群中引入新的变种确保种群中信息的多样性）等遗传操作，使种群一代一代地进化到搜索空间中越来越好的区域，直至达到最优解。具体的算法流程如下：a)初始化:设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。b)种群P(t)经过选择、交叉、变异运算