卫星装配序列规划的智能优化算法研究

曾森 刘继红 郝佳

(1 航天东方红卫星有限公司，北京 100094) (2 北京航空航天大学机械工程及自动化学院，北京 100191)



卫星装配序列规划的智能优化算法研究

曾森1刘继红2郝佳1

(1 航天东方红卫星有限公司，北京 100094) (2 北京航空航天大学机械工程及自动化学院，北京 100191)

结合单个算法的优缺点，文章提出了一种用包含多种改进型智能优化算法的算法库(IIAL)来解决卫星装配序列规划问题的方法。算法库由算法向导和多种算法组成，算法向导可依据若干参数描述给出适合当前规划任务的最合适算法，规划人员可依据向导建议在遗传算法、粒子群算法、蚁群算法、模拟退火算法中选择相应算法进行求解。最后，用实例验证了方法的合理性。该方法可为星上设备装配序列规划提供参考。

卫星装配；装配序列规划；智能优化算法；算法库

1 引言

卫星总装是卫星研制的重要阶段，总装工艺规划是卫星总装的关键环节，而卫星装配序列规划是总装工艺规划的重要内容。随着基于三维模型的数字化制造技术的推广应用，利用计算机辅助给出多种约束条件下的最优装配序列就很有必要。早期的装配规划方法大都是通过“割集法”[1]等图论方法求出所有可能的装配序列，然后按照评价标准从中选取较好的序列。但是，基于图搜索的装配规划方法会遇到“组合爆炸”和“盲目搜索”的问题，从而难以选择出最优的装配序列。

为了解决上述难题，随着人工智能的发展，众多学者将诸如遗传算法、蚁群算法、人工神经网络等 “智能优化算法”引入装配规划研究中[2]。如Marian等人通过改进操作算子的遗传算法迭代计算求得理想的装配序列[3]。邓明星、宁黎华、陈刚、张晶、刘海江等人分别探究了蚁群算法、免疫算法、模拟退火算法、人工神经网络算法、粒子群算法在装配序列规划问题中的应用[4-8]。此外，曾冰、王松等人分别将萤火虫算法和混合蛙跳算法引入到复杂产品装配序列规划中来[9-10]。

智能优化算法都是利用启发式信息来探索最优解。总体来说，待求解装配规划问题的特点不同，采用的智能优化算法不同，最终的求解效果也不同。针对卫星装配特点，为有助于选择更合理的智能优化算法，本文对遗传算法、粒子群算法、蚁群算法、模拟退火算法等智能优化算法在卫星装配序列规划中的应用进行了研究，提出了智能优化算法库(IIAL)，帮助规划人员便捷获得最优装配序列。

2 卫星装配序列优化模型建立

2.1 装配序列优化模型

装配序列优化是指在满足给定装配工艺约束的条件下，产生或找到装配成本最低、装配效率最高的几何可行装配序列[11]。求解最优装配序列，必须首先建立数学模型。在星上设备装配中，要考虑几何干涉、设备安装方向、安装工具、安装方式、是否涂胶、是否涂抹导热硅脂、接地阻值测量等因素。实际操作中，涂胶、涂抹导热硅脂可提前实施，接地阻值测量可安装后统一实施，此3项不占用设备安装主线时间。影响星上设备装配序列成本的因素主要包括4个方面：①序列存在几何干涉则无法安装；②装配方向的改变直接影响装配辅助时间；③螺钉规格和操作空间不同所导致的工具更换会降低装配效率；④单人安装、双人协作以及依靠吊装辅助安装等不同装配方式导致占用的资源和时间不同，从而增加装配成本。因此，评价星上设备装配序列优劣的要素应包括几何和成本约束两类，前者剔除几何干涉的装配序列，缩小求解空间；后者主要包括装配方向、工具、方式等成本信息。

基于上述分析，星上设备装配序列优化问题的数学模型为

(1)

(2)

