A novel multiple black hole inspired meta-heuristic searching optimization for combinatorial testing

ABSTRACT Combinatorial searching-based software testing (CSST) is a challenging optimization procedure. The achievement of optimal solutions involves a careful formulation of the optimization problem and the selection of an appropriate approach. Metaheuristic searching procedures have proven to be effective for solving CSST issues. Black Hole (BH) optimization is among the more recently developed meta-heuristic searching algorithms. While this approach has been observed to be an effective alternative to particle swarm optimization, its operation is based on only one swarm. To date, no efforts have been made to modify this approach to accommodate multiple swarms. This study proposes a new variant of BH which involves a combination of multiple swarms. The BH optimizer was modified from continuous searching to binary searching and subsequently applied for solving CSST. The evaluation is based on a modified-benchmarking mathematical function and well-known CSST problems. This modified BH method is superior to that of the original BH, and that of the established particle swarm optimization (PSO) approach. In terms of CSST problems, binary multiple black hole (BMBH) optimizations generated a reduction rate of 68%.

Key words: black hole optimization, combinatorial searching-based software testing, meta-heuristic searching, multiple black hole optimization, swarm meta-heuristic.

1. INTRODUCTION of A novel multiple black hole inspired meta-heuristic searching optimization for combinatorial testing

Currently, the emergence of a variety of complicated systems in these software productsis on the rise. Consequently, the development of an effective process for assessing the quality of these systems has proven to be an arduous task. A typical way for testing any system is to consider the possible values of input interaction, to generate suite cases that are independent of each other, and can be associated with different faults. Through our observation, the emphasis of software developed over the last two decades has been on customizability to user needs. This makes the configuration of such software an important issue [1]. Software testing entails the coverage of all possible values of input or configuration and their interactions. However, given the current speed of hardware, the coverage of all possible variable interaction is not practical. Assuming a system with 9 input variables, each with 5 levels, the coverage of all possible combinations of its input variables in the traditional way, would require an overall of . This is considered an exceedingly high level of hardware power(Lin et al., 2015).

      Combinatorial testing (CT) is a sub-topic in software engineering for testing purposes. The goal of CT is the conversion of an original space of software variables, into a reduced space. This reduced space is considered the input for the testing process to detect faults. It facilitates the coverage of variable interactions to generate possible faults with the exclusion of superfluous operations [2]. In the context of software generation, an automatic generation of the reduced space is crucial when it comes to cost-effectiveness, time-saving, and quality. In a review by [3], CT based on searching approaches were termed search-based software testing (SBST). 

     In addressing the various challenges associated with SBST, it wasorated that “There exists a structured parallel approach for test data generation, but an idea of using search together with parallel islands has not been explored with branch selection”. Existing search algorithms need upgrading before they can be applied for parallel-based searching.

      Relevant literature documented numerous approaches related to meta-heuristic searching for optimization. Each approach is based on a certain concept or metaphor. Some approaches were inspired by genetic evolution, and their suitability with regards to the environment [4],(Qi, Wang, & Li, 2016) ,(Li, Wong, Gao, Hu, & Hosono, 2017), while others were inspired by social aspects(Prakash, Tatale, Kondhalkar, & Bewoor, 2019). Literature related to heuristic searching reported a wide range of applicable models. The mechanism and searching process vary from one approach to another, and this is reflected in the outcome. In the research of artificial intelligence (AI), opinions vary on the superiority of one searching model over another. While some models generate superior results in certain applications, they perform less effectively in others [5]. It is essential that the evaluation of meta-heuristic searching must be application-dependent. Some models are applicable for evolutionary searching, while others are more suitable for parallel searching. Researchers have recommended several models with a parallel searching forte, to overcome the problems associated with SBST. This study emphasized on the upgrading of an existing meta-heuristic searching algorithm termed black hole (BH) based

Optimization, into a parallel based searching algorithm. In this report, the upgraded meta-heuristic algorithm is named as the multiple black hole (MBH) optimization method.

The current article is separated into the following sections: Section 2 provides preliminaries. Section 3 presents literature survey. Next, section 4 gives background and terms, problem statement and contributions are given in Section 5.Next, we present our proposed approach in Section 6. Next, section 7gives evaluation and experiments results. Finally, section 8 presents the conclusion and future work.

