基于进化算法的软件测试数据生成的自动化

介绍了进化算法在测试数据生成中的应用思想，分析了在不同的覆盖准则下应用进化算法时适值函数的设计方法，把遗传算法等进化算法应用到测试数据生成中的进化测试技术，克服了局部搜索算法无法为较复杂程序的分支生成测试输入的问题。     

基于节点概率的路径覆盖测试数据进化生成

路径覆盖是软件测试领域重要的测试方法之一.为了提高路径覆盖测试效率,在采用遗传算法进化生成路径覆盖的测试数据过程中,利用被测程序条件语句的相关性判定不可达路径,除路径中必经节点外,其他节点在不可达路径中出现的概率越大,穿越该节点的个体就具有越高的穿越度,在进化过程中应得到保护.提出了根据个体的穿越度设计适应度函数方法,从而提高测试数据的生成效率.将所提方法应用于基准程序和工业用例,并与同类方法比较可知,该方法生成路径覆盖的测试数据具有较高的效率.     

基于非结构化控制流的进化测试方法

结构性测试中,进化测试是一种高效的自动生成高质量测试用例的技术.然而,当程序中出现非结构化特征时,在面向节点的测试标准下,其效率极其低下甚至不及随机测试生成方法.在考虑循环体内部出现跳转(goto、retum)语句的情况下,提出了一种适应度计算方法.该方法在结合传统进化测试适应度计算的基础上,充分考虑了循环次数对于进化搜索的影响.实验结果表明,本适应度函数可以很好地引导进化搜索,并以较小的代价生成测试用例.     

基于贪婪-改进果蝇算法的无线传感器网络路由协议

针对无线传感器网络(WSNs)中簇首选择和传输问题,基于贪婪和改进果蝇算法提出一种新型网络路由协议CRP-FOAGA.该协议结合节点位置和剩余能量建立适值函数,通过改进果蝇算法实现适值函数的最优求解,利用贪婪算法实现簇头节点的多跳传输.仿真结果表明:该算法合理规划了簇头节点分布,降低了网络能耗,提升了网络的寿命,具有更好的性能.     

WSNs能量异构节点部署与区域覆盖优化

针对无线传感器网络（WSNs）的热点区域问题所导致的节点能量异构、能量空洞等问题,对网络进行重新部署以满足区域覆盖的要求。建立WSNs能量异构节点区域覆盖优化模型,以网络覆盖率为目标函数,节点位置作为决策变量,采用差分进化算法优化该目标,同时获得各节点的最佳位置。仿真实验表明：该模型能充分调度各节点的剩余能量,对热区问题导致的能量空洞进行重新部署,该策略能够延长网络的生命周期,提高网络的可靠性。     

遗传算法适值函数定义方法的研究

在分析常规遗传算法缺陷的基础上,指出了遗传算法中适值函数定义方法对遗传计算过程的影响很大,并通过构造一种新的适值函数定义方法－－适值比值自调整适值函数在一定程度上解决了此问题,仿真实例证明了该方法的有效性。     

基于遗传粒子群混合算法的测试节点优选方法研究

随着电子技术的大规模发展,电路可靠性要求逐步提高,电路板测试诊断的重要性日益凸显;如何寻求最佳的测试节点或测试矢量集是电路的故障诊断中的重要问题,提出一种基于遗传粒子群优化算法对测试节点进行优化选择.该方法通过建立电路测试节点的"故障-测试"矩阵,用遗传算法对数学模型的进行优化,并采用粒子群算法搜索实现了快速求解;与传统方法相比较,该方法搜索速度快,优化效果明显,已在工程实践中得到应用.     

基于改进双系统协同进化算法的无线传感器网络节点定位

