遗传算法优化设计毕业论文

详谈改进的遗传算法求解柔性作业车间调度问题论文

0 引言

作业车间调度问题(Job-shop scheduling problem，JSP)是研究生产线调度问题最常用的模型之一，也是实现先进制造和提高生产效率的基础和关键. 柔性作业车间调度问题( Flexible jobshopscheduling problem，FJSP)是传统作业车间调度问题的扩展，在传统的作业车间调度问题中，每个工件的加工工序是确定的，每一道工序的加工机器和加工时间也是确定的，而在柔性作业车间调度问题中，每个工件的每一道工序可以在多个可选择的加工机器上进行加工，并且不同的加工机器所需要的加工时间是不同的，增加了调度的灵活性，比较符合生产的实际情况.

柔性作业车间调度问题已经被证明是更复杂的NP-Hard 问题，因而难以取得最优解. 目前，求解FJSP 的常用方法有禁忌搜索( TS)，模拟退火(SA)和遗传算法(GA)等. 其中遗传算法以其操作简单、鲁棒性强、搜索全局最优解速度快等特点，在生产调度领域得到了广泛的应用.

遗传算法是由美国J. Holland 教授于1975 年提出的，是一种模拟自然进化过程的一种优化算法. 由于传统的遗传算法存在着较大的缺陷，国内外学者已从不同角度对其进行了改进，本文对传统遗传算法的初始种群进行了改进，以提高初始解的质量.

1 柔性作业车间调度模型设有n 个待加工工件J(J1，J2，…，Jn)，在m台设备上加工M(M1，M2，…，Mm)，每个工件Ji有Pi(Pi1，Pi2，…，Pin) 道工序，每道工序可在一台或多台设备上加工，同一道工序在不同设备上加工的时间可能不等，工序Pik的可选机器集为Mik(Mik 罬)，每台设备的加工时间从0 开始，加工完所有工件的完成时间为ETMi . 本文以最小化最大完工时间为性能指标，其目标函数为:f(x) = min(max(ETMi))，1 ≤ i ≤ m模型需满足如下约束条件:(1)同一工件的工序加工顺序确定;(2)每道工序必须在它的上一道工序加工完成后才能开始加工;(3)每道工序只能选择一台设备进行操作;(4)每台设备在同一时间只能加工一个工件的一道工序;(5)每道工序在设备上操作时都不允许被中断;(6) 不同工件工序之间没有先后约束条件.一个包含3 个工件、5 台机器的FJSP 的问题.

2 算法的设计

(1) 基因编码

常用的遗传算法编码方案有二进制编码、格雷码编码、矩阵编码、自然数编码等，本文采用自然数编码，每条染色体表示一个可行解，同时采用双层编码，第一层编码为基于工件的工序编码，编码长度为所有工件工序之和，基因值代表工件号，基因值出现的次数代表该工件的工序总数，第二层编码为对应于第一层工件工序的机器编码，所以编码长度也为所有工件工序之和.染色体表示的工序顺序为(O31，O11，O12，O21，O22，O32，O13，O33)，染色体表示的机器序列为(M2，M4，M2，M1，M4，M5，M3，M4).

(2)产生初始种群

初始种群的优良对生物进化会产生很大的影响，本文对初始种群的机器选择进行了改进，首先随机生成初始种群的工序编码，工序编码生成后就要对应生成机器编码，每个工件工序在对应可选机器集中选择机器时，是以不同的概率的来选择不同的机器，机器加工时间短的以大概率被选择，相比之下，机器加工时间长的以小概率被选择，这样既保证了机器选择的随机性，也优化了初始种群.

(3)适应度函数的确定

本文以最小化最大完工时间为目标函数，故选择全部工件完工时间作为评价种群优劣的标准，设n 个待加工工件在m(M1，M2，…，Mm) 台设备上加工，所有加工工件工序在设备上的最后完工时间为ETMi(i = 1，2，…，m)，T = max(ETMi)，则适应度函数fi = 1 /T，T 越小，则适应度越大，即个体越优.

(4)选择

选择操作的目的是为了保留优良个体，使他们可以遗传到下一代. 本文采用精英保留策略和轮盘赌法相结合的方法，对父代个体和子代个体进行选择时直接将最优个体和次优个体遗传到下一代，然后对剩余的个体采用轮盘赌法进行选择，选择出p - 2 个个体到下一代进行遗传操作. 若种群规模为p，个体i 的适应度为fi，则个体i 被选择的概率pi为pi = fi /Σpk = 1fk即适应度越高的个体被选择的概率就越大.

