论文部分内容阅读
[摘 要]在设计领域中,布局及布置设计问题具有重要意义,其在工程实践中具有广泛的应用,它的求解自动化理论和方法在设计自动化领域中有重要作用。由于布局及布置设计问题建模比较复杂,所以求解具有较大的难度。文章主要分析了布局及布置设计问题求解自动化的理论与方法。
[关键词]布局;设计问题;求解;方法
中图分类号:G938 文献标识码:A 文章编号:1009-914X(2018)30-0348-01
布局和布置设计问题实际就是给定一个布局空间和若干待布物体,将待布物合理地摆放在空间中,并且能够满足必要的约束达到某种最优指标。布局问题在机械制造、皮革服装、造船、玻璃、交通运输、航空航天、大规模集成电路的设计及医学物理应用等领域中应用较多,例如车间布局、集装箱货物摆放、仪器舱内仪器布局以及飞机、车辆的布置设计等都涉及到了布局问题。
1 布局问题分类
根据布局空间和待布物体的形状,布局问题可分为:第一,二维规则物体布局问题。待布物和布局空间都是矩形或圆形,如装盘问题等。第二,二维不规则图形布局问题。待布物体和布局空间中至少有一个是二维不规则图形,如服装裁剪中的划印布置问题、造船业板材切割中的部件拼装问题等。第三,三维规则物体布局问题。包括长方体、圆柱体及球体布局问题,常用的是待布物体和布局空间都是长方体,如集装箱布局。第四,三维不规则实体的布局问题。待布物体和布局空间是三维不规则实体,如坦克舱布置设计、火箭仪器舱内的仪器布局问题。
2 布局问题的建模方法
2.1 数学模型
目前,大部分布局问题的模型都是将原问题进行简化,建立单纯的数学模型,然后用组合最优化中广泛应用的线性规划法、整数规划法、动态规划法或分枝定界法等数学方法进行问题的求解。将布局问题抽象简化建立数学模型,为求解提供了便利。但是当原问题涉及一些不易用数学模型表达的约束条件时,采用各种近似方法得到的数学模型往往会与原问题产生较大的偏差,并且当问题规模增大、解空间急剧增加时,它们的求解过程会很复杂,很难得到有效解。
2.2 符号知识模型
布局过程中经常会涉及到一些无法用数学方法描述的部分,如布局物体的材料性能和装卸工艺等,这时就只能建立符号知识模型。但是在布局知识的获取、表达等方面存在很多困难,只能按照预定的模式进行推理,缺乏创造性,更缺乏自学习和自适应能力。布局问题知识模型的建立是目前布局领域的一个弱点,当今学术界在工程布局问题建模上取得的成就只是初步的,距离问题的解决还有很大的距离。所以,需要进一步完善布局问题的建模方法。针对布局知识的多样性,建立问题的复合知识模型可能会取得更好的效果。
2.3 复合知识模型
布局问题会涉及到不同领域、不同功能、不同性质的知识,这些知识需要用不同的形式来描述和表达。其中有些可用数学模型描述,有些无法用数学模型描述,如布局物体的材料性能以及装卸工艺,尤其是人类专家的布局领域知识。现有的布局建模方法无论是基于数学模型或基于符号模型,都是针对布局过程的某一阶段,某一方面,某一领域建立单一知识模型。它们所能描述的只是复杂布局设计任务的一些局部工作。解决复杂布局问题,还需要建立问题的复合知识模型——各种单一模型的集成。
下图1为布局问题基于复合知识模型的建模方法。在计算机中将问题的几何、数学、符号等模型的各种表达方式集成为复合知识模型,并可以通过多通道用户界面使布局专家的认知活动嵌入并与之交互,充分利用各种知识、更加完善地描述布局问题,为进一步求解奠定基础。图1中布局空间和待布物体的几何模型可以采用实体造型软件如Pro/E、AutoCAD等进行计算机辅助建模,并可转换为VRML或其他虚拟现实模型;输入设备可以是键盘、鼠标或数据手套;输出设备可以采用显示器、立体眼镜或数据头盔。这种人机结合的求解方法可充分发挥布局专家的创造性和关键决策的作用,在复杂布局问题的求解中必不可少。复合知识模型对布局设计自动化是非常必要的,将成为复杂布局建模方法的主要发展方向。
3 布局问题的求解方法
3.1 数学方法
布局问题被简化成数学模型后,通常采用数学规划或数值优化的方法求解。数值优化方法只能找到局部最优解,所得解的质量在很大程度上依赖于初始解的选择,所以一些学者致力于研究布局初始方案的自动生成方法。数学规划方法由于依赖于数学模型解析性的原因而导致局部最优解的局限性为很多研究者所重视。他们采用具有全局搜索能力的计算智能算法与局部搜索的数学规划算法相结合,能得到较好的结果。在纯数学推导中加入启发式经验,极大地提高问题求解能力。
3.2 专家系统技术
布局問题是一个领域性很强的问题,有许多学者认为利用专家系统与适合于某一领域的知识模型相结合是解决具体领域布局问题的有效方法。利用专家系统技术辅助机械产品的布局设计,可以充分利用积累在专家头脑中的大量布局知识,构造布局设计领域知识库。专家系统的推理机制和人机接口可以使计算机和用户对比知识,进行处理和利用,在一定程度上完成布局决策工作。但利用专家系统进行布局设计,在布局知识的获取、表达等方面存在很多困难,只能按照预定的模式进行推理,缺乏创造性,更缺乏自学习和自适应能力。由于专家系统技术只能处理单一知识领域范畴的符号推理问题,所以,布局专家系统只能在布局过程的某一阶段起到作用,它的封闭性、领域针对性、缺乏自适应能力,都使之无法单独承担复杂系统布局的求解任务。
3.3 人工神经网络方法
自从Hopfield利用神经网络成功地求解了旅行商问题以来,人工神经网络方法在组合优化领域得到越来越多的重视。人工神经网络具有自适应性、自学习性、强容错性和巨并行性等许多人脑所具有的特性。相关研究人员将人工神经网络的方法和启发式方法结合,构造了求解布局问题的混合算法。然而常规神经网络存在局部最小问题,它的解依赖于网络的初始状态,在许多场合仅能得到次优解。混沌神经网络是一种新兴的神经网络,由于其混沌动力学特性,易于摆脱局部极小点。将混沌神经网络用于二维布局求解中,得到较好的解。
总结:总而言之,布局问题在工业以及生活中都有较广泛的应用,是设计领域的一个重要部分。相关研究人员应该不断研究其建模方法和解决问题的方法,并将这些方法付诸实践,用来解决各种复杂的问题。
参考文献
[1] 李明,刘航,张晓建.多物流配送中心的选址布局问题优化模型研究[J].重庆交通大学学报(自然科学版),2017,36(01):97-102.
[关键词]布局;设计问题;求解;方法
中图分类号:G938 文献标识码:A 文章编号:1009-914X(2018)30-0348-01
布局和布置设计问题实际就是给定一个布局空间和若干待布物体,将待布物合理地摆放在空间中,并且能够满足必要的约束达到某种最优指标。布局问题在机械制造、皮革服装、造船、玻璃、交通运输、航空航天、大规模集成电路的设计及医学物理应用等领域中应用较多,例如车间布局、集装箱货物摆放、仪器舱内仪器布局以及飞机、车辆的布置设计等都涉及到了布局问题。
1 布局问题分类
根据布局空间和待布物体的形状,布局问题可分为:第一,二维规则物体布局问题。待布物和布局空间都是矩形或圆形,如装盘问题等。第二,二维不规则图形布局问题。待布物体和布局空间中至少有一个是二维不规则图形,如服装裁剪中的划印布置问题、造船业板材切割中的部件拼装问题等。第三,三维规则物体布局问题。包括长方体、圆柱体及球体布局问题,常用的是待布物体和布局空间都是长方体,如集装箱布局。第四,三维不规则实体的布局问题。待布物体和布局空间是三维不规则实体,如坦克舱布置设计、火箭仪器舱内的仪器布局问题。
2 布局问题的建模方法
2.1 数学模型
目前,大部分布局问题的模型都是将原问题进行简化,建立单纯的数学模型,然后用组合最优化中广泛应用的线性规划法、整数规划法、动态规划法或分枝定界法等数学方法进行问题的求解。将布局问题抽象简化建立数学模型,为求解提供了便利。但是当原问题涉及一些不易用数学模型表达的约束条件时,采用各种近似方法得到的数学模型往往会与原问题产生较大的偏差,并且当问题规模增大、解空间急剧增加时,它们的求解过程会很复杂,很难得到有效解。
2.2 符号知识模型
布局过程中经常会涉及到一些无法用数学方法描述的部分,如布局物体的材料性能和装卸工艺等,这时就只能建立符号知识模型。但是在布局知识的获取、表达等方面存在很多困难,只能按照预定的模式进行推理,缺乏创造性,更缺乏自学习和自适应能力。布局问题知识模型的建立是目前布局领域的一个弱点,当今学术界在工程布局问题建模上取得的成就只是初步的,距离问题的解决还有很大的距离。所以,需要进一步完善布局问题的建模方法。针对布局知识的多样性,建立问题的复合知识模型可能会取得更好的效果。
2.3 复合知识模型
布局问题会涉及到不同领域、不同功能、不同性质的知识,这些知识需要用不同的形式来描述和表达。其中有些可用数学模型描述,有些无法用数学模型描述,如布局物体的材料性能以及装卸工艺,尤其是人类专家的布局领域知识。现有的布局建模方法无论是基于数学模型或基于符号模型,都是针对布局过程的某一阶段,某一方面,某一领域建立单一知识模型。它们所能描述的只是复杂布局设计任务的一些局部工作。解决复杂布局问题,还需要建立问题的复合知识模型——各种单一模型的集成。
下图1为布局问题基于复合知识模型的建模方法。在计算机中将问题的几何、数学、符号等模型的各种表达方式集成为复合知识模型,并可以通过多通道用户界面使布局专家的认知活动嵌入并与之交互,充分利用各种知识、更加完善地描述布局问题,为进一步求解奠定基础。图1中布局空间和待布物体的几何模型可以采用实体造型软件如Pro/E、AutoCAD等进行计算机辅助建模,并可转换为VRML或其他虚拟现实模型;输入设备可以是键盘、鼠标或数据手套;输出设备可以采用显示器、立体眼镜或数据头盔。这种人机结合的求解方法可充分发挥布局专家的创造性和关键决策的作用,在复杂布局问题的求解中必不可少。复合知识模型对布局设计自动化是非常必要的,将成为复杂布局建模方法的主要发展方向。
3 布局问题的求解方法
3.1 数学方法
布局问题被简化成数学模型后,通常采用数学规划或数值优化的方法求解。数值优化方法只能找到局部最优解,所得解的质量在很大程度上依赖于初始解的选择,所以一些学者致力于研究布局初始方案的自动生成方法。数学规划方法由于依赖于数学模型解析性的原因而导致局部最优解的局限性为很多研究者所重视。他们采用具有全局搜索能力的计算智能算法与局部搜索的数学规划算法相结合,能得到较好的结果。在纯数学推导中加入启发式经验,极大地提高问题求解能力。
3.2 专家系统技术
布局問题是一个领域性很强的问题,有许多学者认为利用专家系统与适合于某一领域的知识模型相结合是解决具体领域布局问题的有效方法。利用专家系统技术辅助机械产品的布局设计,可以充分利用积累在专家头脑中的大量布局知识,构造布局设计领域知识库。专家系统的推理机制和人机接口可以使计算机和用户对比知识,进行处理和利用,在一定程度上完成布局决策工作。但利用专家系统进行布局设计,在布局知识的获取、表达等方面存在很多困难,只能按照预定的模式进行推理,缺乏创造性,更缺乏自学习和自适应能力。由于专家系统技术只能处理单一知识领域范畴的符号推理问题,所以,布局专家系统只能在布局过程的某一阶段起到作用,它的封闭性、领域针对性、缺乏自适应能力,都使之无法单独承担复杂系统布局的求解任务。
3.3 人工神经网络方法
自从Hopfield利用神经网络成功地求解了旅行商问题以来,人工神经网络方法在组合优化领域得到越来越多的重视。人工神经网络具有自适应性、自学习性、强容错性和巨并行性等许多人脑所具有的特性。相关研究人员将人工神经网络的方法和启发式方法结合,构造了求解布局问题的混合算法。然而常规神经网络存在局部最小问题,它的解依赖于网络的初始状态,在许多场合仅能得到次优解。混沌神经网络是一种新兴的神经网络,由于其混沌动力学特性,易于摆脱局部极小点。将混沌神经网络用于二维布局求解中,得到较好的解。
总结:总而言之,布局问题在工业以及生活中都有较广泛的应用,是设计领域的一个重要部分。相关研究人员应该不断研究其建模方法和解决问题的方法,并将这些方法付诸实践,用来解决各种复杂的问题。
参考文献
[1] 李明,刘航,张晓建.多物流配送中心的选址布局问题优化模型研究[J].重庆交通大学学报(自然科学版),2017,36(01):97-102.