ADAPTIVE RANKS CLONE AND k‐NEAREST NEIGHBOR LIST–BASED IMMUNE MULTI‐OBJECTIVE OPTIMIZATION

Artificial immune systems (AIS) are computational systems inspired by the principles and processes of the vertebrate immune system. The AIS‐based algorithms typically exploit the immune system's characteristics of learning and adaptability to solve some complicated problems. Although, several AIS‐based algorithms have proposed to solve multi‐objective optimization problems (MOPs), little focus have been placed on the issues that adaptively use the online discovered solutions. Here, we proposed an adaptive selection scheme and an adaptive ranks clone scheme by the online discovered solutions in different ranks. Accordingly, the dynamic information of the online antibody population is efficiently exploited, which is beneficial to the search process. Furthermore, it has been widely approved that one‐off deletion could not obtain excellent diversity in the final population; therefore, a k‐nearest neighbor list (where k is the number of objectives) is established and maintained to eliminate the solutions in the archive population. The k‐nearest neighbors of each antibody are founded and stored in a list memory. Once an antibody with minimal product of k‐nearest neighbors is deleted, the neighborhood relations of the remaining antibodies in the list memory are updated. Finally, the proposed algorithm is tested on 10 well‐known and frequently used multi‐objective problems and two many‐objective problems with 4, 6, and 8 objectives. Compared with five other state‐of‐the‐art multi‐objective algorithms, namely NSGA‐II, SPEA2, IBEA, HYPE, and NNIA, our method achieves comparable results in terms of convergence, diversity metrics, and computational time.     

An event‐flow model of GUI‐based applications for testing

Graphical user interfaces (GUIs) are by far the most popular means used to interact with today's software. The functional correctness of a GUI is required to ensure the safety, robustness and usability of an entire software system. GUI testing techniques used in practice are resource intensive; model‐based automated techniques are rarely employed. A key reason for the reluctance in the adoption of model‐based solutions proposed by researchers is their limited applicability; moreover, the models are expensive to create. Over the past few years, the present author has been developing different models for various aspects of GUI testing. This paper consolidates all of the models into one scalable event‐flow model and outlines algorithms to semi‐automatically reverse‐engineer the model from an implementation. Earlier work on model‐based test‐case generation, test‐oracle creation, coverage evaluation, and regression testing is recast in terms of this model by defining event‐space exploration strategies (ESESs) and creating an end‐to‐end GUI testing process. Three such ESESs are described: for checking the event‐flow model, test‐case generation, and test‐oracle creation. Two demonstrational scenarios show the application of the model and the three ESESs for experimentation and application in GUI testing. Copyright © 2007 John Wiley & Sons, Ltd.     

敏感变量和感知机结合的测试预言生成方法

测试预言生成技术是软件工程测试领域的研究热点之一.没有可以利用的历史测试用例是目前大部分测试预言生成技术的普遍假设，但是这种假设会使我们错过利用现有部分测试用例协助自动生成新测试用例预言的机会.在已知部分测试用例集的情况下，提出了基于敏感变量和线性感知机的新测试用例的测试预言自动生成方法.首先，收集已知测试用例执行的语句覆盖和不同断点处内存值集合作为训练集，计算与新测试用例执行覆盖信息高度相似的测试用例集；其次，计算各断点处表征成功或失败的敏感变量集；然后，应用线性感知机求解每个断点处成功或失败概率预测的门限值；在此基础上，给出新测试用例测试预言自动生成的方法，并对方法进行讨论；最后，采用7个程序的129个故障版本作为实验对象，对共计14 300个测试用例生成测试预言.实证评价表明，测试预言准确率平均达到96.2%.该成果可以形成测试用例集合构造的"滚雪球效应"，不断迭代自动生成新测试用例的测试预言.     

On the use of a similarity function for test case selection in the context of model‐based testing

Test case selection in model‐based testing is discussed focusing on the use of a similarity function. Automatically generated test suites usually have redundant test cases. The reason is that test generation algorithms are usually based on structural coverage criteria that are applied exhaustively. These criteria may not be helpful to detect redundant test cases as well as the suites are usually impractical due to the huge number of test cases that can be generated. Both problems are addressed by applying a similarity function. The idea is to keep in the suite the less similar test cases according to a goal that is defined in terms of the intended size of the test suite. The strategy presented is compared with random selection by considering transition‐based and fault‐based coverage. The results show that, in most of the cases, similarity‐based selection can be more effective than random selection when applied to automatically generated test suites. Copyright © 2009 John Wiley & Sons, Ltd.     

基于维持种群多样性的测试数据生成算法的研究

测试数据自动化生成技术尝试寻找一个相对小的数据集来满足测试充分性标准,以降低软件测试的成本,提高测试效率.当测试项的数据集大小超过其上限时,算法会使用淘汰算法把差异性较小的测试数据从集合中淘汰掉,把差异性较大的测试数据留下来,以维持种群的多样性.针对此问题,提出一种基于维持种群多样性的演化算法来求解测试数据集,算法利用启发信息迭代地选择一个条件?判定语句作为子目标,通过演化算法生成数据以覆盖目标.在此算法框架内,利用一种新的计算评估值的方法计算数据与测试项的距离信息;以及利用归一的曼哈顿距离计算测试数据差异性,通过淘汰策略把差异性较小的测试数据淘汰掉.在实验中,对14个计算机科学基础算法的基准函数进行了测试,并与现有文献中的测试数据生成方法进行对比,验证了算法有效提高了条件?判定覆盖率,并且减少了测试数据的生成数量,提高了测试性能.     

