基于启发式算法的可重构性指标分配

第 39卷 第 5期2013年 10月空间控制技术与应用Aerospace C ontrol and Application ·7·基于启发式算法的可重构性指标分配 水项昌毅 ，杨 浩 ，程月华 ，姜 斌 ，刘成瑞(1．南京航空航天大学 自动化学院，南京 210016；2．南京航空航天大学高新技术研究院 ，南京 210016；3．北京控制工程研究所 ，北京 100190；4．空间智能控制技术重点实验室 ，北京 100190)摘 要：串联有约束条件下的可重构性指标分 配问题 ，针 对考虑部件故 障的 系统给 出了可重构度的概念和计算方法，并论证 了其合理性．结合最优冗余分配理论和可重构度定义给 出了可重构度最大化的冗余分配模型，在此基础上提 出了基 于启发式算法的可重构性指标分配方法，该方法可解决约束条件 内资源优化配置问题 ，并得到 系统最大可重构度的解．直接寻查法作为以往具有代表性的最优冗余分配方法，用作 系统可重构性指标分配仿真 ，与所提方法作 比较，结果显示基于启发式算法的可重构性指标分配方法较前者有更高的有效性.

关键词：可重构性；可重构度；可重构性指标分配；启发式算法中图分类号：TH7 文献标识码 ：A 文章编号：1674．1579(2013)05—0007．06DoI：10．3969／i．issn．1674—1579．2013．05．002On Heuristic Algorithm for Rec0nfigurability AllocationXIANG Changyi ，YANG Hao ，CHEN Yuehua ，JIANG Bin ，LIU Chengrui ，( ．College of Automation Engineering，Nanjing University of Aeronautics andAstronautics，Na， ng 21 001 6，China；2．Academy of Frontier Science，Nanjing University of Aeronautics and Astronautics，Nanjing 210016，China；3．Beijing Institute of Control Engineering，Beqing 100190，China；4．Science and Technology on Space Inteligent Control Laboratory，Be ng 100190，China)Abstract：The paper aims to find a reasonable solution to the problem of reconfigurabi1ity allocation forthe series system with constrains．The concept and the computing method of reconfigurable degree for thereconfigurable system are proposed，which consider the component failure．Combining the theory of opti—mal redundancy alocation and the definition of reconfigurability，maximum reconfigurable degree modelmodelare proposed．A new heuristic algorithm is presented，which can solve the problem of resources op—timization allocation with constraint conditions．The maximum of reconfigurable degree can be achievedby the method．The proposed heuristic algorithm is compared with the representative optimal redundancyallocation method，i．e．，the direct search method．The simulation results demonstrate the superiority ofthe heuristic algorithm.

Keywords： rec0nfigurability； reconfigurability degree；recon gurability allocation；heuristic algorithm随着工业技术的不 断发展 ，现代控制 系统设计越来越复杂，故障出现的可能性增大，有些故障甚至导致系统崩溃，造成重大的经济损失．为了解决这些问题 ，许 多学者作 了广泛 而深 入 的研 究 ．文献[1]为评估资源约束条件下切换系统的故障恢复能力提供了一种有效方法，以揭示切换系统对最危险国家自然科学基金资助项 目(61203091，61104116，61273171)；上海航天科技创新基金资助项目(SAST201234)；中央高校基本科研业务费专项资助项 目(NS2012069).

收稿 日期 ：2013．07—26· 8· 空间控制技术与应用故障的容错能力．文献 [2]针对快速重组系统提了一种故障可诊断性估计的方法．文献[3]探讨了可重构设计的概念与理论 ，即可重构性是一种系统在一定条件下通过 自身资源重组 内部结构的能力，当故障发生时 ，可重构系统可 以通过切换备份部件来恢复系统功能．由于可重构性系统的这个优点 ，所以对可重构性系统的研究是一项非常必要而紧迫的任务.

