基于演化优化的系统可靠性设计

论文摘要

自六十年代以来,在电力系统、电子系统、软硬件等系统设计中,可靠性作为一个重要指标地位愈发突出,系统可靠性设计（system reliability design,SRD）也吸引了越来越多的科研工作者。近些年来,伴随着工业化进程中系统规模的不断扩大,如何设计更加可靠的系统已变得越来越重要。为了改进系统的可靠性,有两类问题需要更加有效地解决:一类是冗余分配问题（redundancy allocation problem,RAP）;另一类是测试资源分配问题（testingresource allocation problem,TRAP）。在本论文中,我们用演化算法更好地解决了这两类问题中的两个难点问题,分别是多层冗余分配问题（multi-levelredundancy allocation problem,MLRAP）和多目标测试资源分配问题（multi-objective testing resource allocation problem,MOTRAP）。在过去的三十年里,冗余分配问题因其在各种系统中的应用价值得到了广泛关注。在冗余分配问题的研究中,绝大部分是以单层系统为研究对象。但是现实的系统一般包含了多个层次,从最高的系统层到最低的单元层。因此,研究多层冗余分配问题变得十分重要。在本论文之前解决多层冗余分配问题的算法中,缺乏细致的局部搜索过程。为了更进一步地细致地探索解空间,我们设计了一个模因演算法（memetic algorithm）。作为演化算法的分支,模因演算法是结合了全局搜索策略和局部启发探索策略的群体搜索混合启发式方法。模因演算法已经被证实在解的质量和搜索能力上比传统的演化算法具有优势。我们在工作中,基于变量的分层属性表示,首先设计了两个宽度优先的演化算子（宽度优先交叉算子和宽度优先变异算子）以及针对问题的局部搜索算子,然后将这些算子结合到模因演算法框架中,从而得到一个新颖的模因演算法。我们的模因演算法在性能上要比以往的其它算法中的的最好算法（分层遗传算法）有明显的性能提升。在多层系统中,冗余度可以分配到任意层次上去,因此问题的解空间比单层冗余分配问题要大很多。通过对现存分层遗传算法和模因演算法的解的结构分析,我们可以看出这两个算法的搜索区域是局限在某个局部范围内的,也就是说,这两个算法的全局搜索能力较差。因为多层冗余分配问题的解空间十分巨大,约束控制能力将是解决此类问题的关键,同时如何快速地收敛到有潜力的区域也是全局搜索的根本要求。为了使我们的搜索过程更加高效,我们为潜力区域外的解设计了一个全局修复算子（global repair operator）。通过实验可以证明,这个专门的约束处理方法可以明显提升在我们的工作之前存在的最好算法（分层遗传算法）的全局搜索能力。随后,我们将全局修复算子融入到我们的模因演算法中,得到一个新的算法,叫作全局修复模因演算法（GRO+MA）,这个新算法在多个系统上被证实是在现存的算法中最优的算法。在有效地解决了困难的多层冗余分配问题后,我们关注系统设计中的另一个重要问题,测试资源分配问题（testing resource allocation problem）。我们把软件系统作为本文的研究模型。今天,伴随着软件系统的复杂度和规模的不断提升,如何合理分配有限的测试资源变得愈发重要和困难。传统的测试资源分配问题只考虑一个目标（可靠度值或测试代价）。在本文中,测试资源分配问题被定义为两个多目标问题:第一个是同时考虑可靠度值和代测试价;第二个是在第一个的基础上考虑总的资源消耗。在定义问题后,我们在两个软件系统上用一个著名的多目标演化算法,即第二代非支配排序演化算法（NondominatedSorting Genetic Algorithm II,NSGA-II）去解决定义的多目标问题。但是,实验结果告诉我们NSGA-II并不能很好地解决第二类多目标问题。因此,我们进一步设计了一个基于调和距离的多目标演化算法（Harmonic Distance BasedMulti-Objective Evolutionary Algorithm,HaD-MOEA）。通过在三个串并行系统和一个星状系统上的实验可以证明,多目标演化算法优于单目标演化算法,同时调和距离多目标演化算法优于第二代非支配排序演化算法。

论文目录

• 摘要
• ABSTRACT
• 表格
• 插图
• 主要符号对照表
• 第一章 绪论
• 1.1 系统可靠性设计问题概述
• 1.1.1 冗余分配问题描述
• 1.1.2 测试资源分配问题描述
• 1.2 系统可靠性设计问题的研究现状
• 1.2.1 冗余分配问题的研究现状
• 1.2.2 测试资源分配问题的研究现状
• 1.3 工作概述
• 1.4 原创性贡献
• 第二章 基于模因演算法的多层系统冗余分配
• 2.1 多层冗余分配问题
• 2.1.1 问题定义
• 2.1.2 问题难点
• 2.2 分层遗传算法（HGA）
• 2.3 模因演算法描述
• 2.4 在多层可靠性系统上的模因演算法（MA）
• 2.4.1 解的表达和评估
• 2.4.2 解的初始化
• 2.4.3 交叉变异算子
• 2.4.4 局部搜索算子
• 2.5 实验分析
• 2.5.1 实验设置
• 2.5.2 HGA 与MA 的性能比较结果
• 2.5.3 讨论
• 2.6 本章小结
• 第三章 基于容量约束处理的多层系统冗余分配
• 3.1 容量约束处理
• 3.1.1 传统约束处理方法
• 3.1.2 在多层系统冗余分配问题中的容量约束处理策略
• 3.1.3 一个新颖的全局修复算子（GRO）
• 3.2 基于GRO 的多层系统冗余分配算法
• 3.2.1 基于GRO 的分层遗传算法（HGA+GRO）
• 3.2.2 基于GRO 的模因演算法（MA+GRO）
• 3.3 实验分析
• 3.3.1 实验设置
• 3.3.2 HGA，MA，HGA+GRO 和MA+GRO 的综合性能比较
• 3.3.3 讨论
• 3.4 本章小结
• 第四章 基于多目标思想的测试资源分配
• 4.1 多目标测试资源分配问题定义
• 4.1.1 在串并行模块软件系统上的问题定义
• 4.1.2 在星状结构模块软件系统上的问题定义
• 4.2 重温演化多目标优化
• 4.3 演化多目标算法在多目标测试资源分配问题上的求解
• 4.3.1 第二代快速排序演化算法（NSGA-II）
• 4.3.2 基于调和距离的多目标演化算法（HaD-MOEA）
• 4.3.3 在多目标测试资源分配问题上的实现细节
• 4.4 实验分析
• 4.4.1 多目标演化算法与单目标演化算法的实验比较
• 4.4.2 HaD-MOEA 与NSGA-II 的实验比较
• 4.5 本章小结
• 第五章 结论
• 5.1 工作总结
• 5.2 研究成果
• 5.3 未来方向
• 参考文献
• 致谢