目录
摘 要............................................................................................................................ 2 Abstract .......................................................................................................................... 4 1绪论............................................................................................................................. 8
1.1选题背景........................................................................................................... 8 1.2选题意义........................................................................................................... 9 1.3研究现状......................................................................................................... 11
1.3.1生产调度............................................................................................... 11 1.3.2生产过程的动态调度........................................................................... 14 1.3.3间歇过程的生产调度........................................................................... 14 1.3.4生产调度的柔性................................................................................... 17 1.3.5引进算法控制参数............................................................................... 18 1.3.6使用对象函数值进行搜索................................................................... 18 1.3.7隐含并行性........................................................................................... 18 1.4研究内容......................................................................................................... 20 1.5研究方法......................................................................................................... 20 2模拟退火算法理论概述........................................................................................... 22
2.1VFSA理论简述 .............................................................................................. 22
2.1.1模型扰动............................................................................................... 25 2.1.2接受概率............................................................................................... 25 2.1.3退火计划............................................................................................... 26 2.2 VFSA机理分析 ............................................................................................. 26 2.3改进的模拟退火算法..................................................................................... 30 3生产调度优化模型................................................................................................... 32
3.1生产调度模型的构建..................................................................................... 32
3.1.1生产调度模型分析............................................................................... 33 3.1.2生产调度模型约束条件....................................................................... 36 3.1.3生产调度模型成本模型....................................................................... 37 3.2生产调度模型求解方法................................................................................. 38 4优化生产调度过程实例描述................................................................................... 40
4.1问题的提出..................................................................................................... 40 4.2编码................................................................................................................. 46 4.3算法原理......................................................................................................... 47 4.4交叉................................................................................................................. 48 4.5变异与选择..................................................................................................... 48 4.6并行模拟退火遗传算法流程......................................................................... 48 4.7模拟退火算法描述......................................................................................... 49
4.7.1物理退火过程....................................................................................... 49 4.7.2 Metropolis准则 .................................................................................... 50
5优化生产调度的实现及其仿真分析....................................................................... 51
5.1确定解空间..................................................................................................... 51 5.2 目标函数的界定............................................................................................ 51
5.3挑选初始解..................................................................................................... 52 5.3新解的产生及其接受机理............................................................................. 52 5.4停止准则的补充............................................................................................. 53 5.5仿真结果及其分析......................................................................................... 54 6结论........................................................................................................................... 55 参考文献...................................................................................................................... 57
1绪论
1.1选题背景
组合优化问题所存在的范围是非常广泛的，不单单我们可以在工程项目中，甚至经济范畴中也可以看到其被运用的情况。因而，怎么样求得该问题的最优解始终是一个亟待化解的难题。至今为止，有关该课题的实际分析仍旧处于NP——完全化的状态之中，严谨地去求得这些问题的解答需要一笔可观的支出，而其形式也主要是与规模相关的指数化形态。因而，以往所采用的分枝定界法以及整数规划等偏于非常严谨特点的演算方法无法真正地实行。一般而言，启发式算法是具有可行性的方法。
大体上而言，启发式算法包括2种：其一，在展开构造性的求解过程时，其着眼点为基于需要解决的问题及其所出现的原始型数据结构；其二，对当下的解开展迭代改进的方法。就构造性方法而言，其依据为需要解决的问题自身的特点来展开规划的，因此难以推广至其他相异性的应用范围，而迭代改进算法则没有比较与其他算法相异的且比较突出的特征。该类型的演算方法从结构上看有如下的特点：起始于最初的解，由此出现了相匹配的解序列，保持该状态一直至出现让人满意的解终止。该方法的具体演算流程取决于新解的出现定则与终止迭代定则。该类演算方法的缺陷在于2点：第一，该算法通常在获得局部最优解时便结束了；第二，最终解的获得由2点决定，即初始解的确定与出现新解的定则。很多具有启迪作用的计算方法在展开迭代改进流程时，均比较倾向于时间最为迅捷且可以删减目标函数值的方略，也即贪心方略。但从实际效果来看，该类贪心演算方案通常会出现局部性最优解，而并非全局性的最优解。
为了对迭代启迪演算方法加以有效性的改进目的，通常会挑选出一些最初解，再展开同样的迭代方式来强化求得全局最优解的概率比值。同时，亦能够通过随机搜索的演算方法来进行，该方法的特征在于出现下一个新解的途径是随机化的。倘或新解的数值要小于当下解的数值，那么把新解当做暂存解。根据实验数据可知，最优解寻得的概率与最优解和总解二者的比值存在着正相关的关系，即后者数值愈高，那么前者的数值也就自然愈大。因此，如果最优解的数量比较大，那么随机搜索的计算方法的功能是让人满意的。
模拟退火算法通常具有鲜明的通用性，也是随机搜寻演算方法的一种，且凸显出更佳的渐进行为优点。它在最近几年中所出现的，该方法是一种比较近似的算法，比较适用于对大规模的组合优化问题的计算，既有明显的通用性，同时也能够取得一定的效果。和以前的类似计算方法比对后可以发现，其本身拥有一系列的长处：描述简易、运用灵便、范围广泛、运作效率好以及受到最初条件制约性并不多等。同时，并行演算也比较地适合。可见，其实用性比较地突出。
同时，模拟退火算法一般被看做局部性的搜寻算法的延展。在每次对模型加以修改时，均会随机地出现一个全新化的状态模型，再根据一定的概率值来挑选出相邻区域内能量数值最大的情况。该新型的模式能够使其变为一类全局状态下的最优演算方法，并可以通过相关的理论来加以证实与应用。模拟退火算法拥有良好的寻优功能，然而确保其顺利进行的前提是严谨的退火设计。具体而言，即最初的温度、稳健的退火速率、许多的迭代次数与相同温度环境中充分的扰动数量等。因而，有关模拟退火算法使用所产生的实效情况始终是阻碍该计算方法完全成为实用性方向的核心方面。学者Ingber着眼于该课题展开了相关的研究，即创造性地提出了特别快速的模拟退火计划，并构建与之匹配的演算方法，从而在原先的基础上强化了计算方法的效率，并在实践中获得了一定的效果。然而，从整体上看，其方法在实践过程中所取得的效率并不高，同时和约束条件的数量与相关模型的扰动情况存在着一定的关联性。因而该方法依旧对相关的计算方法产生了一定的制约性，也无法进一步地得到范围更为广泛的运用。要成功地克服该问题的关键点有3个：首先，应尽量地获取和该计算方法相关的明确信息，其目的在于具有制约性条件的数量呈现于递增的状态；第二，规约模型相应的扰动领域；第三，深度地对计算方法加以改进，从而强化其效率。其中，第一点与第二点均比较地客观，且和已知的要求有一定的内在联系，倘若要深入地获取更多的信息，则应该加大投入的比例抑或是翻阅更为丰富的资料；至于改善第三点方面，应于原先条件的基础上以及确保该计算方法处于全局最优的环境下开展。本论文正是基于此环境背景下展开相关课题的研究的。
1.2选题意义
作为诸多优化算法中的一类，模拟退火算法具体的方法有2种：其一是基于函数所展开的一阶抑或是二阶导数，也即解析法，比较常见的有共扼梯度法、最
速下降法以及牛顿法等；其二则是基于函数数值自身对信息的运用，也即直接法，比较常见的有模式搜寻法、powell法、坐标轮换法以及单纯形法等。在对实际问题加以处置时，会碰到一系列的函数表达式，且通常这些函数表达式并不简单，有时难以具体地表达出来，进而难以得出其导数表达式，这样显然会影响具体运用第一种途径的效果。因而，第二种方法普遍性更为明显。而模拟退火算法正从属于优化算法中的后者。该算法最初来自于分析固体退火的现象，提出该方法的鼻祖是学者Metropolis（1953年），而学者Kirkpatrick则于1982年成功地将其运用在组合优化领域。而该方法的物理前提为在固体退火时所凸显出的物理性质。Metropolis接受定则使得本算法挣脱出局部最优的囹圄。
从实用性而言，研究该课题的意义在于减少公司的生产开销，进而推进公司的前进与发展。而这也是关键的方式及其必然性走向。从实质上看，公司立足于社会，必须离不开整个社会的需求。这在市场中就出现了供需现象，也是对商品的价格产生影响的最为关键性的因素，竞争现象应运而生。竞争存在着良性与恶性2种完全不同的现象。就公司的角度而言，它们关注的是具体生产的产品，除却需求因素之外，还存在着市场竞争的情况，即若从消费者的角度而言，他们会自动地挑选出称心如意的商品，在货比三家中选择出“物廉价美”的产品，这也对公司提出了生产方面的要求。
而模拟退火算法对于用电公司而言，其重要性更加地明显。倘若公司的电费开销在整个成本支出中大于50%，那么可以被认定是用电的大户。当下，因为能源供应比较地紧缺，这会明显地影响工业的效率以及百姓的日常生活，尤其是电能处于频繁拉闸的状态，会逼迫我国制定出全新的收费标准，从而废弃以往有关炼钢以及炼铁公司相关的优惠条例。而这又会对依赖该优惠政策的公司产生制约性的影响，甚至可能带来致命性的打击。要寻求发展的出路，那么必须减少电费的支出，其方法主要有2点：停产或要采取有效性措施来减少电费的开销。显然，前者是无法实施的，只能选择后者。若要减少电费开支，一般有2个途径：第一个更置设施，以旧换新，尤其是废弃使用那些极其浪费奢侈的设施，而重新选用节能的设施；第二个是基于当下的收费标准来确定变化了的生产时间。毫无疑问的是，第一个途径是不大现实的。因为要落实第一条必须花费数额庞大的开销，同时还不可忽视的是培训相关工作人员的开支，有可能还要因为引入相关领域的