(5)交叉

交叉操作是产生新个体的主要方法，提高全局搜索能力. 本文采用单点交叉方式，即随机产生一个交叉点，交换交叉点后的基因. 从种群中随机选择两个个体，交换两个个体工序编码的交叉点后面的基因，将交叉后工件多余的工序替换为其他工件缺失的工序;机器部分则按交叉前工件工序所选择的机器进行相应调整以保证其子代染色体的`合法性.

(6)变异

变异操作的目的是改变算法的局部搜索能力，有助于维持进化群体的多样性，防止过早陷入局部最优. 本文采用互换方式，即随机产生两个变异点，交换两点的基因值. 从种群中随机选择一个个体，对该个体的工序编码部分随机产生两个变异点，交换两点的基因值，同时将交换的基因位所对应的机器号也进行交换.

3 仿真实例分析

6 × 6(6 个工件，6 台机器) FJSP的加工工序，机器选择和加工时间矩阵表. 分别用标准遗传算法和本文提出的改进遗传算法对工件最小化最大完工时间进行优化计算，并分析优化计算结果.

遗传算法采用以下参数:种群规模为100，进化代数为100，交叉概率Pc = 0. 8，变异概率Pm =0. 1. 算法运行10 次，标准遗传算法的最大完工时间为20，收敛代数为75 代左右;改进遗传算法的最大完工时间为16，收敛代数为35 代左右. 改进遗传算法既缩短了工件完工时间，也加快了收敛代数. 从而验证了改进遗传算法的可行性

4 结论

传统遗传算法在进行种群初始化时采用的大多是随机选择方式，而本文提出了一种新的种群初始化方法，提高了种群初始解的质量. 最后对改进遗传算法进行了仿真实验，并将结果与标准遗传算法进行比较，结果表明了本算法的优越性和可行性.

机械创新设计是一个极其重要而又困难的实践性较强的研究课题。目前创新设计方法研究虽然已取得一些成果，但创新学还处于发展初期，各种不同理论及工具不断涌现，远没有形成普遍可以接受的统一的理论体系。本文认为，要进行机械创新设计要有两个必要条件：一是充分获取适用的知识；二是要使用符合创新设计思维并能激发创新思维的设计系统。设计过程充满了矛盾，所获取的知识应有助于矛盾的迅速解决，这就要求知识获取工具紧密集成到设计过程中，因此要统一研究知识获取工具与设计系统。另外，人类的创新设计思维模式是在长期的成功设计经验中总结形成的，因此设计系统必需符合创新设计思维规律。创新设计思维规律应作为算机辅助创新设计系统的理论基础。基于上述考虑，本文从创新设计思维的研究出发，融合知识获取方法，研究创新设计理论，进而开发机械产品创新设计系统。1 机械创新设计思维规律我们常把思维的过程称为“思路”，是因为可用路径问题来说明人类思维过程。本文提出两个机械创新设计思维原则：一是最短路径原则。设计者得到产品的功能要求后，往往首先检索出最佳设计实例，这样可以最迅速接近目标，然后运用价值工程方法，找出价值较低的极少数组件作为研究对象，再分析所得对象存在的矛盾，尝试作最小变动以解决矛盾，如矛盾没有解决则拟作更大变动或扩大研究对象范围，最后得出最优结果。通过这样途径所消耗的能量最少，体现了最短路径原则。二是相似性联想。汤川秀树的定同理论认为，联想能力就是找出事物彼此相似性的创造力，相似性是指事物间的内在联系。要用计算机系统来辅助设计师从自然界中发现形态各异的事物的相似性是很困难的，因此本文只研究从机械产品实例中挖掘相似性，以促进机械创新设计。机械设计过程是从功能要求到作用原理，再到物理结构的映射过程[1]。在CBR系统中，功能要求、作用原理与物理结构可作为实例索引，因此可统称它们为索引项目。同一索引的不同类索引项目之间的联想可称为纵向联想，而不同索引的同类索引的联想可称为横向联想。判断联想是否合理的依据是相似性，相似性由已有产品实例确定。比如，“超声波研磨机产品实例”使“超声波振动”作用原理与“研磨”功能要求纵向地产生了内在联系；又如，多种产品实例可满足同一功能要求，那么它们用于实现该功能的作用原理及物理结构具有相似性。功能要求是联想的起点，经验丰富的设计师通常记忆有大量的设计实例，因而掌握纵向及横向相似性，所以能迅速地进行横向及纵向的联想，能触类旁通，得出具有相似作用原理及物理结构的实例（简称相似实例）并进行组合优化，最后得到最优解。 这两项原则已被多种设计方法不自觉地采用了，基于实例推理不但能迅速接近最优解，体现最短路径原则；物场分析法（简称TRIZ）分析了上百万设计实例，确定功能要求与作用原理及物理载体的内在联系，以及不同作用原理或物理载体的可替代关系，使设计师可根据功能要求找到适当的作用原理及物理载体，体现相似性联想原则。2 计算机辅助创新设计系统 两项创新设计思维原则充分体现在计算机辅助创新设计系统的设计中，系统还利用了多种创新设计方法及人工智能技术。计算机辅助创新设计系统的流程如图1所示，它包含如下关键技术：2.1 实例检索 利用基于实例推理（CBR）技术时首先要深入研究它的优缺点。CBR是一种以实例为知识载体的知识供应方法。当前它仍有如下不足：首先，系统为了达到实用通常建立庞大的实例库，这导致管理困难，系统运行效率低；其次，通过检索得到的只是一个或很少实例，而其它不符合检索要求但含有适用知识的实例没有利用，支持创新的力度不够；最后，实例调整严重依赖领域知识，难度大，所以很多CBR系统简化为实例检索系统[2]。导致这三项缺点的深层原因是实例是独立的，不同实例所蕴含的知识难以组合利用。为了克服这个矛盾本文提出通过相似性联想找出相似实例，并利用遗传算法进行组合优化，实现实例知识的重用。本系统的实例检索功能用商品化PDM系统IMAN中的产品结构与配置管理功能及搜索功能来实现，实例的可视化表示与管理依靠IMAN的产品结构树功能实现。2.2可视化的实例模型表达及矛盾分析概念设计技术的发展方向为研究一种统一的设计方案表达方法[3]。文献[4]对日本学者吉川弘之提出的FBS图进行扩充，使用两个框架分别描述一个设计方案的功能层次与结构层次，并存储功能单元与结构单元的对应关系，使计算机理解产品的结构及其功能。这种方法的缺点是结构与功能的关系不够直观，因此本系统在功能层次图与结构层次图的基础上增加功能关系图，以语义网络的方式描述结构及之间的作用关系，使结构与功能处于同一张图中，设计者可直观地理解产品原理，根据功能关系图并运用价值工程方法分析实例存在的矛盾。实现创新的关键是正确分析产品中所存在的矛盾[5]。产品设计中的基本矛盾是产品功能成本比不能满足用户要求，它有两种表现形式，一是未能实现某些产品功能质量目标；二是某些功能质量得到改善而某些功能质量却恶化。矛盾分析结果用于指导新作用原理、新物理结构的联想，进而找出相似实例。2.3基于WEB的创新设计知识库本系统的创新设计知识库包括作用原理库、物理结构库与实例库。当系统根据相似性搜索到新作用原理或物理结构后，相应的实例自动调出。作用原理库与物理结构库的开发借鉴了TRIZ的成果，再针对机械领域补充整理出二百四十余种作用原理（其中包括五十余种基本措施）。在每种作用原理下分别存储多种物理结构，形成物理结构库。实例库主要针对几种常见的家电产品进行开发。创新设计知识库是创新设计系统的核心部件，它是一种WEB文本知识库，文本经过笔者开发的机械知识XML标记处理，使知识库建立在国际标准XML文本之上，因此可实现知识资源的异地共享，并且在此知识库之上可建立基于WEB的机械产品计算机辅助创新设计系统，满足异地协同设计的需要。2.4相似性的量化方法及改进的遗传算法每种产品的结构不同，需要不定相同的遗传算法编码。本系统为了提高运行效率，采用浮点数编码方式。在传统的遗传算法中，初始群体是通过用随机的方法来产生的[6]，这具有一定的盲目性。因此本文提出利用实例的作用原理或物理结构的相似性作为筛选实例产生初始群体的依据。实现该途径的关键在于相似性的量化也即相似度的计算方法。相似度实质是实例的关联知识，必须以一定的算法在实例集合中挖掘得到。纵向联想的相似度实质是功能目标与实现手段的关系程度，横向联想的相似度实质是实现手段的可替代关系程度。相似度越高意味着得到已有产品实例的更多支持。根据相似度来筛选初始群体就等于利用以前的设计经历，使初始群体的产生有合理的基础，因此能加快遗传算法的收敛。本文根据相似性联想原理提出如下纵向及横向联想的相似度计算方法。设产品实例集合为C，功能元素集合为F，作用原理或物理结构元素集合为G。分别记为：C={Ci|i=1,2,…,n}; F={Fj|j=1,2,…,m}; G={Gk|k=1,2,…,q}。实例集合中的实例Ci以不同的隶属度uij及uik分别隶属于Fj及Gk。 设元素Gk到元素Fj的纵向联想相似度为rkj，则：rkj = 又设G空间中有元素Gk和Gm。实例Cji分别以隶属度uik和uim隶属于元素Gk和Gm，设从Gk到Gm的横向联想相似度为rkm，则：rkm = 隶属度作为实例对象的一项属性来存储。系统根据以上算法从实例集合中挖掘相似度知识，辅助设计师从相似度较高的方向进行联想，并用于指导遗传算法初始群体的产生，从而促进设计创新。3 结论 本文研究创新设计思维规律并用于指导机械产品创新设计系统的开发，系统的成功应用证明了关于创新设计思维规律论断的正确性以及多种新技术的可行性。系统可通过矛盾分析与联想，搜索到适用的作用原理、措施、物理结构及实例以解决矛盾，完成概念设计阶段的功能优化与原理优化，是实现机械广义优化设计方法的新成果。也不知道你是否满意啊！

采矿工程毕业设计论文

采矿工程是一个国家的重要产业,采矿工程直接关系到国家资源、能源的正常供应和使用安全。以下是专门为你收集整理的采矿工程毕业设计论文，供参考阅读！

采矿工程方法优化研究

【摘要】采矿工程中的许多方法都是可以优化的，比如采矿工程中的开拓系统和采矿方法。这些方法优化问题，由于决策变量众多，并且不同情况的所起的作用不同，导致多数问题都是复杂的非线性化问题，不仅如此变量之间的联系有时很难用确切的数学模型或者数学表达式表达出来。因此我们考虑到可以利用计算机技术和人工智能的技术来实现采矿工程中方法的优化问题，比如遗传算法，神经网络等，本文从上述几种技术角度，结合实际例子探讨了采矿工程方法的优化问题。

【关键词】采矿工程;优化;采矿方法

采矿工程中的许多问题的决策和方法的优化，都是多决策变量问题。以往对这种问题的处理方式都是采用单一变量法，即采用固定其他变量使其值保持不变，通过变化某一变量来探索这一变量对目标函数或目标问题结果的影响，从而找出最优解。虽然这种方式大大简化了这种多变量问题的求解方式，但是它忽略了各个变量之间的相互关系，以及他们之间的相互作用对最终结果的影响，因此所得的结果并不是真正的最优值。为了求得真正的最优解，需要同时改变各决策变量，探索他们在这种情况下和目标的关系以及的对目标结果的影响，从而找出综合最优值。

1、优化方法

1.1遗传算法的定义

遗传算法是一种自适应优化的方法。这种方法基于生物进化的原理，它模拟了生物进化的步骤，将繁殖、杂交、变异、竞争和选择等概念引入到算法中。[1]通过对一组可行解的维持和重新组合，在多决策变量共同作用的条件下，改进可行解的移动轨迹曲线，最终使它趋向最优解。这种方式是模拟生物适应外界环境的遗传变异机理，克服了传统的单决策变量法容易导致的局部极值的缺点，是一种全局优化算法。

1.2神经网络的定义

人脑思维方式的一大特点就是：通过多个神经元之间的同时的相互作用来动态完成信息的处理。人工神经网络就是模拟人脑思维的这种方式，通过计算机来完成一个非线性的动力学系统，可以实现信息的分布式存储和并行协同处理。

1.3遗传算法与神经网络协同优化

由于采矿工程的问题很难用一个显式来表示，所以我们可以利用人工神经网络强大的非线性映射能力建立决策变量和目标函数的关系，实现对问题的显式化，然后用遗传算法对这个目标函数的决策变量进行搜索和寻优，搜索到后就输入之前已经建模好的神经网络，网络将自动进行学习和匹配，从而我们可以计算出目标函数对该组决策变量的适应性，然后根据适应性进行遗传变异操作，反复多次后即可寻得最优解。

2、优化实例

2.1遗传算法在矿石品位优化中的应用

遗传算法是由原始数据，模拟优胜劣汰的方式通过反复迭代获得最优解，在这里实质上是随机生成一组矿石品位，利用自适应的技术调整品位，经过反复迭代计算，逐步逼近最优解。

(1)编码：用定长字符代表遗传中的基因，在这里表示某种特定品位，编码顺序依次为边界品位、最小工业品位、原矿品位和精矿品位。[2]

(2)初始群体：每次迭代的初始群体由上一次迭代生成，第一次的初始群体随机生成，每个群体包含的个体数确定。

(3)适应度：自然界中的适应度是生物个体对自然界的适应程度，适应度大，那么它存活下来的可能性就大。类似的这里的适应度是衡量个体优劣的指标，可以驱动遗传算法的优化，本例中的适应度取不同品位的矿石所能取得的净现值。

(4)复制和交换：根据达尔文进化论，适应性强的个体容易生存下来，那么他们的有利性征就被保留了，同样的不利性征就被淘汰了，适应性强的个体他们的后代跟他们的相似度会比较高，在遗传算法中可以用复制来代表这一部分;交换就是指上一代多个个体的部分基因相互置换产生新个体。

(5)突变：遗传算法中产生新个体的又一手段，通过求补运算完成。

(6)终止条件：遗传算法是迭代运算，在迭代到符合某一要求时停止，一般都是当群体的平均适应度或最大适应度变化平稳时，迭代终止。

2.2采矿工程优化实例

本处选择山东莱芜铁矿施工时的填充材料刚度与采场结构参数的优化问题来说明一下神经网络和遗传算法的具体应用。

山东莱芜铁矿谷家台矿区矿体赋存于大理岩与闪长岩的.接触带中，上部为第四系和第三系所覆盖，全部为隐伏矿体，矿脉地理结构十分复杂。[3]上部有河流流过，虽然河流和矿带之间有第三系的红板岩，但是由于局部天窗的分布，导致水层和第四系砂砾石层和灰岩层接触，隔水效果不好。由于灰岩层的含水性，导致这部分成为承压含水层。复杂的地质背景给开矿带来了巨大的难度，为了实现不改河、不疏干、不搬迁、不塌陷、不还水的“五不”方针，最终决定的开矿方案是采用矿体近顶板大理岩注浆补漏堵水措施与阶段空场嗣后胶结充填采矿方法相结合的综合治水方案。制约这一方案顺利实施的两个重要因素就是充填材料刚度与采场结构参数的优选问题。

设矿房宽度为Bf，填充体刚度为EC，бt为上盘出现的最大拉应力。推测得出：从安全性角度考虑，矿房宽度Bf越小，填充体刚度EC越大，则上盘出现的拉应力越小，施工越可靠;从经济型角度考虑，矿房宽度越大，填充刚度越小越经济，可以看出两者是相对的，我们要在这之间找一个最佳匹配值。使得上盘出现的拉应力小于但又接近于大理岩的抗拉强度。

先通过神经网络建立决策量Bf、EC和目标бt的映射关系，然后用遗传算法搜索最佳匹配，得到结果Bf=21.256m，EC=396.6MPa，бt=-1.9297MPa，最后进行的结果的合理性验证，表明这个结果是令人满意的。

3、结论

作为现阶段比较先进的计算智能和人工智能技术，遗传算法和神经网络着重于通过迭代算法和非线性映射来求得问题的最优解。由于绝大多数矿场的复杂条件导致采矿工程中的许多问题和方法的决策存在众多的决策变量，并且多数变量和目标量的关系都是非线性的，这些特点使得遗传算法和神经网络等现代先进智能技术能很好的运用到采矿工程的优化中去，通过文章研究和实例证明，对于采矿工程的方法优化，遗传算法和神经网络能起到很好的效果，随着这些技术的进步，他们将会为采矿工程的优化方面提供更有力的帮助。

参考文献

[1]李云，刘霁.神经网络与主元分析在采矿工程中的应用[J].中南林业科技大学学报，2010，30(6)：140-146.

[2]张磊，柴海福.浅谈人工神经网络在采矿工程中的应用[J].学术探讨，2008，(6)：172.

[3]刘加东，陆文，路洪斌.浅谈采矿方法的优化选择[J].IM&P化工矿物与加工，2009，(1)：25：27.