2 PRELIMINARIES: Several important preliminaries are to explain the data and theory presented in this article with the following definitions:

 Definition.1

Software under test (SUT) is a software or application that is tested based on the possible values of its parameters by assuming that SUT has  parameters , the parameters can represent a possible input, or certain event (internal or external), or a configuration variable as illustrated in Example.1. SUT has  variables ( )that take any possible value such that , , … .  Based on this approach, the application of CSST is appropriate for solving the unlimited array of problems associated with the software engineering industry. There arethree examples from different types of applications: the first is the service application known as the pizza ordering system case study, the second is the smart mobile system case study, and the third is a heart disease case study.

Example .1

This example is found in the article by Alsewari & Zamli (2012)as well as in other relevant and summarized in Table 1.  The pizza ordering system comes with five variables: pizza type, crust, toppings, size, and delivery. Three variables take one of two values: (pizza type, crust, and delivery) while two variables take one of three values: (toppings and size). Therefore, the covering array combined with the number of cases equal to . Table 2 shows encoding for the covering array for pizza ordering system case study.Also, Table 3shows the dataset for the pizza ordering system case study.

THE PIZZA ORDERING SYSTEM CASE STUDY

TABLE 2:

ENCODING OF POSSIBLE VALUES OF INPUT TO THE PIZZA ORDERING SYSTEM CASE STUDY

Table 3:

THE DATASET EXTRACTED FROM THE PIZZA ORDERING SYSTEM CASE study

Example .2

The smart mobile system, this system was also utilized as a case study where the selection is based on its capacity for offering a wide range of factors and levels as explained in Figure 1 [6]. This renders it favourable for software testing. The factors were correlated such that, every factor has its relationship among several other factors.  Thesmart mobile system consists of 18 features which are divided into two categories: one-valued and two-valued parameter. There are ten features in the two-valued parameters category (video call, voice message, video message,basic colour, higher solution screen,camera, video player, music player, radio and voice recorder) and eight features in the one-valued parameter category (smart mobile system ,calls ,messages, GPS, screen, media, voice call and text message). From this, the possible configurations that need to be tested are (2¹⁰×1⁸=1024).

 Figure 1: Smart Mobile System Case Stu

Example .3

The Heart Disease case study [7] for predictions comprises seven variables: gender (2 levels: male/female), age (four levels: lower than 20, between 20 and 40, between 40 and 60, and more than 60), morning, evening, and sleeping

heartbeat rate (three levels: lower than 60, between 60 and 100, more than 100), the blood test (three levels: lower than 10, between 10 and 15, and more than 15). The full extent of the problem is  . The states can be represented as in Table 4. 

TABLE 4   HEART DISEASE PREDICTIONS CASE STUDY

Definition.2: The test case is an n-tuple  where , , …  If a fault is generated when testing the system based on TC, then the test case has served in the t-testing of the system. Based on previous examples like the pizza ordering system, which include vegetarian cheese, extra thick, ground beef, large, and takeaway is regarded a .

Definition.3:All possible test cases are denoted  , , , … . In previous examples, the encoded possible values with integer levels = 0, 1, 2... is portrayed in Table 2. Table 3 displays the .

