系统工程结课论文专业资料模板

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。系统工程结课论文姓名:刘易初班级:物流101学号:模拟退火算法摘要:本文给出一种使用模拟退火算法(SSA:SimulatedAnnealingAlgorithm)求解课表问题的方案,详细地讨论了该方案涉及的各种问题,包括目标函数和初解的确定,邻域和新解的产生方法,初始”温度”的确定和”温度”更新的方式,内循环次数及算法终止条件等等。文章的最后给出了该方案实现的一个实例和若干性能分析。关键词:时间表问题;模拟退火算法;性能分析;课表实例1.模拟退火算法(SAA)介绍模拟退火算法(SAA:SimulatedAnnealingAlgorithm)来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却。加温时,固体内部粒子随温升变为无序状,内能增大;而徐徐冷却时粒子渐趋有序,在每个温度都达到一个平衡态,最后在常温时达到基态,内能减为最小。模拟退火算法最早由Kirkpatrick等应用于组合优化领域,它是基于Mente-Carlo迭代求解策略的一种随机寻优算法,出发点是物理中固体物质的退火过程与一般组合优化问题求解过程之间的相似性。模拟退火算法从某一较高初温出发,伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解,即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法,理论上算法具有概率的全局优化性能。2.算法结构模拟退火算法(SAA:SimulatedAnnealingA1gorithm)是一种启发式的随机搜索算法,往往能在较短的时间和较大的解空间内找到最优解,对解课表这样的组合优化问题是很有效的。设S={S1,S2,…,Sm}是所有可能解的集合,f:S→R为非负目标函数,则寻找最优解即是寻找S*∈S,使得:(2.1)SAA主要包括Metropolis抽样过程和退火过程两个部分,可描述如下／*分别为初始状态和控制参数初值*／{S=;k=0;{//Metropolis抽样while(notinner-loopstopcriterion){Snew=Generate(S);if;elseif(Accept(Snew,S));}//退火过程T=update(T);K=k+1;}}这里:(1)Generate函数表示从当前解的邻城,随机产生下一解;(2)Accept函数决定接受新解作为当前解的条件,描述如下:Accept(Snew,,S){ifaccept=true;elseaccept=false;}3.SAA在求解问题中的实现上面给出的SAA只是一种抽象算法,要在求解课表问题中得以实现,还须具体解决以下问题:(1)数据结构的建立;(2)解的表示方式及目标函数的计算方法;(3)初始解的确定;(4)邻域及新解的产生方法;(5)初始”温度”的确定和”温度”的更新方式;(6)内循环次数的确定和算法的终止条件。下面将本文解决上述问题的方法作一简单介绍。由本问题的性质及其数据结构可见,其目标函数并不是一个易于计算的数学式,而需要检索大量数据,过程比较复杂。如何尽可能的减少检索数据和计算量呢?首先,考虑到每个新解都是在旧解的邻域中产生的,变化涉及的课很少,因此计算的步骤大致如下:(1)计算变换涉及的所有课在变换前对目标函数的贡献之和,从△f中减去;(2)计算变换后以上课对目标函数的贡献之和,加入△f中;(1),(2)步中都需要分别求出每个涉及到的课对目标函数的贡献,求和,再减去重叠的部分。由SAA算法的特点可知,在当前解的邻域中,接受为下一当前状态的新解相对于产生出的新解来说只是很小的一部分(特别当退火”温度”足够低时),因此以上第(1)步的计算有许多不必要的重复。为了尽可能避免这种重复,本文对第(1)步和第(2)步使用了不同的计算方法,即不对称的计算方法。确定初始解时,本文要求它仅满足硬条件(1)～(3),且要求退火过程中产生的每个解都满足此条件．其它各项要求在目标函数中都得以体现,可在退火过程中逐步优化,故无须在初始解中加以考虑。4.”初始温度”和”温度”的更新方式初始”温度”的选择方式有以下几种常见方式:(1)均匀随机抽样{Si},取此时f(Si)的方差为初始”温度”;(2)在所有可能的组合状态中,选两个状态使△f,取初始”温度”为最大值的若干倍;(3)按经验给出。本文采用第三种方式,即按经验给出。一般选取相邻解(相差一个变换的解)△f的最大值,令初始”温度”为此最大值的若干倍。在此”温度”下,多数新解都可被接受为下一当前解。总体来说,无论”温度以什么方式变化,它必须满足T→0。常见的有以下几种方式:(1),其中,一般取;(3.1)(2),(3.2)(3.3)根据退火算法的特点,可看出(2)方式更科学:在搜索初期,它能使解迅速收敛,在搜索末期,又能使退火过程逐渐稳定。本文采用了一种特殊的”温度”变化方式,即”温度”并不是单调递减的,而偶然会回升。一般情况下,”温度”以(2)中方式下降,当有迹象表明,退火算法陷入了某个局部最优时,”温度”会适当提升,增加扰动以跳出此局部最优。一般,以目标函数长时间没有改进或当前解一直不变为陷入局部最优的特征。”温度”的回升公式如下:(3.4)其中为常数,一般设为2或3。在这种”温度”更新方式下,搜索开始时”温度”急剧降低,中间”温度”呈锯齿状逐渐降低,退火过程即将结束时”温度”缓慢降低,各项参数的设置对系统性能影响较大。5.内循环次数的确定内循环次数决定Metropolis抽样是否达到稳定,有以下几种检验方式:(1)检验目标函数的均值是否稳定;(2)继续若干步目标函数值变化很小;(3)按固定步数抽样;本文采用第三种方式,内循环次数大致设定为邻域大小。若一共有k个班,每个班一周有m个课时,则内循环次数为:。这样,在每个退火”温度”下,邻域中的每个解都很有可能被搜索到。6.SAA的终止条件算法的终止条件一般有:(1)T小于某值;(2)系统的熵已达到最小;本文采用的终止条件为:T小于某值,或用户满足已搜索到的最优解,或系统已达到稳定。参考文献[1]康立山.非数值并行算法[M].北京:科学出版社,1994.[2]黄干平.解时间表问题的启发式算法[J].武汉大学学报(自然科学版),VOL.51,No.3,.[3]陈华根.吴建生等模拟退火算法机理研究[J].同济大学学报(自然科学版),V