然而 目前可重构性研究仅限于对系统故障的评估预计和可重构性的概念分析 ，并没有给出指导可重构性设计的有效方法．为此 ，针对考虑部件故障的系统可重构性设计问题，本文提 出基于启发式算法的可重构性指标分配 ，通过该方法可 以实现 系统可重构性优化设计，并获得满意的配置方案 ，最后的仿真计算验证了所提方法的有效性.

1 可重构性指标计算与分配模型从工程实际出发，当系统部件故障后，优先采用的是硬件备份切换方式来重构系统 ，假定部f，{：之间没有故障关联 ，故障部件 的切换成功率达 到 100％.

由此，针对 系统发生故障情形 ，取硬件是否可切换备份来衡量系统是否可重构．当系统 中有 n个部件发生故障时，定义为 n重故障.

如何衡量系统的可重构性水平与故障之间的关系是一个新的问题．为了量化体现这一关系 ，本文将衡量系统可重构性水平 的指标定 义为可重构度．当系统发生 n重故障时，相应地称该可重构性指标为n重可重构度．下面给出了 n重可重构度的定义.

定 义 1.

n重故障下系统可重构的故障数 ， 、一 系统可能发生的 n重故障的总数其 中0≤R≤1．当一个系统的 n重可重构度等于 1时，称这样的系统对于 n重故障是饱和的．相应地 ，当一个系统的 n重可重构度小于 1时 ，称这样的系统对于 n重故障是不饱和的．一个饱和系统对于更高重故障可能是不饱和的．后文如果没有特殊强调 ，系统指的是不饱和系统.

一 般认为系统冗余增加时，系统可重构度增加才是合理的．下面给出了定理和证明过程.

定理 1．对于考虑部件故障的串联系统，在式 (1)所描述的可重构度的计算方法下 ，可重构度随着 部件冗余增加而增大.

证明．以一重故障为例．假设系统有 M个部件 (所有部件都有可能发生故障)，其中可重构的故障有 Ⅳ个 ，则系统可重构度为 R = i V．当系统第 i个分系统增加一个冗余时(该冗余部件采用并联的方式)，则系统可能发生故障的部件总数为 1+ 个 ，可重构的故障数是 1+Ⅳ个，增加冗余后的可重构度R {-_ ·由于 >N，所以MN+M>MN+Ⅳ，即} > N，可得尺 >R．结果表明系统可重构度随冗余 的增加而增大．同理可 以证 明式 (1)对于其他多重故障也是满足的.

下面根据式(1)的定义给出一重和二重故障下系统可重构度的计算公式.

1．1 一重可重构度计算一 个由 个分系统串联组成的系统 ，每个分 系统表示一个独立功能的部件 ，所有部件都可能发生故障，其一重故障情形共有 k种，见图 1中 case 1，case 2。·一。case k.

图 1 系统发生一重故障示意 图Fig．1 Schematic diagram for single fault假设第 i个分系统有 m 个部件 ，其 中可重构 的一 重故障有 n， 个．下面给出了系统一重可重构度的定义.

定义2．当系统发生一重故障时，系统的一重可重构度为：∑= { 一 (2)∑m其中，m 是第 i个分系统部件数，n 为第 i个分系统可重构的一重故障数.

1．2 二重可重构度计算系统发生二重故障时 ，所有情形如图 2所示.

假设第 i个分系统有 m 个部件，其中可重构的一 重故障有 n． 个 ，可重构的二重故障有 n 个，下面给出了系统二重可重构度的定义.

第 5期 项 昌毅 等 ：基于启发式算法 的可重构性指标分 配 ·9·、、^ — ＼ ▲ 、### ### [=》?### ### 图2 系统发生二重故障示意图Fig．2 Schematic diagram for double faults定义 3．当系统发生二重故 障时 ，系统的二重可重构度为k k∑ +∑nil～尺 = 一 (3)∑mik k其中，i≠ ，∑n 和∑niln 分别为二重故障发生I ，J= I在同一个分系统和不同分系统时系统可重构的故障k(∑m 一1)‘∑m数．C2 , =— —— — 一 表示 系统可能发.

生的二重故障总数.

1．3 可重构性指标分配最优化模型可重构性指标分配是系统可重构性设计 的重要组成部分，旨在将使用方提出的，在产品研制任务书中规定的可重构性或资源约束指标，自上到下，逐步分解，得到满足系统要求的最优配置．结合大量文献上的指标分配模型 以及 可重构性指标定义给出可重构度最大化的冗余分配.

模型 1：可重构度最大化的冗余分配通过对元件冗余设计来提高系统可重构度是常用的方法：在资源约束条件下，寻找最优的元件冗余数 一， 使系统可重构度最大化模型为rmaxR =l厂( 1，?， ){s．t． g ( 1，?， )≤b ，t=1，?，P，L Z ≤ ≤ t，
i = 1，? ，k其中，g (·)表示第 t种资源的总消耗，b 为第 t种资源上限， 为第 i个分系统的实际冗余部件数，z和 u 分别为该分 系统的冗余 下限和上限 ，且 、z和 u 均为正整数．对于考虑部件故障的系统可重构性设计，可分离性假设g ( 一， )=∑g ( 。)i= l是成立的，其 中 g ( )为第 i个分系统第 t种资源的消耗.

2 基于启发式算法的可重构性指标分配方法Chern 曾指出，即使一个简单的带有线性约束的串联系统冗余分配问题都是 NP(non—deterministicpolynomia1)困难的．从计算量 的角度来看 ，NP困难问题属于高难度复杂问题．然而 ，随着对 NP困难问题研究的深入，启发式算法因为能大大减少计算量并获得令人满意的最优解 ，从而引起 人们 的关注和研究.

启发式算法 (heuristic algorithm)是指那些受大自然 的运行规律或者面向具体 问题 的经验 、规则启发出来的方法 ．在发展启发式算法方 面不少学者都作 了贡献，如 Sharma 和 Nakagawa 叫等．下面将结合可重构性 的特 点 ，分别 阐述 基于启 发式 算法和基 于直接寻查法 ¨的可重构性指标 分配方 法 ，最后将 两种 不 同方 法 用于 系统 仿 真并 比较 实 际结果 .

2．1 基于启发式算法的可重构性指标分配对于一个由 k个分 系统 串联组成的系统 ，基 于启发式算法的可重构性指标分配流程如图 3所示.

图 3 基 于启发式算法 的可重构性指标分配流程图Fig．3 Flow diagram of reconfigurabm ty alocation· 10· 空间控制技术与应用结合 图 3，基于启发式算法 的可重构性指标分配方法叙述如下 ：步骤 0：为 系统 找 到一个 可 行解 = ( 。， ，? ，^)；步骤 1：确定系统第 t种资源的剩余量 s =b 一∑g ( )，6 表示第 种资源的上限．如果某个t使得 s =0，则进入步骤 3；否则 ，找 出非饱和阶段 的子集 U( )= {i：

其 中，n重可重构度分配下第 i个分系统的敏感 因子为F ( )=[n+Ri( +n)一∑Ri( +p)][ +P =U(1一 )rain Ax ] (4)其中，i=(1， )，P是第 i个分系统冗余数 ， ，P为正整数·△ =min ， (0< < )是一个平衡系数 ，根据实际情况选取.

敏感因子是一个反映分系统增加冗余对系统影响的指标 ，当某个分系统敏感因子最大时，表明在该分系统增加冗余对于整个系统而言是最有利 的．由于敏感因子是比较不同分系统之间增加冗余优先程度的指标 ，同时为防止 出现某个分 系统 因为初 始敏感因子最大而总在该分系统增加冗余的现象，所以规定敏感因子必须大于 0，且必须是递减 函数．下面给出定理及证明过程.

定 理 2．敏 感 因子 F ( ) = [n+R ( +n) 一Ri( +p)][ △ +( 一 Axm]为递减函数且始终大于 0.

证明．首先证 明敏感因子大于 0．因为 R (z +P)<1，所以n一∑Ri( +p)>0．所以n+Ri( +n)P =U一 R ( +p)>0·又由于 △ >0且)
△ m>0，所以 △ +(1一 ) ra
?
in
、
△ >0，因此 F ( )> 0 .

其次证明敏感 因子是一个 递减 函数．假 设第 i个分系统增加一个冗余后的敏感因子为F：( )，则F ( )=[n+Ri( +1+n)一∑Ri( +1+P =UP)][ △ +(1一OL) rain△ ]，由于 Ax =rain，当第 个分系统增加冗余时，资源的剩余量减少 ，即 S ． ．
in Ax < rain Ax ．所 以 △ +(1—5 E u( ) m E “( )13／) rain△ < △ +(1一 ) rain Axm，即 (△一 Ax )+(1一O／)(ra． ．in△ 一 rain Ax )<0.

s∈U( ) m ∈U( )由于分系统部件数至少为 1，即 ≥ 1．因为冗余部件采用并联的安装方式 ，冗余数为 n的分系统已经饱和 ，则 R ( +n)=1．由于 R ( +n+1)≥( +n)，且 R ( +1+n)≤1，所 以R ( +1+n)=1．故 R ( +1+n)一尺 ( +n)=0．由第 1节可知 ，分系统 i的可重构度 R ( +1+P)>R (+p)．故∑Ri( +1+p)>∑Ri( +p)，所以P=0 D =0∑Ri( +p)一∑Ri( +1+p)<0．因此有P =0 P =0F ( )一F( )= { (Ax 一Ax )+(1一 )[ra
—
in△ 一 rain Ax ]}×E ( ) ，n∈“( )[Ri( +1+n)一∑Ri( +1+p)一P =UR ( +n)+∑Ri( +p)]p =u= { (Ax —Ax )+(1一O1)[rain Ax 一min△ ]}×∈u(x) m ∈ ( )[∑Ri( +p)一∑R ( +1+p)]<0.

P =0 P= 0所 以 F ( )

在计算敏感 因子时，有 时会 出现两个或更多分系统敏感因子相等的情况，理论上增加任何一个分系统的冗余都是可以的．然而 ，实际中我们希望尽量多的阶段具有重构的能力或者改善重构能力差的阶段 ，所以规定当有两个或多个分 系统的敏感 因子相等时，在可重构度最小的阶段增加冗余部件.

2．2 基于直接寻查法的可重构性指标分配在以往有约束条件的指标最优分配方法中，直接寻查法因为计算量少并能获得接近系统最优值的解 ，所以应用广泛 ，是最具有代表性 的一种．基于直接寻查法的可重构性指标分配的思路是改善可重构度最小的分系统，每次在可重构度最小的环节增加冗余.

第5期 项昌毅等：基于启发式算法的可重构性指标分配具体做法是设系统 的每一个 串联单元均没有冗余 ，即 { 、， ，? ， }= {1，1，?，1}，计算 比较每个分系统的可重构度，每次在系统可重构度最小的一 级上加入一个冗余单元 ，并检查约束条件．在约束条件允许范围内，通过一系列试探 ，可以使系统可重构度接近最大值．约束条件为 ： ≠0，t=1，2，3，其中，s，表示第 t种资源剩余量.

3 系统可重构性指标分配仿真由于实际系统较高的可靠性 ，同时出现多个部件故障的概率较小，故仿真计算时只考虑二重故障，其他多重故障可重构性指标分配的原理步骤与二重故障类似．为了评价一个系统的资源消耗 ，通常考虑重量 、能耗和成本等 3个经济指标 ，本章仿真时将这3个指标作为约束条件.

3．1 基于启发式算法的可重构性指标分配仿真有一个 系统 由 5个分 系统 串联组成 ，二重故障下系统的敏感因子计算公式为F ( )= [2+R ( +2)一R ( +1)一R；( )][aAx +(t一 ) ra
～
in Ax ].

给定系统各分系统 部件 的重量 、能耗和成本如表 1所示 .

其 中，t=1，2，3分别表示重量 、能耗和成本．给定系统的资源上限 b ：b。=40，b：=32，b，=30.

根据启发式算法的步骤 ，首先选取 系统初始方案．取无冗余 的最低配置为初始方案 ： = (1，1，1，1，1)．此时，资源剩余量 s =24，S =20，s，=18.

表 1 分 系统 部件 的资源消耗Tab．1 Resource consumption of components221分配方案 =(1，1，1，1，1)对应 的非饱和阶段集合是 U( )：{1，2，3，4，5}．为了计算分系统 i的敏感因子 F ( )，首先需要对所有的 i U(X)计算△ 和 2+R ( +2)一R ( +1)+R ( )的值 ，这时有 = 去 =min{ ， ，萼}=4．5.

同样 可 计 算 ：△ 2 = 6，Ax3 = 9，△ 4 = 8，Ax5 =10 .

因此 ，min△ =min{4．5，6，9，8，10}：4．5.

当 i∈ U( )，2+尺 (3)一R (2)一R (1)=3.

因此， ：0．5时所有非饱和阶段的敏感 因子为 ：F ( ) = 13．50，F ( ) = 15．75，F3( ) =20．25，F ( )=18．75，F ( )=21．75.

由于分系统 5给出了最大的敏感因子 ，所 以对从 1增加到 2． =0．5的迭代结果 由表 2给出.

由表 2可知 ， =0．5时，基于启发式算法的可重构性指标分配方法得 到的解是 (2，2，3，3，3)．相应的系统可重构度为 0．9744．顺便提及，当 取其他值时 ，所得到的最优分配方案不变 ，但是最优分配的排列顺序不一样.

表 2 迭代结果Tab．2 Iteration results分配方案剩余 资源 敏感因子20．2519 l2501810．596．72．6251．125b敏感因子的最大值 ；h资源饱和阶段3 l 2 2 2 2 4 3 3 5 4 41 2 3 6 b 3 5 订 ；8 b ～ 一4 b 4 1 4 l 2 6 5 ¨ 9 b 1 5" 9 7 3 ●加 B 4加 ¨ 9 4^ ， 、 ^ i ^ ^ ^ 1 2 3 3 3 3 3 3 3 ， ， ， ， ， ， ， ， ， 1 1 1 1 2 2 2 2 3 ， ， ， ， ， ， ， ， ， l 1 l 2 2 2 3 3 3
， ， ， ， ， ， ， ， ， l l l 1 l 2 2 2 2 ， ， ， ， ， ， ， ， ， l 1 l 1 l 1 l 2 2 } l l · 12· 空间控制技术与应用 39卷3．2 基于直接寻查法的可重构性指标分配仿真如 2．2节所述 ，基于直接寻查法的可重构性指标分配的思想是改善可重构度最小的分系统(薄弱环节)，以此提高系统的可重构度．首先取无冗余的最低配置为初始解 =(1，1，1，1，1)，此时 s．=24，S，=18， = 1 8．计 算 5个 分 系统 的可重 构度 ：R = ，=R =R =R =0．由于分系统可重构度相等 ，依据直接寻查法的思想 ，对任何分系统增加冗余部件都是一样的，这里首先增加第一个分系统．检查约束条件 ：s．：19，s 2：14，s3=14.

重复上述计算过程 ，可得 R，=R =R ：R =R =0．由于各分系统敏感 因子相等，继续选择在第一个分系统增加冗余，此时s，=14，s =10，s =10．按照上面的算法继续进行，直到约束条件不满足．当所以分系统冗余数都小于 2时 ，则所有分系统的可重构度都 为 0，以至于无法判断在哪个分系统增加冗余 ，导致分配结果不唯一．取定其中一种可能配置z=(3，3，2，2，1)，此时资源剩余量为：S．=1，，=3， =0．该配置的可重构度为 0．9636.

比较本文两种不同可重构性指标分配方法的分配结果 ，由于 0．9744>0．9636，所以基于启发式算法的可重构性指标分配较基于直接寻查法更有效.

4 结 论本文针对考虑部件故障的系统可重构性设计问题 ，提出一种基于启发式算法的可重构性指标分配方法，通过比较不同分系统敏感因子的大小，在敏感因子最大的一级增加冗余 ，系统仿真计算验证了方法的有效性．该方法不仅考虑 了增加冗余对于系统可重构度的影响，同时也考虑了资源的消耗，相对于基于直接寻查法的可重构性指标分配方法具有一定的优越性．由于启发式算法的计算量少并能获得理想的分配结果 ，对于工程领域处理 串联系统冗余分配的问题具有一定的应用价值.

[2]参 考 文 献Yang H，Jiang B，Staroswiecki M．Fault recoverabilityanalysis of switched systems『J]．International Journalof Systems Science，2012，43(3)：535—542刘阶萍，罗振璧，陈恳，快速可重组制造系统的可诊断性设计 原 理 [J]．清华 大 学学 报 (自然 科 学版 )，2000，40(9)：14-17[3][4][5][6][7][8][9][10]I iu J P．Luo Z B，Chen K．The diagnostic design prin—ciples of fast reconfigurable manufacturing system[J].

Journal of Tsiughua University ：Science and Technolo—gY，2000，40(9)：14—17罗振璧 ，于学军，刘阶萍．可重构性和可重构设计理论[J]．清华 大学学 报 (自然科学版 )，2004，44(5)：577-580Luo Z B，Yu X J，Liu J P．Reconfigurahtlity and recon—figurable design theory[J]．Journal of Tsinghua Univer-sity：Science and Technology，2004，44(5)：577—580Kuo W，Prasad Rajendra V．Optimal reliability design：fundamentals and applications[M]．Ox~rd city：Cam-bridge University Press，200 1Liang Y C．Smith A E．An ant colony optimization algo—rithm for the redundancy alocation problem (RAP)[J]．IEEE Transactions on Reliability，2004，53(3)：417_423Ramirez—Marquez J E．Coit D W．A heuristic for solvingthe redundancy allocation problem for multi·-state series·-paralel systems[J]．Reliability Engineering＆ SystemSafety，2004，83(3)：341—349Chern M S．On the computational complexity of reliabil-ity redundancy allocation in a series system[J]．Opera—tions Research Leters，1992，11(5)：309—315Tvsersky A，Kahneman D．Judgment under uncertainty：heuristics and biases[J]．Science，l974，185(4l57)：1124—1131Sharma J．Venkateswaran K V． A direct method formaximizing the system reliability[J]．IEEE Transac—tions on Reliability，1971，R一20(20)：256—259Nakagawa Y ，Nakashima K．A heuristic method for de—termining optimal reliability alocation[J]．IEEE Trans-actions on Reliability，1977，R一26(26)：156-161Chen C L，Chen N．Direct search method for solving C-conomic dispatch problem considering transmission ca—pacity constraints[J]．IEEE Transactions on Reliabili—ty，2001，16(4)：764—769作者简介 ：项 昌毅 (1988一 )，男 ，硕士研究 生 ，研 究方向为故障诊 断 与容错 控制 ；杨 浩 (1982一 )，男 ，硕士生导师，研究方向故障诊断与容错控制；程月华(1977一 )，女 ，助理 研究 员 ，研 究方 向为卫 星故 障诊断与可靠控制研究；姜 斌 (1966一)，博士生导师，研究方向为故障诊断与容错控制；刘成瑞(1978一)，男，高级T程师，研究方向为航天器故障诊断与可靠性研究 .