Print Email Download Reference This Send to Kindle Reddit This
submit to reddit

Bee Colony Optimization Algorithm Biology Essay

The process of verifying the modified software in the maintenance phase is called Regression Testing. The size of the regression test suite and its selection process is a complex task for regression testers because of time and budget constraints. In this paper, A Bee Colony Optimization (BCO) algorithm for the fault coverage regression test suite prioritization has been presented. In the natural bee colony, there are of two types of worker bees; Scout bees and forager bee, who are responsible for the development and maintenance of the colony. The BCO algorithm developed for the fault coverage regression test suite is based on the behavior of these two bees. The BCO algorithm developed for fault coverage has been explained to attain maximum fault coverage in minimal units of execution time of each test case, using two examples whose results are comparable to optimal solution. Average Percentage of Fault Detection (APFD) metrics and charts has been used to show the effectiveness of proposed algorithm.

Keywords: Bee Colony Optimization, Regression Testing.

1. Introduction

Due to the time and cost constraints, software maintenance is one of the most difficult and crucial activities of the software development life cycle. Software maintenance phase extends for ten to fifteen years of duration in which regression testing is performed to check and confirm the correctness and accuracy of the modified software. Exhaustive regression testing is also not possible due to the time and cost constraints associated with it. Thus effective selection and prioritization methods are required to make regression testing handy and worthy. Various techniques have been proposed for the same which have been mentioned in next section of related work.

In this paper the optimization phenomenon used is the Bee Colony Optimization phenomenon where bee behavior has been observed, studied and mapped to find prioritization of the modified software’s test suite.

Automated software testing has been an area of concern for big software development companies. Automated testing allows development and execution of test cases unattended. Also, comparison of actual test results to expected test results can be determined easily. Automation of the manual testing process is done to improves accuracy; increase test coverage, save time and money and help developers and testers to develop test cases quickly and efficiently. This algorithm automates the test suite prioritization process as per the bee colony optimization criteria.

Organization of the paper is as follow. In section 2 related work is presented, BCO method has been explained in section 3. In Section 4 the formalized BCO algorithm for regression test suite prioritization has been presented, in section 4.2 the explanation of the algorithm is given, 5 presents the prioritization of test cases based on total fault coverage with examples. Section 6 gives the comparison of various prioritization approaches to BCO and their APFD values and charts. And finally in the succeeding sections threats to validity, conclusion and future work are presented.

2. Related work

This section presents an overview of the related work of test case selection and prioritization and the areas where BCO technique has been used to find solutions to problems.

The selection problem has been addressed by many researchers and they have proposed several techniques for solving it. In the selection process we choose test cases from the already available test suite according to some criteria as per the required solution to the problem in hand. The selection process is based on the approach being used to prioritize test cases. “Control Flow based approach” [1], which is based on incremental testing approach. Another approach could be based on “Automated Selection Revalidation” proposed by Fisher et. al. in 1981 [2] and was later extended and implemented for Fortran projects by [3] in 1990.In this a revalidation strategy based on zero-one integer programming model and test criteria based on mathematical optimization algorithm. Next, there was “A Safe, Efficient algorithm for Regression Test Selection technique” given by Rothermal in 1997. In this approach graph theory has been used to identify tests with the potential to identify fault revealing data. Another approach was based on “Intermediate code for virtual machines” given by Rothermal in 2000 [5]. In this the analysis of source code is done to select the candidate test cases. It was designed for C++ projects by Rothermal in 2000[5], redesigned for Java software by Harrold Jones in 2001[6] and then generalized by Koju 2003 [7] for virtual machines and languages like C/C++, Java, .Net etc.

There are a variety of prioritization techniques too. Some of them are “Modification Based Approach” [8], [9], [10],[11] in which prioritization is made after selection and performed based on sorting the test cases selected using Modification based techniques.“Total fault detection technique” [12] in which test cases are prioritized according to the increasing order of the number of faults detected by a test case. “Coverage Based Approach” [8], [12], [13] in which concept like code coverage, branch coverage, statement coverage etc are used for deciding the order of regression test suite. “History based prioritization” [14], [15], [16] in which reordering of test cases is based on the historical execution data. Another technique is “Control flow based technique”[17] in which the test cases are prioritizes using modified condition/decision coverage pairs. Many more techniques are there like “Data Flow based”[18], “Requirement Based”[19],“Cost based”[20],[21] “Slicing Based”[22],[9] “Genetic Based”[23], “Algorithm Based”[4], [24],[25],[26], [27] ,[28], [29]etc.