Using program data-state scarcity to guide automatic test data generation

Finding test data to cover structural test coverage criteria such as branch coverage is largely a manual and hence expensive activity. A potential low cost alternative is to generate the required test data automatically. Search-based test data generation is one approach that has attracted recent interest. This approach is based on the definition of an evaluation or cost function that is able to discriminate between candidate test cases with respect to achieving a given test goal. The cost function is implemented by appropriate instrumentation of the program under test. The candidate test is then executed on the instrumented program. This provides an evaluation of the candidate test in terms of the “distance” between the computation achieved by the candidate test and the computation required to achieve the test goal. Providing the cost function is able to discriminate reliably between candidate tests that are close or far from covering the test goal and the goal is feasible, a search process is able to converge to a solution, i.e., a test case that satisfies the coverage goal. For some programs, however, an informative cost function is difficult to define. The operations performed by these programs are such that the cost function returns a constant value for a very wide range of inputs. A typical example of this problem arises in the instrumentation of branch predicates that depend on the value of a Boolean-valued (flag) variable although the problem is not limited to programs that contain flag variables. Although methods are known for overcoming the problems of flag variables in particular cases, the more general problem of a near constant cost function has not been tackled. This paper presents a new heuristic for directing the search when the cost function at a test goal is not able to differentiate between candidate test inputs. The heuristic directs the search toward test cases that produce rare or scarce data states. Scarce inputs for the cost function are more likely to produce new cost values. The proposed method is evaluated empirically for a number of example programs for which existing methods are inadequate.     

Engineering an efficient two‐phase local search algorithm for the co‐rotating twin‐screw extruder configuration problem

The twin‐screw configuration problem arises during polymer extrusion and compounding. It consists in defining the location of a set of pre‐defined screw elements along the screw axis in order to optimize different, typically conflicting objectives. In this paper, we present a simple yet effective stochastic local search (SLS) algorithm for this problem. Our algorithm is based on efficient single‐objective iterative improvement algorithms, which have been developed by studying different neighborhood structures, neighborhood search strategies, and neighborhood restrictions. These algorithms are embedded into a variation of the two‐phase local search framework to tackle various bi‐objective versions of this problem. An experimental comparison with a previously proposed multi‐objective evolutionary algorithm shows that a main advantage of our SLS algorithm is that it converges faster to a high‐quality approximation to the Pareto front.     

A taxonomical analysis,current methods and objectives on location‐routing problems

Location‐routing is a branch of locational analysis that takes into account distribution aspects. This paper proposes a taxonomy, with two levels, for location‐routing problems. The first level focuses on the structural characteristics of the problems. The second level branches into the different algorithmic approaches and objective perspectives. An introduction to the previously defined problems is presented, categorising the papers in the literature (a total of 149 references) according to the proposed classification. Moreover, an overview of the most significant aspects of the different solution methods and main objectives, with special emphasis on multi‐objective approaches, is provided. Some data providing a better insight into the publication progress are also included. Finally, several promising research directions are identified.     

MRMOGA: a new parallel multi‐objective evolutionary algorithm based on the use of multiple resolutions

In this paper, we introduce MRMOGA (Multiple Resolution Multi‐Objective Genetic Algorithm), a new parallel multi‐objective evolutionary algorithm which is based on an injection island approach. This approach is characterized by adopting an encoding of solutions which uses a different resolution for each island. This approach allows us to divide the decision variable space into well‐defined overlapped regions to achieve an efficient use of multiple processors. Also, this approach guarantees that the processors only generate solutions within their assigned region. In order to assess the performance of our proposed approach, we compare it to a parallel version of an algorithm that is representative of the state‐of‐the‐art in the area, using standard test functions and performance measures reported in the specialized literature. Our results indicate that our proposed approach is a viable alternative to solve multi‐objective optimization problems in parallel, particularly when dealing with large search spaces. Copyright © 2006 John Wiley & Sons, Ltd.     

Multi‐Objective Cost‐Detectability in Unfalsified Adaptive Control

Vector‐valued controller cost functions that are solely data‐dependent and reflect multiple objectives of a control system are examined within the framework of unfalsified adaptive control. The notion of Pareto optimality of vector‐valued cost functions and the conditions under which they are cost‐detectable are discussed. A sampled data/discrete‐time Level‐Set controller switching algorithm is investigated which allows for the relaxation of the assumption that the controller cost function be monotonically nondecreasing in time. This opens up the possibility of the use of fading memory cost functions which are nonmonotone. When an active controller is falsified at the current threshold cost level, the Level‐Set switching algorithm replaces it by an effectively unique solution of the weighted Tchebycheff method, thus ensuring the selection of an unfalsified Pareto optimal controller. Theoretical results for convergence and stability of the adaptive system are given. Simulation results validate the use of cost‐detectable multi‐objective cost functions. An example of a cost‐detectable cost function which uses fading memory norm of the fictitious tracking error as a performance measure is shown. This allows for computation of performance of nonactive controllers with respect to a reference model.