式中：nt、nd、nc是一次计算过程中装配工具、装配方向和装配方式的改变次数；M是几何干涉的零件数目；ct、cd、cc和cg为装配约束的权重系数，一般ct、cd、cc之和为1，可根据实际情况分配各值，而cg一般取值为50(远大于1)。对于n个待安装的星上设备，s={p1，p2，…，pn}表示装配序列，pi(1≤i≤n)，满足几何约束，用f1(s)计算装配成本，否则，用f1(s)+f2(s)计算。

2.2 优化模型中相关参数的计算

优化模型中需要计算的参数有M、nd、nt和nc。需要指出的是，与一般机电产品的装配不同，星上设备装配是将不同设备按要求安装到星体结构上，设备之间没有连接关系；同时，因部分方向结构板阻挡，星上设备无法从6个方向装配到位。为此，给出如下两点限定：

(1)参与装配的星上设备或组件均为刚体，且每次操作设备均一次装配到位；

(2)设备均安装在方箱式星体结构板上，星体坐标系为XYZ三轴坐标系，装配路径为直线装配，即装配方向为±X，±Y，±Z共6个，若设备安装方向已装有结构板，则该方向对该设备存在干涉。

为计算几何干涉零件数，须建立适合星上设备装配特点的集成干涉矩阵，定义如下：

(3)

式中：Iijx=0是指当设备pi从结构外沿+X方向装配到位时不与设备pj发生干涉；Iijx=1是指当设备pi从结构外沿+X方向装配到位时与设备pj或+X侧结构板发生干涉。同理，I中的元素Iijy、Iijz分别表示设备pi在+Y轴方向和+Z轴方向上装配与设备pj或结构板的干涉情况，其取值类似于式(3)。设备pi沿-X轴方向装配与设备pj干涉的情况，与设备pj沿+X轴方向装配与设备pi干涉的情况相同，由元素Ijix表示。同样，可以确定Ijiy和Ijiz的值。

定义pi是待装配设备，Sa是在当前装配状态下由m个已装配好的设备组成的临时组件，Sa={P1，P2，…，Pm}，设备pi的装配方向向量βi，βi={+Iix，+Iiy，+Iiz，-Iix，-Iiy，-Iiz}，某元素的值为0就表示待装设备在该方向上是可装配的，若为1则表示待装设备在该方向上装配将发生干涉。其中

(4)

(5)

式中：“∨”表示二进制的“或”操作。其余4个方向数值的求解与式(4)、(5)类似。待装设备pi的装配方向向量βi中的0值元素所对应的装配方向组成了待装设备pi的可行装配方向集Fi。如果Fi=Φ，则表示待装设备在当前状态下没有可行的装配方向。装配序列中存在一个没有可行装配方向的设备，则该序列就不可行，存在多个此类设备，就发生多次干涉，就可得出M值。

装配工具方面，星上设备的装配一般可由多种工具来完成，用一个Bit代表一种工具的信息，某一位值为1代表该种工具可用，值为0代表该种工具不可用，按二进制求值后，用一维矩阵E(q)来储存装配工具的信息，若有4种工具T1,T2,T3和T4，某个零件q可以用T1和T4来装配，则T1位、和T4位所对应的值均为1，则E(q)=23+20=9，依此类推可以完成装配工具信息的存储。建立矩阵后，可通过给定初始值再对矩阵各元素按Bit位求“与”操作来求得装配工具更换次数nt。

装配方式方面，一般规定一台设备对应一种装配方式，可用一维矩阵B(q)来储存装配方式的信息。若有3种装配方式，分别为C1,C2和C3，零件pi和零件pj的装配方式属于C1和C2，则相应的B(q)值为1和2，依此类推，可以完成装配方式信息的存储。建立该矩阵后，可通过直接通过对矩阵中各元素的比较来求得装配方式更换次数nc。

装配方向方面，可采用类似装配工具的方法来求得待解序列的装配方向改变次数nd。

3 算法库原理及组成