Bee Colony Optimization is an emerging field for researchers. It has been applied to areas like “Travelling Salesman Problem” [30] which is a NP-Hard combinatorial problem where an optimal path is to be searched from source to destination for a travelling salesman. “Optimization of problems” [31] where the optimal solution is to be searched on the basis of some known function. “Scheduling problems” [32] like job shop scheduling problems, task scheduling problems, project scheduling problems, process scheduling problems etc. For solving other combinatorial problems like “Generation of pair-wise test sets” [33] where automated test cases are to be generated. The concept of BCO is used for solving “Sudoku Puzzles” [34]. Routing problems where optimized path for better routing is searched using “Routing Algorithm” [35]. Moreover, BCO has also been applied in the area of “Web Search” [36] for effective search engine mechanism. The bee colony optimization has also been used for understanding the concept of software test suite optimization [37]. The bee’s concept has also been used for optimization approaches in the field of engineering [38].

3. Bee colony optimization (natural phenomenon of bee colony)

Bee Colony Optimization is the name given to the colony formed by the mutual understanding and team work of the natural bees in the process of foraging food. It is a fact that all the creatures on this earth follow one or the other mechanism/process to find food sources that suite them.

Honey bee comb build-up and management is a classic example of teamwork, synchronization experience and co-ordination. The way the bees find, build and maintain their comb and hive is remarkable. These are the factors which have given rise to interest of researchers to study this system and find solutions to their problems.

In a natural honey bee hive there are a variety of bees with specific role(s) to play. There are three types of bees:

1. Female Queen Bee

There is only one Queen of a bee colony. She is responsible for laying eggs which are used to build new colonies.

2. Male drone bees

There are many drone bees of a colony. They mate with the Queen to build new colonies.

3. Worker bees

There are thousands and thousands of worker bees. These perform all the maintenance and management jobs in the hive. There are two types of worker bees, namely Scout bees and Forager bees, which perform the Scout behavior and Forager behavior respectively, which are collectively responsible for the development of the honey bee colonies.

3.1. The Scout Scenario

In the Scout Scenario there are following steps:

The Scout bees start from the hive randomly in search of the available food sources.

They continue with this exploration process and return back to the hive until they are out of energy/tired.

When they return back to the hive, they share their knowledge and experience with the fellow Forager bees by performing the mechanism called “Waggle Dance”.

Waggle Dance is a form of dance in which the bees follow in circular direction in the shape of digit 8. It is repeated again and again. Its intensity and direction gives the idea of food source location and food source quality respectively to other bees. It is the means by which the bees communicate with each other. It is used to convey the parameters like foods Source Quality, distance of food source from hive, Location of food source w.r.t. sun, to guide the path to the available forager bees.

These steps of the scout bees constitute the first step of the BCO process called the “Path Exploration”.

3.2. The Forager Scenario

In the Forager Scenario, the Forger bees perform the following:

Upon the arrival of the Scout bee to the hive, the Forager bees observe and learn the steps done by the scout bees so as to ease their journey.

Then these Forager bees go to the food sources as guided by the Scout bees to exploit Best Food Source Quality food sources.

These forms the second step of the BCO process called the “Path Exploration”.

4. Proposed BCO algorithm

In [19] Artificial bee colony system has been modeled in [29]. This paper presents a new bee colony optimization algorithm that maps the food foraging behavior of natural worker bees as an algorithm to prioritize regression test suite’s test cases based on maximum fault coverage. This algorithm takes the test cases as food sources, number of test cases as the number of scout bees, number of forager bees which make the initial population and the ratio of number of faults detected by each test case to the test case’s execution time as the food source quality of that test case.

Following is the basic flow of the proposed BCO Algorithm:

Figure 1. Basic flow of the proposed BCO Algorithm.

Following is the list of notations that are being used in the proposed algorithm:

Nb : Total number of bees (Initial Population)

NS : Number of scout bees

NF : Number of forager bee

FSQi : Quality of ith Food Source

Si : ith Socut Bee

Fi : ith Forager Bee

