1 Introduction

The test point selection is becoming more and more important in analog circuit fault diagnosis nowadays. The analog circuit diagnosis methods are usually classified into two main categories [1–3]: the simulation before test (SBT) and the simulation after test (SAT) approach. Fault dictionary and probabilistic techniques fall into SBT, whereas optimization, fault verification, and parameter identification techniques fall into SAT [2]. Since each circuit under test (CUT) consists of more than two test points, especially for the medium and large scale circuits, it’s impractical and too expensive to test the responses of all the test points to diagnose the faulty circuit. At the same time, not every test point is measurable and some measurements are redundant. Therefore, the optimum selection of test points is especially significant.

The fault dictionary technique has been proven to be a very practical method in analog catastrophic fault diagnosis [3]. A fault dictionary is a set of measurements of the CUT simulated under potentially faulty conditions (including fault-free case) and organized before the test. The measurements could be at different test points, test frequencies, and sampling times [4, 5]. There are three important phases in the fault dictionary approach [5, 6]. First of all, a network is simulated for each of the anticipated faults (including fault-free case) excited by the chosen stimuli (dc or ac), and the signatures of the responses are stored and organized in the dictionary for use. The second phase is the selection of test points. An optimum selection of test points is the main work of this stage. By doing this, we can achieve the desired degree of fault diagnosis with less test points and save the fault test and diagnosis time greatly. The last phase is fault isolation. At the time of testing, the CUT is excited by the same stimuli that are used in constructing the dictionary, and measurements are made at the preselected test points. They are compared with the responses stored in the fault dictionary to identify the fault according to the preset criteria. This paper mainly focuses on the second phase.

The aim of the analog test point selection is to find the least number of test points that can isolate all the faults. Until now, lots of researchers have been studied in this area. Varghese et al. [7] proposed a heuristic method based on given performance indexes to find the sets of test points. Hochwald and Bastian [8] proposed the concept of ambiguity sets and developed logical rules to select the test points. Lin and Elcherif [3] first proposed the integer-coded dictionary to distinguish the ambiguity sets for analog test point selection. Spaandonk and Kevenaar [9] proposed to select the test-point set by combining the decomposition method of the system’s sensitivity matrix and an iterative algorithm. Prasad and Babu [6] proposed four algorithms based on three strategies of inclusive approach and three strategies of exclusive approach. Pinjala and Bruce [10] proposed a method to find the test point set by computing the information content of all the candidate test points. An entropy-based approach, using entropy index (EI) as a criterion to choose test points, was proposed by Starzyk et al. [4]. Golonek and Rutkowsk [11] used a genetic algorithm (GA) based method to determine the optimal set of test points. Yang and Tian [5] used the graph node search method to find the near minimum test-point set. Jiang et al. [12] proposed a multidimensional fitness function discrete particle swarm optimization (MDFDPSO) algorithm to optimize analog test point selection. Luo and Wang [13] used the extended fault dictionary and the overlapped area values together to select the optimum test points.

In 2010, Yang [14] proposed the bat algorithm (BA), which is a novel heuristic optimization algorithm based on the echolocation behavior of bats. The capability of echolocation of bats is so special and powerful that they can find their prey and discriminate different types of insects even in complete darkness. Preliminary studies suggest that the BA can have superior performance over particle swarm optimization (PSO) and genetic algorithms (GA) [14, 15], and can solve the real engineering optimization problems. In 2012, Nakamura et al. [16] introduced the first version of discrete binary bat algorithm (BBA) for feature selection. Ref. [17] proposed another binary version of the bat algorithm (BBA) and used it to deal with the optical buffer design problem.

On the other hand, the application of chaos in optimization algorithms has gained great success in many papers. In Ref. [18], chaotic sequences were used to tune parameter in genetic algorithm (chaos-genetic algorithm) to solve the scheduling problem. In Ref. [19], the authors introduced chaos into the accelerated particle swarm optimization (CAPSO) to further enhance the global search ability of the algorithm. The success of these combinations shows us that the right use of chaotic maps may improve the performance of the optimization algorithms.

