当前位置: > 硕士毕业论文 > 31500字硕士毕业论文模具制造厂调度改革后模拟退火的遗传计算分析

31500字硕士毕业论文模具制造厂调度改革后模拟退火的遗传计算分析

论文类型:硕士毕业论文
论文字数:31500字
论点:算法,退火,调度
论文概述:

本文在总结了遗传算法在模具车间调度中的研究后,提出了一种基于模拟退火遗传算法的改进算法,并用实际车间数据进行了验证,结果表明该算法在作业车间调度中能够提高车间调度的生产效

论文正文:

第一章模拟退火遗传混合算法的研究

1.1简介
模拟退火和遗传算法是解决大规模组合优化问题的相对有效的算法,但在实际应用中,两种算法都有其固有的缺点和局限性。由于要计算的数据量巨大,模拟退火算法在解决大规模组合优化问题时往往过于缓慢。虽然它可以计算出所需的结果,但它变得不太实用。遗传算法的计算效率是可以接受的,但它往往会陷入局部早熟现象,实际的最优解还没有计算出来,这也是不可取的。因此,在20世纪90年代,林峰-谢等研究小组将遗传算法与模拟退火算法相结合,提出了模拟退火遗传混合算法(OENETIE/simulated EALINGALGRITHIN-GSA)。该算法在理论上有效结合了两种算法的优势,即通过模拟退火算法增加遗传群体的多样性,克服陷入局部早熟现象,同时利用遗传算法解决模拟退火算法计算效率低的问题。目前,混合算法已成功应用于自然科学、工程技术和管理等领域。

1.2模拟退火算法概述
模拟退火算法是解决大规模组合优化问题,特别是NP-hard问题的有效近似算法,由柯克帕特里克(Kirkpatrick)等人在1982年将固体退火的思想引入组合优化时提出。它源于固态退火过程的模拟,采用Metr接受准则,并使用一组称为冷却计划的参数来控制算法过程,从而使算法在多项式时间内给出近似最优解。Metropolis准则是模拟退火算法的基础,因此首先讨论了Metr敲击。Lis标准假设随机变量的状态在某个时间是“1”,在另一个时间是“2”。假设该状态的转变满足以下条件:p(e1Ez)=树脂(E,1eZ)(1.1),以指示系统从状态“转变到状态“2”所产生的能量差。如果能量差为负,这意味着状态能量减少。新状态被作为算法下一步的起点。同时,如果能量差为正,则算法在此时执行概率运算。首先,选择一个服从(0,1)内均匀分布的随机数。根据随机数来确定是否选择数值,这个过程称为抽样过程。
退火过程通常称为冷却过程,即在取样过程中,退火过程通过缓慢降低温度来模拟。如何选择参数将极大地影响算法的最终结果。初始温度和终止温度的设置也会影响搜索时间。如果冷却过快,可能会错过全局最佳点。如果冷却太慢,搜索速度就会慢,增加了搜索的时间复杂度,这是难以接受的。

1.2.1模拟退火算法的特点
模拟退火算法是一种求解复杂系统优化问题的搜索算法。与常用的优化搜索算法相比,它采用了许多独特的方法和技术,具体从以下几个方面进行阐述:

1。SA算法
在搜索策略上不同于传统的随机搜索方法,它接受一定比例的劣化解。它不仅引入了适当的随机因素,还引入了物理退火过程的自然原理。自然机制的引入使得模拟退火算法不仅接受了使目标函数变差的结果,而且接受概率也随着温度的降低而降低。复杂的问题将导致许多局部最优解出现在解中空。传统的优化方法通常是确定性的,并且总是沿着提高解决方案质量的方向进行搜索。这种确定性使得搜索没有达到全局最优点。然而,服务协议的搜索策略有助于防止在搜索过程中由于陷入局部最优解而导致的跳出失败,提高寻找全局最优解的可靠性。

2。算法控制参数T
算法的引入类似于退火温度的算法控制参数T。优化过程分为几个阶段,确定每个阶段选择随机状态的标准。接受函数允许Metr敲0115给出一个简单的数学模型。模拟退火算法的两个重要步骤如下:第一,在每个控制参数T下,相邻的随机状态x(i+1)由前一迭代点x(O)生成,由T确定的接受准则决定这一新状态的选择,形成一定长度的随机马尔可夫链;其次,控制参数t0缓慢减小,接收准则提高,直到t0。状态链在优化问题的最优状态下是稳定的,从而提高了模拟退火算法获得全局最优解的可靠性。

第二章车间调度问题研究

2.1简介
当今的企业面临着激烈的国内外竞争。为了在激烈的竞争中生存和发展,他们必须不断提高产品的质量和生产效率,充分满足客户的各种需求。车间调度问题是计算机集成制造领域的一个关键环节,也是典型的NP难问题之一。制造业的实际需求是研究这一问题的主要驱动力。由于现有计算条件的限制和作业车间调度问题的复杂性,实际问题在研究过程中一般被简化和抽象,复杂问题通过有效的方法转化为可解问题。然后,考虑各种目标和实际约束,使抽象的系统更符合实际车间制造系统。

