论文部分内容阅读
在产品生产过程中,产品装配所需工时占生产制造总工时的40%-60%,装配成本约占总生产成本的40%。合理的装配序列规划(Assembly Sequence Planning,ASP)对提高产品的质量、降低生产成本具有十分重要的意义。几何推理方法和以进化算法(Evolutionary Algorithm, EA)为代表的智能算法是求解ASP的典型方法。由于装配序列规划问题实际上是一个NP组合优化问题,传统的几何推理方法利用零部件间的几何配合信息计算推理出装配序列,将不可避免地遇到装配序列的组合爆炸问题。有序二叉决策图(Ordered Binary Decision Diagram, OBDD)是一种新型的图形数据结构,具有高紧凑性和易操作性特点,是减缓或者在部分程度上避免状态组合复杂性问题的有效技术。基于OBDD的装配序列生成的几何推理方法在一定程度上扩大了问题的求解规模,但仍无法克服ASP组合爆炸问题。进化算法是一种适合解大规模组合优化问题的有效近似算法,ASP用进化算法求解可有效克服组合爆炸问题,但当前求解ASP的进化算法仍难以有效利用装配经验知识。另外,这些进化算法运行时支撑的数据结构基本上还是数组类或集合类,导致算法需要较大存储空间和存有大量盲目搜索。针对以上问题,本文给出了多个求解ASP问题的多智能体进化算法和基于装配计算的进化算法,并把基于装配计算的进化算法推广到一类约束满足问题求解领域。具体研究内容如下:1.为了克服传统进化算法(如模拟退火、遗传算法等)中个体难以有效利用装配经验知识的问题,给出了一种求解ASP的多智能体进化算法。设计了智能体的学习算子、协作算子、竞争算子和变异算子,构造了表示装配经验的公有知识和私有知识。该进化算法中的智能体可以有效利用装配体的几何,工艺等相关知识。智能体之间通过领域实现私有知识的分享。另外,还根据基于联接件ASP的特点,实现了基于联接件ASP求解的一种多智能体进化算法。仿真实验表明这两种进化算法与同类算法相比均具有较好性能。2.多智能体进化算法对约束条件和装配经验的有效利用是通过知识来实现的,存在一定盲目性。在自装配计算的启发下,为了在进化算法中能有效抑制不满足基本约束条件的装配序列的生成,提出了基于装配计算求解ASP的进化算法,设计了新型进化算子-生长算子,生长算子直接利用装配计算的特征,使得个体在进化过程中遵守装配体的约束条件,从而减少进化算法搜索的盲目性。另外,结合多智能体学习和智能推理特征,本文还给出了基于装配计算求解ASP的多智能体进化算法。实验表明,这两种进化算法与同类算法相比有效提高了ASP的求解效率。3.目前求解装配序列规划的进化算法的装配体模型主要是数组或矩阵型,而用OBDD等符号技术表达装配体模型则能节省存储空间,其隐式数据模型表示的特征还有利于搜索的隐含并行。为节省数据的存储空间,提高进化算法相关算子的搜索性能。本文设计了基于符号技术OBDD的进化算法,实现了随机重组、启发重组两种算子。其中启发重组具备了装配计算的特征,类似于生长算子。仿真实验表明,与类似的传统进化算法相比,该算法能有效节省数据的存储空间,同时发挥了符号技术的隐含并行搜索能力。4.为了测试基于装配计算的进化算法可扩展性,深化装配计算进化算法的研究,在自装配计算刚体计算模型的启发下,设计和实现了求解TSP、n皇后等问题为代表的约束满足问题求解的基于装配计算的进化算法,设计了相应的自装配计算模型和进化规则,进化个体间的迭代不必以代同步,进化过程由装配计算模型的约束规则控制。仿真实验表明,基于装配计算的进化算法在求解此类问题时与同类算法相比具有较好的性能。