Therefore, we introduce chaos into the BBA, and as a result, propose the chaotic binary bat algorithm (CBBA). Meanwhile, the elitist strategy is applied to the new proposed algorithm to store all the possible global best solutions, which can help to show the advantages of using chaos’ non-repetition and ergodicity in the new algorithm. In this paper, the new proposed CBBA is used to deal with the test point selection problem for the first time. Since different chaotic maps may lead to different behavior of the algorithm, we have constructed a set of CBBAs. In these algorithms, we use different chaotic maps to replace the corresponding parameter of BBA. In order to evaluate the proposed algorithms, two analog circuits’ examples and a group of statistical experiments are carried out, and the other reported test point selection algorithms are also applied to do the comparison.

Since about 90 % of all the analog faults found in practice are single catastrophic faults [5, 8], we deal with these most commonly encountered single catastrophic faults in analog circuits in this paper. Section 2 presents a brief introduction to BA and BBA. The chaotic maps used in our paper are illustrated in Sect. 3. Section 4 introduces the proposed CBBA and its application in analog test point selection problem. Two analog circuits’ examples and a group of statistical experiments are given in Sect. 5. Finally, brief conclusions and future research plan are given in Sect. 6.

The nomenclatures of this paper are as follows:

nj

The test point j

fi

The fault i

N

Number of all the test points

N s

Number of selected test points

M

Number of all the fault states (including fault-free case)

S

Number of separated CUT states

f i

Frequency of the i-th bat

f min

Minimum frequency

f max

Maximum frequency

A

Loudness of emitted sound

r

Pulse emission rate

T max

Maximum number of iterations

2 Bat algorithm (BA) and binary bat algorithm (BBA)

2.1 Bat algorithm (BA)

The bat algorithm was inspired by the echolocation behavior of bats [14]. In the real world, bats use this type of sonar (echolocation) to detect prey, avoid obstacles, and locate their roosting crevices in the dark. They can emit a very loud sound pulse and use their two ears to listen for the echo that bounces back from the surrounding objects. Bats calculate the time delay from emission and detection of the echo and the loudness variations of the echoes to build up three dimensional scenario of the surrounding. When the target is nearby, their pulse emitting rates increase and the frequency is tuned up. The frequency tuning and the speedup of pulse emission will shorten the wavelength of echolocations and thus increase accuracy of the detection. The BA was developed by using these pivotal factors. The standard BA is based on three idealized rules [14]:

  1. (1)

    All bats use echolocation to sense distance, and they also ‘know’ the difference between food/prey and background barriers in some magical way;

  2. (2)

    Bats fly randomly with velocity \(v_{i}\) at position \(x_{i}\) with a fixed frequency \(f_{\hbox{min} }\), varying wavelength \(\lambda\) and loudness \(A_{0}\) to search for prey. They can automatically adjust the wavelength (or frequency) of their emitted pulses and adjust the rate of pulse emission \(r \in [0,1]\), depending on the proximity of their target;

  3. (3)

    Although the loudness can vary in many ways, we assume that the loudness varies from a large (positive) \(A_{0}\) to a minimum constant value \(A_{\hbox{min} }\).

The basic pseudo code of the bat algorithm (BA) is summarized in Fig. 1. The technique is initialized with a swarm of bats collaborate together during the process to find the best solutions. In the BA, each bat (say \(i\)) has a defined position \(x_{i}\) and velocity \(v_{i}\) in a d-dimensional search space, and they are updated subsequently during the iterations. Initially, each bat is randomly assigned a frequency which is drawn from interval \([f_{\hbox{min} } ,f_{\hbox{max} } ]\). The new solutions \(x_{i}^{t}\) and velocities \(v_{i}^{t}\) at time step t can be calculated by [14]:

Fig. 1
figure 1

Pseudo code of the bat algorithm (BA) [14]

Full size image
$$f_{i} = f_{\hbox{min} } + (f_{\hbox{max} } - f_{\hbox{min} } )\beta$$
(1)
$$v_{i}^{t} = v_{i}^{t - 1} + (x_{i}^{t - 1} - x_{Gbest} )f_{i}$$
(2)
$$x_{i}^{t} = x_{i}^{t - 1} + v_{i}^{t}$$
(3)

where \(\beta \in [0,1]\) is a random vector drawn from a uniform distribution, \(x_{Gbest}\) is the current global best location (solution) which is located after comparing all the solutions among all the bats.