为进一步提高无线传感器网络(WSN)中节点的定位精度,提出了一种双系统协同进化(BCO)算法。改进算法利用粒子群优化(PSO)算法快速收敛的特性和混合蛙跳算法(SFLA)较高的寻优精度的特性,在较少的迭代次数内快速收敛且实现深度搜索达到较高的精度。仿真实验结果表明:在应用双系统协同进化算法对测试目标函数进行求解时,能非常接近最优解;同时将该算法应用到基于接收信号强度值(RSSI)测距的节点定位中,预测位置与实际位置的绝对误差在0.05 m范围内;相比基于RSSI的分步粒子群算法(IPSO-RSSI),其定位精度至少提高了10倍。     

支持测试节点按需调整的分布式测试调度模型

针对分布式测试系统动态调整测试节点能力差、测试总体效率低的问题,提出一种实用的支持测试节点按需调整的分布式测试调度模型。该模型利用M/M/N排队理论描述分布式测试任务到达和处理的概率分布,提出待处理强度指标来动态调配测试节点,基于此建立任务调度数学模型,并利用0-1线性整数规划法求解,实现了分布式测试执行时间最短的目的。仿真实验结果证明,该模型可以根据测试需求的变化动态调整测试节点数量,利用简单实用的调度方法,有效地降低测试节点负载,提高了测试效率。     

无线传感网中基于和声搜索和局部搜索的节点定位问题的研究

准确的节点定位信息对于无线传感网中收集重要数据是必须的。基于有噪声的距离相关测量值对网络中所有未知定位节点的位置进行评估,该评估通常由于网络可能不是唯一可定位的事实而进一步加重。为了有效地处理该问题,提出一种新的双目标定位方法,该方法基于和声搜索算法和局部搜索过程的组合。此外还利用基于连通性的几何约束来限制传感器节点可定位的区域。在标准化定位误差和三种多目标质量指标方面,所提方法用一种基于Pareto存档进化策略的元启发式定位方案,在不同网络配置中进行测试和比较。结果表明所提方案获得相当不错的精度,并在大多数情况下优于Pareto存档进化策略。     

一种新的软件测试数据的进化生成方法

测试数据自动生成对降低软件开发成本是非常重要的.本文首先提出了基于程序结构和程序规范相结合来设计适应度函数的新方法：分别设计基于程序结构和基于程序规范的适值函数,再将二者结合作为最终的适应度函数值;然后,在采用上述适应度函数定义的基础上,构造了一种软件测试数据的进化生成方法.     

基于函数级FPGA原型的硬件内部进化

电路进化设计是现阶段可进化硬件（EHW）研究的重点内容，针对制约进化设计能力的主要“瓶颈”，该文提出并讨论了一种简洁高效的内部进化方法，包括基于函数变换的染色体高效编码方案，与之配套的函数级FPGA原型和进化实验平台以及在线评估与遗传数自适应方法等，交通灯控制器，4位可级联比较器等相对复杂且具应用价值的电路的成功进化，证明该方法适用于组合，时序电路的进化设计，并可显著地减少运算量，提高进化设计的速度和规模。     

分层多目标最优化进化算法

文章用进化算法给出了求解二层字典分层多目标最优化的方法,该算法把求解问题转化为多目标最优化,并研究了这两个问题的解集之间的联系。对多目标最优化定义了一个新的选择算子和适应值函数,这样定义的选择算子和适应值函数结合均匀设计能有效地引导搜索,直接求出问题的解而不用逐层求解。数值模拟表明该方法十分有效。     

基于正交设计求解动态鲁棒问题的新算法*

设计了一个基于正交设计法求解动态鲁棒优化问题的新算法(RODEA).该算法把目标搜索区域划分成很多小邻域(小生境),每个小生境都有一个代表,对每个小生境用正交设计法(构造正交矩阵进行抽样)搜索可能成为小生境代表的潜在优解.还设计了一个基准测试函数用来测试动态鲁棒优化问题.实验数据表明RODEA用来求解动态鲁棒问题具有很好的效果.     

Multi-Objective Methods for Tree Size Control

