1、现代制造系统,第10章 现代制造系统的设计（1-3） 东北大学秦皇岛分校 黄亮 n-xyz,第10章 现代制造系统的设计,制造系统的分析与综合： 系统分析的目的是了解系统的运行原理； 系统综合的目的是利用掌握的原理，构造出新的更优秀的系统。 长期（几月或几年）综合问题称为设计问题： 即包括从无到有产生符合要求的新系统， 也包括在现有系统基础上，通过系统校正、系统重构等方法产生比原系统性能更优良的新系统。,本章首先对现代制造系统的设计方法进行概述； 然后对与这些设计方法的实现关系密切的层次分析法和智能优化算法进行介绍； 评价和选择方案是设计不可缺少的组成要素； 层次分析法是实现复杂系统多角度综合
2、评价的主要方法； 智能优化算法则是从众多待选方案中找出较好方案的重要工具。 最后将典型的制造系统设计问题按照能力配置、路径设计和规则设计的分类举例进行介绍。,第10章 现代制造系统的设计 10.1 设计方法概述 10.2 层次分析法 10.3 智能优化算法 10.4 能力配置问题 10.5 路径设计问题 10.6 规则设计问题,10.1 设计方法概述,由于制造系统领域的相关研究开展得较晚，因此其设计方法大多参考了其它设计领域的成熟理论，主要包括 （1）最优化设计方法； （2）并行设计方法； （3）迭代设计方法； （4）重构设计方法； （5）鲁棒性设计方法。,（1）最优化设计方法 首先要知道能够
3、优化什么？ 即定义决策变量。 设计问题的常见决策变量有 能力，包括设备、人员、工具、库位、库存等资源的数量； 路径，包括工艺路线、物流路线等； 规则，包括生产批量、调度方法、产品抽检方案、设备维护方案等。,对于最优化设计， 其次要知道什么样的方案为好？ 即构造目标函数。 最根本的目标函数为企业效益， 可分为收入（产量毛利润） 和支出，支出又包括 时间支出（延期惩罚等）， 质量支出（不合格品损失等）， 生产成本（构成复杂，见课件下一页）。,生产成本又包括 原材料费， 生产工具损耗 （设备折旧、厂房折旧、刀具损耗等）， 人员酬劳 （生产、技术和管理人员的工资与奖金）， 能源动力费 （电费、水费、燃
4、气费等）， 管理成本 （办公、外联、活动经费等）。,在解决实际设计问题时， 目标函数的构造分为以下几种情况： 直接使用多项式描述， 成为数学规划问题。 通过过程模型间接描述， 包括时间分析类模型（排队网络等）， 时间仿真类模型（Petri网等）， 以及成本模型和质量模型。 定性与定量相结合的多目标综合评价， 主要方法为层次分析法（analytic hierarchy process, AHP），本章后面介绍。,对于最优化设计， 再次，需要限定决策变量的取值范围是什么？ 以减少优化问题的搜索范围， 这称之为约束条件。 例如在能力配置问题中，超出车间购买能力或摆放能力的设备数量预先排除掉，只在一定
5、范围内分析配置多少设备成本最低； 又例如在工艺路线设计问题中，如先钻孔后绞丝等强制性工艺顺序不可改变，需要预先排除掉不可能实现的工艺路线设计方案，然后再在可行方案中寻找总体时间最短的工艺路线。,对于最优化设计， 最后，是找到合适的优化算法。 对于数学规划问题， 可使用数学规划模型求解， 包括单纯形法、梯度法、分支定界法等。 对于嵌入各种过程模型的的优化问题， 往往需要智能搜索算法（也称为亚启发式算法或邻域搜索类算法）近似求解，包括遗传算法、模拟退火算法、蚁群算法、粒子群算法、禁忌算法、免疫算法、混沌算法等。本节后面介绍。,制造系统的最优化设计方法概述：,最早出现于 产品设计领域， 后来扩展到
6、整个制造领域。 参考并行工程 （第6.4节）。,（2）并行设计方法,（3）迭代设计方法 指制造系统的设计过程 需要反复试验和修改多次才能够定型。 每一个设计阶段从用户需求开始，包括 总体规划、初步设计、 详细设计、工程实施、 运行与维护五个反复执行的阶段， 最终形成系统与文档。,（4）重构设计方法 包含两层含义： 一是进行制造系统设计时要充分利用已有资源，在尽量不改变制造系统资源配置的情况下，引入新的运行模式，建立新的组织结构，从而使系统获得更好的性能； 二是在设计制造系统时，要考虑增加其可重构性，为今后的重构工作提供便利。参考第5.2节可重构制造系统。,（5）鲁棒性设计方法 鲁棒是robus
7、t的音译，也就是健壮和强壮的意思。 鲁棒性（robustness）原是统计学中的一个专门术语，20世纪70年代初开始在控制理论的研究中流行起来，也意译为稳健性或抗变换性，用以表征控制系统对特性或参数摄动的不敏感性。 对于一个设计方案不仅要求其在当前环境下是优秀方案，当环境在一定范围内发生的变化，原设计方案仍不失为好方案，这就是鲁棒性设计的思想。,案例，瓷砖生产的鲁棒性设计： 某型瓷砖经过多次实验，确定了最佳的尺寸和原料配比，但是经过烧制却常常变得大小不一，方便使用。此时可采取措施有 （1）剔除掉尺寸不合格的，出售剩下的瓷砖； （2）分析工艺，发现窑内受热不均导致瓷砖大小发生变化，花大成本改造窑
8、坑，减少受热不均的情况发生； 上述两种方法直接处理问题，不属于鲁棒性设计。 （3）重新研制瓷砖配方，使温度变化不再明显影响其体积。该措施从减少设计方案受环境的影响入手角度改进设计方案，属于鲁棒性设计。 制造系统的鲁棒性指非计划任务的承受能力，通常与制造系统的敏捷性和柔性密不可分。,第10章 现代制造系统的设计 10.1 设计方法概述 10.2 层次分析法 10.3 智能优化算法 10.4 能力配置问题 10.5 路径设计问题 10.6 规则设计问题,10.2 层次分析法,层次分析法（analytic hierarchy process, AHP）是将与决策总是有关的元素分解成目标、准则、方案等
9、层次，在此基础之上进行定性和定量分析的决策方法，适合辅助建立多目标优化模型。 该方法为美国运筹学家、匹茨堡大学教授萨蒂（T. L. Saaty）于上世纪70年代初，在为美国国防部研究“根据各个工业部门对国家福利的贡献大小而进行电力分配”课题时提出的。,层次分析法的求解步骤： 建立层次结构模型； 构造判断矩阵； 层次单排序； 层次总排序； 一致性检验。,建立层次结构模型。 决策目标即最优化方法中的目标函数； 有可能存在多个子准则层。,层次结构模型举例1：,层次结构模型举例2：,例题1，某生产线从经济效益、可发展性和技术可行性3个角度评选最佳系统方案。备选的方案有自动生产线、数控生产线和柔性生产线
10、。 对上述问题使用AHP层次结构模型描述如下：,构造判断矩阵， 形式如下图，为正互反阵： 判断矩阵是针对上层的某个目标或准则的， 对全部相关的下层准则或方案的重要性判断。 判断矩阵维数等于相关的下层准则或方案数量。,判断矩阵的取值（标度）方法：,注意：标度是矩阵行因素与列因素比较的结果。,对于例1而言， 由于A层存在着1个最终目标， C层存在着3个评价准则， 故需要4个判断矩阵来描述它们与下层的关系。 分别是A-C判断矩阵： 举例：表格中红色的3表示准则2可发展性比准则3技术可行性稍微重要；其余元素含义以此类推。,对于例1而言，其余3个判断矩阵如下,层次单排序。 含义：针对上一层某一因素，当前
11、层所有相关因素的重要性排序，是权衡多因素相互重要程度的综合结果。 表现形式：以当前层所有相关因素个数为维数的向量，即前面判断矩阵表格中列标题为W的最后一列。 设判断矩阵为B，则向量W的定义如下 其中max为矩阵B的最大特征根， 向量W为对应的max归一化特征向量。,在层次单排序这步中， 当判断矩阵维数较大时，求解最大特征根和特征向量的计算量较大，故实际应用时常使用近似方法处理。 常用的近似算法有3种，分别为根法、和法和幂法。 其中，根法最为常用；和法计算相对简单；幂法精度最高，但需要迭代计算，所以也常用计算机处理。本课程仅介绍最常用的根法。 例题1中各判断矩阵的最后一列W向量就是使用根法计算得
12、到的。,根法也称为几何平均法，计算过程如下 首先，计算判断矩阵B每行元素的几何平均值 其中bij为中判断矩阵B的各个元素值。 其次，将各行的几何平均值进行归一化处理 最后，得到特征向量,以例题1中的A-C判断矩阵为例 第1行的几何平均值为 第2行的几何平均值为 第3行的几何平均值为 三行的几何平均值求和为 0.8736+2.0801+0.5503=3.5040,以例题1中的A-C判断矩阵为例 第1行的归一化处理为0.8736/3.5040=0.2493 第2行的归一化处理为2.0801/3.5040=0.5936 第3行的归一化处理为0.5503/3.5040=0.1571 即用此方法获得上述
13、矩阵的而最后一列， 例题1中其余3个判断矩阵的最后一列也是如此计算获得。,层次总排序。 含义：针对上一层全部因素，当前层所有相关因素的重要性排序，是权衡多因素相互重要程度的综合结果。 表现形式：以当前层所有相关因素个数为维数的向量，通过以下公式得到 其中 为本层因素j的层次总排序权值； 为上一层因素i的层次单排序权值； 为对应上一层因素i的判断矩阵中第j行的层次单排序权值。,对于例题1，层次总排序的计算结果如下表 其中红色字体的数据来源如下,对于例题1，层次总排序的计算结果如下表 其中红色字体的数据来源如下,对于例题1，层次总排序的计算结果如下表 其中红色字体的数据来源如下,对于例题1，层次总
14、排序的计算结果如下表 其中红色字体的数据来源如下,对于例题1，层次总排序的计算结果如下表 其中红色字体的数据的计算方法如下 第1行：0.24930.6250+0.59360.1220+0.15710.2970=0.2749 第2行：0.24930.2385+0.59360.5584+0.15710.5396=0.4757 第3行：0.24930.1365+0.59360.3196+0.15710.1634=0.2494 最后选择层次总排序权值最大的方案即为最佳方案，例题1中即为数控生产线。,一致性检验， 含义：表示判断矩阵自相矛盾的程度。 若根据判断矩阵能够清晰地整理出各因素的重要程度，则称其
15、具有良好的一致性； 若判断矩阵表示的各因素重要程度存在自相矛盾（例如A比B重要，B比C重要，C比A重要），则称其不具备良好的一致性。 常用的一致性判别方法：特征根法。,特征根法的一般步骤为 计算判断矩阵的实际最大特征根max 。 若使用计算机编程进行检验， MATLAB等软件提供直接计算的函数。 若使用手工计算进行检验， 可通过近似计算得到的特征向量计算最大特征根，即通过如下公式计算,对于例题1中的以下判断矩阵 特征根计算公式为 则,然后计算判断矩阵的一致性比例 查表获得修正系数RI（平均随机一致性指标），下表为3至9阶判断矩阵的RI值 最后，计算修正后的一致性检验指标,对于例题1，由于P层存
16、在3个判断矩阵， 需要按权重计算3个矩阵的综合一致性比例 然后按权重计算3个矩阵的综合修正系数 最后计算综合的一致性检验指标 若CR0.1,则认为判断矩阵的一致性可以接受。 对于例题1，使用上述方法计算出的CR=0，因此其判断矩阵的一致性是非常好的。,层次分析法总结： 层次分析法的优点在于可以将定性的评价标准转化成定量的评价标准，并且能够综合评价多个优化目标，因此非常适合在一些评价标准过多、难以直接打分评价的场合应用。 其缺点在于计算较复杂，稍大规模的问题通常需要计算机编程求解。 另一个缺点在于判断矩阵中的元素主要是由专家评经验打分，人为的主观因素影响仍然很大，有些适合的难以给出令人信服的结果
17、（例如不能通过判断矩阵的一致性检验）。,层次分析法的新发展： 今年来，有学者将层次分析法与模糊数学相结合，提出了模糊层次分析法（fuzzy analytical hierarchy process，FAHP），在处理一些不好直接打分评价的问题上有着更好的表现。 另外，但层次分析法中的判断矩阵不能通过一致性检验时，往往要对判断矩阵的元素进行修正。修正一方面要提高判断矩阵的一致性，另一方面也要尽量保留专家的原有打分，这是一个复杂优化问题。使用粒子群算法（particle swarm algorithm，PSO）等智能优化算法求解这个优化问题也是当前研究的热点之一。,第10章 现代制造系统的设计 1
18、0.1 设计方法概述 10.2 层次分析法 10.3 智能优化算法 10.4 能力配置问题 10.5 路径设计问题 10.6 规则设计问题,10.3 智能优化算法,以遗传算法、模拟退火算法、蚁群算法、粒子群算法、禁忌算法、免疫算法等为代表的一系列优化算法，有数十种之多。 相对于传统的数学规划法，上述算法虽然通常只能得到近优解（与最优解相差不多的近似解），但因为其适应范围广，在目前多个领域的科学研究中都有广泛的应用，是当前的研究热点之一。,（1）遗传算法（genetic algorithm，GA） 模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索
19、最优解的方法。,它最初由美国Michigan大学J. Holland教授于1975年首先提出来的，但直到他并出版了颇有影响的专著Adaptation in Natural and Artificial Systems后，才广泛流传起来。 后来，基于遗传算法的改进算法的研究非常多，因此Holland教授最初提出的遗传算法现在被称为简单遗传算法或经典遗传算法。,经典遗传算法的主要步骤： 对解进行编码， 常用方法有直接编码、二进制编码等; 随机或按照一定规则构造初始解集合，称为种群；继而采用以下4种算子反复改变种群，寻找更好的解； 选择（复制）算子： 采用一定策略（例如轮盘赌策略），选出一些较优秀的
20、解用于以下算子进一步处理；,经典遗传算法的主要步骤： 交叉（交换）算子： 按一定概率在所选择的解之间互换部分编码； 倒位算子： 按一定概率在所选择的解内部互换部分编码； 变异算子： 按一定概率改变所选解的部分编码，变异范围为通常为邻域（neighborhood）；,经典遗传算法的主要步骤： 若新产生的解的适应度更好， 则取代原有解中适应度较差的解， 保持一定的种群数量。 循环直至满足结束条件， 结束条件通常为到达指定的迭代次数或时间， 或者长时间没有找到更优的解。,（2）模拟退火算法 （simulated annealing algorithm，SAA） 模拟退火算法来源于固体退火原理。,退火
21、是一种金属热处理工艺。指的是将金属缓慢加热到一定温度，保持足够时间，然后以适宜速度冷却。目的是降低硬度，改善切削加工性；消除残余应力，稳定尺寸，减少变形与裂纹倾向；细化晶粒，调整组织，消除组织缺陷等。,模拟退火算法最早的思想是由N. Metropolis等人于1953年提出。1983年，S. Kirkpatrick等成功地将退火思想引入到组合优化领域。,模拟退火算法的主要步骤： 设置初始温度和结束温度，构造初始解； 按一定概率改变所选解的部分编码，变异范围为邻域；若新解更好，则取代当前解，否则以一定概率取代（温度越高概率越高）； 重复搜索若干次后降温； 重复上述过程直至当前温度低于结束温度。,
22、（3）蚁群算法 （ant colony algorithm，ACO） 蚁群算法又称蚂蚁算法，是一种用来在图中寻找优化路径的随机型算法。 它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。,蚁群算法的主要步骤： 构造初始蚁群（解集合）； 蚂蚁找到的解越好， 就留下越多信息激素； 每个蚂蚁向视野内信息激素最多的方向移动（掺杂一定的随机性）； 每个蚂蚁携带的信息激素有限，全部用完即结束搜索。,（4）粒子群算法（particle swarm algorithm，PSO） 1995年由Eberhart博士和Kennedy博士提出。,该算法是受到
23、飞鸟集群活动规律的启发，进而利用群体智能建立的一个简化模型。 该算法与蚁群算法的思想非常相似。,（5）禁忌算法（Tabu search，TS） 最早由Glover于1986年提出。通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。 禁忌搜索最重要的思想是标记对应已搜索的局部最优解的一些对象，并在进一步的迭代搜索中尽量避开这些对象（而不是绝对禁止循环），从而保证对不同的有效搜索途径的探索。,（6）免疫算法（immune algorithm，IA） 或称为人工免疫算法。 有关理论可追溯到1958年澳大利亚
24、学者Burnet率先提出了克隆选择原理，1960年因此获得诺贝尔医学奖（生理学奖）。 1974年，诺贝尔奖得主、生物学家、医学家、免疫学家Jerne提出了免疫网络理论并建立了数学模型，奠定了免疫计算的基础。 1990年，Bersini首次使用免疫算法来解决组合优化问题。 免疫算法模拟了免疫系统独有的学习、记忆、识别等功能，表现出较高的智能性和鲁棒性。,智能搜索算法总结： 搜索过程都是反复迭代的，全都具有一定的随机性，用以避开复杂优化问题的局部最优。 搜索过程全都采用一定的规则指导，而这些规则随着搜索的进行也在不断的调整，以保证搜索过程的收敛性，故这些算法被称为亚启发式算法，也被称为进化算法。
25、搜索过程全部遵循一个假设：解的优劣存在这一定的连续性，故应多在优解附近寻找更优解，故这些算法也被称为邻域搜索类算法。 搜索过程在局部是简单、随机的，但在整体上随着计算量的增大，表现出一定的规律性和智能性，故这些算法被称为智能搜索算法。,由于进化算法普遍没有搜索方向指导， 存在速度过慢和质量不稳定的缺点。 因此当前研究的热点在于 将进化策略与梯度策略结合起来， 通过梯度或近似梯度指导搜索过程， 用以加快速度、保障质量。 代表性的方法有 差分进化算法（Differential Evolution，DE）， 通过对已搜索到的解进行统计分析， 预测可能存在较好解的搜索方向， 作为近似梯度指导搜索过程。,课程要求（10.1）,知道制造系统设计的基本方法（5种）。 理解制造系统最优化设计的主要工作： 决策变量、目标函数、约束条件和优化算法； 简单了解并行设计、迭代设计和重构设计的概念。 知道常规设计与鲁棒性设计的区别。,课程要求（10.2-3）,掌握层次分析法（本节例题1，知道判断矩阵元素位置和大小的含义，会使用根法进行层次单排序，会计算层次总排序，一致性检验不要求）。 知道常用的亚启发类优化算法（6种）； 理解遗传算法中各个算子的含义； 理解模拟退火算法中初始和结束温度的含义； 理解蚁群算法中信息激素的含义。,