Definition.4: Covering Array (CA) is adopted as a mathematical object for the description of the generated t-way test suit. Generally, SUT is composed of multiple parameters that cross-interact with their associated values. In this research, denotes the number of parameters. The associated levels are denoted by , while  is the interaction strength. When all parameters  have the same number of values ( ), the CA is represented as CA ( . That is, six rows of test cases generated from two columns of parameters with two values per parameter, can be represented as , . When the numbers of values are not similar for all parameters, CA can be represented as MCA . For instance, an array with 12 rows, where four parameters have two values, while one parameter has three values, can be represented as MCA .

Definition.5: Orthogonal Array (OA) with strength , is defined as , where the size of the array is  and it fulfills the two conditions:

1-   Each column of OA with an index  contains all possible elements from the set  where

2-   Any subset of  columns covers all possible -tuples exactly 

3. LITERATURE SURVEY of A novel multiple black hole inspired meta-heuristic searching optimization for combinatorial testing

The study is separated into two sub-sections of the literature of (CSST) (Section 3.1) and a review of meta-heuristic-based approaches focusing on the parallel nature of some methods (Section 3.2). 

A.      CSST TESTING 

The literature on CSST is relatively extensive embracing numerous approaches. However, all these approaches share a common factor: they exploit the power of random combinatorial searching when they are integrated with heuristics for determining the t-strength covering array. The formulation of the optimization problem calls for an emphasis on two aspects: the devising of the objective function and the selection of the approach employed (pure based approach or hybrid-based approach [8].In terms of the objective function formulation, some models use a minimization formulation, while others use a maximization formulation. The fitness function is the total number of different pairs, covered by all the test cases in an individual. If an individual covers more different pairs than others, it is superior to the others (Qi et al., 2016)). Thus, their formulation of the problem is a maximization problem, where an individual becomes a solution when it covers all pairs. In other work, the number of covered d-tuples was used as a fitness value for the candidate solution [9]. On the other hand, investigating the objective function was used as the number of non-covered interaction tuples covered by the candidate solution (Zamli et al., 2016).  In another situation, the number of uncovered tuples was taken as the cost of the candidate solution which requires minimization (Lin et al., 2015). The cardinality of the set and the objective value represented by the number of non-covered interaction tuples covered by Z (Zamli et al., 2018).

      In terms of the type of meta-heuristic algorithm applied, Zamli et al., (2017) proposed a new variant of the teaching learning-based optimization (TLBO) algorithm. Their meta-heuristic algorithm comes with a Mamdani fuzzy inference system, which not only provides a solution to trapping in a local optimum but also greater diversity. In an undertaking by [10], the firefly meta-heuristic algorithm was applied as a test suite generator. Their computational comparison between the firefly meta-heuristic algorithm, genetic, and ant colony optimization revealed that firefly has a shorter optimization time. Other models developed for solving combinatorial software testing using meta-heuristic searching include the Memetic algorithm (MA) [11], particle swarm optimization (PSO) [12],artificial bees colony (ABC), harmony search algorithm (HSA) [13], bat algorithm (BA) (Alsariera et al., 2015b), flower pollination algorithm (FPA) [14] and [15].All these models are considered pure models as they utilize a common pure meta-heuristic approach.

      In terms of hybrid-based approaches, several researchers integrated meta-heuristic algorithms with other models. For example, Mahmoud & Ahmed (2015) integrated the particle swarm optimization approach with fuzzy logic, for the tuning of , , and . They built three fuzzy inference systems to monitor the PSO performance, and to adjust the , , and  for optimization improving efficiency. [16]developed a hybrid artificial bee colony (HABC) strategy, by hybridizing an artificial bee colony (ABC) algorithm, with a particle swarm optimization (PSO) algorithm.

B.     PARALLEL META-HEURISTIC SEARCHING

Parallel meta-heuristic searching refers to methods that come with a parallel searching quality. Researchers have made efforts to improve the exploration qualities of existing meta-heuristic searching algorithms, by converting them into parallel searching algorithms. Gülcü & Kodaz (2015) developed the parallel comprehensive learning particle swarm optimizer (PCLPSO). This optimizer, which comes with multiple swarms based on the master-slave paradigm, operates both cooperatively and concurrently. [17].Fashioned a multi-swarm optimizer for multi-objective optimization. They used a hybrid strategy decomposition and dominance (MSMO/2D), to improve

5.      PROBLEM STATEMENT AND CONTRIBUTION

There are several differences between BH optimization and the newly developed MBH optimization. While BH optimization involves the use of a single BH during its search in the solutions space, MBH optimization involves the use of the  black hole for the same purpose. Also, the MBH optimization algorithm comes with the concept of energy of the BH. This concept serves to eliminate non-active BHs, as well as BHs that do not show improvement with time. By improvement, we mean the capacity of the algorithm, for searching out better fitness values of the solution, representing the BH. In comparison to the BH optimization algorithm, the MBH optimization algorithm is more effective for searches in the solutions space. Additionally, the MBH optimization algorithm can be relied on to

achieve better results with a lesser number of iterations, than that required by the BH optimization algorithm. In both MBH and BH optimization, the movement of stars beyond the permitted region of search (violation of the constraint), will result in their clipping. This renders their searching prowess less effective. The MBH optimization algorithm overcomes this dilemma through the addition of random components after being subjected to clipping.

B. Binary Variant of both the BH and MBH Algorithms

The equation for defining the movement of stars toward the black hole,   is random number between 0 and 1 the move equation for the stars as follows:

The setback accompanying Eq. (1) is its ineffectiveness when it comes to binary values because of the addition of a second term to a binary value which causes a breaching of the binary constraint, which is 0 or 1. In order to overcome this problem, we introduced a parameter, which we named the pulling rate .  This approach generates a random number  between 0 and 1, where  denotes the index of the dimension. We checked its value, and altered the value of   to  in compliance to Equation 2 below.

A small value of the pulling rate pr is preferred for a diligent search in the solution space. The following example provides an explanation on the performance of Equation 2.  Assuming one star has the value , while the black hole  ,  , generated one random number rd for each element of  Taking for granted that that , then based on the Equation 2, the value of  While the initial distance between the star and the black hole was observed to be (  ), the movement of the star in compliance to Equation 2, altered this distance to 1.  The similarity of the BMBH and BBH concepts allows for the use of the same equation for moving the stars. The addition of another subscript to the equation, serves to indicate the index of the BH.  Subsequently, we generated a random number  between 0 and 1, where  denotes the index of the dimension. We identified its value, and altered the value of   to  in compliance to Equation 3 below.

where  indicates the index of the black hole, 

To verify the covering array of strength t, with the entire number of test cases, a function designed for this purpose was employed. This function, which verifies the validity of the covering array, returns a Boolean variable with a value of 0, if the covering condition for a certain strength is not met, or the value of 1, if the covering condition for a certain strength is met. Known as the cover CheckGR, the integration of this function with the BBH and BMBH algorithms is portrayed in Figure 4. As can be observed, the searching algorithm generates a random candidate solution and delivers it to the objective function. The objective function comes with cover CheckGR, which determines if the array has a covering property with strength t. Then, if the covering property strength is met, the number of rows of the covering array represents a reflection of the fitness values. The objective of this exercise is the minimization of the number of rows. In a circumstance where the covering property strength is not met, the fitness value is given as infinity. This implies that the solution is no longer be included, in iterations for the generation of new solutions.

7. EVALUATION AND EXPERIMENTAL RESULTS of A novel multiple black hole inspired meta-heuristic searching optimization for combinatorial testing

The evaluation process is separated into two sections. In the first, MBH optimization is assessed and its performance compared with the original BH optimization and PSO. Benchmarking mathematical functions were employed for this exercise. In the second section, BMBH optimization is assessed and its performance compared with BBH and BPSO. Several CSST problems reported in relevant literature were referred to for this exercise. These two sections are presented in sub-sections 7.1 and 7.2 respectively.

A.     Benchmarking Mathematical Functions

In order to gauge the performance of the MBH algorithm, it was compared with the BH and PSO algorithms, with respect to the capacity for determining the optimal point, of the provided benchmark optimization functions. The formulas of the mathematical functions, which cover the true optimal, dimension, searching range, and setting of the algorithms in terms of the number of solutions and number of iterations, are presented in Table 6. MBH optimization converges closer to the optimal value than either BH or PSO. Furthermore, BH optimization is a cut above PSO in most functions, and similar in some. This comparison emphasizes the superiority of MBH optimization over both BH optimization and PSO.

B.     Benchmarking Case Studies based on CSST

The Three case studies (i.e. pizza ordering system,Heart disease system, smart mobile system) were used to evaluate the performance of proposed BMBH and BBH and compare them with BPSO. Each case study has its features and aspect of industry. While Pizza ordering system considers the user as a client of restaurants. Heart disease system considers the health care centre. On the other side, smart mobile system offers wide range of factors and levels which makes it suitable for software testing. From t-way testing point of view, all case studies are different in the size of covering array, number of variables and levels. The results for the three case studies were generated based on CSST. Table 7  shows the features of each case study.

 The results from a comparison between BMBH optimization, BBH optimization and BPSO for the three literature case studies (in Examples.1, 2 and 3) are presented in this section. The algorithms were tested with the number of solutions and iterations equalling to 100 each. The resulting numbers were used for expediting experimental operations, as well as for increasing the number of solutions and iterations to generate better results.

        For pizza ordering system problem,the full size of the problem is CA  cases.In a comparison exercise involving BPSO, BBH optimization, and BMBH optimization, for the three values of t=2, t=3, and t=4, it was observed that both BBH and BMBH are superior to BPSO in this area. It was also revealed that BMBH achieved a lower cost value for t=2 with a reduction of the full size from 72 to 22, and for t=3 with a reduction rate of the full size from 72 to 35. Furthermore, as illustrated in Table8, the greatest reduction rate of 68% for t=2 was recorded by BMBH because the original size was 72 and it became after applying BMBH 22.

        In Figure 5For pizza ordering system problem, a boxplot diagram based on 20 experiments performed for t=3, shows that BMBH optimization is the only method that can effectively reduce the full size of the case study. This is portrayed in Figure 5. Based on the figure,ascan see that BBH and BMBH resultsalmost have similar tabulation of minimum cost but BMBH do have better results in term of the means. However, by cross reference the figure 5 with table 8, the tabulation of the result and the standard deviation for both algorithm shows that both of them have almost similar consistency in producing the results. This is due to the multi-swarm nature of BMBH.Another factor is BMBH performance is the energy variable of the swarm.

       For smart mobile system,the full size of the problem is CA ( =1024) cases. BMBH optimization reduced the full problem size from 256 to 100for t=2 and t=3, while BBH optimization reduced the full problem size from 256 to 104,also for t=2 and t=3. However, although BPSO reduced the full problem size from 256 to 234 this was only for t=2 and t=3. In Table 9 displays the reduction rate of each algorithm with respect to the full size of the problem. This table makes clear that the highest reduction rate was achieved by BMBH optimization (60% for t=2,t=3 and t=4).

Also, according to the boxplot diagram for smart mobile system displayed in Figure 6, BMBH optimization is a cut above the rest when it comes to reducing the problem size. It exhibited a lower standard deviation, as well as a lesser number of rows, when compared to BPSO and BBH optimization. Based on the figure, as can see that BBH and BMBH results almost have similar tabulation of minimum cost but BMBH do have better results in term of the mean and standard deviation. Also, by cross reference the figure 6 with table 9, the tabulation of the result and the standard deviation for both algorithm shows that BMBHhassuperior results. Again, this is due to the multi-swarm nature of BMBH.  Another factor is BMBH performance is the energy variable of the swarm and it has high exploration power in the searching space.

 For Heart Disease Prediction problem, the full size of the problem is CA ( . It was observed that BMBH optimization reduced the full problem size from 1296to 587, for t=2 and t=3.while BBH optimization reduced the full problem size from 1296to 610, also for t=2 and t=3. However, while BPSO reduced the full problem size from 1296 to 883, this was only for t=2 and t=3. Table 10 displays the reduction rate of each algorithm with respect to the full size of the problem. This table makes obvious that the highest reduction is associated with BMBH optimization, which recorded 54%for t=2,t=3 and t=4.

   Also, the boxplot diagram for Heart Disease problem(Figure 7) reveals BMBH optimization to be superior to the rest in terms of problem size reduction. It exhibited a lower standard deviation, as well as a lesser number of rows, in comparison to BPSO and BBH optimization. Also, by cross reference the figure7 with table 10, the tabulation of the result and the standard deviation for both algorithm shows that BMBHhasbettermean and higher standard deviation. Again, the superiority is in the multi-swarm nature of BMBH.  Another factor is BMBH performance is the energy variable of the swarm and powerful searching is high.

9. CONCLUSION AND FUTURE WORK

CSST represents a challenging optimization problem. This challenge has been treated with a proposal of the application of the multiple swarm concept to existing swarm methods. To achieve this, the existing meta-heuristic searching optimization method known as BH optimization has been upgraded to a multiple swarm-based BH optimization method, and named as MBH optimization.  In this paper, the application of MBH on CSST by the conversion of MBH optimization into a binary variant called BMBH optimization was employed. BMBH was able to generate more optimal solutions to CSST problems comparing with BBH and BPSO.

This is interpreted by the exploration power of CSST which is able to generate swarm distribution in various regions in the solution space comparing with BBH. Another aspect of the powerful searching performance of BMBH is the energy variable which increases or decreases according to the successfulness of the black hole in finding more optimal solutions and updating its value. This factor has not existed in classical BH nor binary variant of BH.

In the future, the optimization will be extended to accept various constraints of the variables which makes it more complicated than only boundary constraints. Another direction of search is to incorporate re-enforcement learning which makes the searching subject to training, hence, more fruitful.