PSBi : Path of SBi

PFBi : Path of FBi

ET : Execution time of test case

NF : Total number of faults

FC : Number of Faults covered by a test case

Following two tables will be formed in execution of the algorithm:

PSB Table

Path of Scout Bee Table, as seen in Table 2 and 5 contains all the paths explored (visited) by the BS. It is used for the path exploration phase of BS. This table will act as input for the PFB table formed by BF.

PFB Table

Path of Forager Bee Table, as seen in Table 3 and 6 contains all the paths exploited (selected) by the BF. In this table an account of the total ET of each path is also kept. This table helps in final path selection.

4.1. BCO Algorithm

Following are the proposed algorithm’s main steps:

1) Assumptions

All the food sources have been identified initially.

The distance between hive to food source, food source to food source, food source to hive is equal that is unity.

A bee will visit any food source only once.

The input consists of a test suite T, with following information

T={t1,t2…tn} test cases,

Faults Covered, FC by each test case and

Execution Time, ET of each test case.

The number of bees Nb (NS + NF) to search and form the solution is 2n (n for scout bee and n for forager bee).

Each Si will start the exploration process randomly till it develops such a path in which all the faults are covered.

Each Fi will exploit only Si path.

Stopping criteria for both the processes is total number fault coverage.

No two scout bees will have same random path in the exploration process.

FSQ of a test case = (Number of Faults covered by a test case/Execution Time)

= FC/ET

2) Initializations

Nb = NS + NF

NS = NF = number of test cases in the test suite under test.

3) BCO Module

START

(1) For each Scout Bee

(i)Do

{Perform exploration process randomly to develop PSB Table}

until FC of Si = NF.

(ii)Sort the hops in scout bee path in decreasing ratio of FSQ of each test case in that path.

(2) For each Forager Bee

{Perform Exploitation process to develop PFB Table}

until FC of Fi = NF.

(3)Select Path of bee from PFB Table with minimum ET.

STOP

4.2. Explanation of the BCO algorithm

1. Path Exploration

This is the first step in the execution of the proposed BCO algorithm. This step is executed by the Scout bees, NS times, in order to explore all the food sources (Test Case) available. The Si starts its exploration process randomly. After this they continue the exploration of test cases until the stopping criterion is met. Each path PSBi constructed by the Si is entered into the PSB Table.

2. Path Exploitation

In the next step the forager bees exploit the PSB. This step uses the PSB table as input. Each Fi starts exploiting the PSBi to form the PFBi. Here each Fi chooses the test case (food source) with best FSQi value. The succeeding test cases are chosen such that which detects faults those are not detected by the already existing test cases. This condition makes sure that only those test cases are selected which are effective in fault detection and total fault coverage (stopping criteria). The summation of the ET of all the test cases present in a particular PFBi is done to get that PFBi’s total ET. All these entries are maintained in PFB Table.

3. Path selection

This is the final step of the BCO algorithm done by the Fi. From the PFB table select the PFBi with minimum Total ET.

4.3. Analysis of the BCO algorithm

The running time of the proposed BCO Algorithm is bounded by time required to explore path and exploit path. For the input population of size ‘n’, the path exploration requires O(n) operations . All ‘n’ particles in the population will go through ‘n’ iterations for completing the process of path exploration in the proposed BCO algorithm.

For the sorting of the PSBi step O(n) operations will be required.

For the path exploitation step all the ‘n’ individuals of the population will go for ‘n’ iterations to develop the path. Hence, taking O(n2) operation complexity. For the final path selection step only minimization process will take place which takes O(n) operations.

Therefore, the best running time of proposed algorithm is O(n2) + O(n) + O(n2)+ O(n), which makes the final running time as O(n2).

4.4. Implementation of Proposed BCO Algorithm

The proposed BCO algorithm has been implemented in CPP compiler comprising of about 300 LOC. There are two structures in this code namely the test_case structure and the bee structure. Since, till now the input table is entered manually the code has been executed on small examples as shown in section 5.1. and 5.2. Work of incorporating file handling into the code is in progress so that this code will be able to take the input automatically and hence it could be used to solve test suites of larger size.

5. Prioritization of test cases based on maximum fault coverage

