模拟退火优化算法（精选9篇）
模拟退火优化算法 篇1
引言
近年来,模拟退火算法不仅因为其自身的稳健性、隐并行性和全局特性而得到了广泛的应用,而且,其中的杂交思想作为一种方法论也给从事科学研究的人们以许多启迪,并导致许多边缘学科的产生。本文利用正交设计能快速找出最优解的特点,把正交设计嵌入到遗传算法的交叉算子中,研究了一种采用多点正交交换的遗传算法。算法通过正交表安排遗传算法的交叉运算,并在所产生的多个子代中选择适应度大的进入下一次进化。随后,利用这种改进的算法来优化计算机网络设计中的路由选择与容量分配问题,与拉格朗日松弛法、传统遗传算法进行了比较。结果表明该算法较之传统方法结果更优,与传统遗传算法相比,获得同样解的情况下,收敛速度明显加快。
一、模拟退火算法
模拟退火算法的依据是固体物质退火过程和组合优化问题之间的相似性。物质在加热的时候,粒子间的布朗运动增强,到达一定强度后,固体物质转化为液态,这个时候再进行退火,粒子热运动减弱,并逐渐趋于有序,最后达到稳定。根据Metropolis准则,粒子在温度T时趋于平衡的概率为e-ΔE/(kT),其中E为温度T时的内能,ΔE为其改变量,k为Boltzmann常数。用固体退火模拟组合优化问题,将内能E模拟为目标函数值f,温度T演化成控制参数t,即得到解组合优化问题的模拟退火算法:由初始解i和控制参数初值t开始,对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代,并逐步衰减t值,值得注意的是,当T为0时,模拟退火就成为局部搜索的一个特例。算法终止时的当前解即为所得近似最优解,这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表控制,包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。
模拟退火的典型特征是除了接受目标函数的改进外,还接受一个衰减极限,当T较大时,接受较大的衰减,当T逐渐变小时,接受较小的衰减,当T为0时,就不再接受衰-减。这一特征意味着模拟退火与局部搜索相反,它能避开局部极小,并且还保持了局部搜索的通用性和简单性。
模拟退火的基本思想:
(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步。
模拟退火算法与初始值无关,算法求得的解与初始解状态S(是算法迭代的起点)无关;模拟退火算法具有渐近收敛性,已在理论上被证明是一种以概率l收敛于全局最优解的全局优化算法。
二、在网络优化设计中的应用
1. 问题描述
在设计计算机通信网,特别是干线网时,各条链路的容量分配和报文的路由选择是需要考虑的两个重要问题。在网络拓扑结构已定的情况下,怎样确定各条链路的容量分配和报文的路由选择,使得整个网络的建设、运转费用最低?因此,最佳的结果应当是考虑线路选择和容量这两个问题。本文采用模拟退火算法给出了优化该问题的数学模型。
2. 模拟退火算法设计
拓扑结构用图1描述如下,在图G(V,A)中,V表示网络的节点(即容量或路由互通立交)集合,V={v1,v2,...,vn},对G中的某一条边(vi,vj)之间连通则为路段长度,如(vi,vj)之间不连通为∞,在实际计算中以一个足够大的值代替。我们把矩阵w={d(vi,vj)|vi,vj∈V}称为网络拓扑权矩阵。
在模拟退火算法中加入倒置思想:随机在路径中选出两个节点vi与vj,然后将两个节点之间的节点顺序完全倒置得出新的路径。如两相异点k和m,则将原路径(w1,w2,...wk-
变为新路径:(w1,w2,...wk-1,wm,wm-1,...,wk+1,wkwm+1,...,wn)。
得出解空间,通过权w{i,j}>0,且节点x的标号为D(x),那么D(z)是从节点a到z的最短路径的长度,所以最短路径可以表示为:
其中
2.2.1.适应度函数
由解空间计算出权值向量W,由此计算出网络的输出,以训练集样本作为网络的输入和期望输出。设节点规模为N,每节点相应的实际输出yk(k=1,2,…n,n是网络输入输出样本对数)。第i(i=1,2,…N,N是节点群体规模)个节点的误差平方和表示为,其倒数作为群体的适应度值。
2.2.2最优路径模式
设优化问题的系统参数(变量)有x1个,x1表示分配第x1类容量给第l条链路,构成可供优化选的参数(变量)集X:
X即为优化问题的解空间。其中的一组参数如下式所示:
,称为该参数优化问题的一个解。
网络矩阵有如下递归方程和第k步的邻接矩阵:
设评价优化问题的性能指标有m个,构成性能指标集Q:
对于某一个参数解x(j),对应的性能指标值为:
其中,qk(j)是每一个性能指标qk关于参数解x(j)的取值。
sk反映了指标qk的满意程度;利用sk构成满意度函数向量:s=[s1,s2,...,sm],
,以向量函数g(·)表示性能指标向
量q的满意度函数,得到:
定义综合满意度函数:
其中,
综合满意度函数为标量函数,反映出了网络对性能指标的综合评价。根据以上各式,可以定义优化问题的计算模型如下:
三、程序设计
节点越多,循环次数越多,计算时间将成倍增长,因此机器的运行速度、计算时间和占用的计算机内存也会大幅度的提高。考虑到每个路由器周期性地发送数据,提供其邻接点的信息或当其状态改变时通知其它路由器。通过对已建立的邻接关系和链接状态进行比较,失效的路由器可以很快被检测出来,网络拓扑相应地更动,建立一个邻接矩阵和一个动态数组来存储网络的拓扑关系。从生成的拓扑数据库中,每个路由器计算最短路径树,以自己为根。进行动态最短路径优化。模拟退火算法的网络优化设计程序设计如图2所示。
四、实验结果
为准确证明算法的效率,由于算法要求初始温度必须充分大,所以在算法中我们设置初始温度都为300000,降温速率都为0.92,迭代次数均为2000次。设在网中,节点有72个并且每个节点都与网络其它节点进行通信,设每队通信结点的通信量为每秒4个报文,采用Matlab编制了算法程序,为了消除随机干扰,不同分组长度下的实验都运行多次。在所有参数相同的情况下,算法得到的结果为:总路线长度为8868.2,运算时间为13.11秒。算法优化的最终结果如图3所示。
摘要：网络是个随机性很强系统,为了获得良好的通行效率,提出了一种基于模拟退火算法优化方法,同时给出了程序设计流程。在算法中加入倒置思想,选择合适的适应度函数值,然后构造模型,给出了优化函数。仿真结果表明:这种算法不仅收敛性和稳定性都很好,而且模型是可行的、有效的。
关键词：网络优化,模拟退火算法,拓扑权矩阵
参考文献
[1]王伟,殷志祥.基于模拟退火算法的可逃逸粒子群算法[J].计算机应用研究,2008,(05):1326-1327,1339
[2]徐潘萍.浅谈模拟退火算法在自动排课系统中的应用[J].井冈山学院学报,2008,(06):35-37
[3]李薰春,史虹湘,杨明,李栋.基于模拟退火算法的地面电视频率指配方法研究[J].广播与电视技术,2008,(06):27-30
[4]李香平,张红阳.模拟退火算法原理及改进[J].软件导刊,2008,(04):47-48
[5]王伟.模拟退火算法的并行化策略研究[J].电脑知识与技术,2008,(25):1523-1524
[6]冯剑,岳琪.模拟退火算法求解TSP问题[J].森林工程,2008,(01):94-96
[7]潘海琳,张松涛,张福利.并行模拟退火算法在拱坝体形优化中的应用[J].黑龙江水专学报,2008,(02):29-31
[8]李爽,张瑾.改进模拟退火算法在数据挖掘中的应用[J].计算机与数字工程,2008,(02):17-19,168
[9]叶子伟,韩红超.基于退火BP神经网络的GPS高程转换[J].测绘工程,2008,(04):4-7
[10]陈广洲,汪家权.基于模拟退火算法的投影寻踪方向优化[J].合肥工业大学学报(自然科学版),2008,(08):1315-1317,1325
模拟退火优化算法 篇2
线性最小二乘估计在对非线性函数进行线性近似的.过程中会产生模型误差,而一些非线性参数估计方法可能因为函数复杂而难以求导,法方程系数矩阵秩亏或呈病态矩阵时难以求解,非线性迭代解法有时对初始值的选择存在依赖性,不恰当的初始值会导致迭代无法收敛.针对这些问题,引入了模拟退火算法,介绍了该算法的基本原理、计算步骤和收敛性,并以3个控制网平差应用为例,说明该算法具有无需求导求逆,简洁实用,易于编程等优势,并能实现全局优化,获得高精度的平差结果.
作 者：邓兴升 王新洲 DENG Xing-sheng WANG Xin-zhou 作者单位：邓兴升,DENG Xing-sheng(武汉大学,测绘学院,湖北,武汉,430079;武汉大学,灾害监测与防治研究中心,湖北,武汉,430079)
王新洲,WANG Xin-zhou(武汉大学,测绘学院,湖北,武汉,430079;武汉大学,灾害监测与防治研究中心,湖北,武汉,430079;山东科技大学,地球信息科学与工程学院,山东,青岛,266510)
模拟退火优化算法 篇3
一、遗传算法
遗传算法（Genetic Algorithm）是最初由美国Michigan大学J.Holland教授于1975年首先提出来的，是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法包含5个要素：初始化种群，选择，交叉，变异，更新初始群体，结束条件。
模拟退火算法是根据固体退火原理，将固体加热到充分高的温度，再让其徐徐冷却，加温时，固体内部的粒子随着温度上升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到到平衡态，最后在常温时达到基态，内能减为最小【1】。
由于遗传算法具有良好的全局搜索能力，但是对于局部空间搜索却不是很有效，容易产生早熟收敛现象，陷入局部最优【2】。为了解决这个问题，可以将模拟退火算法结合到遗传算法中，模拟退火算法的局部搜索能力可以解决遗传算法局部搜索能力差以及早熟现象，同时也解决了模拟退火算法全局搜索能力差和效率不高的问题。
二、软件测试
软件测试是运行程序并发现程序错误的过程。测试是为了发现程序中的错误，而不是证明程序中没有错误。而测试用例应该包括为测试某个程序路径或者确定是否满足某个特定需求而编制的一组测试输入、执行条件和与之对应的预期结果。一个好的测试用例是能够快速有效的发现程序中的错误。一般把测试分为两类：白盒测试也称为结构测试、透明盒测试、逻辑驱动测试或基于代码的测试，是按照程序内部的结构测试程序，通过测试来检测产品内部动作是否按照设计规格说明书的规定正常进行，检验程序中的每条通路是否都能按预定要求正确工作；黑盒测试也称为功能测试或数据驱动测试，是通过测试来确认每个功能是否得到完整实现，检测每个功能是否都能正常使用。而黑盒测试的测试用例设计通常是用等价划分法。
用等价类划分法首先要划分等价类：输入规定了的取值范围或值的个数就可以确定一个有效等价类和两个无效等价类。输入规定了的输入值的集合或者一个布尔量可以确定一个有效等价类和一个无效等价类。输入规定的输入数据的一组值（假设m个）且对每一个输入值分别处理可以确定m个有效等价类和一个无效等价类。输入的数据必须遵守一定的规则可以确定一个有效等价类和若干个无效等价类。已划分的等价类中各元素处理方式不同时应将等价类再划分为更小的等价类。其次确定测试用例：给等价类编号设计一个重复使其尽可能多地覆盖尚未被覆盖过的合理等价类直到所有合理等价类被测试用例覆盖的测试用例。设计一个使其只覆盖一个不合理等价类的测试用例。
三、用模拟退火遗传算法需求最佳测试用例
（1）编码。模拟退火遗传算法需要将软件测试中的一个问题的可行解从解空间转换到遗传算法所能解决的搜索空间。初始化种群规模为100，编码方法可以选择浮点法、grey法则和二进制法，本文每个参数的编码方式采用二进制编码。
（2）选择退火算子
在软件测试中，测试的目的是发现程序中至今没有发现的错误，一个好的测试用例就相当于遗传算法中适应度值大的个体，本文将初始群体中的100个个体进行适应度评价，个体适应度值越大，该个体被遗传到下一代的概率也越大。
①随机选择初始群体两个个体A、B，计算其个体适应度值f（A）和f（B）。
②如果f（A） ③重复①、②操作直到新的一代群体中也包含100个个体。 （3）选择。染色体的选择方法可以采用锦标赛法和轮盘赌法，本文采用轮盘赌法，通常适应度大的被选择的几率较高。 （4）交叉。在遗传算法的遗传操作中，交叉运算决定了遗传算法的全局搜索能力【3】。将父代中的任意两个个体进行交叉产生最新染色体。进行退火操作，如果最佳适应度大于最新染色体适应度，就用最新染色体适应度取代之前的最佳适应度，否则以概率P（exp（（f（A）-f（B））/T））接受最新个体。重复操作，直至以概率0.7完成所有的交叉操作。 （5）变异。在遗传算法的遗传操作中，变异操作决定了遗传算法的局部搜索能力【3】。变异方法的选择浮点法和单点法。本文采用浮点法。随机选择一个的内部选择两个节点进行变异，如果新产生的个体适应度小于原个体适应度，就用最新个体取代原个体，否则以概率P（exp（（f（A）-f（B））/T））接受最新个体。重复此操作。直至以概率0.05完成所有的交叉操作。 （6）终止条件。当进化代数超过某个值而适应度不变时或者进化代数达到最大值时。最后留下的也即最优的软件测试用例。 四、结束语 综上所述，本文重在在软件测试中使用模拟退火遗传算法需找最好的软件测试用例。以一种高效率的方式完成软件中的黑盒测试，并找出最佳测试用例。 参考文献 [1]季海婧.基于模拟退火—量子遗传算法的路径测试数据自动生成方法研究[D].浙江：杭州师范大学，2012. [2]杨清平.基于改进遗传算法的测试用例自动生成研究[D].广东：广东工业大学，311. [3]李欣，基于贝叶斯网络和遗传算法的测试用例生成模型[D].重庆：重庆交通大学，2012. 为了提高BFOA的性能,人们对算法的改进进行了研究,主要集中在算法参数和算法融合两个方面。梁艳春等人对趋向性操作进行改进提出了两种新的搜索策略:基于个体信息和基于群体信息的搜索策略;陈瀚宁等人分析步长C对BFOA局部开采和全局探索能力的影响提出自适应趋向性步长,并利用步长C的特点提出了协同细菌觅食算法[2];储颖等人针对细菌觅食优化收敛速度慢的特点,提出一种快速细菌群游算法[3],加强了算法在优化初期的全局搜索能力以及优化后期的局部搜索能力;Dasgupta和Das等人理论分析了使用自适应机制的步长对算法收敛性和稳定性的影响[4],但是他们的理论分析是基于一定的条件假设,只考虑在一维的连续空间中一个单独粒子进行的趋向性操作;Mishra提出用Takagi-Sugeno型模糊推理机制选取最优步长,该算法被称为模糊细菌觅食算法,但是,模糊细菌觅食算法的性能完全依赖于隶属函数和模糊规则参数的选择[5]。Biswas等人结合BFOA和PSO形成了混合算法—细菌种群优化(BSO)[6],有效地平衡了局部开采能力和全局探索能力,但是该算法在细菌的趋化算子内嵌入粒子群方法,赋予细菌对全局极值的感知能力,所有细菌通过与全局极值的对比,根据粒子群迭代公式更新细菌位置,此时算法中的趋化算子并没有起到作用;Dasgupta等人将差分进化算法中的交叉与变异操作引入到BFOA,提出了一种混合全局优化算法[7],虽然增加了种群的多样性,但同时也容易导致群体中优秀个体的缺失。 本文将模拟退火策略引入到基本的BFOA,提出了一种基于模拟退火策略的细菌觅食优化算法。该算法在趋向操作完成后,采用模拟退火策略对全局最优个体进行优化,提高算法的优化精度和稳定性,利用模拟退火算法的概率突跳性来避免陷入局部极值。 1 基本细菌觅食优化算法 1.1 BFOA的基本原理 BFOA模拟的是大肠杆菌在人体肠道内吞噬食物的行为,该算法主要有三大基本操作:趋化操作、复制操作、迁移操作。一个优化周期主要由3个部分组成,它们分别是趋化过程(Chemotaxis),繁殖过程(Reproduction),迁徙过程(Elimination and Dispersal)。 1)趋化过程 趋化行为是指细菌向含有丰富营养的区域聚集的行为,包括翻转(Tumble)和前进(Swim)两种模式。趋化行为使得算法中的细菌具有连续局部搜索的能力。细菌的趋化行为如图1所示,其中(1)为细菌的前进行为,(2)为细菌的翻转行为。 BFOA算法的趋化过程,可以描述如下,设(j,k,l)表示细菌i的位置,则在细菌趋化过程中细菌的运动可以表示为: 公式(1)中,j表示第j代趋向性操作循环,k表示第k代繁殖循环,l表示第l代迁徙循环,C(i)>0为细菌的趋向性行为步长,公式(2)中表示随机方向上的向量,是随机的翻转角度。 2)繁殖过程 趋化过程结束后,为了提高搜索的精度和缩短搜索时间,细菌进入繁殖过程,这一过程是参考了某一时间区域内细菌的整体表现后,执行的“优胜劣汰”行为,是以趋化周期内的细菌能量(适应值累加和)为标准,选择繁殖能量高的半数细菌来代替较差的另一半。 单个细菌的健壮函数表示为: 公式(3)中Jhealth表示细菌i在第j次趋向操作,第k次复制操作,第l次迁徙操作的健康值,Jhealth的值越大,细菌的健壮性就越差。淘汰的细菌个数表示为: 公式(4)中S表示细菌种群数,Sr表示淘汰的细菌数。 3)迁徙过程 在复制操作完成之后,细菌按照一定的概率p被随即分配到解空间中去,该操作就是迁徙操作。迁徙操作避免了细菌陷入局部极值,从而提高了算法的全局寻优能力。 1.2 BFOA流程 BFOA的流程图如图2所示。 2 模拟退火算法 模拟退火算法的思想最早是由Metropolis等提出的,1983年Kirkpatrick等将其用于解决组合优化问题[8]。该算法的出发点来源于工程中固体物质的退火原理,模拟了高温金属降温的热力学过程。从某一较高温度出发,伴随温度参数的不断下降,逐渐产生新的状态,结合概率突跳性在解空间中随机寻找目标函数的全局最优值,最终固体内粒子逐渐有序,达到平衡态。模拟退火算法在搜索过程中的概率突跳能力可以有效避免算法陷入局部极值,从而高效快速的找到全局最优解[9]。算法优化流程如下: 1)随机产生初始状态s=s0,确定初始温度t=t0,令k=0; 2)若算法终止条件未满足,则重复以下步骤: (1)若抽样稳定准则未满足,则重复如下步骤: (a)由当前状态s产生新的状态sj; (b)若min{l,exp[-(Jsj-Js)/tk]}≧rand[0,1],则s=sj;否则保持当前状态不变,其中Js为状态s的目标值; (2)退温操作tk+1=f(tk),令k=k+1; 3)输出算法搜索结果。 3 改进的细菌觅食优化算法 3.1 对优化变量进行越界处理 在优化过程中,当优化变量超过搜索区间时,对其采用撞壁法进行处理,以保证变量满足边界约束条件。 3.2 基于模拟退火策略的细菌觅食优化算法(SA-BFO) 3.2.1 SA-BFO的主要思想 BFO算法容易陷入局部极值,收敛精度低。SA算法是通过控制初温和温降过程来控制算法的搜索过程,在高温时,算法具有较高的突跳性,可以避免陷入局部极值;在低温时,有较好的保优性能,增强了算法的搜索能力。将细菌觅食优化算法和模拟退火算法有效的结合起来,用模拟退火算法来处理细菌觅食优化算法的早熟收敛和精度不高的问题。首先对每个个体进行趋向性操作,然后用趋向操作搜索到的全局最优个体进行模拟退火搜索,根据Metropolis准则接收新个体,并用搜索到的最优个体作为全局最优个体位置,最后执行复制操作和迁移操作。从而引导细菌快速跳出局部最优,加快收敛速度,提高算法的精度。 3.2.2 SA-BFO流程 SA-BFO的流程如图3所示: 4 仿真实验 4.1 测试函数 为了测试SA-BFO的性能,选取以下典型函数进行仿真实验,并且与标准的BFOA进行比较。 其中函数f1、f2、f3为单峰函数,f4、f5、f6为复杂的多峰函数,容易陷入局部极值,很难找到全局最优。为了测试SA-BFOA的性能,对上述六个函数分别采用基本的BFOA和SA-BFOA求解其最小值,进行30次实验,测试指标包括平均优化值、标准差和平均运行时间。其中平均优化值是指30次优化搜索结果的平均最优值,反映了在给定迭代次数下算法所能达到的精度;标准差反映了算法的鲁棒性和稳定性,标准差越小,算法越稳定;平均运行时间是指算法运行1次的平均时间,反映了算法的求解速度,平均运行时间越小,算法的求解速度越快。 4.2 参数设置 为了保证算法的可比性,对基本细菌觅食优化算法设置相同的参数,种群数为100,维度为100,趋化次数Nc=10,趋化步长c=0.2,最大前进步数Ns=4,复制次数Nre=10,迁移次数Ned=2,迁移概率Ped=0.25。模拟退火算法中的参数设置为:链长MarkovLength=50,温度衰减参数Decay Scale=0.95,步长因子Step Factor=0.02,初始温度Temperature=100。 4.3 实验结果 表1为BFO和SA-BFO优化6个测试函数的实验结果。从表1可以看出,不管是单峰函数还是多峰函数,SA-BFOA在平均最优值和标准差方面都优于基本BFOA,其中对于单峰函数f1、f2、f3,SA-BFOA的优化效果明显优于基本BFOA,对于多峰函数f4、f5、f6,SA-BFOA的优化效果略优于基本BFOA,表明SA-BFOA的求解精度和稳定性都优于基本BFOA,但是,由于在SA-BFO算法中加入了模拟退火搜索,所以,SA-BFOA的平均运行时间明显大于基本BFOA,运行速度较慢。 5 结束语 将退火策略引入基本细菌觅食优化算法中,提出了一种基于退火策略的细菌觅食优化算法。该算法利用模拟退火算法的概率突跳性来避免陷入局部极值,采用模拟退火策略对全局最优个体进行优化,提高算法的优化精度和稳定性。实验结果表明,改进算法具有更好的求解精度和鲁棒性,但是运行速度较慢,有待在后续研究中改进并将其应用于实际工程优化问题中。 摘要：针对标准细菌觅食优化算法(BFOA)求解精度不高、稳定性较差、容易陷入局部极值的问题,提出了一种基于模拟退火策略的细菌觅食优化算法(SA-BFO)。该算法在趋向操作完成后,采用模拟退火策略对全局最优个体进行优化,提高算法的优化精度和稳定性,利用模拟退火算法的概率突跳性来避免陷入局部极值。仿真实验结果表明,改进算法比标准细菌觅食优化算法具有较高的优化性能。 关键词：细菌觅食优化算法,模拟退火,概率突跳性,精度,稳定性 参考文献 [1]麦雄发,李玲.混合PSO的快速细菌觅食算法[J].广西师范学院学报,2010,4(27):91-95. [2]Chen H,Zhu Y,Hu K.Cooperative bacterial foraging optimization[J].Discrete Dynamicsin Natureand Society,2009,3(5):635-656. [3]储颖,靡华,纪震,等.基于粒子群优化的快速细菌群游算法[J].数据采集与处理,2010,25(4):442-448. [4]Das S,Dasgupta S,Biswas A,et al.Onstability of the chemotactic dynamicsin bacterial foraging optimization algorithm[J].IEEETransac tionson Systems,Man,and Cybernetics-PartA:Systems and Humans,2009,39(3):670-679. [5]Mishra S.Hybridleast-square adaptive bacterial foraging strategy forharm onicestimation[J].IEEEProceedings-Generation,Transmission,Distribution,2005,152(3):379-389. [6]Biswas A,Dasgupta S,Das S,et al.Synergy of PSO and bacterial foraging optimization-Acomparative study on Merical benchmarks[J].In novationsin Hybrid Intelligent Systems,2007,26(13):44(3):255-263. [7]Dasgupta S,Biswas A,Das S,et al.Automatic circled etectiononimages with an adaptive bacterial foraging algorithm[C],2008Genetic andEvolutionary ComputationConference(GECCO 2008),2008,13(5):1695-1696. [8]魏延,谢开贵.模拟退火算法[J].蒙古师范高等专科学校学报,1999,1(4):8-11. 模拟退火算法是一种通用的随机探索算法,利用它做优化无需复杂的求导运算和数学公式推导。通过模拟高温物体退火过程,即在某一初温下,伴随温度缓慢下降,结合概率的突跳性在解空间中寻找目标的全局最优解[3]。因此它非常适用高度非线性问题的优化。 1多项式拟合的最佳次数确定 一系列离散数据可以由多个多项式相互叠加后精确地表示,其中某一多项式占有主导地位,从而可以“最佳”地拟合[4]。 在对给水管道造价的离散数据进行公式拟合时,已知给水管道的各种标准管径Di及其所对应的综合单价C′(Di),C′(Di)为定义在区间(α,β)上的离散 数据点,Di取值范围 为标准管 径。 根据最小二乘法原理知,给水管线造价公式的拟合问题即求以参数a(a为某一给 定的函数 法则的系 数)为对应法 则的函数C(Di)满足C(Di)与C′(Di)之差的平方和最小。 这里引入数理统计中“均方差σ”的概念来衡量曲线的拟合精度,它能反映一个数据集的离散程度,其值越小则表明拟合程度越高。如下: 式中:N为离散数据点(D,C′)的数量。 对于实测的m组数据(Di,C′i),采用曲线拟合方法,给水管线的造价公式C(D)可以近似的用D的n-1次多项式表示: 式中:a1,a2,a3,…,an为曲线拟合系数。 其矩阵表达式为: 用矩阵符号可以表示为C=D·A,将等式两边同时乘以D的转置DT,整理变形后可得系数矩阵: 在式(2)中选取多项式的次数n越大,拟合精度越高,即均方差σ越小。但是随着 次数n的增加,虽然可以 提高拟合 精度,但是会导致函数的波动现象(即Runge现象),这样在未知的数据点反而会使函数值偏离标准值;并且σ值的下降会存在一个“畸变点”,即随着次 数n的升高σ 值下降很 小甚至升 高[4]。所以根据以上两点,在拟合数据前有必要先研究确定适合给水管线造价公式的多项式次数。 现通过对5个地区的给水铸铁管造价数据分别进行1~10次的多项式拟合,来确定给水管线造价公式所适应的最佳多项式次数。采用Matlab7.0多项式曲线拟合工具箱(原理为最小二乘法)可以得出拟合结果。 表1为收集的5个地区原始数据,算例1是调查西安市给水铸铁管(Ci,Di)数据、算例2~5(Ci,Di)数据资料分别源于文献[5-8]。 对表1数据进行 多项式拟 合的次数 与方差n~σ2结果如图1所示。从图1可以看出,σ2随着n的增加而减小,从一次到二次有一突降,n继续增加σ2值降低幅 度明显减 小甚至增 加,因为高次曲线拟合的精度较线性拟合会大幅提高,在n=2处存在一个 “畸变点”,为了达到 最佳拟合 且避免Runge现象[9],将给水管线造价函数的多项式拟合次数选择为n=3。 模拟退火优化算法 篇4
模拟退火优化算法 篇5
2模拟退火算法(SA)设计
模拟退火算法是通过对高温物体的模拟退火过程来搜索优化问题的全局最优解或近似最优解。对目标函数的自变量给定任意初始解利用摄动方法在当前解邻域内产生一个新解, 根据Metropolis准则确定是否接受该解。算法进行 之前首先 确定一个初始温度值t0,持续进行“产生新解 - 判断 - 接受或舍弃”的迭代过程,当该温度t0下的目标函数值持续不变时再根据一定的规则降低初始温度t0值,按照以上步骤进行迭代, 当t0值趋于0时,该解对应 于目标函 数的最小 值即全局 最优解。
2.1优化数学模型
为方便比较模拟退火算法与最小二乘法的优化效果,采用方差σ2即式(1)的平方作为优化给水管道造价函数曲线 算法的目标函数,并选择三次多项式作为给水管线造价函数C(D) 的形式,则目标函数如下:
该值愈小则拟合精度愈高,其取最小值时对应的一组参数a就是最佳的拟合参数。
2.2算法设计
限于篇幅,这里直接给出传统SA流程图,如图2所示,具体原理 见参考文 献[10]。由图2可见 ,算法中包 含1个内循环和1个外循环。内循环就是在同一温度tk下的多次扰动产生不同状态下的解,通过新状态产生函数实现扰动,并按照Metropolis准则接受新状态,因此是以状态扰动次数作控制的;外循环包括了温度下降的模拟退火算法的迭代次数的递增和算法停止的条件,因此基本是以迭代次数作控制的[11]。
2.2.1新状态产生函数
新状态的产生是对当前状态扰动得到的,新状态产生函数应保证所产生的候选解遍及整个解域。新状态每个独立变量新值基本方程形式如下:
式中:r为[0,1]之间均匀分布的随机数;K为区域缩减系数,取K≥1;α为分布系数,取正奇数3,保证(2r-1)α值可以取正或取负;ai(k)为第k次外循环时的候选解,k为外循环迭代次数编号;a′i为新状态候选解;aiL、aiU分别为候选解ai的下限与上限。
2.2.2Metropolis准则
Metropolis准则是算法避免限于局部最优解的关键,指从一个状态ai(一组可行参数解)向另一个状态aj(另一组可行参数解)的转移概率pt。它确定是否接受从当前解ai到新解aj的转移,由下式确定:
式中:tk为第k次迭代的温度,tk∈R+;pt为接受新状态aj的转移概率;f(ai),f(aj)分别为ai,aj状态下的目标函数值σ2。
由式(7)可知,当新状态aj对应的目标函数值σ2小于原状态ai对应的目标函数值σ2时:以概率1选取新状态的aj值作为“重要状态”;当新状态aj对应的目标函数值σ2大于原状态ai对应的目标函数值σ2时:以一定的概率确定新状态的aj值是否被接受,用随机方法产生[0,1]区间的随机数ε,若pt>ε, 则接受新状态aj,否则舍去。
同时,原状态ai向新状态aj的转移概率与当前温度tk有关,高温下(即tk值较大)可接受与当前状态能差较大的新状态作为重要状态,在低温下(即tk值较小)只能接受与当前状态能差较小的新状态作为重要状态,在tk值趋于0时就不能接受任意ai与aj对应的目标函数值f(aj)>f(ai)的新状态了。这种性质一方面保证了 搜索的全 局性,另一方面 保证了搜 索的收敛性。
2.2.3状态接受函数
对状态接受函数要求接受目标函数下降的候选解的概率要大,并且随着温度的下降概率越来越大,当退火温度接近零时概率接 近于1,即只能接 受目标函 数下降的 候选解。采用min{1,exp(-Δf/tk)}作为状态接受函数,其中 Δf=f(aj)f(ai),tk为第k次迭代的温度。
2.2.4退温函数
初始温度t0越高,获得高质量解的概率则越大,从而保证最终的优良收敛性。均匀抽样一组状态,以该状态目标函数的方差作为初始温度。
退温函数用于确定外循环的温度变更,形式如下:
式中:0≤α≤1,取0.8;tk,tk+1为第k,k+1次迭代的温度,k为外循环迭代次数编号。
3算例及分析
现以西安市铸铁管综合造价以及文献[5-8]中数据资料用模拟退火算法进行计算分析,并将其所得结果与最小二乘法所得结果比较。为了保证搜索结果的全局最优性,暂不限制候选解ai的上下限aiL与aiU;规定内循环连续30次迭代候选解ai的目标函数σ2的均值相当稳定时停止迭代;算法在每 个tk下搜索到的最优解值在连续10次迭代保持不变时,停止外循环迭代。在计算机上运行得到优化结果见表2所示。
对于不同算例的给水铸铁管原始数据(C′i,Di),由表2的算例1~5可见采用模拟退火算法能够获得更低的目标函数值 σ2,较最小二乘法能达到更优的拟合数据效果。图3为算例3最小二乘法的拟合曲线及残差图,代入参数得拟合公式:
其残差范数为77.518,方差σ2为500.73。
图4为算例3模拟退火算法的拟合曲线及残差图,代入参数得拟合公式:
C =-227.39 D3+2 010.95 D2+1 365.88 D+40.04 (10) 其残差范数为58.752,方差σ2为287.64。
图5为算例3的模拟退火算法进化过程曲线。模拟退火算法为非导数优化方法,通过残差 范数、方差σ2的比较可 见, 模拟退火算法对给水管线造价公式参数优化有较理想结果。
4结论
(1)给水管线造价公式拟合并不是次数越高越好,其拟合函数在次数n=2处存在一“畸变点”,且选择给水管线造价公式的多项式拟合次数为3次时可以提高公式的拟合精度,同时避免Runge现象。
(2)模拟退火算法优化造价公式参数无需求导及复杂的公式推导,只利用目标函数的信息并且可同时优化多个参数,优化效果良好。
(3)通过理论分析和算例表明:以三次多项式作为给水管线造价公式形式,利用模拟退火算法的随机全局搜索优势可以求解给水管线 造价公式,较最小二 乘法表现 出良好的 优化效果。
摘要：给水管线造价公式的精确性对工程经济分析与给水管网优化的科学性和经济性有重大影响。通过五个地区的铸铁管综合单价数据,采用最小二乘法对各组数据进行多项式一至十次的拟合,确定了给水管线造价公式的最佳拟合次数为三次;进一步采用模拟退火算法对拟合的多项式参数进行优化计算,求解给水管线造价公式。结果表明:凭借模拟退火算法随机全局搜索模式以及不受函数性质影响的优势,能够克服传统算法难以求解多阶导数的困难,提高公式拟合精度。
模拟退火优化算法 篇6
钎焊炉是机械、冶金等行业零部件热处理加工中的重要设备,热处理设备能耗巨大[1,2]。对工业生产过程调度优化可降低能耗,提高生产效率,所采用的调度优化算法也获得了广泛的研究[3~5]。目前对钎焊炉的研究主要集中在炉内温度控制问题,而针对钎焊炉生产调度优化问题的研究没有涉及到。钎焊炉的生产调度水平影响着其生产加工的质量、产量和生产过程的能耗。钎焊炉生产过程能耗主要包括所耗电能及氮气量。
近年,智能搜索算法在解决调度优化问题成效显著[6],主要有蚁群算法、遗传算法、模拟退火算法、粒子群算法等等。这些算法在调度优化问题求解中都有其各自优缺点。粒子群算法有概念简单、容易实现,快速收敛的优点,但其容易陷入局部最优,使得精度降低[7]。为弥补这一缺点,学者们进行了广泛的研究,其中,将粒子群优化算法(Parti-cle Swarm Optimization,PSO)与具有跳出局部最优能力的模拟退火算法(simulated annealing,SA)相结合,提出模拟退火粒子群算法(SAPSO)改进系统性能,取得了较好的应用[8,9]。论文在借鉴前人研究成果基础上研究SAPSO在钎焊炉调度优化的具体应用,以达到良好的优化效果。论文在考虑降低钎焊炉生产能耗和提高生产效率下,建立了钎焊炉调度优化数学模型,并结合粒子群算法和模拟退火算法的优点,设计了求解模型的算法。
1 过程描述及建模
1.1 生产过程描述
在一般企业生产中,由于钎焊炉开炉温升阶段耗能大,周期长,所以钎焊炉常采取订单定期计划开炉,多品种分批次批量统一加工生产等方式,以保证企业利益最大化。钎焊炉生产工艺流程如图1所示,待加工的工件摆放至钎焊炉传送机带后,进入喷淋钎焊剂区对工件喷淋焊剂液,然后在空气吹落区吹落工件上多余的多钎焊剂,通过干燥区烘干钎焊剂和工件表面水分后再进入加热区[10]。工件在加热区要通过多个不同温度环境的加热段进行加热焊接。工件从加热区出来,最后进入冷却区进行水冷、风冷区进行冷却后取下,完成加工。由于企业常按订单定期计划开炉进行生产,在生产计划安排中,企业按订单所要求的加工产品的种类进行分类,将相同或相近的产品作为一类,统一加工。图中D1,D2,D3分别代表三个不同的工件类别。
从图1可知,每个加工工件都要经历5个加工单元,每一个加工单元又对应不同的加工设备。钎焊炉调度问题优化目标就是在确定的加工工件类别的基础上,合理设计不同类别工件的加工顺序使其在不同加工设备上的驻留时间最小,从而缩短全部产品的加工时间,降低能耗,提高生产效率。
钎焊炉调度过程,需要考虑以下七个约束条件1)待加工工件各类有i种,且都需要经历5个连续生产单元;2)第i类工件第j个工件在第m个生产单元中加工时开始加工的时间为Bijm,加工完成的时间为Eijm;3)工件加工最小时间,根据其种类不同都有其规定的加工时间及加工温度。每一类工件在每个加工单元驻留时间需要达到其在该单元满足加工工艺要求的最小驻留时间(该时间为已知),加工温度满足加工工艺要求,且每一类加工工件加工最小时间相同;4)每类工件在各个加工单元中按先进先出的顺序执行,只有当前一类加工工件离开加工单元时,新的工件才能进入;5)不考虑钎焊炉停机等待情况;6)每一个加工单元,同一时刻只能加工同一类工件;7)在加工初始时刻,任意一类工件都有可能被选择加工。
1.2 钎焊炉调度的数学模型
根据1.1节描述,可建立钎焊炉调度问题的数学模型,模型中主要的参数定义如下:
i:待加工工件类别编号,i=1,2,3,…;
Di:第i类待加工工件集合,设不同类别加工工件集合交集为空;
j:Di中待加工工件的编号,j=1,2,3,…,;
m:钎焊炉加工单元编号,m=1,2,3,4,5;
Hm:第m号加工单元可同时加工的工件数量;
Bijm:第i类第j个工件进入第m个加工单元的起始时间;
Eijm:第i类第j个工件加工完毕后离开第m个加工单元的时间;
STim:第i类工件在第m个加工单元中满足加工工艺需要的最小加工时间;
Tijm:第i类第j个工件在第m个加工单元驻留时间;
Φim:第i类工件在第m个加工单元中加工状态,为1表示在加工,为0表示不在加工;
δijm:第i类工件第j个工件在第m个加工单元中加工状态,为1表示在加工,为0表示不在加工;
基于上述定义,调度模型如下[5]:
以上模型中,目标函数(1)表所示有待加工工件加工时间最小化;约束条件(2)表示每一次中能选择同一类加工工件进行加工;约束(3)表示每一件加工工件都可被选择到每个加工单元加工且只能选择一次;约束(4)表示每一个加工工件在某个加工单元的驻留时间不能小于额定最小加工时间;约束(5)只有当前加工工件离开加工单元时,新的工件才能进入。
2 求解钎焊炉调度的SAPSO算法
PSO算法是一种模拟鸟群觅食行为的群体智能优化计算技术,是一种基于迭代的并行优化搜索工具[11]。在PSO算法中,设置一群“粒子”并将每个粒子看作是优化问题的一个可行解。被优化的函数确定每个“粒子”的适应度值,以此评价粒子的好坏。“粒子”根据自己的速度和位置变量计算其在可行解空间中运动的方向和距离;粒子将跟踪自身迄今为至找到的最优解和整个种群迄今为止至找到的最优解更新自己的位置与速度;通过多次迭代运算找到最终最优解。粒子i在第t次迭代的状态属性可由其位置与速度变量表示。位置变量表示为:和分别为搜索空间的下限及上限。速度变量表示为:和分别为粒子在可行解空间运动时速度的最小值与最大值。算法中粒子的速度和位置更新公式分别为
其中ω为惯性权重,合适的惯性权重可平衡全局搜索和局部搜索能力,实现在更少迭代次数下提高寻优性能,目前常采用线性策略、非线性策略两种ω调整策略;c1和c2为学习因子,它反映了粒子间信息交流强度,通过取c1=c2∈[1,2,5];r1和r2为0到1之间均匀分布的随机数;Pid为个体最优位置;Pgd为全局最优值。
将模拟退火算法应用于PSO中粒子的速度和位置更新过程。PSO每次迭代中的适应度值根据模拟退火算法中的Metropolis准则按一定概率允许接收非优化解,使算法从局部极值区域中跳出,最终收敛于全局最优解,按下以步聚实现SAPSO算法,搜索最优解[12]:
1)参数初始化,包括粒子数m,惯性权重ω,迭代次数t,学习因子c1和c2,搜索空间的下限及上限和,粒子在可行解空间运动时速度的最小值与最大值、和,退火起至温度T和T0,退火速度α,随机设置粒子的位置初始值xi(t)和速度初始值Vi(t),个体最优值pid和全局最优值pgd;
2)根据被优化的函数及其约束条件,计算每个粒子的适应度值f(xit),并分别与个体最优值和全局最优值比较,选择更优值,以对pid和pgd进行更新;
3)根据公式(6)和公式(7)以及的值对粒子的位置、速度进行更新;
4)重新计算粒子更新后的适应度值f(xit+1);
5)计算粒子更新前后两个适应度值之差,在,ε∈[0,1]两种情况中,接收更新后的粒子位置和速度值,否则拒绝。在接收新值后,更新终止温度T值,T=KT,否则不更新T值,返回步骤2),直至迭代次数结束。
3 实验与结果分析
3.1 粒子编码与适应度函数
SAPSO应用于钎焊炉调度,首先要建立位置矢量与调度方案之间的映射,即寻找一种表达方式,使粒子与解对应。考虑到钎焊炉加工过程是流水作业,同一加工单元只加工同类别的工件,且待加工工件数量,加工单元最大加工数量和最小加工时间已知。对粒子采用矩阵编码[13],如下所示:
矩阵A是所有待加工工件对应5个加工单元的编码。矩阵中每一个元素值aij表示第i个工件在第j个加工单元中加工的顺序号,为一整数。A矩阵每一行为某一类中某个工件在各加工单元加工顺序,每一列对应着一个加工单元。由于钎焊炉各加工单元是流水线作业,故矩阵A中每一列的数值就代表所有工件加工的顺序,且对于同一行,各列的值相等。解码时,提取矩阵A中的任何一列的数值,其值表示元件加工顺序。在搜索矩阵A最优值时,从第二个生产单元开始,必须考虑工件在前后两个个生产单元的最小加工时间差,将该时间差与工件加工顺序相结合。由于各工件在某加工单元标准加工时间确定,所有待加工工件在各加工单元的标准加工时间表示为:
其中,STim表示第i个加工工件在第m个加工单元上的标准加工时间。则所有待加工工件在加工过程中,相邻两个加工单元加工时间差总和可表示为:
调度优化则可转换成求U的最小极值。对于调度数学模型中的约束项,可在目标函数中增加一项可以映射约束条件的惩罚像,构成一个无约束的广义目标函数。因此论文中钎焊炉调度优化的适应度函数即转换成是一种对B矩阵排序的问题。
3.2 实验结果
将论文中的算法应用于钎焊炉调度优化。算法中主要参数进行适当设置:最大迭代次数为800,群体粒子数为50;学习因子C1和C2取1.8,惯性权重ω∈[0.9,0.4],
模拟退火中退火起至温度T和T0分别取8000和0.03,退火速度α取0.9。采用某企业钎焊炉加工工件数据进行仿真实验,针对不同批次数据分别按标准PSO算法和SAPSO算法仿真,并与无调度优化前加工时间进行对比,结果如表1所示。
表1结果表明SAPSO算法达到优化目的。当工件类别量多,加工时间较长时,SAPSO算法比标准PSO算法效果更好。
4 结论
1)将模拟退火粒子群算法应用于钎焊炉生产调度。该混合算法在PSO算法中应用模拟退火机制,提高搜索过程中跳出局部极值的能力。
2)研究SAPSO算法在钎焊炉生产调度中的实际问题,给出粒子编码,目标函数及约束条件以及SAPSO具体实现步骤。
3)通过数值仿真实验验证论文中SAPSO算法的可行性和有效性,为工业热处理设置生产过程调度优化提供一种有效的方法。
摘要：针对工业热处理生产中的钎焊炉调度问题,考虑到钎焊炉的能耗和生产效率,以工件加工时间最小化为目标,建立了钎焊炉调度问题的数学模型。结合粒子群算法快速收敛和模拟退火算法能从局部极值区域跳出等的优点,设计了求解模型的模拟退火粒子群算法。数值仿真实验证明了所提模型及算法的可行性和有效性。
模拟退火优化算法 篇7
模拟退火算法 (Simulated Annealing, 简称SA) 是一种启发式算法, 与一般局部搜索算法不同, 它将局部搜索算法扩展为全局搜索算法。模拟退火算法是源自于对热力学中退火过程的模拟, 即在某一给定的初始温度下, 通过缓慢地下降温度参数, 使算法能够在多项式时间内给出一个近似的最优解。它以一定的概率来选择邻域中目标值相对比较小的状态, 是一种理论上的全局最优算法。本文在充分考虑配送车辆配送时间不确定性与客户时间窗前提下, 探究基于模拟退火算法优化物流配送路径问题。
1 VRPTW数学模型
设物流中心有k台配送车辆, 需要向L个客户送货。为了安排路线, 须预先估计所需要的车辆数。一般情况下, 当问题的约束条件越多, 组织线路就越难, 一辆车可以完成的满足所有约束的任务就越少, 一辆车实际所能容纳的任务量就越小, 但其所需要的车辆数可能要多。
本文中有关符号的定义:
Qk:车辆k的载重量k=1, 2, …, k;
qi:客户i的需求量i=1, 2, …, L;
dij:客户i到j的运输距离i, j=1, 2, …, L;
d0j:物流中心到各客户的距离j=1, 2, …, L;
si:车辆到达客户i的时刻;
Tij:配送车辆从客户i行驶到客户j的旅行时间;
ti:配送车辆在客户点i处的服务时间;
nk:第k辆车配送的客户数 (nk=0表示未使用第k台车辆) ;
ai:客户可以接受服务的服务延误时间。
要求货物在时间bi前送到, 在客户i的服务时间为0 (即不考虑停留时间) ;集合Rk表示第k条路径, 其中的元素rkj表示客户rkj在路径k中的顺序为j (不包括物流中心) , 令rk0=0表示物流中心, s0=0表示配送车辆从物流中心出发的时刻为0。
为了使线路安排具有一定的弹性, 用 (1) 式来确定所需要的车辆数
式中:[]为取整;为参数, 0<<1, 是对装车 (或卸车) 的复杂性程度及约束条件多少的估计, 一般来讲, 装 (卸) 车越复杂, 约束条件越多, 值就越小, 即一辆车所能容纳的货物量就越少, 在实际中的大小是可以调整的, 在本文中取0.85;Q为车辆的载重量, 该式由C++程序实现。
取目标函数为配送总里程最短, 针对单边硬时间窗车辆路径问题建立如下数学模型
约束条件
上述模型中, (2) 为目标函数, 即要求配送总里程最短; (3) 为保证每条路径上各客户的货物需求量之和不超过该路径上配送车辆的载重量; (4) 为保证每条路径上的客户数不超过总客户数; (5) 为保证每个客户都可以得到配送服务; (6) 表明每条路径的客户组成; (7) 限制了每个客户仅能有一台配送车辆送货; (8) 当第k辆车服务的客户数≥1时, 表示该辆车参加了配送, 则取φ (nk) =1;当第k辆车服务的客户数<1时, 表示未该辆车未参加配送, 因此取φ (nk) =0; (9) 表示从前一配送点到下一配送点所用的时间; (10) 保证客户的货物在其指定的时间内送到。
2 模拟退火算法
一个优化问题可以描述为
式中:S为一个离散有限状态空间, i为一种状态。
针对这样一个优化问题, SA算法的算法步骤描述如下:
第1步:初始化, 任意选初始解i∈S, 给定初始温度T0和终止温度Tf, 令迭代指标k=0, Tk=T0。
第2步:随机产生一个邻域解j∈N (i) (N (i) 表示i的邻域) , 计算目标值增量Δf=f (j) -f (i) 。
第3步:若Δf<0, 令i=j转第4步;否则产生ξ=U (0, 1) , 若, 则令i=j。
第4步:若达到热平衡 (即内循环的次数大于n (Tk) ) 转第5步;否则转第2步。
第5步:降低温度Tk, k=k+1, 若Tk<Tf, 则算法停止, 否则转第2步。
3 用模拟退火算法研究车辆路径问题
针对单边硬时间窗的物流配送路径问题进行设计模拟退火算法。
3.1 初始解产生
Step1:k=1, 最优解集合为数组opt, 尚未分配的客户编码存储在数组Nd中。
Step2:当前车辆编号rk=k, 当前所在配送点np=0, 已载货重Wrk=0, 已在途时间srk=0, 已行驶距离Drk=0, 解optrk=。
Step3:将np放入数组opt[rk], 从数组Nd存储的客户中随机挑选客户nr, 作为车辆rk的下次预备配送客户。
Step4:如果Wrk+qnr>Qrk, 则转Step8。
Step5:计算np与nr之间的距离dpr, 依据dpr与车辆行驶速度计算得到np与nr之间的车辆旅行时间Tpr, 令
Step6:比较srk与客户nr所要求的最迟送达时间tnr, 若srk>tnr, 转Step8;
Step7:令Drk=Drk+dpr, np=nr, 从数组Nd中删除客户nr, 若Nd=, 将np放入数组opt[rk], 给数组opt[rk]中存入0, Drk=Drk+dp0, 转Step9;否则将数组Nd中的数据前移, 并转Step3。
S tep8:给数组opt[rk]中存入0, Drk=Drk+dp0, 令k=k+1, 转Step2。
Step9:得到随机解, 输出初始解opt, , 输出总里程D。
3.2 领域构造
用产生初始解的算法产生随机解, 这样就得到一个新状态, 进行比较决定是否进行一次邻域移动。
Step1:最优解集合为opt, nl=0, Δf=0, NL。
Step2:运用产生初始解的算法, 产生随机解, 将随机解赋值给rans, 计算总里程。
Step3:Δf=D′-D, 若Δf≤0, 则opt复制rans的解, D=D′, nl=nl+1;否则进入Step4。
Step4:若exp (-Δf/t) >r (r为产生的随机数) , 则opt复制rans的解, D=D′, nl=nl+1;否则, nl=nl+1。
Step5:如果nl<NL, 转Step2;否则, 结束循环。
4 应用案例
案例具体描述为:配送中心有25辆车, 每辆车容量为50, 车速为每单位时间行驶1, 每辆车在客户点的服务时间10, 客户分布点如图1所示, 具体信息如表1所示。
模拟退火算法参数设置如下:初始温度t=8 000, 终止温度t′=6 000, 退火速度=0.95, 内循环次数NL=200。用C++程序产生初始解以及满意解。按表1中客户点数据用MATLAB绘制客户点分;产生初始解之后, 用MATLAB绘制初始解路线, 如图2所示;得到满意解之后, 用MATLAB绘制满意解的路线, 如图3所示。
5 结束语
通过对车辆路径问题各要素的研究, 建立起了单边硬时间窗的数学模型。针对其数学模型进行设计模拟退火算法, 利用C++程序来实现基于仿真随机解的模拟退火算法, 求得优化结果。结合算例将设计的算法进行运用, 得到了车辆行驶路线的初始解和优化解, 并利用MATLAB绘制出了其对应的路线图。由于模拟退火算法的收敛性不好, 因此, 本文所求的解并不是最优解, 而是一个比较合理的趋于最优解的满意解。
摘要：模拟退火算法是解决NP完全组合优化问题的有效近似算法, 将该算法应用于路径优化问题中, 利用该算法对类似货郎担问题的路径问题进行求解。针对城市道路行走不同的目标条件 (路径最短、时间最短) 进行优化, 选择最佳行走路径, 并用该算法优化得到的计算结果, 结果表明该算法在解类似货郎担交通路径方面问题时具有较高的精确性。因而, 该算法在解决城市道路交通问题方面具有一定的实用价值。
关键词：模拟退火算法,NP,车辆路径安排,物流配送
参考文献
[1]贺国先.基于仿真随机解的模拟退火算法在单物流中心配送VRP中的应用[J].铁道报, 2009, 31 (4) :92-97.
[2]宾松, 符卓.求解带软时间窗的车辆路径问题的改进遗传算法[J].系统工程, 2003, 21 (6) :12-15.
[3]王鑫.物流配送中车辆优化调度问题的研究与实践[D].沈阳:沈阳航空工业学院, 2006.
[4]李军, 谢秉磊, 郭耀煌.非满载车辆调度问题的遗传算法[J].系统工程理论与实践, 2000, 20 (3) :235-239.
[5]董雪.基于模拟退火算法的供应链管理分析[J].交通科技与经济, 2012, 14 (6) :53-55.
[6]吴隽.基于改进蚁群算法的物流配送路径优化研究[D].武汉:武汉理工大学, 2009.
[7]胡大伟, 朱志强, 胡勇.车辆路径问题的模拟退火算法[J].中国公路学报, 2006, 19 (4) :123-126.
模拟退火优化算法 篇8
在眼镜架的制造过程中,利用典型的电感线圈和电容的谐振原理,采用高频感应加热的方法对钛合金进行焊接,要求加热速度快,焊接效率高。但高频焊接过程中,由于高频线圈的高度非线性、多变量耦合作用,焊接工件的工艺参数与焊接质量之间的数学关系复杂,依靠传统的数学建模和分析方法无法达到预期的控制效果,所以需要在线快速自动寻找最佳的感应加热的频率,使感应加热的功率达到最大,效率最高。
模拟退火遗传算法遵循自然界优胜劣汰的原则,由于其直接对结构对象进行操作,不存在求导和函数连续性的限定,又具有鲁棒性强、随机性、全局性及适于并行处理的特点。因此利用模拟退火遗传算法进行高频焊接过程控制的优化设计,可以得到高频焊接过程中振荡工作频率的选择,并向感应线圈输出[1]。
本研究主要探讨基于模拟退火遗传算法的高频焊接输出功率优化控制技术。
1模拟退火遗传算法
1.1遗传算法原理
遗传算法以编码空间代替问题的参数空间,以适应度函数为评价依据,以编码群体为进化基础,以对群体中个体位串的遗传操作实现选择和遗传机制,建立起一个迭代过程。在这一过程中,通过随机重组编码位串中的重要基因,使新一代的群体优于老一代的群体,群体个体不断进化,逐渐接近最优解,最终实现求解问题的目的。
1.2模拟退火算法原理
基于粒子在自由状态下有向能量较低状态转移的趋势,而热运动又妨碍它准确落入最低能量状态这一物理现象,Metropolis采用下述方法产生固体的状态序列[2]:先给定以粒子相对位置表征的初始状态i作为固体的当前位置,该状态的能量是Ei;然后用摄动装置使随机选取的某个粒子的位移随机地产生一个微小变化,得到一个新状态j,新状态的能量是Ej。如果Ei<Ej,则该新状态作为“重要”状态;如果Ei>Ej,则考虑到热运动的影响,该状态是否可作为“重要”状态,要依据固体处于该状态的几率来判断。而固体处于状态i和j的几率的比值等于相应的Boltzmann因子的比值P,即:
其中,P是一个小于1的数。
将能量E模拟为目标函数值f,温度T演化成控制参数t,即得到解组合优化问题的模拟退火算法:由初始解i和控制参数初值t开始,对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代,并逐步衰减t值,算法终止时的当前解即为所得近似最优解,这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。
1.3模拟退火遗传算法
在遗传算法的起始,一个包含许多染色体的初始群体随机形成。接着遗传算法使用3个基本操作,即:选择、交叉、变异,自适应地生成一代新的群体。然而,在经遗传算法搜索形成的新一代群体中,新染色体的邻域中都有大量的适应度或高或低的染色体。如果在下一代产生之前,所有新染色体由其邻近染色体取代,则可以实现快速收敛的精细调整。因此,可以对每个新的染色体使用模拟退火来搜索更高适应度的邻近染色体。例如,当模拟退火发现稍微随机改变现存染色体的值而形成一个新的有更高适应度的染色体时,就用新的染色体来取代现有的染色体。当然,邻域中适应度稍差的新染色体仍然保持等待退火。
1.4模拟退火遗传算法实现
模拟退火遗传算法与控制参数初始值无关,算法求得的解与初始解状态(算法迭代的起点)无关;模拟退火遗传算法具有渐近收敛性,已在理论上被证明是一种以概率l收敛于全局最优解的全局优化算法;模拟退火遗传算法具有并行性,其新解的产生和实现可分为以下几个步骤[3,4]:
(1) 给定群体规模M,k=0;控制参数初始值tk=t0,群体pop(k);
(2) 若满足停止规则(利用率为95%以上),停止计算;否则,在群体pop(k)中每一个染色体i∈pop(k)的领域中随机选一状态i∈N(t),按模拟退火中的接受概率:
决定接受或拒绝j,其中f(i)为状态i的目标值;这一阶段共需M次迭代选出新群体newpop1(k+1);
(3) 在newpop(k+1)中计算适应度函数:
其中,fmin是newpop1(k+1)中的最小值;由适应度函数决定的概率分布从newpop1(k+1)中随机选M个染色体形成种群newpop2(k+1);
(4) 按遗传算法的常规方法进行交配得到crosspop(k+1);再变异得到mutpop(k+1);
(5) tk+1=d(tk),k=k+1,pop(k)=mutpop(k),返回到(2)。
基于模拟退火遗传算法的程序流程图,如图1所示。
从程序流程图中不难看出,第1步主要是设置控制参数初始值,生成初始群体,确定群体规模等初始化操作;第2步则在遗传算法中加入模拟退火的随机接受邻域解的接受转移概率;第3步更是以遗传算法的指数接受概率来求解优劣的不同得到不同的生存概率,从而缩小群体规模,最终实现优胜劣汰;第4步采用通常的遗传变异方法得到下一代种群。用
2高频焊接原理及工艺介绍
高频焊接所需功率取决于感应线圈的材质、磁化强度、LC振荡器的传递能量方式。在实际生产中用振荡器输入功率来度量输出加热功率[5,6]。当输出的功率较小时,就不足以达到焊接温度而产生未焊透。因此应选择适当的高频振荡频率来产生最大的输出功率。国内眼镜架的钛合金焊接采用高频加热设备,其主要功率一般为1 kW～15 kW。
输出功率决定设备焊接的能力,而输出频率则决定集肤深度的大小。研究表明,电流频率越高,集肤效应和邻近效应就越显著,焊接所需的功率就越小。但频率过高,会使焊接装置电源的指标不合理,高频感应线圈制作时漏感增加,同时会使高频输出的大功率管过热或击穿,而且焊接时会有不稳定现象。其主要振荡频率为500 kHz～1.2 MHz。
高频感应线圈是焊接设备中的主要部件,由外部振荡器提供给线圈一个振荡频率,使高频线圈工作在LC谐振点上。
由于并联电感调谐匹配,其阻抗变换作用没有变化,同时缺乏滤波作用,而采用串联电感匹配可以使有功电阻降低,并且兼有调谐和滤波作用。串联匹配电感等效电路,如图2所示,其中,C0为静态电容,Rm、Lm、Cm为等效动态电阻、动态电感和动态电容。
负载的等效输入阻抗为:
其中,串联调谐角频率为
由此可得所需串联匹配的电感大小为:
因此,其负载等效输入阻抗为:
从理论上说,当f0在LC谐振点上时,电感两端会产生无穷大的电压,但电路中有损耗及漏感等,输出电压与电流就有一个最大值,此时输出功率将达到最大值即期望值。
3实验方法与数据
由于随着工件规格的不同,感应线圈形状人为的改变,都会引起电感量L的变化,谐振频率f也会产生变化,如果此时振荡频率不在谐振点上,输出功率就会急剧下降。
假设正常工作时谐振频率为f0(如图3所示),输出功率将达到最大值P0。当工作状态发生变化时,高频感应线圈的谐振点也随之变化到f1点,而振荡频率不变,其输出功率就下降到P1点,振荡频率调整到f1后,输出就能继续保持最大值P0。
根据以上的分析,采用单片机C2051和DAC0832电压输出转换模块及锁相环CD4046调整振荡频率f0,就可以实现频率跟踪。高频焊接机的电路原理,如图4所示。
由于感应线圈的输出是高频低压电流,无法直接测试输出功率。笔者采用了测量输入交流总功率的方法,因为输入总功率中除了内部电子振荡电路和单片机的供电外(消耗很小能量),大部分输入功率都转换成输出,所以能间接地测量出输出功率的大小。在实际工作中,焊接的工件不同,会影响到高频感应线圈的电感量L值产生变化,LC谐振点就会变化。因此研究的目的就是要求当负载的等效输入阻抗Z发生变化时,单片机通过功率输出取样,快速调整锁相环CD4046的振荡频率,使输出功率P达到最大,即P=F(f0)。
本研究对某高频焊接电源进行了有模拟退火遗传算法和无模拟退火遗传算法的测试,其输出的功率,如表1所示。
由表1可知,当工件改变时,如果频率不变化(始终为f0),则输出功率将大幅度下降,必须由单片机按照模拟退火遗传算法自动快速调整到新的f值,才能保持输出的最大化。
4结束语
高频焊接过程中输出功率的控制优化问题是一个多参数的非线性优化问题,本研究采用基于模拟退火法则的遗传优化方法对该问题进行了优化计算,克服了简单遗传算法可能引起的局域解及早熟收敛的缺点,是一种自稳定性较强的全局稳定收敛算法。
参考文献
[1]周双娥,雷辉.基于改进的遗传-模拟退火的有序任务调度算法[J].微电子学与计算机,2006(10):62-64.
[2]田东平,迟洪钦.混合遗传算法与模拟退火法[J].计算机工程与应用,2006,42(22):63-65.
[3]赵艳敏,霍达,腾敏.基于改进的遗传模拟退火算法的钢框架优化设计[J].工业建筑,2006(z1):462-465.
[4]马坤,于海平,彭启山.改进的遗传模拟退火算法在TSP中的应用[J].武汉科技大学学报:自然科学版,2006,29(3):266-269.
[5]夏小荣,陈辉明,蒋大鹏.一种新型高频感应加热用驱动电路[J].电子器件,2006,29(1):142-144.
模拟退火优化算法 篇9
换热网络的优化目标是利用有限的换热单元使冷热流体得到合理的匹配,充分利用系统内部的能量让各股流体达到所需目标温度。换热网络的综合优化问题是在有约束条件下,获得目标函数的全局最优解,其本质是混合整数非线性规划问题(MINLP)。综合国内外研究,换热网络优化的研究经历了窄点技术法[1,2]、数学规划法[3,4]以及基于随机技术的启发式方法[5,6]的历程。面对大规模复杂换热网络的优化问题,因为具有较强全局搜索能力,基于随机技术的启发式方法成为众多学者研究的热点,其中具有代表性的是模拟退火算法。
Dolan[7]于1989年提出了考虑所有费用目标项的模拟退火算法,由于涉及大量试探解,计算效率低。Athier[8]在1997年提出用模拟退火算法自动得到固定热容流率和传热膜系数下最小费用的换热网络,并用非线性规划方法优选操作参数。Floquet[9]利用模拟退火算法和NLP模型来求解换热网络最优综合。方海鹏[10]构造改进的遗传模拟退火算法(IGA/SA),并将换热网络综合转化为双层规划问题。虽然退火模拟算法提高了启发式方法在换热网络优化问题中的全局搜索能力,但由于算法本身存在随机性,使得优化过程的不确定性增加,难以得到准确的局部最优解。
本文在发现换热网络的结构与性能具有连续性的基础上,预先生成一系列连续变化的换热网络结构,以结构的序号作为优化变量,利用模拟退火算法对换热网络的整型变量进行最优搜索,从而将多维整数变量的优化问题转变为一维连续变量的优化问题,很大程度上简化了整型变量优化过程的复杂性,而且有效地跳出了局部最优陷阱。
1 换热网络超结构及数学模型
1.1换热网络的综合描述
换热网络优化问题可描述为:在过程系统中,有若干股冷热流体需要加热或冷却到目标温度,就利用换热器使冷热流体进行匹配换热,回收系统内部的大部分热量,为了使流体达到工艺要求的目标温度,需要加入额外的热量或冷量(即公用工程)来加热或冷却过程流体。换热网络的设计目标是:确定热流体和冷流体的换热匹配关系及相应的换热器面积,在满足流体达到目标温度的前提下,使换热网络回收量最大,或者年综合费用最小。
1.2 换热网络的超结构
换热网络的结构模型很多,其中应用最具有代表性的结构是Grossmann分级超结构,该结构能够包含冷热流体之间所有可能的匹配情况。例如:3股热流体和3股冷流体的换热网络,其分级超结构如图1所示。所有冷、热流体之间换热的组合,记为一个级,每种换热组合需要一个换热器,则该换热网络在一个级内的换热器数目为9个。若热流体的股数为NH,冷流体的股数为NC,则换热网络的级数为NK,NK一般取max(NH,NC),换热网络最大的换热器数目为NH×NC×NK,冷热公用工程分别加在第NK级的后面和第1级的前面。
1.3 换热网络的性能函数
用年综合费E表示换热网络的性能,该费用由运行费用和设备投资费用组成。换热网络的优化以费用E为目标函数目标同步优化,寻求费用最低的换热网络。其目标函数如下:
undefined
式中:NH—热流体流股数;
NC—冷流体流股数;
N—换热器的数目;
CCU—冷却器公用工程费用系数;
QCU,i—第i股热流体与冷公用工程换热量;
CHU—加热器公用工程费用系数;
QHU,j—第j股冷流体与热公用工程换热量;
C0—换热器固定投资费用;
C0′—换热器面积费用系数;
Ak—换热器面积;
β—面积费用指数;
C1—冷却器固定投资费用;
C1′—冷却器面积费用系数;
ACU,i—冷却器的换热面积;
C2—加热器固定投资费用;
C2′—加热器面积费用系数;
AHU,j—加热器的换热面积。
2 换热网络的结构与性能的连续性
连续性原理是德国自然科学家和哲学家莱布尼兹(G.W.Leibniz)在继承亚里斯多德的思想而提出来的,原理指出:“自然界中的一切事物都是按阶段发展的,没有任何跳跃”。该原理在众多的科学领域得到了广泛的应用,例如微积分理论、生物进化理论、量子性与连续性相统一的宇宙观等,所以在换热网络的优化问题中,也应该存在类似的连续性原理。可以认为:任意对换相邻两个换热器的位置,其结构的变化是微小的。对于某个初始结构,通过排列组合的方式,不断地对换相邻换热器的位置,直至完成换热网络结构的全排列,得到的一系列结构是具有连续性的。本文采用实际算例检验这些结构所对应的换热网络的性能(综合费用)是否依然具有连续性。
以文献[11]中的算例作为试验算例,该换热网络由3股冷流体及3股热流体组成,冷热流体参数如表1所示,换热器面积的费用为171.4×A美元/m2,热公用工程的费用为80美元/kW,冷公用工程的费用为20美元/kW,为了单独讨论换热网络结构与性能之间的关系,以控制变量法固定所有换热器的面积,以1级的超结构模型作为初始结构,生成一系列连续变化的结构,计算对应的综合费用,结果如图2所示。
结果表明:换热网络的结构进行一系列连续的变化时,其性能的变化也是连续的。
3 基于连续性的模拟退火算法
固体退火是一个获取固体低能晶格状态的热物理过程。首先将固体加热,使其熔化为完全无序的液态,此时粒子处于自由运动状态,然后逐渐降温,粒子运动渐趋有序,当温度降低到结晶温度,粒子运动变为围绕晶格点的微小振动,液体凝固成固态晶体。退火过程要求降温过程足够缓慢,使每个温度下所有粒子随机排列达到热平衡,最终达到固体的基态,即系统能量最小状态。1983年,Kirkpatrick注意到固体退火过程与求解优化问题的类似性,将Metropolis准则引入优化中,提出了模拟退火算法。求解优化问题的模拟退火算法与固体退火过程的模拟比较如表2所示。
基于换热网络结构与性能的连续性,在固定换热器数目的情况下,用全排列的方式,预先生成一系列连续变化的结构,这些结构对应的综合费用也必然是连续的,两者就形成一条换热网络综合费用与结构的一维曲线,将多维的整形变量优化问题转化为一维的连续变量优化问题。利用退火模拟算法优化换热网络时,以这些连续性结构的序号作为优化变量,随机搜索到一个初始点,以综合费用下降的方向作为整型变量的搜索方向,进行换热网络整型变量的最优搜索,提高退火模拟算法的准确性与可靠性。
基于换热网络连续性的退火算法,在换热网络优化问题中的具体步骤如下:
1)给定一个可行的换热网络整型变量的初始解X0及其综合费用F(X0),确定控制参数初始值tk、衰减函数、停止准则和Mapkob链长度Lk。
2)参数t=tk时,按照如下过程作Lk次试探搜索:
a.根据换热网络结构与性能的连续性,以当前整型变量的解Xk为原点,搜索相邻的整型变量的解Xk′,从而在领域内得到一个新的试探点。
b.产生一个在[0,1]上均匀分布的随机数ξ,计算出当前整型变量的解和控制参数下与Metropolis接受准则相对应的转移概率P:
undefined
如果P≤ξ,则接受新解Xk′,否则当前解不变。
c.试探搜索次数小于Lk次,返回步骤1,否则进入步骤3。
3)如果迭代终止条件满足,则算法结束,当前解为最终解,否则进入步骤4。
4)根据衰减函数产生新的控制参数tk+1及链长度Lk+1,转入步骤2进入下一点的寻优。
4 算例
本文优化算例取自文献[12],该换热网络由15股流体组成,8股热流和7股冷流体。流股初始参数如表3所示,换热设备费用公式为8000+500A0.75美元/a,冷、热公用工程的单价分别为10美元/(kW·a),80美元/(kW·a)。
本文在换热器数目固定为9个的情况下,利用基于连续性的模拟退火算法,控制参数的初始值取t0=8,衰减函数取tk+1=0.9tk,链长度Lx=12,进行换热网络整型变量的最优搜索,最终的费用为1581165美元,结果如图3和表4所示。
5 结论
利用基于连续性的模拟退火算法处理换热网络整型变量的优化问题,得到以下结论:
1)在换热网络中,存在结构与性能的连续性。
2)在换热器数目固定的情况下,利用换热网络结构与性能的连续性,能将多维整数变量的优化问题转变为一维连续变量的优化问题,从而很大程度上简化了整型变量优化过程的复杂性,保证了退火模拟算法的可靠性,最终得到了较好的结果。
摘要：换热网络优化是典型的混合整数非线性问题,其整型变量的组合情况(换热网络的结构)对于其优化的走向以及局部最优解的质量具有至关重要的作用。指出换热网络的结构与性能存在连续性,并由此提出以连续性指导整型变量最优搜索的换热网络模拟退火算法,对换热网络的结构进行最优搜索,降低换热网络的综合费用。通过对实际算例的优化,将换热网络的综合费用由1599229美元降至1581165美元。结果表明:换热网络结构与性能的连续性能指导整型变量的优化走向,保证模拟退火算法在换热网络优化过程中的可靠性。
关键词：换热网络,结构性能连续性,模拟退火算法
参考文献
[1]Linnhoff B,Hindmarsh E.The pinch design method forheat exchanger network[J].Chemical Engineering Sci-ence,1983,38(5):745-764.
[2]刘智勇,李志伟,霍磊夹.点理论及其在换热网络中的优化分析[J].节能技术,2012,30(3):273-277.
[3]Papoulias S A,Grossmann I E.A structural optimizationapproach in process synthesis-II:heat recovery networks[J].Computers&Chemical Engineering,1983,7(6):707-721.
[4]涂惟民,崔国民,胡向柏,等.以综合费用最小为目标的无分流换热网络全局优化[J].化学工程,2011,39(5):90-93.
[5]Lewin D R,Wang H,Shalev O.Generalized method forHEN synthesis using stochastic optimization-I.Generalframework and MER optimal synthesis[J].Computers&Chemical Engineering,1998,22(10):1503-1513.
[6]张勤,崔国民,关欣.基于蒙特卡罗遗传算法的换热网络优化问题[J].石油机械,2007,35(5):19-22.
[7]Yee T.F,Grossmann I E.Simultaneous OptimizationModels for Heat Integration-III:Process and Heat Ex-changer Network Optimization,Computers Chem[J].En-gng,1990,14:1185-1201.
[8]Athier G,Floquet P,Pibouleau L.A mixed method for ret-rofitting heat-exchanger networks[J].Computers&Chemical Engineering,1998,22:501-505.
[9]Floquet G.Process.Optimization by simulated annealingand NLP Procedures Application to Heat Exchanger Net-work Synthesis[J].Computers Chem.Engng,1997,21:475-480.
[10]方海鹏,王其冬,冯恩民,等.基于遗传模拟退火算法的带约束换热网络综合问题[J].大连理工大学学报,2000,40(1):24-28.
[11]V.Briones,A.C.Kokossis.a Conceptual Programming ap-proach for the optimisation of industrial heat exchangernetworks-II[J].Chemical Engineering Science,1999,54:541-561.