Variable length methods for evolutionary computation can lead to a progressive and mainly unnecessary growth of individuals, known as bloat. First, we propose to measure performance in genetic programming as a function of the number of nodes, rather than trees, that have been evaluated. Evolutionary Multi-Objective Optimization (EMOO) constitutes a principled way to optimize both size and fitness and may provide parameterless size control. Reportedly, its use can also lead to minimization of size at the expense of fitness. We replicate this problem, and an empirical analysis suggests that multi-objective size control particularly requires diversity maintenance. Experiments support this explanation.The multi-objective approach is compared to genetic programming without size control on the 11-multiplexer, 6-parity, and a symbolic regression problem. On all three test problems, the method greatly reduces bloat and significantly improves fitness as a function of computational expense. Using the FOCUS algorithm, multi-objective size control is combined with active pursuit of diversity, and hypothesized minimum-size solutions to 3-, 4- and 5-parity are found. The solutions thus found are furthermore easily interpretable. When combined with diversity maintenance, EMOO can provide an adequate and parameterless approach to size control in variable length evolution.     

多路径覆盖测试数据生成适应度函数设计方法

综合考虑影响适应度函数设计的因素,提出一种基于层次分析法的适应度函数设计方法。该方法首先将影响路径之间相似度的因素归结为三要素,并建立层次分析模型。根据不同因素对路径间相似度的作用重要程度不同,建立因素之间两两比较的判断矩阵,确定每个因素的权重系数,进而构造适应度函数。最后,将该方法用于基于遗传算法的多路径覆盖的测试数据生成。实验结果表明,对于解决多路径覆盖的测试数据生成问题,与已有方法相比,该方法具有较好的优越性。     

基于控制流图支配树的测试数据灰度编码生成

为进一步提高数据测试算法性能,提出一种基于控制流图支配树的测试数据灰度编码进化生成算法。首先,利用三角分类程序示例构建数据测试的数据流控制流图,并利用其支配树关系构建测试数据的数据流分析,建立程序变量间的支配关系集;其次,结合遗传算法并利用支配关系及分支距离构建测试数据生成的适应值函数,同时在应用遗传算法时,采用灰度编码方式取代二进制编码,简化编码更新过程;最后,通过在测试程序样例中的实验对比显示,本文所提方法在测试性能上得到明显提升。     

Graph grammars for evolutionary 3D design

A new interactive evolutionary 3D design system is presented. The representation is based on graph grammars, a fascinating and powerful formalism in which nodes and edges are iteratively rewritten by rules analogous to those of context-free grammars and shape grammars. The nodes of the resulting derived graph are labelled with Euclidean coordinates: therefore the graph fully represents a 3D beam design. Results from user-guided runs are presented, demonstrating the flexibility of the representation. Comparison with results using an alternative graph representation demonstrates that the graph grammar search space is more rich in organised designs. A set of numerical features are defined over designs. They are shown to be effective in distinguishing between the designs produced by the two representations, and between designs labelled by users as good or bad. The features allow the definition of a non-interactive fitness function in terms of proximity to target feature vectors. In non-interactive experiments with this fitness function, the graph grammar representation out-performs the alternative graph representation, and evolution out-performs random search.     

An evolutionary‐based approach for dealing with numerical and categorical attributes in ILP

Inductive logic programming (ILP) induces concepts from a set of positive examples, a set of negative examples, and background knowledge. ILP has been applied on tasks such as natural language processing, finite element mesh design, network mining, robotics, and drug discovery. These data sets usually contain numerical and multivalued categorical attributes; however, only a few relational learning systems are capable of handling them in an efficient way. In this paper, we present an evolutionary approach, called Grouping and Discretization for Enriching the Background Knowledge (GDEBaK), to deal with numerical and multivalued categorical attributes in ILP. This method uses evolutionary operators to create and test numerical splits and subsets of categorical values in accordance with a fitness function. The best subintervals and subsets are added to the background knowledge before constructing candidate hypotheses. We implemented GDEBaK embedded in Aleph and compared it to lazy discretization in Aleph and discretization in Top‐down Induction of Logical Decision Trees (TILDE) systems. The results obtained showed that our method improves accuracy and reduces the number of rules in most cases. Finally, we discuss these results and possible lines for future work.