由于智能优化算法各自不同的特点以及装配规划问题的复杂性，没有哪种算法能解决所有规划问题，而且对各算法在质量、效率等方面表现的评价仍停留在定性评价阶段。为了便捷给出最优装配序列，针对星上设备装配特点，本文构建了一个算法库，基于量化指标将多种智能优化算法集成到同一平台下进行研究。算法库原理示意图如图1所示。

算法库由算法向导和算法池组成。算法向导以规划人员对待求解问题的描述为输入，以算法库中已总结的各个算法效能指标历史经验值为主要量化参考依据，通过一定加权计算后，由算法向导给出当前问题的各算法适合值排序，帮助规划人员快速选择算法。算法池中包含装配规划遗传算法(GA-SAP)、装配规划粒子群算法(PSO-SAP)、装配规划蚁群算法(AC-SAP)和装配规划模拟退火算法(SA-SAP)等4种智能优化算法，规划人员可基于同一优化模型，按照算法向导的建议排序采用一种或多种算法进行计算，并将最后结果反馈到算法库中。

3.1 算法向导

3.1.1 问题描述

问题描述是算法向导的主要输入，包括3个方面：一是算法性能要求，明确使用者对算法质量、效率、成功率的优先权重以及参数复杂性方面的要求。初始阶段，使用者可能更偏重于效率高且参数设置比较简单的算法；而在实际处理阶段，使用者就需要在算法效率与质量以及参数复杂性方面做一个平衡。二是装配特征要求，明确装配体零件数、装配关系数、装配类型、是否已得可行初始序列等信息。面对不同零件数、不同层级复杂度、不同装配类型(单轴/多轴)的装配规划问题，不同算法求得的结果有明显的质量差异。三是规划人员经验需求，明确其熟悉、倾向或指定的算法。算法应用效果与参数设置密切相关，必须考虑规划人员已有的算法应用经验。

根据上述输入，可以大体判定当前问题的特点和规划人员对算法的使用需求等信息，支持算法向导给出更合理的算法选择建议。

3.1.2 算法评价指标

本文主要从求解质量、效率及成功率三方面量化评价算法的性能，评价指标见表1。

表1 算法评价指标体系Table 1 Algorithm evaluation index system

其中，相对误差越小，求解质量越好；搜索效率值越小，算法收敛速度越快；成功率越高，算法可信度越高。依据上述评价指标，可量化评价算法库中各算法的效能。

3.2 算法池

针对卫星装配仍主要以手工操作为主、星体多为箱式结构等特点。本文建立了适应卫星装配特点的4种智能优化算法。规划人员可根据算法向导的建议选择相应算法，设置装配序列优化模型参数和算法参数来完成问题的求解。这当中，由于蚁群算法寻优机制的独特性，需要建立不同设备之间的装配关系矩阵。区别于一般的机电产品，卫星各设备之间一般没有联接关系。为此，适用于星上设备的装配关系矩阵可做如下定义。

(6)

式中：Rij=0 是指当设备pi安装后影响或无法判断是否影响设备pj的安装。Rij=1 当指当设备pi安装后不影响设备pj的安装。

4 实例与分析

本文以某微小卫星为例对前文所述方法进行了验证，例子相关信息如图2所示。

(1)建立集成干涉矩阵I和装配关系矩阵R

(2) 建立存储装配工具的矩阵E(q)，E(q)={1,17,4,2,4,2,8,1,17}。装配工具总共有5种，信息存储格式为

T5T4T3T2T1

(3) 建立存储装配方式的矩阵B(q)，B(q)={2,3,2,1,1,2,2,1,2}。

本文基于JAVA语言实现了算法库。利用算法库来处理该装配规划问题，第一步是问题描述：零件数9，装配关系数8，装配类型为多轴装配，尚未获得可行序列；对算法质量、效率、成功率要求均衡，接受参数较复杂算法；规划人员经验均为空，图3为问题描述界面。第二步是选择算法：根据描述，算法向导给出的算法建议从高到底依次为遗传、模拟退火、蚁群、粒子群算法。第三步是设置装配序列优化模型参数和算法参数，其中ct、cd、cc和cg权重系数分别设置为0.5，0.2，0.3和50。第四步是迭代计算，结果分析、应用。