In the proposed BCO technique the test cases are prioritized in such a manner so as to achieve maximum fault coverage within minimum execution time. To ensure that all the faults are covered by the test cases selected in the prioritized ordering we use mutation testing. In this we deliberately alter a program’s code, then re-run a suite of valid test cases against the mutated program.  A good test will detect the change (fault) in the program and fail accordingly. Thus, the proposed algorithm’s effectiveness is measured using mutation testing. This is illustrated by two examples in section 5.1. and 5.2. in which mutants are created.

5.1. Example 1

The problem taken is “college program for admission in courses”. The problem specification is available at website http://www.planet-source-code.com. In this example a test suite has been developed which consisted of 35 test cases. For simplified explanation of the working of the algorithm, a test suite with 9 test cases is considered in it, covering a total of 5 faults.

The input test suite contains 9 test cases with default ordering {T1, T2, T3, T4, T5, T6, T7, T8, T9}, the faults covered (FC) by each test case, the execution time (ET) required by each test case in finding faults and food source quality (FSQ) are as shown in Table 1. Equal priority is given to the number of faults covered and minimum execution time in selecting the test cases.

Table 1. Test cases with the faults covered, execution time and food source quality.

Test Case

F1

F2

F3

F4

F5

FC

ET

FSQi

T1

X

X

X

X

4

11.5

.34

T2

X

X

2

11.5

.17

T3

X

X

X

3

12.33

.24

T4

X

X

X

3

10.66

.28

T5

X

1

15

.06

T6

X

X

X

3

8.33

.36

T7

X

1

15

.06

T8

X

X

X

3

10

.30

T9

X

1

11

.09

Step 1. Scout Bee Performs Path Exploration and creates PSB Table, Table 2.

Table 2. Path Explored by Scout bee. (PSB Table).

Si

PSBi

S1

T1

T6

T7

T4

S2

T2

T1

T9

T4

S3

T3

T1

T6

T8

S4

T4

T3

T5

T7

T2

S5

T5

T1

T4

S6

T6

T3

T5

T7

T2

T4

S7

T7

T6

T3

T9

T1

T8

S8

T8

T1

S9

T9

T5

T7

T8

T3

Step 2. Forger Bee Performs Path Exploitation and creates PFB Table, Table 3.

Table 3. Path Exploited by Forager bee. (PFB Table).

Fi

PFBi

Total ET

F1

T6

T1

T4

30.49

F2

T1

T4

22.16

F3

T6

T1

T8

29.83

F4

T4

T3

T2

34.49

F5

T1

T4

22.16

F6

T6

T4

T2

30.49

F7

T6

T1

T8

29.83

F8

T1

T8

21.5

F9

T8

T3

22.33

Step 3. Forger bee performs final path selection.

Hence PFB8 with test cases T1 T8 forms the prioritized test suite for the given problem.

5.2. Example 2

Another problem specification for “Hotel Reservation” which reserves the rooms in hotel and maintains the record. The complete problem specification is available at the website “http://www.planet-source-code.com”. In this example a test suite has been developed which consisted of 40 test cases. For simplified explanation of the working of the algorithm, a test suite with 5 test cases is considered here, covering a total of 5 faults.

The input test suite contains 5 test cases with default ordering {T1, T2, T3, T4, T5}, the faults covered (FC) by each test case, the execution time (ET) required by each test case in finding faults and food source quality (FSQ) are as shown in Table 4. Equal priority is given to the number of faults covered and minimum execution time in selecting test cases.

Table 4. Test cases with the faults covered, execution time and food source quality.

Test Case

F1

F2

F3

F4

F5

FC

ET

FSQi

T1

x

x

x

3

12.2

.2459

T2

x

1

10

.10

T3

x

x

x

3

10.67

.28

T4

x

1

7

.14

T5

x

x

x

x

4

9.97

.40

Step 1. Scout Bee Performs Path Exploration and creates PSB Table, Table 5.

Table 5. Path Explored by scout bee. (PSB Table).

Si

PSBi

S1

T1

T2

T3

T4

S2

T2

T3

T5

S3

T3

T1

T2

T5

S4

T4

T3

T2

T5

S5

T5

T3

Step 2. Forger Bee Performs Path Exploitation and creates PFB Table, Table 6.

Table 6. Path Exploitated by Forager bee. (PFB Table).

Fi

PFBi

Total ET

F1

T3

T1

22.87

F2