2.2车间调度问题概述
模具制造车间调度是生产调度问题之一。它可以使用共享资源分配和生产任务排序来满足特定时间段内的指定性能指标。从数学规划的角度来看,作业车间调度问题是在多个不等式或方程的约束下对一个或多个目标函数的优化。简而言之,生产调度问题是根据时间分配资源和完成任务。作业车间调度决策包括时间决策、分配决策和路径决策。生产调度问题是如何在一定的约束条件下,为某个可分解的工作安排工件的部件和工序来占用资源、加工时间和顺序,从而获得产品制造时间或成本的优化。一个典型的作业车间调度问题包括一组需要完成的作业,并且必须根据特定的过程进行处理。每台机床都可以加工工件,并且可以在不同机床上加工的一组操作可以不同。调度的目的是合理安排每台机床上的工作,合理安排工作加工顺序的开始时间,确保满足约束条件,优化性能指标。

第三章改进的适应性模拟退火遗产...................24-40
3.1简介..............................24
3.2改进的模拟退火遗传算法..............................24-37
3.2.1遗传编码..............................25-29[/比尔/] 3.2.2初始人口和健身功能..............................29-31 [/BR/] 3.2.3选择操作员..............................31-33
3.2.4交叉算子和变异算子..............................33-35
3.2.5冷却操作..............................35-36
3.2.6改进的模拟退火遗传算法..............................36-37 [/BR/] 3.3改进算法的验证..............................37-38[/比尔/] 3.4核查..............................38-39[/br/[本章概述..............................39-40
第四章模具制造车间调度系统..............................40-47
4.1简介..............................40
4.2系统功能简述..............................40-41
4.3车间调度系统实施..............................41-44
4.4系统实施环境和数据库设计..............................44-46
本章概述..............................46-47

结论

近年来,车间调度问题越来越受到研究者的关注和研究。通过研究和实际应用,遗传算法等算法有效、合理、适用于解决这类问题。与单一的组合优化算法相比,混合优化算法可以结合不同算法的优势,更好地解决作业生产调度问题。作业车间调度问题是给出一个作业集和一个机器集。每台机器可以同时处理一个操作,每个操作包括一系列过程。每个过程都需要在某台机器上连续处理几次。作业车间调度研究的问题是如何在给定任务完成时最小化所需时间。
在过去的几十年里,国内外许多研究者对此问题进行了深入研究,并取得了许多令人鼓舞的成果。然而,随着作业车间调度问题中要考虑的实际问题变得越来越复杂和不可预测,对作业车间调度的实时性和有效性的要求也越来越高,企业需要一种更适合企业的作业车间调度方案。通过阅读大量国内外文献和调研实际车间,将模拟退火算法与遗传算法相结合,提出了一种改进的模拟退火遗传算法。该算法已应用于实际车间调度系统,取得了良好的效果。
本文开发的模具制造车间调度系统可灵活应用于车间调度系统,对降低生产成本、缩短制造企业制造周期起到积极作用。然而,由于作业车间调度问题本身的复杂性,该算法仍然存在许多不足。在实践中,许多偶然因素没有考虑在内,与实际环境仍有一定差距。因此,晚上还有许多工作要做。其次,系统需要关注实际环境中可能出现的紧急情况,进一步扩大系统的可用范围,使其应用范围更广。

参考
[1]姜国,岳红廖,贝扎德帕维兹。http://sblunwen.com/cnc/计算机科学系。加州州立大学洛杉矶分校。第13届国际电子电气工程师协会(IEEE)计算机系统工程国际研讨会暨研讨会论文集(ECBS\'06).2006:1~2
[2]陈豪,时颖,刘进,SE4SC:软件组件开发的特定搜索引擎——第四届计算机与信息技术国际会议,CIT 2004,第863-868页,2004,论文集——第四届计算机与信息技术国际会议,CIT 2004:1
[3]工作。流动管理联盟。工作流标准互操作性抽象规范[,1 999。
[4]巴图什·姆,莫赫林·r·h,拉德马赫·f·J..在资源限制和时间窗口的情况下调度项目网络[。运筹学年鉴,1988,16: 201-240
[5]布雷泽维奇j .,伦斯特拉J. K . \'林努伊Kan A. H. G..资源约束下的调度:分类和复杂性[。离散应用数学,1983,5: 11-24
[6]克里斯扎诺夫斯基,纽约,Jr &&约翰斯顿,华盛顿。线性构造的应用。建筑工程杂志,美国建筑学会,1986,112(4): 476-491
[7]哈梅林克·德·杰,罗林斯·杰..线性调度模型:控制活动路径的发展[。建筑工程与管理杂志,1998,124(4): 263-268
[8]哈梅林克..线性调度模型:浮动特性[。《建筑工程与管理杂志》,2001,127(4): 255-260
[9]哈里斯,皇家银行。安排重复活动的项目。密歇根大学土木与环境工程系第96-26号报告,安阿伯密歇根大学土木与环境工程系,麻省理工学院,1998年
[10]卡伦兹阿,兰波罗斯..通过将最小和最大时间和距离约束结合到线性调度中来确定关键路径[。工程、建筑和建筑管理,2004,11(3): 211-222