تست مورچه: رویکرد سیستم کلنی مورچه برای تست های متوالی تحت اولویت بندی محدودیت ها

We consider the problem of minimum cost sequential testing (diagnosis) of a series (or parallel) system under precedence constraints. We model the problem as a nonlinear integer program. We develop and implement an ant colony algorithm for the problem. We demonstrate the performance of this algorithm for special type of instances for which the optimal solutions can be found in polynomial time. In addition, we compare the performance of the ant colony algorithm with a branch and bound algorithm for randomly generated general instances of the problem. The ant colony algorithm is particularly effective as the problem size gets larger.

In its most general setting, the sequential testing problem requires the identification of the correct state of a system consisting of a number of components with the minimum expected cost. Different states of the system could correspond to different types of failures or working conditions. The state of the system depends on the state of the components via a certain structure function. Both the state of the system and the state of the components belong to discrete sets. For instance, if we have a reliability system, the individual components and the system could be in one of the two states, failing state or working state. In another context, the system could be in one of the many failure states or in working state. In order to learn the correct state of the system, one has to learn the states of a sufficiently large subset of the components, which requires costly tests. We also assume that we have apriori probabilistic information regarding the states of the components. Then the problem is to find a strategy that minimizes total expected cost of this process. A feasible strategy, in a sense, classifies the current state of the system in a deterministic manner, by learning the states of the individual component with the minimum expected cost. The general sequential testing problem arises in different application areas such as diagnosis problems (e.g. see Ruan et al., 2004 and Qiu and Cox, 1993), artificial intelligence problems (e.g. see Greiner et al., 2006 and Wang, 2005) etc. The sequential testing problem for series–parallel systems appears as a subproblem for a resource allocation problem for reliability systems in Azaiez and Bier (2007). In addition, there are many studies in the literature that theoretically work on the problem for special structure functions and for special cases of the input data regarding probability distributions and cost. Different application areas and results related to the general sequential testing problem can be found in Ünlüyurt (2004). In this particular study we consider the sequential testing problem of a series system under precedence constraints. A series system functions if all its components function. A feasible strategy tests the components one by one until a failing component is found or all components are tested. Consequently, a strategy for this particular system corresponds to a permutation of the components obeying the precedence constraints. In order to solve this problem, we propose an ant colony optimization (ACO) algorithm. We demonstrate the effectiveness of the proposed algorithm through an extensive experimental study. To the best of our knowledge, this is the first ACO algorithm proposed in the testing literature. Some preliminary results of this study were presented in Çatay, Özlük, and Ünlüyurt (2009). The rest of the article is organized as follows. In Section 2, we define the problem, provide a literature review and a mathematical model of the problem. In Section 3, we describe the proposed ACO algorithm. Section 4 outlines the greedy and the branch and bound (B&B) algorithms developed to test the performance of the proposed ACO algorithm. Section 5 is devoted to the experimental study. We conclude by discussing future research directions in Section 6.

In this paper, we presented TestAnt, an ACO algorithm designed for solving the sequential testing problem of a series system under precedence constraints. We demonstrated the efficiency of TestAnt by comparing its performance with those of Greedy and a B&B algorithm. The experiments performed on random instances showed that TestAnt produces good and robust results in relatively short computation times. The performance of TestAnt may be improved by developing a more efficient visibility function and implementing a different pheromone update mechanism. In addition, a local search algorithm may be utilized to further enhance the solution quality, if needed. The B&B algorithm could be developed further in terms of branching strategies and by different bounding schemes. From a computational point of view, effective and efficient heuristic algorithms are needed for k-out-of-n systems, which is a more general class of systems. To our knowledge, there are a few analytical results related to testing of k-out-of-n systems under precedence constraints; yet no computational results have been reported in the literature. In this case, the feasible solutions will not necessarily be described by a permutation but rather by binary decision trees. This will make it difficult to adapt the algorithms for the simple series case to k-out-of-n systems.