T5

T3

20.64

F3

T5

T3

20.64

F4

T5

T3

20.64

F5

T5

T3

20.64

Step 3. Forger bee performs final path selection.

Hence PFB2 with test cases T5 T3 forms the prioritized test suite for the given problem.

6. Comparison

The examples mentioned in sections 5.1 and 5.2 are compared with BCO order w.r.t. the following orderings: No order, Reverse order, Random order, Optimal order of the test cases. The orderings with respect to these approaches for examples in sections 5.1 and 5.2 are listed in Table 7 and 9. These approaches are compared by calculating Average Percentage of Faults Detected (APFD) [40] in Tables 8 and 10, for the maximum fault coverage concept.

APFD =

Where, T - The test suite under evaluation

m - The number of faults contained in the program under test P

n - The total number of test cases in and

TFi - The position of the first test in T that exposes ith fault.

The results obtained for the examples explained above have been plotted in APFD charts in Figure. 2 and Figure. 3. These show that the APFD values for the prioritization achieved using the proposed BCO algorithm are comparable to that obtained with the optimum ordering.

Table 7. Order of test cases for various prioritization approaches for example 1 of maximum fault coverage.

No Order

Reverse Order

Random Order

Optimum Order

BCO

Order

T1

T9

T3

T8

T1

T2

T8

T7

T6

T8

T3

T7

T1

T5

T6

T4

T6

T5

T4

T3

T5

T5

T4

T1

T5

T6

T4

T2

T7

T2

T7

T3

T6

T3

T4

T8

T2

T9

T2

T9

T9

T1

T8

T9

T7

Table 8. APFD values of various prioritization approaches for example 1.

Technique

APFD %

No Order

77

Random Order

71

Reverse Order

71

Optimal Order

82

BCO Order

82

Figure 2. APFD chart for example 1 of total fault coverage.

Table 9. Order of test cases for various prioritization approaches for example 2 of maximum fault coverage.

No Order

Random Order

Reverse Order

Optimum Order

BCO

Order

T1

T2

T5

T5

T5

T2

T1

T4

T3

T3

T3

T5

T3

T4

T2

T4

T3

T2

T1

T1

T5

T4

T1

T2

T4

Table 10. APFD values of various prioritization approaches for example 2 of maximum fault coverage.

Technique

APFD %

No Order

46

Random Order

46

Reverse Order

62

Optimal Order

66

BCO Order

62

Figure 3. APFD chart for example 2 of maximum fault coverage.

7. Threats to validity

The proposed BCO algorithm which has been presented here has certain short comings which are as follows:

In the natural BCO the number of scout bees is 5-10% of forager bees which are assumed to be equal in the algorithm proposed here.

The concept of waggle dance has not been incorporated in the algorithm, which is used as a means of communication in the natural BCO because it was not required.

Since the paths are developed randomly it is possible that we may sometimes not get optimal/required solution.

Although the algorithm has been automated but it requires manual input of test suite information such as test case number, faults covered by each test case and its execution time, which also needs to be automated.

8. Conclusion and Future Work

An artificial bee colony optimization algorithm for the fault coverage regression test suite prioritization has been developed and presented. This has been done by studying the natural food foraging behavior of bees. This algorithm makes effective use of the path exploration and path exploitation phenomenon of Scout bees and Forager bees for the prioritization of the fault coverage test suite of the modified code. The proposed BCO algorithm has been explained using examples on maximum fault coverage. The effectiveness of this algorithm has well been demonstrated using APFD metric and chart. The results of the fault based test case prioritization are comparable to the optimal ordering values.

Although the algorithm has been implemented, but it requires manual interface for the input test suite data which makes the utility of the implemented part restricted to small sized test suite. So to apply it to larger programs, there is a need to improve its automation concept to minimize the human interface requirement. Therefore a complete automation tool for the complete usage of the algorithm is being developed. It will also be analyzed on larger projects with large number of test cases and faults.

Print Email Download Reference This Send to Kindle Reddit This

Share This Essay

To share this essay on Reddit, Facebook, Twitter, or Google+ just click on the buttons below:

Request Removal

If you are the original writer of this essay and no longer wish to have the essay published on the UK Essays website then please click on the link below to request removal:

Request the removal of this essay.


More from UK Essays

Doing your resits? We can help!