在算法参数设置上，遗传算法设置初始种群为200，循环次数200，交叉概率0.8，变异概率0.6，交叉方式为OX算子，变异方式为双点，个体选择为指数排序法；蚁群算法设置蚂蚁数目为9，循环次数为20，信息素为0.8，信息素的重要性为1，启发信息的重要性为1，信息素局部和全局挥发率为0.6和0.1，调节常数为2；模拟退火算法设置初始温度为500，状态接受函数为概率方式Ⅱ，领域解产生为两位置点间序列逆序，温度更新系数为0.95，内循环迭代步数为500，外循环终止温度为0.001；粒子群算法设置粒子数为500，循环次数为500，速度算子的保留概率c0，c1，c2分别为0.8，0.5，0.5。图4为粒子群算法参数设置。图5为利用算法库中各算法计算出的最优装配序列。

为了验证算法向导所给出算法建议的有效性，同时进一步研究各算法的性能，本文对同数据源采用算法库中4种算法进行了多次运算。图6为各算法多次运算的装配成本折线图(局部)。并根据多次运算结果，计算了表1中算法评级体系中各项指标值，如表2所示。其中，基于智能优化算法求解目标函数的随机收敛原理，同种算法在多次运算中结果并不完全相同，这也是开展智能优化算法性能评价研究的出发点。

从表2中可以看出，针对该实例，遗传算法的求解质量最优、搜索效率居上(收敛速度快)、成功率最优，综合比较，遗传算法最适合当前实例。其余算法，模拟退火算法求解质量居上，成功率高，但搜索效率一般；蚁群算法求搜索效率居中，成功率高，但求解质量居中；粒子群算法搜索效率居上，但成功率一般。综合比较，基于对求解质量、效率、成功率要求均衡等描述，算法向导给出的有关适合实例的算法排序是合理的。即算法向导可向规划人员推荐最优算法，从而便捷获得多种约束下的最优装配序列。

此外，依据算法库计算得出的最优装配序列，完成了一次实例中星上设备安装，与之前依靠工艺人员的经验规划确定的装配序列相比，依据最优序列节省了约20%的工时，同时，进一步规范了设备安装过程中方向、工具、方式等因素的选用，避免了盲目操作和纯经验操作。

算法fafbEm/%Ga/次Ta/sEs/%Rsuc/%Rb_suc/%遗传算法3.33.301996.13.1100100模拟退火算法3.43.3016623.113.910020蚁群算法3.83.815.2191.89.51000粒子群算法3.53.3049914.62.99040

5 结束语

基于三维模型的数字化制造背景，本文提出的面向星上设备装配特点的改进型智能优化算法库，可增强规划人员便捷获取最优装配序列的能力，同时为量化评价各算法的效能提供了同一平台。随着研究的深入，可加入更多的算法并将相应效能值存入到算法库中，不断拓展算法库的维度和应用深度，为规划人员提供更加便捷、可靠的工具。

References)

[1] Homem de Mello L S,Sanderson A C. A correct and complete algorithm for the generation of mechanical assembly sequences [J]. IEEE Transactions on Robotics and Automation,1991,7(2): 228-240

[2]Liu Jihong，Zeng Sen. A survey of assembly planning based on intelligent optimization algorithms[C]//Proceedings of the ASME 2008 International Design Engineering Technical Conferences & Computers and Information in Engineering Conference. New York,USA: ASME,2008

[3]Marian M R,Luong H S L,Abhary K,et al. A genetic algorithm for the optimization of assembly sequences [J]. Computer & Industrial Engineering,2006,50(4): 503-527

[4]邓明星，唐秋华，雷喆. 基于蚁群算法的改进装配序列规划方法[J].武汉大学学报：工学版,2013,46(2): 246-251