All these equations could guarantee the exploitability of the BA. However, a local search part procedure is also used to perform the exploitation. For this local search part, once a solution is selected among the current best solutions, a new solution for each bat is generated locally using random walk [14]:

$$x_{new} = x_{old} + \varepsilon A^{t}$$
(4)

where \(\varepsilon \in [ - 1,1]\) is a random number, \(A^{t}\) is the average loudness of all the bats at this time step.

It is worth pointing out that, to a degree, the BA can be considered as a balanced combination of the standard PSO and the intensive local search controlled by the loudness (A) and pulse rate (r). These two parameters are updated as follows [14]:

$$A_{i}^{t + 1} = \alpha A_{i}^{t} ,\;\;r_{i}^{t + 1} = r_{i}^{0} [1 - \exp ( - \gamma t)]$$
(5)

where \(\alpha\) and \(\gamma\) are constants. In the simplicity case, we can use \(\alpha = \gamma\) [14], and we have in fact used \(\alpha = \gamma = 0.9\) in our algorithms. It can be easily found that both the loudness and pulse rate are updated when the new solutions are improved to guarantee that the bats are moving toward the best solutions.

2.2 Binary bat algorithm (BBA)

As each bat moves in the search space towards continuous-valued positions in the bat algorithm, a binary version of the bat algorithm is needed in the test point selection problem. Therefore, the bats’ position should be represented by binary vectors. In Ref. [16], the authors first proposed a binary version of the bat algorithm and used it to deal with the feature selection problem successfully. In their algorithm, they chose the sigmoid function to restrict the bat’s position to binary values. However, the authors in Ref. [17] illustrated that their proposed v-shaped transfer function was better than the sigmoid function in the binary version of the bat algorithm, and used it to deal with the optical buffer design problem successfully. We chose to use their better strategy in our algorithm. The v-shaped transfer function and the position updating rule are listed as follows [17]:

$$V(v_{ik}^{t + 1} ) = \left| {\frac{2}{\pi }\arctan (\frac{2}{\pi }v_{ik}^{t} )} \right|$$
(6)
$$x_{ik}^{t + 1} = \left\{ \begin{array}{ll} (x_{ik}^{t} )^{ - 1} \;\;\;\;If\;rand < V(v_{ik}^{t + 1} ) \hfill \\ x_{ik}^{t} \;\;\;\;\;\;\;\;\;rand \ge V(v_{ik}^{t + 1} ) \hfill \\ \end{array} \right.$$
(7)

where \(v_{ik}^{t}\) and \(x_{ik}^{t}\) indicate the velocity and position of the i-th bat at iteration t in the k-th dimension, and \((x_{ik}^{t} )^{ - 1}\) is the complement of \(x_{ik}^{t}\).

The general pseudo code of the BBA is presented in Fig. 2. The changes from the standard BA are underlined.

Fig. 2
figure 2

Pseudo code of the binary bat algorithm (BBA) [17]

Full size image

3 Chaotic maps

Chaotic optimization method is a kind of random-based optimization method, which uses chaotic variables instead of random variables. Due to the non-repetition and ergodicity of chaos, it can carry out overall searches at higher speeds than stochastic searches that depend on probabilities [20]. Chaos is a deterministic and random-like process, which is very sensitive to its initial conditions and parameters. The nature of chaos is apparently random and unpredictable, but it also possesses an element of regularity [21].

In almost all the metaheuristic algorithms with stochastic components, randomness is achieved by using some probability distributions (such as uniform). In principle, replacing such randomness by chaotic maps could obtain better algorithms since chaos can have very similar properties of randomness with better statistical and dynamical properties. This can help to reach nearly all the different modes and ensure the diversity of the solutions generated by the algorithm. The chaotic search can escape from local optima more easily compared with other stochastic search optimization algorithms. Therefore, many researchers [18–21] have combined chaos with optimization algorithms to enhance the search efficiency and prevent from premature convergence to local minima.

To enhance the diversity of solution and improve the effectiveness and robustness of the BBA, one-dimensional, non-invertible maps are used to generate chaotic sequences in our proposed CBBA. Here we outline some well known chaotic maps which will be used for later simulations.

  1. (1)

    Chebyshev map

    The family of Chebyshev map [22, 23] is defined as follows:

    $$x_{i + 1} = \cos (i \cdot cos^{ - 1} (x_{i} ))$$
    (8)
  2. (2)

    Tent map

    Tent map [22, 24] is defined by the following iteration equation:

    $$x_{i + 1} = \left\{ \begin{array}{ll} x_{i} /0.7\;\;\;\;\;\;\;\;\;\;\;\;x_{i} < 0.7 \hfill \\ 10(1 - x_{i} )/3\;\;\;\;\;x_{i} \ge 0.7\; \hfill \\ \end{array} \right.$$
    (9)
  3. (3)

    Circle map

    Circle map [22, 25] is represented by the following equation:

    $$x_{i + 1} = x_{i} + b - (\frac{a}{2\pi })sin(2\pi x_{i} )mod(1)$$
    (10)

    where \(a = 0.5\) and \(b = 0.2\)

  4. (4)

    Iterative map

    The iterative chaotic map with infinite collapses [22, 26] can be defined as:

    $$x_{i + 1} = \sin \Big(\frac{a\pi }{{x_{i} }}\Big)$$
    (11)

    where \(a \in (0,1)\) is a suitable parameter. We set \(a = 0.7\) in our later experiments.

  5. (5)

    Logistic map

    Logistic map [22, 26] can be written as:

    $$x_{i + 1} = ax_{i} (1 - x_{i} )$$
    (12)

    where \(x_{0} \in (0,1)\),\(x_{0} \notin \{ 0.00,\;0.25,\;0.50,\;0.75,\;1.00\}\). We set \(a = 4. 0\) in our later experiments.

  6. (6)

    Piecewise map

    Piecewise map [22, 27] can be described as:

    $$x_{i + 1} = \left\{ \begin{array}{ll} \frac{{x_{i} }}{p}\;\;\;\;\;\;\;\;\;\;\;\;\;\;0 \le x_{i} < p \hfill \\ \frac{{x_{i} - p}}{0.5 - p}\;\;\;\;\;\;\;p \le x_{i} < 0.5\; \hfill \\ \frac{{1 - p - x_{i} }}{0.5 - p}\;\;\;\; 0. 5\le x_{i} < 1 - p \hfill \\ \frac{{1 - x_{i} }}{p}\;\;\;\;\;\;\;\;\;1 - p \le x_{i} < 1 \hfill \\ \end{array} \right.$$
    (13)

    where \(p \in (0,\;0.5)\), and we set \(p = 0.4\) in our later experiments.

  7. (7)

    Sine map

    Sine map [22, 28] can be described as:

    $$x_{i + 1} = \frac{a}{4}\sin (\pi x_{i} )$$
    (14)

    where \(0 < a \le 4\), and we set \(a = 4\) in our later experiments.

  8. (8)

    Singer map

    One dimensional singer map [22, 29] is formulated as:

    $$x_{i + 1} = \mu (7.86x_{i} - 23.31x_{i}^{2} + 28.75x_{i}^{3} - 13.3x_{i}^{4} )$$
    (15)

    where \(\mu \in (0.9,\;1.08)\), and we set \(\mu = 1.07\) in our later experiments.

  9. (9)

    Sinusoidal map

    Sinusoidal map [19, 22] is generated as the following equation:

    $$x_{i + 1} = ax_{i}^{2} \sin (\pi x_{i} )$$
    (16)

    where \(a = 2.3\).

    Figure 3 shows the chaotic value distributions of 100 iterations for all the above listed maps with random initial values. It should be noted that the chaotic maps which do not generate values between 0 and 1 are normalized to have the same scale.

    Fig. 3
    figure 3

    Visualization of chaotic maps

    Full size image

4 New proposed CBBA and its application in analog test point selection

In order to enhance the diversity of solution and meanwhile improve the effectiveness and robustness of the BBA, the chaotic maps are used to tune the BBA parameter and the elitist strategy is also introduced to store all the possible global best solutions, which will lead to a set of CBBAs. The construction of the CBBA and its application in analog test point selection will be discussed in this section.

4.1 Construction of the CBBA

4.1.1 Using of chaotic maps

In our proposed CBBA, parameter \(\beta\) of Eq. (1) is modified by chaotic maps during iterations, and the new frequency equation is written as:

$$f_{i} = f_{\hbox{min} } + (f_{\hbox{max} } - f_{\hbox{min} } )c_{i}$$
(17)

where \(c_{i}\) is the chaotic map value in the i-th iteration. It should be noted that all the chaotic maps here are normalized between 0 and 1. Since the chaotic maps are sensitive to the initial conditions and parameters, we should decide the proper parameter values by experiments. In order to simplify the procedure, meanwhile, do the comparison conveniently, we chose the same initial parameter values of chaotic maps as Ref. [22] in our experiments.

Since nine different chaotic maps are listed in Sect. 3, we could obtain nine different CBBAs totally.

4.1.2 Elitist strategy

It is possible that the global best solution may be more than one in reality [12]. Therefore, all the best solutions should be stored during the non-repetition and ergodicity searching of the algorithm. An elitist set XGbest is defined in the proposed CBBA to get more possible solutions. If more than one global best solutions (have got the same best fitness value) is obtained during the iteration, they can synchronously be stored in the elitist set. In the next iteration, if there are more new global best solutions that have the same fitness value as these in the elitist set, these new solutions are add into the elitist set. If these new global best solutions have better fitness values, all the old solutions in the elitist set are replaced by these new best solutions. Finally, we will get all the optimal solutions with the same best fitness value in the elitist set.

The general pseudo code of the CBBA is presented in Fig. 4. The changes from the BBA are underlined.

Fig. 4
figure 4

Pseudo code of the chaotic binary bat algorithm (CBBA)

Full size image

4.2 Application of CBBA in analog test point selection

As discussed in Sect. 1, the integer-coded dictionary has been proven to be an effective tool for optimal selection of test points; the utilization of CBBA in analog test point selection is also based on the integer-coded dictionary of the analog circuit. Besides the construction of integer-coded fault dictionary, inosculating CBBA with the test point selection problem rightly is also very important. We will discuss the details about them below.

4.2.1 Integer-coded fault dictionary of analog circuits

Hochwald and Bastian [8] first proposed the concept of ambiguity sets and defined a diode drop (0.7 V) as the ambiguity gap. The ambiguity group is defined as that any two faulty cases fall into the same ambiguity set if the gap between the voltage values of their responses is less than 0.7 V. Lin and Elcherif [3] first proposed the integer-coded fault dictionary technique in 1985. The fault dictionary provides information about the ambiguity sets for each test point and the mutual information among them [10]. The purpose of test point selection is to separate all the faults (including fault-free case) with a minimum number of test points, and reduce the dimension of the fault dictionary.

The integer-coded fault dictionary is a two dimensional integer matrix. Its rows represent all the faults (including fault-free case), and its columns show all candidate test points. For each fault, an integer code is generated from the numbers of ambiguity sets of each test point, and the same integer number represents all the faults that belong to the same ambiguity group in a given candidate test point. Since each candidate test point represents an independent measurement, the ambiguity groups of different test points can be numbered using the same integer without confusion [5, 8]. More details about fault dictionary and ambiguity set can be found in Ref. [3, 5].

4.2.2 Initialize parameters of CBBA

The best solutions are the bats with the best position that CBBA can explore. In this paper, the position of each bat is initialized as the binary vector. The number of elements in this binary vector is the same as the number of test points N. The position of the i-th bat is defined by

$$\begin{aligned} x_{i} = \left( {x_{i1} ,\;x_{i2} , \ldots ,x_{ij} , \ldots ,x_{iN} } \right) \hfill \\ \hfill \\ \end{aligned}$$
(18)

where \(x_{ij} = 1\;or\;0\), which indicates whether the corresponding test point is selected or not. That is to say, if the j-th test point is selected by CBBA, \(x_{ij} = 1\); otherwise, \(x_{ij} = 0\).

The bats’ velocity will decide the position of the bats in the next iteration. For simplicity and comparison, the velocity of the bat is initialized as a zero vector (the same as Ref. [17] ), which has the same dimension as the position vector.

4.2.3 Fitness function

For the analog test point selection problem, we hope to separate all the faults with minimum test points. To evaluate the quality of the i-th solution properly, the fitness function is defined as:

$$Fitness_{i} = \frac{{S_{i} + (N - Ns_{i} )}}{M + N}$$
(19)

where \(S_{i}\) is the number of separated CUT states, \(Ns_{i}\) is the number of selected test points, \(M\) is the number of all the fault states (including fault-free case), \(N\) is the number of all the test points.

It can be seen from the fitness function that the fitness value is in the region [0, 1] and the better solution always has larger fitness value. Therefore, the best solutions will get the largest fitness value during the iterations.

4.2.4 Work principle of CBBA for test point selection

As discussed above, the bats’ positions in CBBA denote the results of the test point selection. After initialization, all the bats will have a random position. And then, the algorithm goes into the iteration phase. The fitness function [Eq. (19)] is used to calculate the fitness values of all the bats. The algorithm will find out all the bats with largest fitness values during the iteration, and judge whether their locations should be added into the elitist set XGbest (or even replace all the solutions in the elitist set sometimes). The loudness (\(A_{i}\)), pulse rate (\(r_{i}\)), chaotic map value (\(c_{i}\)), frequency (\(f_{i}\)), velocity (\(v_{i}\)) and position (\(x_{i}\)) of each bat will be updated during the iterations. The algorithm is going to be finished at the end of the maximal iteration T max , which should be set as a proper number according to the complexity of the problem. We will finally get all the optimum solutions in the elitist set XGbest.

4.2.5 Time complexity of CBBA for test point selection

For analog test point selection with M fault states and N test points, there exist T max iterations for the CBBA. Based on the fitness function [Eq. (19)], when evaluating each solution (bat’s position), we need to check the number of isolated fault states. This can be transformed into a sorting problem and the computational time complexity is \(O(M\log M)\). If the population size of bats is \(P\), we need to evaluate \(P\) solutions for each iteration of the algorithm and the time complexity is \(O(PM\log M)\). Therefore, the total time complexity of CBBA is \(O(T_{\hbox{max} } PM\log M)\).

5 Experiments

In order to demonstrate the feasibility and effectiveness of the CBBA for test point selection, meanwhile, compare with other reported methods based on the integer-coded dictionary, we have done different kinds of experiments (two analog circuits’ examples and a group of statistical experiments). Since nine well known chaotic maps have been introduced in Sect. 3 and different chaotic maps used in CBBA may lead to different results, all these chaotic maps are adopted to construct the CBBA respectively in our experiments. The names of these methods (CBBAs) and the corresponding chaotic maps are listed in Table 1.

Table 1 Methods and the corresponding chaotic maps
Full size table

During all the experiments, the population size of bats is set as 40, the dimensions of the position and velocity vectors are set as N (the number of test points). For comparison and simplicity, we referred to the Ref. [17] and set the initial loudness (\(A_{0}\)) as 0.25, the initial pulse rate (\(r_{0}\)) as 0.2. The maximum number of iterations \(T_{\hbox{max} }\) is set as 100. The initial parameters of chaotic maps are set as the discussions in Sects. 3 and 4.1.1. By the way, all the parameters can be modulated experimentally in practice to suit different applications.

In order to highlight the improvements of our proposed CBBA, the BBA in Ref. [17] is also used to do all the experiments. The relevant parameters of BBA are set the same as the CBBA.

All the programs run on an Intel 3.2 GHz processor computer with MATLAB R2013a circumstance during the experiments.

5.1 Video amplifier example

The experiment is implemented on a video amplifier circuit that is shown in Fig. 5. This circuit is also cited by Ref. [12] to verify the efficiency of the MDFDPSO method. The excitation signal is a 5-kHz 8-V sinusoidal wave. The marked voltage sources “V1” and “V2” in Fig. 5 are 5-kHz -6-V and 5-kHz 6-V sinusoidal waves. Totally, there are sixteen potential catastrophic faults f1 to f16 (including the nominal case, M = 16) and thirteen test points n1 to n13 (N = 13). The responses of voltage values at all test points for different faulty conditions are obtained by PSPICE simulation. The integer-coded fault dictionary is constructed and shown in Table 2 (it’s the same as the fault dictionary obtained in Ref. [12]).

Fig. 5
figure 5

Video amplifier with two transistors

Full size image
Table 2 Integer-coded fault dictionary for video amplifier
Full size table

After running, all the proposed nine different CBBAs (CBBA1–CBBA9) have found the same best solutions in their elitist set:

\(XGbest = \left\{ \begin{aligned} n_{2} ,\;n_{7} ,\;n_{8} ,\;n_{9} ,\;n_{12} \hfill \\ n_{3} ,\;n_{7} ,\;n_{8} ,\;n_{9} ,\;n_{12} \hfill \\ n_{7} ,\;n_{8} ,\;n_{9} ,\;n_{10} ,\;n_{12} \hfill \\ \end{aligned} \right\}\).

The final best solutions are the same as the results in Ref. [12]. For comparison, the GA [11], MDFDPSO [12], EI [4], HGS [5] and BBA [17] are applied in this example. For each algorithm, 100 independent runs are implemented. The results are shown in Table 3.

Table 3 Comparison of CBBA with other methods for video amplifier
Full size table

As indicated in Table 3, all the algorithms achieve 100 % of success. Although EI and HGS cost shorter computation time, they can only find one best solution while other methods (except GA and BBA) can find three best solutions. Comparing with GA and MDFDPSO method, our proposed algorithms (CBBA1–CBBA9) cost less computation time and have better efficiency. The improvement of our methods (compare with BBA) is obvious (nearly the same computation time but more best solutions).

Finally, it comes to a conclusion that our new proposed algorithms (CBBAs) are superior to other mentioned methods.

5.2 Leapfrog filter amplifier example

The experiment is implemented on a leapfrog filter circuit that is shown in Fig. 6. This circuit is also cited by Ref. [5] to verify the efficiency of the HGS method. The excitation signal is a 1-kHz 4-V sinusoidal wave. The low-input-impedance failure of the amplifiers and some resistance and capacitance failures are considered in this circuit. Totally, there are twenty-three potential catastrophic faults f1 to f23 (including the nominal case, M = 23) and twelve test points n1 to n12 (N = 12). The responses of voltage values at all test points for different faulty conditions are obtained by PSPICE simulation. The integer-coded fault dictionary is constructed and shown in Table 4 (it’s the same as the fault dictionary obtained in Ref. [5]).

Fig. 6
figure 6

Leapfrog filter

Full size image
Table 4 Integer-coded fault dictionary for leapfrog filter
Full size table

After running, all the proposed nine different CBBAs (CBBA1 ~ CBBA9) have found the same best solutions in their elitist set:

\(XGbest = \left\{ \begin{array}{llllll} n_{1} ,\;n_{2} ,\;n_{3} ,\;n_{4} ,\;n_{7} ,\;n_{8} ,\;n_{11} \hfill \\ n_{1} ,\;n_{2} ,\;n_{3} ,\;n_{4} ,\;n_{7} ,\;n_{9} ,\;n_{11} \hfill \\ n_{1} ,\;n_{2} ,\;n_{3} ,\;n_{4} ,\;n_{7} ,\;n_{10} ,\;n_{11} \hfill \\ \end{array} \right\}\).

One of the final best solutions is the same as the results in Ref. [5]. For comparison, the GA [11], MDFDPSO [12], EI [4], HGS [5] and BBA [17] are also applied in this example. For each algorithm, 100 independent runs are implemented. The results are shown in Table 5.

Table 5 Comparison of CBBA with other methods for leapfrog filter
Full size table

As indicated in Table 5, all the algorithms achieve 100 % of success except the MDFDPSO method (99 %). EI and HGS cost shorter computation time, but they can only find one best solution while other methods (except GA and BBA) can find three best solutions. Comparing with GA and MDFDPSO method, our proposed algorithms (CBBA1 ~ CBBA9) cost less computation time and have better efficiency and accuracy. The improvement of our methods (compare with BBA) is obvious (nearly the same computation time but more best solutions).

Therefore, we can draw the same conclusion with the video amplifier circuit example that our new proposed algorithms (CBBAs) are superior to other mentioned methods in dealing with the test point selection problem because of their higher efficiency, better accuracy and robustness.

5.3 Statistical experiments

Although the above experiments have shown the great advantage and ability of the proposed algorithms in finding the optimum test point sets, there still no theoretical proof can be offered to demonstrate a specific non-exhaustive algorithm’s optimality so far. The new proposed algorithms (CBBAs) must be statistically tested on larger number of fault dictionaries to demonstrate their efficiency and qualities of generating optimum test point sets.

Such statistical experiments are carried out on the randomly computer-generated fault dictionaries and the final solutions are found by using the GA [11], MDFDPSO [12], EI [4], HGS [5], BBA [17] and the proposed methods (CBBA1–CBBA9) respectively. Here, a total of 100 integer-coded dictionaries are randomly created. Each dictionary is generated for a hypothetic CUT with 100 simulated faults, 25 test points and randomly five ambiguity sets per test point. Meanwhile, all the randomly created dictionaries are first analyzed by the exhaustive search algorithm to make sure that all the 100 dictionaries have five test points in their best solutions (optimum sets). The final results are shown in Tables 6 and 7.

Table 6 Statistical results of the solution accuracy
Full size table
Table 7 The average running time of each method
Full size table

As can be seen from Tables 6 and 7, the proposed methods (CBBA1–CBBA9), together with GA and BBA method, can always find the optimum solutions (success rate is 100 %), meanwhile, the MDFDPSO method achieves 96 % of success (with 4 % chances to get trapped into local optima), but our proposed methods (CBBA1–CBBA9) can find more final best solutions. Although the time consumptions of the EI and HGS method are radically lower than the other methods, their final solution accuracy rates are lower. Therefore, through statistic experiments, the proposed methods (CBBAs) also reveal their high accuracy and effectiveness and are demonstrated to be superior to other methods.

Actually, whether the data in the integer-coded fault dictionary are randomly computer generated or derived from a realistic circuit, it does not spoil the validity of the proposed methods (CBBAs).

5.4 Practical application analysis

Although the components of the analog circuit with parameter tolerance may be encountered in practice, it doesn’t affect the efficiency of our proposed algorithms either. If only the integer-coded fault dictionary can be constructed properly, our proposed algorithms (CBBAs) can be used to find the optimum test point sets.

From the experiments carried out above, we may come to the conclusion that our new proposed CBBAs can find nearly all the best solutions efficiently. However, which best solution should be used during our practice becomes a problem. Since each test point in the actual circuit has a test cost, which can be defined as the manpower requirements, equipment requirements, measure time and technique requirements, test complexity or even other economic factors and so on. Therefore, the test cost of each candidate test point is a constant value for an actual analog circuit in practice and can be estimated. Since minimizing the total expected test cost is an important target in practice, the best solution with the lowest test cost of all the best solutions would be the real best solution in practice. Therefore, our CBBAs have significant practical application value.

6 Conclusion and future research

The analog test point selection problem remains an important research field in fault diagnosis of analog circuit. How to find a minimum set of test points efficiently to isolate all the faults to a desired degree, therefore, becomes the key point. In the present work, we have introduced chaos and elitist strategy to the BBA and developed a set of CBBAs, meanwhile, for the first time applied them to deal with the analog test point selection problem. The attractiveness of our proposed CBBA mainly lies in two aspects: the utilization of different chaotic maps to tune the BBA parameter and the application of elitist strategy to store all the possible global best solutions. These improvements obviously enhance the performance of BBA and make our new algorithms (CBBAs) obtain all the best solutions (usually more than one) easily and effectively, which will give us more possible choices in the real engineering practice. Carried out on the same trademark analog circuits, the proposed algorithms show great advantage in finding the best solutions than the other mentioned methods. Since no theoretical proof can be given to the optimality of the proposed algorithms, statistical experiments are utilized for their evaluation. The results demonstrate that our proposed methods (CBBAs) have higher efficiency, better accuracy and quality in finding the optimum test point sets. They are effective and feasible methods in minimizing the size of the test point set of the analog circuit, and can help to find the best solution with lowest test cost of all in practice. Therefore, they are particularly applicable to actual circuits and engineering practice.

CBBA offers new techniques for improving the properties of BBA and whether it is fit for solving other optimization problems is being investigated. In addition, we used default values referred to other researchers’ work for the variable parameters of some chaotic maps in this paper, and how these parameters affect the solutions so as to further improve the performance of CBBA will be our future research direction.