Deng Mingxing,Tang Qiuhua,Lei Zhe. A novel approach for assembly sequence planning based on ant colony algorithm [J]. Engineering Journal of Wuhan University,2013,46(2): 246-251 (in Chinese)

[5]宁黎华，古天龙. 基于免疫算法的装配序列规划问题求解[J].计算机集成制造系统，2007,13(1): 81-87

Ning Lihua,Gu Tianlong. Immune algorithm for assembly sequence planning problem [J]. Computer Integrated Manufacturing Systems,2007,13(1): 81-87 (in Chinese)

[6]陈刚，陆海滨，庄纯，等. 基于配合节点序列的航天产品装配序列规划[J].机械制造与自动化，2015,(5): 68-70

Chen Gang,Lu Haibin,Zhuang Chun,et al. Assembly sequence planning for aerospace products based on fit nodes sequence [J].Machine Building & Automation,2015 (5): 68-70 (in Chinese)

[7]张晶，崔汉国，朱石坚. 基于人工神经网络的装配序列规划方法研究[J].武汉理工大学学报(交通科学与工程版)，2010,34(5): 1053-1056

Zhang Jing,Cui Hanguo,Zhu Shijian. Study on assembly sequence planning using neural networks [J]. Journal of Wuhan University of Technology (Transportation Science & Engineering),2010,34(5): 1053-1056 (in Chinese)

[8]刘海江，李玲玉，张含叶. 基于改进粒子群算法的锂电池模块装配序列规划[J].中国工程机械学报，2014,12(4):306-312

Liu Haijiang,Li Lingyu,Zhang Hanye. Assembly sequence planning for lithium-ion battery modules based on improved particle swarm optimization algorithm [J].Chinese Journal of Construction Machinery,2014,12(4):306-312 (in Chinese)

[9]曾冰，李明富，张翼，等. 基于萤火虫算法的装配序列规划研究[J].机械工程学报，2013,49(11): 177-184

Zeng Bing,Li Mingfu,Zhang Yi,et al. Research on assembly sequence planning based on firefly algorithm [J]. Journal of Mechanical Engineering,2013,49(11):177-184 (in Chinese)

[10] 王松，孙振忠，郭建文，等. 基于混合蛙跳算法的复杂产品装配序列规划[J].计算机集成制造系统，2014,20(12):2991-2999

Wang Song,Sun Zhenzhong,Guo Jianwen,et al. Assembly sequence planning based on shuffled frog leaping algorithm [J]. Computer Integrated Manufacturing Systems,2014,20(12):2991-2999 (in Chinese)

[11]王俊峰，李世其，刘继红，等. 计算机辅助装配规划研究综述[J].工程图学学报，2005(2):1-7

Wang Junfeng,Li Shiqi,Liu Jihong,et al. A survey of computer aided assembly planning [J]. Journal of Engineering Graphics,2005(2):1-7 (in Chinese)

(编辑：李多)

Improved Intelligent Optimization Algorithm Library for Assembly Sequence Planning of Satellites

ZENG Sen1LIU Jihong2HAO Jia1

(1 DFH Satellite Co.,Ltd.，Beijing 100094，China) (2 School of Mechanical Engineering and Automation，Beihang University，Beijing 100191，China)

Considering the disadvantages of single algorithm，an approach to resolve assembly sequence planning problem of satellites with improved intelligent optimization algorithm library(IIAL)is proposed．The IIAL is composed of an algorithm advisor and several improved algorithms．The most suitable algorithm will be obtained to assembly planners by the algorithm advisor according to the description of the assembly planning problems. Assembly planners can chose one of then to solve the problem. Finally，an illustrative example is given to verify the rationality of the algorithms suggested by the IIAL．The approach could be useful for equipment assembly sequence planning on the satellite.

satellite integration；assembly sequence planning；intelligent optimization algorithm；algorithms library

2016-08-01；

2016-12-27

曾森，男，硕士，工程师，研究方向卫星数字化总装，智能优化算法等。Email：dddyx026@163.com。

TP391.7

A

10.3969/j.issn.1673-8748.2017.01.007